Image for post
Image for post
Photo by Cytonn Photography on Unsplash

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

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store