RSA Encryption Algorithm and Large Integers in Python

Monday, September 1, 2008

Everyone who knows how public key cryptography works, should be familiar with RSA Public Key Algorithm (for those who don't, this may be a good place to start with). The question is the implementation part of it, I always see people not looking anything beyond big integer libraries whenever they want to work on large integers, a typical application is RSA algorithm key generation, Encryption/Decryption, which involves large numbers, in fact the default implementation language which is used to illustrate the algorithm to novice users most often remained C (the example keys used were mostly small numbers), as a result the power of languages which can easily handle large integers often remained unexplored.

In this writing all I am going to show is the power of python scripting language in handling large integers, the next time when you want to use cryptographic services, play with large primes and factoring (another important mathematical problem) or explore cryprographic algorithms like RSA, start with python, so that you can focus more on the mathematical part of it with less hiccups on the implementation part due to its simplicity. Some of the implementation methods I have seen also used random trail and error methods to generate keys for RSA which will be a very slow process when the prime numbers are more than 10 digits, in this implementation, we will use the correct algorithms to generate keys, encrypt/decrypt data in finite time.

Lets come back to RSA public Key algorithm, which I am going to use as an example to show how to use large integers in python. For beginners, a public key is part of your key which will be used by all other parties to encrypt messages they send to you in a secure way, in other words its known to all persons participating in the protocol who want to communicate to you in a secure way, a private key is the another part of the key which is known only to you, only the source with a corresponding private key can decipher messages sent by others encrypted with its public key, or in other words PrivateKey(PublicKey(Message)) = Message.

Alright lets go to the implementation of RSA Encryption algorithm, it works like this.

1. Generate two numbers p & q which are typically large primes.
2. Compute n = p * q and m = (p - 1) * (q - 1)
3. Choose a number 'e' which is relatively prime to m, or gcd (m, e) = 1 (See here for the GCD computation algorithm)
4. Choose a number 'd' so that ((d * e) - 1) % m = 1 (Find a number 'd' so that the product of 'd' * 'e' subtracted by 1 is perfectly divisible by m).
Step 4 is called finding the multiplicative inverse of a number modulo 'n', for which we will be using Extended Euclidean Algorithm.
5. Now your public key is (n, e) and the private key is (n, d).
6. Encryption: Anyone sending a message say NUM (message is a number here < enc =" (NUM" style="font-weight: bold;">Decryption: The message ENC recieved can be decrypted with your private key (n, d) using NUM = (ENC ** d) % n
Note: ** here denotes exponent operator and "%" denotes remainder operator in the above description.

Easier said than done, in a typical implementation, the numbers p & q are very large primes (more than 200 bits for example) so that the key generation process itself consumes sometime (more slow, more secure). Let's look at the implementation, see how easy its in a scripting language.

RSA Algorithm: rsa_algorithm.py
#
# Sample implementation of RSA algorithm
# rsa_algorithm.py
# Author: S.Prasanna
#

def gcd (a, b):
"Compute GCD of two numbers"

if b == 0: return a
else: return gcd(b, a % b)

def multiplicative_inverse(a, b):
""" Find multiplicative inverse of a modulo b (a > b)
using Extended Euclidean Algorithm """

origA = a
X = 0
prevX = 1
Y = 1
prevY = 0

while b != 0:

temp = b
quotient = a/b
b = a % b
a = temp

temp = X
a = prevX - quotient * X
prevX = temp

temp = Y
Y = prevY - quotient * Y
prevY = temp

return origA + prevY

def generateRSAKeys(p, q):
"Generate RSA Public and Private Keys from prime numbers p & q"

n = p * q
m = (p - 1) * (q - 1)

# Generate a number e so that gcd(n, e) = 1, start with e = 3
e = 3

while 1:

if gcd(m, e) == 1: break
else: e = e + 2

# start with a number d = m/e will be atleast 1

d = multiplicative_inverse(m, e)

# Return a tuple of public and private keys
return ((n,e), (n,d))

if __name__ == "__main__":

print "RSA Encryption algorithm...."
p = long(raw_input("Enter the value of p (prime number):"))
q = long(raw_input("Enter the value of q (prime number):"))

print "Generating public and private keys...."
(publickey, privatekey) = generateRSAKeys(p, q)

print "Public Key (n, e) =", publickey
print "Private Key (n, d) =", privatekey

n, e = publickey
n, d = privatekey

input_num = long(raw_input("Enter a number to be encrypted:"))
encrypted_num = (input_num ** e) % n
print "Encrypted number using public key =", encrypted_num
decrypted_num = encrypted_num ** d % n
print "Decrypted (Original) number using private key =", decrypted_num

Sample Output 1
: (with small numbers)

C:\>python rsa_algorithm.py
RSA Encryption algorithm....
Enter the value of p (prime number):101
Enter the value of q (prime number):103
Generating public and private keys....
Public Key (n, e) = (10403L, 7)
Private Key (n, d) = (10403L, 8743L)
Enter a number to be encrypted:4
Encrypted number using public key = 5981
Decrypted (Original) number using private key = 4

Sample Output 2: (with large numbers used for key generation)

Here lets see the difference in time it takes to decrypt the same data as we used before (I have used two four digit prime numbers from here), the decryption process will be little longer than the above example, the more the number of digits, the time taken for encryption or decryption will increase exponentially (Try the number to be encrypted as 5 in the below example with same keys, let me know the time it takes to decrypt the data).

C:\>python rsa_algorithm.py
RSA Encryption algorithm....
Enter the value of p (prime number):4007
Enter the value of q (prime number):6037
Generating public and private keys....
Public Key (n, e) = (24190259L, 5)
Private Key (n, d) = (24190259L, 19344173L)
Enter a number to be encrypted:4
Encrypted number using public key = 1024
Decrypted (Original) number using private key = 4

The above example shows a simple and correct way to implement a cryptographic algorithm using python, obviously there are lot of other challenges which may involve the use of large integers, for which a scripting language like python can be used for all mathematical calculations like prime factoring, etc. So the next time when you work with those magical large primes or big integers, you know where to start with.

11 comments:

Ben said...

An interesting and simple program illustrating the idea of RSA. However, you should really use the fast modular exponentiation algorithm, because for still larger primes the attempt to take any input number to encode and raise it to the d that results will fail/take far too long.

Prasanna Seshadri said...

You are absolutely right Ben, I should use a faster modular exponentiation algorithm than what was in the code, for big numbers even I am feeling the pinch for obvious reasons.

I will improve the above with a mature algorithm, but this is just a start.

Appreciate your feedback.

PermanentScowl said...

In the Extended Euclidean Algorithm, you have written:

temp = X
a = prevX - quotient * X
prevX = temp

shouldn't it be:

temp = X
X = prevX - quotient * X
prevX = temp

Prasanna Seshadri said...

Thanks a lot for correcting ths, luckily this code doesn't break because of tat, will change it.

Rahul said...

Looks simple and elegant..
How about my version more scalable than this. Even for prime numbers around 1 million ;)

http://rahulrajpl.wordpress.com/2010/05/17/rsa-key-generator-in-python/

I would like to have your feedback. ;)
thanks

Yurii said...

Thanx man for that gr8 script.Its looks so elegant!

Marmy said...

Fairly certain you multiplicative_inverse function is incorrect.

If you're trying to find a^-1 mod (b), a usually is not bigger than b.

If you do a*m_i(a,b) modb you do not get 1.

Prasanna Seshadri said...

Interesting, thanks for the comment, will check this code again with different values.

arun said...

by using vedic math formula we can reduce time consumtion try !!!!

Prasanna Seshadri said...

Interesting, I don't have any knowledge on Vedic math, but will try that.

Mark said...

Thanks for the structure,
This will make it work correctly -

def multiplicative_inverse(t, e):
x = 0
y = 1
lastX = 1
lastY = 0
a = t
b = e
while b != 0:
quotient = (a / b)

tmpB = b
b = (a % b)
a = tmpB

tmpX = x
x = (lastX - (quotient * x))
lastX = tmpX

tmpY = y
y = (lastY - (quotient * y))
lastY = tmpY
return (t + lastY)


Copyright © 2016 Prasanna Seshadri, www.prasannatech.net, All Rights Reserved.
No part of the content or this site may be reproduced without prior written permission of the author.