The Digital Signature Algorithm (DSA) is a standard defined in Federal Information Processing Standard (as FIPS 186) for digital signatures, and is based on discrete logarithms. It was outlined by NIST is 1991, and proposed within the Digital Signature Standard (DSS). This was then standardized with FIPS 186 in 1994, and FIPS 186-4 in 2013. Within FIPS 186-5, it is defined that DSA should not be used for the generation of signatures, but can be used for signature verification. Although DSA has a patent (Patent 5,231,668 by David W. Kravitz, who had previously worked for the NSA), NIST published the standard as a royality-free. Initally, we created a private key of \(x\) and a prime number of \(p\) with a generator of \(g\). The public key is then [\(Y=g^x \pmod p\), \(g\), \(p\)], and the private key is \(x\).
DSA Signatures with Hazmat |
Method
The Digital Signature Algorithm (DSA) is a standard defined in Federal Information Processing Standard (as FIPS 186) for digital signatures, and is based on discrete logarithms. It was outlined by NIST is 1991, and proposed within the Digital Signature Standard (DSS). This was then standardized with FIPS 186 in 1994, and FIPS 186-4 in 2013. Within FIPS 186-5, it is defined that DSA should not be used for the generation of signatures, but can be used for signature verification. Although DSA has a patent (Patent 5,231,668 by David W. Kravitz, who had previously worked for the NSA), NIST published the standard as a royality-free. The ECDSA method is an extension of DSA, but implemented with elliptic curve (EC) methods. As with most public key signing methods, we take a hash of a message, and then apply a private key to create a signature (\(r,s\)). This is done by creating a random value (k) to produce the signature. The signature is then verified using the associated public key. This then verifies the creator of the signature and that the message has not been changed.
Initially, Bob creates two prime numbers (\(p\) and \(q\)) and generates a generator value of \(g\). Next, he generates his secret key (\(x\)) and then computes his public key:
\(Y=g^{x} \pmod p\)
To create a signature for a message (\(M\)), he creates a random value (\(k\)) and then computes two values for the signature:
\(r = g^{k} \pmod{p} \pmod{q}\)
\(s=(k^{-1}.(H(m)+x.r)) \pmod {q}\)
When Alice receives this signature, she takes Bob's public key \((p,q,g,Y)\) and the message can computes:
\(w = s^{-1} \pmod q\)
\(u_1 = H(M).w \pmod q\)
\(u_2 = r.w \pmod q\)
\(v = (g^{u_1} . y^{u_2}) \pmod {p} \pmod {q}\)
She then checks that \(v\) is equal to \(r\). If so, the signature checks out. This works because:
\(v = g^{h.w}.y^{r.w} = g^{h.w}.g^{x.r.w} = g^{h.w+x.r.w} = g^{h/s+x.r/s} = g^{(H+x.r)/(k^{-1}(H+x.r))} = g^k = r\)
Coding
The code we can use is:
from cryptography.hazmat.primitives import serialization as crypto_serialization from cryptography.hazmat.primitives.asymmetric import dsa,utils from cryptography.hazmat.primitives import hashes from cryptography.hazmat.backends import default_backend as crypto_default_backend import binascii import sys keysize=1024 message="Hello" if (len(sys.argv)>1): message=(sys.argv[1]) if (len(sys.argv)>2): keysize=int(sys.argv[2]) key = dsa.generate_private_key( backend=crypto_default_backend(), key_size=keysize ) try: private_key = key.private_bytes(crypto_serialization.Encoding.PEM,crypto_serialization.PrivateFormat.PKCS8,crypto_serialization.NoEncryption()) print(f"Private key:\n{private_key.decode()}") public_key = key.public_key().public_bytes(crypto_serialization.Encoding.PEM,crypto_serialization.PublicFormat.SubjectPublicKeyInfo) print(f"Public key:\n{public_key.decode()}") chosen_hash = hashes.SHA256() hasher = hashes.Hash(chosen_hash) hasher.update(message.encode()) digest = hasher.finalize() signature = key.sign(digest,utils.Prehashed(chosen_hash)) sig_bytes=binascii.b2a_hex(signature).decode() b=len(sig_bytes)//2 print(f"Signature (DER): {sig_bytes}") print(f"r={utils.decode_dss_signature(signature)[0]}\ns={utils.decode_dss_signature(signature)[1]}") rtn=key.public_key().verify(signature,digest,utils.Prehashed(chosen_hash)) if (rtn==None): print("Signature verified") else: print("Signature failed") except Exception as e: print("Public key error: ",e) print("Type:\t\t\tDSA") print(f"Key size:\t\t{keysize}") print("\n== DSA Key details ==") print(f"Private key x: {key.private_numbers().x}") print(f"\nPublic key Y: {key.private_numbers().public_numbers.y}") print(f"Public key p: {key.private_numbers().public_numbers.parameter_numbers.p}") print(f"Public key q: {key.private_numbers().public_numbers.parameter_numbers.q}") print(f"Public key g: {key.private_numbers().public_numbers.parameter_numbers.g}") print("\n== DSA Key details (hex) ==") print(f"Private key x: {hex(key.private_numbers().x)}") print(f"\nPublic key Y: {hex(key.private_numbers().public_numbers.y)}") print(f"Public key p: {hex(key.private_numbers().public_numbers.parameter_numbers.p)}") print(f"Public key q: {hex(key.private_numbers().public_numbers.parameter_numbers.q)}") print(f"Public key g: {hex(key.private_numbers().public_numbers.parameter_numbers.g)}")
A sample run gives:
Private key: -----BEGIN PRIVATE KEY----- MIIBSgIBADCCASsGByqGSM44BAEwggEeAoGBAJnYufH2QsPww0q42LGCnkdJZnqu lzAmI/vyOe321TyCMpYJ3vtJKzQ891CkDZJGQ/vD/M/ZPaQItbFwuV2qBc71+YHh f7sTtprOri5/1ulzMaOajGNRZNg1X2W4XaDr+qkb41SkZ2g6JQvOpyn5Ne1qlxM0 nbehFopfcFjdRkBbAhUA4WjsjPeGt8S9NthYqLV4CfYGhLkCgYBcZdUhOklSe1Rv 6lntK7TCMnNr4iafgX2oeBVlE5Z1NCbG+MYTrQMxF+b5DrnH3J0ruZTPZ85+V6lY 4AJRklIygOKc1O5F6w+Y+IdFMS0bXvSK+zzPuqmiKbH6PsD8eotstVAMkZEO9uo1 VeysDchjYMtivcKxV6uMEMcVjvB1qgQWAhRB5uWONoZx8iBbuyO3+8b4X6Cqeg== -----END PRIVATE KEY----- Public key: -----BEGIN PUBLIC KEY----- MIIBtjCCASsGByqGSM44BAEwggEeAoGBAJnYufH2QsPww0q42LGCnkdJZnqulzAm I/vyOe321TyCMpYJ3vtJKzQ891CkDZJGQ/vD/M/ZPaQItbFwuV2qBc71+YHhf7sT tprOri5/1ulzMaOajGNRZNg1X2W4XaDr+qkb41SkZ2g6JQvOpyn5Ne1qlxM0nbeh FopfcFjdRkBbAhUA4WjsjPeGt8S9NthYqLV4CfYGhLkCgYBcZdUhOklSe1Rv6lnt K7TCMnNr4iafgX2oeBVlE5Z1NCbG+MYTrQMxF+b5DrnH3J0ruZTPZ85+V6lY4AJR klIygOKc1O5F6w+Y+IdFMS0bXvSK+zzPuqmiKbH6PsD8eotstVAMkZEO9uo1Veys DchjYMtivcKxV6uMEMcVjvB1qgOBhAACgYB2hpLWch9T+ndDZ+asxdshFQrRNGcW B8CXisM8tLf6pNt688W53qMlfdhUh3xKIDF4SmyUY53HepsK5A/jcuP+PwZ3ztjj GgIcU6fM3JZSVma0xRypgaG+oF4g08uSs2X0rmxzpf03CRRKgbOdqdX5wlc+nqmW YKkNVbNBdMlbXA== -----END PUBLIC KEY----- Signature (DER): 302d021500d3ee4afbdab601f78686c351834950c2a44ad59c02143f6dfa62905e681fae9a9551dfeace22feb969d2 r=1209911162011830216337449691977237367320920905116 s=362119011399595645441185781617789094164067609042 Signature verified Type: DSA Key size: 1024 == DSA Key details == Private key x: 376233568605262478914395537366808186692623706746 Public key Y: 83231561626036727556746656948839315681678919128823681569042626051851720244296342625239923491604867508531479101310532538766015156011682618065120567587353549074463441594286757388466519766132510172994097099739924568469555390336978901826163449391613652319370775865544553914821372473969302303381284745098230848348 Public key p: 108034747581121063051054561925230104874408952662452241106730277462540160648480660573511222090057092799075561242297753242716842244941378465281752090447998888806171263275385791884804822973263527124792902483672428853483438412499834590614901282935385856649564308334162884542261964886785804162069047935353978503259 Public key q: 1286862807404041152114924754395713812623425701049 Public key g: 64883930003693214331228959894549515597459562214169261709512306203870794746486094584920532916574142892866333741391139464855785414848615446374281548710950346284610955175570433938193843909026587575280860782388758330163409504948710826985430294445247231785336177233455277802123544758797543355486017632257153463722 == DSA Key details (hex) == Private key x: 0x41e6e58e368671f2205bbb23b7fbc6f85fa0aa7a Public key Y: 0x768692d6721f53fa774367e6acc5db21150ad134671607c0978ac33cb4b7faa4db7af3c5b9dea3257dd854877c4a2031784a6c94639dc77a9b0ae40fe372e3fe3f0677ced8e31a021c53a7ccdc96525666b4c51ca981a1bea05e20d3cb92b365f4ae6c73a5fd3709144a81b39da9d5f9c2573e9ea99660a90d55b34174c95b5c Public key p: 0x99d8b9f1f642c3f0c34ab8d8b1829e4749667aae97302623fbf239edf6d53c82329609defb492b343cf750a40d924643fbc3fccfd93da408b5b170b95daa05cef5f981e17fbb13b69aceae2e7fd6e97331a39a8c635164d8355f65b85da0ebfaa91be354a467683a250bcea729f935ed6a9713349db7a1168a5f7058dd46405b Public key q: 0xe168ec8cf786b7c4bd36d858a8b57809f60684b9 Public key g: 0x5c65d5213a49527b546fea59ed2bb4c232736be2269f817da87815651396753426c6f8c613ad033117e6f90eb9c7dc9d2bb994cf67ce7e57a958e0025192523280e29cd4ee45eb0f98f88745312d1b5ef48afb3ccfbaa9a229b1fa3ec0fc7a8b6cb5500c91910ef6ea3555ecac0dc86360cb62bdc2b157ab8c10c7158ef075aa