In today’s digital landscape, where memes, emojis, and cat videos reign supreme, it’s easy to overlook the serious business of secure communication and data integrity. But fear not! We have a cryptographic superhero ready to save the day. Enter the Digital Signature Algorithm (DSA), the caped crusader of authenticity and integrity in the digital realm. DSA, the cool cousin of the ElGamal encryption scheme, takes cryptographic awesomeness to the next level. It’s like ElGamal’s bolder, more extroverted sibling, sporting a flashy suit of mathematical prowess. In this blog post, we’ll peel back the mask and reveal the inner workings of DSA, all while having a laugh or two along the way. So fasten your seatbelts, put on your Python coding cape, and get ready to embark on a thrilling adventure to master the art of creating and verifying digital signatures using the fantastic Digital Signature Algorithm (DSA). Let’s dive into the wonderful world of DSA and boldly go where no Python programmer has gone before!
Vlog
Dependent Prime Numbers
DSA requires to generate two dependent prime numbers: p and q where p minus 1 must be divisible by q without remainder.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
p – 1 mod q = 0
Generating large prime numbers are costly operations. Luckily, python pycryptodome package can generate these dependent prime pairs easily and relatively fast.
# !pip install pycryptodome from Crypto.PublicKey import DSA key = DSA.generate(3072) p, q = key.p, key.q
Prime Modulo and Prime Divisor
These pair is going to be publicly known. Mostly we are using pre-generated prime numbers for p and q! So, you do not have to generate these pair always. We are going to use following ones in this experiment. Here, p is 3072-bit prime integer and q is 256-bits prime integer.
# p, q = (283, 47)
# p, q = (1279, 71)
p = int ("\
368577123415647035185869509923454362988806654876528082212642441963073\
112178399735415809071414511788930869249295250430304540353013866431229\
965510814733779933506798365268561425933870873229773800684661220325186\
508845233129736449679530102708242450177182372322415658482081901982139\
935504459436526193127136706104380369832924830561868635645974615813718\
599034288471386879791087503489121436698353515121613823867525619537313\
836546517502082093400007321208415057847562620627644914725375992993318\
465393374569764496785505998125381607827118352697037326000376764847745\
255637988916261264753020692214535700561224725217079718071094435237402\
156088273408028838936890398130926616753252644546343571080376158118499\
400126944433056814392717271382689271187098581742948664096320444706415\
422463846704028520445125935059579157543820582424507879000158982185479\
411941493007828836744389091928984640165167590618063453847542820383591\
5397282804819083435616816897")
q = 65032841498903519040222055260781303700863228372896251521604890600319447022433
assert (p - 1) % q == 0
Testing the primeness
A prime number is a number that is divisible only by 1 and itself, and it has no other factors. Once we set values to p and q, we should apply primeness test for them. If we cannot find any number divisible to them from 2 to its squared root value, we can classify it as prime.
def is_prime(number):
if number < 2:
return False
for i in range(2, int(number**0.5) + 1):
if number % i == 0:
return False
return True
assert is_prime(p) is True
assert is_prime(q) is True
However, this will take a long time for large integers. On the other hand, Miller-Rabin primality test can answer this question much faster. Sympy python package runs this approach algorithm with a simple interface.
# !pip install sympy from sympy import isprime assert isprime(p) is True assert isprime(q) is True
Generator
Similar to Diffie-Hellman, DSA requires a public generator value. As mentioned, prime numbers p and q must be dependent. P minus 1 must be divisible by q without remainder as
(p – 1) mod q = 0
This can be represented as
p – 1 = a * q
Now, we are going to generate a random integer h in scale of [2, p-2] and find its a-th power in modulo p.
import random a = int( (p - 1) // q ) h = random.randint(2, p-2) g = pow(h, a, p) assert g > 1
Notice that we used double slash characters while calculating a because p and q are large integers.
Fermat’s Little Theorem in DSA
We calculated generator g as
g mod p= h(p-1)/q mod p
If we find the q-th power of two sides of the equation
gq mod p= (h(p-1)/q )q mod p
q terms can be simiplified in the right hand side because it apperars in both numerator and denominator.
gq mod p= h(p-1) mod p
Fermat’s little theorem states that (p-1)-th power of anything must be equal to 1 if p is prime.
gq mod p = 1
This can be verified in the DSA scheme as
# Fermat's Little Theorem assert pow(g, q, p) == 1
Generating private and public keys
Alice is going to generate a large integer between [1, q-1].
# private key of Alice x = random.randint(1, q-1)
Then, she is going to calculate her public key. This is going to be generator g to the power of her private key in modulo p.
# public key of Alice y = pow(g, x, p)
Alice will keep her private key x secret and publish her public key y publicly. Meanwhile, arguments p, q, a and g will be publicly known as well.
Hashing
Alice firstly uses a hash function to digest a plain message. This hash function will be public and will be used by recipient as well. Basically, that function digests a message and represent as integer.
def find_hash(m) -> int:
if isinstance(m, int):
m = str(m)
# to bytes
m = str.encode(m)
hash_value = hashlib.sha1(m).digest()
# Convert the hash value to an integer
return int.from_bytes(hash_value, 'big') % q
message = "attack tomorrow!"
H = find_hash(message)
Signing a message
She is going to generate a random integer for signing. Then, she will find r as random key k-th power of generator g in modulo q; and s as multiplicative inverse of random key times hash plus her private key times r.
# random key k = random.randint(1, q-1) r = pow(g, k, p) % q s = ( pow(k, -1, q) * (H + x * r) ) % q assert r != 0 and s != 0
Please notice that calculation of r requires to find generator g to the power of random key k in modulo p and then in modulo q respectively. We are going to consider this nested modulo pattern while proving the DSA algorithm.
r = (gk mod p) mod q
Finally, she is going to send plain message and (r, s) pair to Bob. Notice that her public key y, and public arguments p, q, a and g are known publicly as well.
Verification
Bob will use same hash function to digest the coming message. Secondly, he will find w as the multiplicative inverse of s part of the signature. Then, he will find u1 as hash times w in modulo q; and u2 as r part of signature times w in modulo q. Thereafter, he calculates generator g to the power of u1 in modulo p times Alice’s public key to the power of u2 in modulo p. Later, he will find it in modulo p and modulo q respectively. Finally, result must be equal to the r part of the signature.
H = find_hash(message) w = pow(s, -1, q) u1 = (H * w) % q u2 = (r * w) % q v = ( ( pow(g, u1, p) * pow(y, u2, p) ) % p ) % q assert v == r
Proof
Let’s remember how Alice calculated s
s = k-1 * (H + x * r) mod q
If we find k from this equation
k = s-1 * (H + x * r) mod q
Let’s move multiplicative inverse of s multiplier into the parenthesis
k = H * s-1 + x * r * s-1 mod q
We represented multiplicative inverse of s as w
k = H * w + x * r * w mod q
We can move this equation to exponents of same base g and same modulo p. Please notice that we intentionally use modulo p here.
gk mod p = g(Hw + xrw mod q) mod p
According to the product rule of exponents, this can be re-arranged as
gk mod p = gHw mod q * gxrw mod q mod p
According to the power of power rule, this can be represented as
gk mod p= gHw mod q * (gx)rw mod q mod p
Generator g to the power of Alice’s private key x is equal to her public key y
gk mod p = gHw mod q * yrw mod q mod p
Bob represented Hw mod q as u1 and rw mod q as u2
gk mod p = gu1 * yu2 mod p
Basically, Bob calculates generator g to the power of k in verification. Please notice that k is the random key generated by Alice and Bob does not know this value directly.
Meanwhile, Alice calculated r as generator g to the power of random key k in modulo p and modulo q respectively.
(gk mod p) mod q = (gu1 * yu2 mod p) mod q
r = (gu1 * yu2 mod p) mod q
So, Bob’s calculation must be equal to r always!
Conclusion
In conclusion, we’ve embarked on a thrilling journey through the realm of cryptography, specifically exploring the Digital Signature Algorithm (DSA) in Python from scratch. We’ve witnessed the power of DSA as an extension of the ElGamal encryption scheme, providing us with the tools to create and verify digital signatures with confidence. Armed with our newfound knowledge, we can now navigate the digital landscape with a sense of security, knowing that our communications and data can be authenticated and protected from tampering. Remember, though, that this is just the beginning of your cryptographic adventures. There’s a whole world of algorithms and protocols waiting to be explored, each with its own unique quirks and applications. So, keep diving deeper, keep learning, and keep pushing the boundaries of your Python skills. The world of cryptography is ever-evolving, and you’re now equipped to be part of that exciting journey. May your digital signatures always be secure, and may your coding endeavors be filled with endless fun and discovery. Happy coding!
I pushed the source code of this study into GitHub. You can support this work if you star⭐ its repo.
Like this blog? Support me on Patreon
