Ode To John Napier, The NSA and FIPS 186: Meet DSA — The Original Builder of Digital Trust

I am so proud to work in the university has is hosted in John Napier’s Tower. To work in a place that sourced logarithms is a real…

Ode To John Napier, The NSA and FIPS 186: Meet DSA — The Original Builder of Digital Trust

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:

Coding

Now, let’s implement using PowerShell. With this, we can create a key pair with:

$dsa = [System.Security.Cryptography.DSA]::Create([int]$bits)

and where $bits is the number of bits we need. Normally this will start at 512 bits, but we need at least 1,024 bits to be secure. To create a signature, we take a hash of the message and then generate the signature. The following generates a SHA-1 hash, for a word ($word) and then generates a signature:

$hash1=[System.Security.Cryptography.HashAlgorithm]::Create("SHA1').ComputeHash([System.Text.Encoding]::UTF8.GetBytes($word))

$SignedHash = $dsa.CreateSignature($hash1);

The full code is [here]:

$word=$Args[0]
$hashmethod=$Args[1]
$bits=$Args[2]

"Input word: "+$word
"Hash method: "+$hashmethod
"Bits: "+$bits

$dsa = [System.Security.Cryptography.DSA]::Create([int]$bits)

$KeyInfo = $dsa.ExportParameters($true)

"`n==== DSA Key (Secret) ===="
"x: "+[System.Convert]::ToHexString($KeyInfo.Seed)
"`n==== DSA Key (Public) ===="
"P: "+[System.Convert]::ToHexString($KeyInfo.P)
"Q: "+[System.Convert]::ToHexString($KeyInfo.Q)
"g: "+[System.Convert]::ToHexString($KeyInfo.P)
"Y: "+[System.Convert]::ToHexString($KeyInfo.Y)

"`n==== Signature ===="
$hash1=[System.Security.Cryptography.HashAlgorithm]::Create($hashmethod).ComputeHash([System.Text.Encoding]::UTF8.GetBytes($word))

$SignedHash = $dsa.CreateSignature($hash1);

"Hash (Hex): "+[System.Convert]::ToHexString($hash1)
"Signature (Hex): "+[System.Convert]::ToHexString($SignedHash)
"Signature (Base64): "+[System.Convert]::ToBase64String($SignedHash)

$rtn = $dsa.VerifySignature($hash1,$SignedHash);
"`nSignature Verified: "+$rtn

and a sample test is [here]:

Input word: qwerty
Hash method: md5
Bits: 512

==== DSA Key (Secret) ====
x: 0786A628C5FDA280868984120D71EAB6AEDB2215

==== DSA Key (Public) ====
P: 865C0A9855AA1B307C26EF28DD40478F85B0E04E4A4B9AD5CC0D549D2548FAA420AE42332DC0ED0EB92064586C96293F9F2EC26D542AE221D4E3DD6F17018FC5
Q: C76DFDB11B04A4D675CF1EB3B84D3E526ED96491
g: 865C0A9855AA1B307C26EF28DD40478F85B0E04E4A4B9AD5CC0D549D2548FAA420AE42332DC0ED0EB92064586C96293F9F2EC26D542AE221D4E3DD6F17018FC5
Y: 79247303CC8F3E3A2102C05291D33137F7845C2B9F3A8BB43D6CF2E64CB1DA661E59D92295A3F82F14115CC333A2E225BA53BBACCBC0C67884CEE7E8FE950366

==== Signature ====
Hash (Hex): D8578EDF8458CE06FBC5BB76A58C5CA4
Signature (Hex): 5C54CCC5EF8A15024BFF04AF98C879A4DBC4308818E74A5F659E7B7849D29DEDDBB37FBA91028A6A
Signature (Base64): XFTMxe+KFQJL/wSvmMh5pNvEMIgY50pfZZ57eEnSne3bs3+6kQKKag==

Signature Verified: True

And that’s it. Here is the demo:

https://asecuritysite.com/powershell/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.