John Napier’s Legacy: DSA
John Napier’s Legacy: DSA
I am so proud to work in a university that has one of its campuses built around John Napier’s Tower. It is thus a privilege to be in a place that sourced one of the greatest mathematical discoveries: logarithms. And, for a while, it was discrete logarithms that secured the Internet and where:
and:
For this, Whitfield Diffie and Marty Hellman define the Diffie-Hellman method and that allowed us to use discrete logarithms to create a secret key. While this has now been mainly replaced by more efficient elliptic curve methods, the usage of discrete logarithms is still a valid method of key exchange. Well, with this we have the DSA digital signature method.
The DSA patent (No 5,231,668) was created by David W. Kravitz (an ex-NSA employee) and assigned to the USA in a royalty-free way:
David spent 11 years at the NSA and is currently a Senior Director of Research at Spring Labs [here]:
DSA was first outlined by NIST in 1991, within the Digital Signature Standard (DSS). This was then standardized within FIPS (Federal Information Processing Standard) 186 in 1994, and by FIPS 186–4 in 2013. Within FIPS 186–5, though, it is defined that DSA should not be used for the generation of signatures but can be used for signature verification. Most methods now use either RSA or ECDSA signing.
The ECDSA method is basically an extension of DSA, but implemented with elliptic curve (EC) methods. Overall, ECSDA is much more efficient in its computation and in its key sizes.
As with most public key signing methods, in DSA, we take a hash of a message — H(M) — 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:
To create a signature for a message (M), he creates a random value (k) and then computes two values for the signature:
When Alice receives this signature, she takes Bob’s public key (p,q,g,Y) and the message and computes:
She then checks that v is equal to r . If so, the signature checks out. This works because:
OpenSSL
With this, we can create a 1,024-bit key pair with [here]:
openssl dsaparam -out dsaparam.pem 1024
openssl gendsa -out 1.pem dsaparam.pem
openssl dsa -in 1.pem - textWith this, we create a parameters file which contains P, Q and G. Next the key is generated with a private key and computed a public key [here]:
Private-Key: (1024 bit)
priv:
4e:53:4b:0d:e7:e3:b5:b3:9b:47:2a:43:d4:bc:22:
90:39:77:3e:6c:b9:1d:a6:fb:5f:67:6b:66
pub:
00:8d:d4:e7:09:46:51:e7:c5:8f:c2:5f:67:94:de:
2c:56:0b:d3:8a:a0:f6:5a:05:37:99:52:d6:97:d8:
25:20:31:17:d8:e9:93:0e:c2:70:a0:44:e6:5d:31:
84:53:d0:27:80:d9:bc:c6:6e:18:7c:57:7b:9b:49:
eb:cf:4c:17:12:92:d3:ba:23:b8:af:be:c3:02:81:
fa:f6:7c:5d:48:46:27:57:96:4c:f6:fd:5c:71:35:
bc:b6:0d:4e:8d:b1:b3:c2:e8:db:8c:1c:81:d7:5b:
5c:57:72:01:14:2b:2e:5b:fb:32:5e:c5:e2:4d:c3:
c3:f0:29:7b:96:99:55:66:b6
P:
00:94:be:04:7b:21:fd:01:4f:23:97:cf:fb:1a:3e:
ca:71:56:c2:4e:b9:be:b5:27:5a:b6:61:f3:f5:48:
84:fe:40:b2:b2:d4:0a:bc:fc:b5:dd:9a:35:8e:f7:
d5:fc:11:4e:95:a1:51:0b:5d:f8:fa:7c:dc:b8:03:
ab:27:23:9c:fe:2a:d5:18:de:68:a2:fa:66:51:33:
dc:21:c2:cb:1d:4e:7e:3e:0b:b8:cb:a2:c9:6e:ef:
44:23:b2:d8:e8:8e:04:d2:61:8e:74:67:f8:29:90:
cf:5e:2f:01:9f:9c:33:ac:23:e5:0e:27:83:c2:7a:
8d:b7:20:06:91:c9:10:a8:53
Q:
00:89:fa:e5:6f:cf:9f:54:a8:c0:59:c3:db:e6:24:
99:95:ed:37:e8:8a:f1:a4:be:f5:d4:ec:42:5d
G:
48:25:90:15:a9:c4:bf:8f:d6:83:1d:47:69:0c:c1:
b1:f5:be:c5:4b:e3:03:5a:41:2c:64:66:1b:72:51:
d7:ae:27:5e:63:31:9f:d5:22:50:54:9e:31:41:9b:
3f:92:0f:52:b3:21:9b:2c:54:ea:2b:76:a2:22:e5:
84:89:d2:4c:ff:bb:49:67:69:1e:99:03:f2:bf:44:
a1:55:c8:f8:d3:aa:15:b4:8f:40:b9:f5:eb:76:6b:
2b:60:aa:0a:08:a4:24:12:eb:a1:86:ee:4b:57:df:
c0:7f:7a:cd:7a:94:b5:63:73:7a:2e:21:a4:d0:b1:
82:40:3a:e9:a1:d3:0f:0c
-----BEGIN DSA PRIVATE KEY-----
MIIBywIBAAKBgQCUvgR7If0BTyOXz/saPspxVsJOub61J1q2YfP1SIT+QLKy1Aq8
/LXdmjWO99X8EU6VoVELXfj6fNy4A6snI5z+KtUY3mii+mZRM9whwssdTn4+C7jL
oslu70QjstjojgTSYY50Z/gpkM9eLwGfnDOsI+UOJ4PCeo23IAaRyRCoUwIdAIn6
5W/Pn1SowFnD2+YkmZXtN+iK8aS+9dTsQl0CgYBIJZAVqcS/j9aDHUdpDMGx9b7F
S+MDWkEsZGYbclHXrideYzGf1SJQVJ4xQZs/kg9SsyGbLFTqK3aiIuWEidJM/7tJ
Z2kemQPyv0ShVcj406oVtI9AufXrdmsrYKoKCKQkEuuhhu5LV9/Af3rNepS1Y3N6
LiGk0LGCQDrpodMPDAKBgQCN1OcJRlHnxY/CX2eU3ixWC9OKoPZaBTeZUtaX2CUg
MRfY6ZMOwnCgROZdMYRT0CeA2bzGbhh8V3ubSevPTBcSktO6I7ivvsMCgfr2fF1I
RidXlkz2/VxxNby2DU6NsbPC6NuMHIHXW1xXcgEUKy5b+zJexeJNw8PwKXuWmVVm
tgIcTlNLDefjtbObRypD1LwikDl3Pmy5Hab7X2drZg==
-----END DSA PRIVATE KEY-----We can see that the private key (priv) has 28 bytes (224 bits), while the public key (pub=G^{priv} (mod P)) and prime number P has 128 bytes (1,024 bits). Notice that the Q value is smaller that the other prime (P). In a signature, Bob will sign with priv, and then send his public key (pub, P, Q and G) to Alice. She can then check Bob’s signature with his public key. This is implemented here:
https://asecuritysite.com/openssl/dsa
Conclusions
While not supported in the generation of DSA by FIPS anymore, it is still a valid method, and its method has been adopted by ECDSA, and thus used with Ethereum and Bitcoin. And, so, its legacy lives on, as does John Napier’s legacy in this modern world. His discovery of logarithms was one of the great discoveries of all time.
And, so, for Bitcoin, Satoshi Nakamoto selected the elliptic curve implementation of DSA: ECDSA, and the rest is history. While ECDSA was a good choice, the use of EdDSA is now preferred for new implementations. But, without DSA, there would be no ECDSA. The patent free DSA built a strong foundation, as opposed to the Claus Schnorr approach.