DSA Keys (Y, g, p, q and x)[OpenSSH Home][Home]
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\).
|
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 from cryptography.hazmat.backends import default_backend as crypto_default_backend import binascii import sys keysize=1024 if (len(sys.argv)>1): keysize=int(sys.argv[1]) key = dsa.generate_private_key( backend=crypto_default_backend(), key_size=keysize ) 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:
Type: DSA Key size: 1024 == DSA Key details == Private key x: 261949624604611637755199275567157147291569992769 Public key Y: 57698295050685311016562744964577601463945231157931755584252392160855321454564566818546157478901603838396223466244805971507180835360607457826781558154989821184854036767950207745905647952302394392293373939906034165599691196871562949587365946090626454869336270520632541950510502923404092502568111399070804785200 Public key p: 147078461861343662615367166980736725238543321477022304438957060968057550833016124719153897498871879433905714105735728443964091269223985701822390035024878435703006696784840814468977920344778063455421729838583089476642246167579282669157644082987479794580727389794422527767737871752600599054759630648407150082903 Public key q: 1421882723547063186892110934717437693249423321209 Public key g: 26640009379436268735232058984445303287754833135080152873740180304181992254033056523670426186445682333206479528235617212470655026172897293014543581429480578464518392712436592167381044102923658192795300715933528772755351850381322102856643857041133709802552819234523298920255465010594754910492560061193379417277 == DSA Key details (hex) == Private key x: 0x2de23a37ce8db3331a2ac4338d19deee8ecdb441 Public key Y: 0x522a43f648b48a2132af6d5f12c7e06ff8d2ea2bc32e43969f7897c20031dc72b4e96f1fe391f056298781a1ab49f09fdaacf92bae60ee7dbeff6df9aef32c93b3f8ec336ac4e3cd703a3ed011f7d160bbddbea4c6084d167b75d4ffb413ca71b0257c19a0a58fd3514a94aa0b364e44f031a13cfeb6fbd1dc15f1100b40b830 Public key p: 0xd17259c08709e39e07b2017e9ace0876fe72d48e3f7b8f233db7cdde922064247167692524bed1f428ce1f830a959c74558af1dadce20f9c79d3aea10ab63d5d5bbe7527615a68de9f850493c24c5357a42002fb5fe72f70c08be3d191ffb7e9e2ad14a9d0a28724fbfd1b38585a136ea759f6d6f452dc2bf443ba3a4494bb57 Public key q: 0xf90f6d2ca748af784ce90c93f1d5ad73194aa879 Public key g: 0x25efc727b0c857dd784f89d51a18e4a93d1ff13a67f7e9d9c6b6c16727d6cb5d209993db051d000c5d3061104deeef96d3ca1655d344d0404596e19a489a537816913c60ed20c859d8fff467a4ae27bcb42dcf97d4140d57c55858e7f7fb3230aa33d7a85a874bf8fcce747c8ea4c14c6f9f7ffc9bc9d61fc3b9f1ca36cc8cbd
We can see that the private key has 80 hex characters, and so our private key is 320 bits long. This is the same length as \(q\). All the other parameters in the key (\(g\), \(p\) and \(Y\)) are 1,024 bits long. If we select a 2,048 bit key, we get a 256-bit private key:
Type: DSA Key size: 2048 == DSA Key details == Private key x: 37955152717897877282169960793768061354842133905175928808998935692637663403144 Public key Y: 11610938054059498182401881236261811426657976762910618048988121660541323382912276040288067140560192550426495997568522574038558135390364833385636321030187616277899655983494251589107533329982086885114825918171969655419213071961657963589996949183688620477487974389037381475993107165205549418847725760470555598016851524989202337226887683867272037856988087665082266363494412412439424233494602747844127628294504943876321698132421957142764790966116966803816470497946246904101679662085086662391312827215855647112383327041241543728732114974857671014347202571179751298014216684871365028322997923852001381003810454940322273096863 Public key p: 16431696015861153233463488300157451952571921712248194204491087000919872016890227928497694385410046348053228168759207944790409477430056620163575763872771995671904001465658762985786312196093509677607848750566650265532253522381469304445496290557585282515050705166714558744865397362992971472222693374143013513142133345069067925499317330917030401870965203158277767935600825138176240815190146388501123692560473495781279970938058176552766739814779088003170625387426716232568987791902589189486059506503741828324886581565097757797691679154820077149274276089391321753834892293980208906668313033883145062668055185202242559905917 Public key q: 66856334663232993101168262656825054956226710779724062649235763668572036316591 Public key g: 5344473390335690922091304205958786090021199398033804219737875513451478204547648579767299766495879114648294847607231597891615347439660456667571167118144600889101701114712233859511623927275724761752846675993856351326293368491989676150300767445866166542628561849739608059576995683973918450265050338275952118337120917765788994363819103085508072700724320489747525229122586232538803799342760321464296690803482410924812695123120873162234286146620979001308113048239926505936942462097628756801294921154341809929396450047034735603413939012717297291333125291544385003599574654351727173747861468070665535788600615362187210031889 == DSA Key details (hex) == Private key x: 0x53e9daeb1d755caa79dbcd1019cb2a4a5d76212a428a78ce52cff85cc7b81c88 Public key Y: 0x5bf9f1d4ca1171fdf89c70252ee8942aaee4e03ba8c4d14da02ef2fd3a1c88ae1e4d0cf1192b0e5c85eb3a61b1c3d97e0032024989b1e41a7a70ba5e1fccc1c7a49935e6028dfc25eba36eb1f3f58b42c5240a88abd9dd19e9f9ee93957248420bebbbc19ad28b5094855c9331c59a0be654b5caac0cbf544e57bb7c1c2843cd70d587c1d86c4d61266cbe8a0e9d84f7f1f5318e497f0e28baae531e3d21a2798e99bbf3b89ae104bdf450bbde4a1c2bc7e0aa699c40181d150182e5c05a9aa31671e21020edf8e2fd3db0ff9fd5ba1ee8c29cb826978d9017fc3bc43d014b18b7330a5181b1961445c5ca41eec98e57f618d391ea5cfe6bd0c54471d25ef49f Public key p: 0x822a02cd72eccd713330fc45b5da3e6c882f1a48b35cb89f5848339d7e8dd57b64dfd27a030d113e92147d89a841e42293e5d5241f9b0cc39a251a71e306b32a0c6f0f66b7391a535666622cca0770900906826f116187ae4d0f40a0459b6caa389b4a9e3a0943459c7d405c29a0d6a1276141b4ff40e26313b1dd22d39bec068ffeeaa20c8c397df8fad8852b785e08b4910f9e5e0052a5246daeb5a5b293cb2e5e4358ae89bda613e6044ed49a63f7351c18f1446e88e6c5e247e2575f82936e15340c8dc49eea180a124a0c0aec2cb958924e4fe4016af914ca4736bbb941d66808f1c077083bec80e70aa8031c9ab8102751d2f70898730861405d5f907d Public key q: 0x93cf582d73eb0271c6251f876712bafe6549af5c1d6d35705fba478b14c6bdaf Public key g: 0x2a561d47c859825278e73231532ce778ad9860475458df9632d3580db8819581a36af7be691f84b94652a339bd0ea1465ee0d60a182915ad11e0def928452f482bdd43132f3bbbbe495b74702e33f103489ecc0142c6fd96f9c0fc45bd5b322ff5d01f59a19c9e16448c78d4fca7d33295fd18b4d116f9a1fdbda0e9fb10c18c8e3620a5818801dd397e573c60738c6775996ac5f1f5e0f55f420cfa1b2841b4f916d649d365eb86950a59ab301aa5f59f4571af75b43b78fc704eb16dcdb546ca841c38fd484ecf53f19f33223c1f3d7d5e53b1a5e5b814db4b566b2006f74f5645f752cb0a233d8ed0bcbcf15a94e1915e6ab6fc8ab414552c023f56bc8311