RSA Digital Signatures in 12 Lines of Python

RSA Digital Signatures in 12 Lines of Python

I have been setting myself 12 line challenges for RSA encryption, so here’s one which signs a message in RSA in just 12 lines of Python code. With digital signing, we take our private key, and encrypt our message to give a signature. Our public key is then used to verify the signature.

With this we use the decryption key value to encrypt for a signature, and the public key to prove the signature. In this case, we use s as the signing exponent (which would be defined as d for decryption), and v for the verification exponent (which would be defined as e for encryption). Alice initially has two secret prime numbers (p and q), and which she produces a product (the modulus):

N=pq

Next, she selects a verification exponent (v), and which does not share a factor with:

PHI=(p-1)(q-1)

In most cases she will select:

v=65,537

Next she computes the signature exponent (s) with:

sv=1(mod(p−1)(q−1))

Next she takes a message (D) and sign with:

S=D^s (mod N)

Bob then checks the signature with:

M=S^v(modN)

If M is equal to D , the signature matches.

This works because of Euler’s formula, where:

S^v=D^{sv}=D (mod N)

The coding is here:

A sample run [here]:

Message=hello
p=1051446937579387829
q=696907085081608369

s=575356501766415283802339857698644801
v=65537
N=732760820386434997658767113743140901

Signing exponent (s,n)
Verification exponent (e,n)

Signature=297464987342041490716961481648211666
Check=hello

Now, here is a challenge for your Python skills. For a message of “hello”, and v=65537, N=1153226552172867843905302101042644849, which is the valid signature:

(a) 258328677494448090555019031167631465
(b) 278328677494248090555119031167631463
(c) 258388677494748090555919031167631462