A simple RSA implementation in Python

rsa.py

'''
620031587
Net-Centric Computing Assignment
Part A - RSA Encryption
'''

import random


'''
Euclid's algorithm for determining the greatest common divisor
Use iteration to make it faster for larger integers
'''
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

'''
Euclid's extended algorithm for finding the multiplicative inverse of two numbers
'''
def multiplicative_inverse(e, phi):
    d = 0
    x1 = 0
    x2 = 1
    y1 = 1
    temp_phi = phi
    
    while e > 0:
        temp1 = temp_phi/e
        temp2 = temp_phi - temp1 * e
        temp_phi = e
        e = temp2
        
        x = x2- temp1* x1
        y = d - temp1 * y1
        
        x2 = x1
        x1 = x
        d = y1
        y1 = y
    
    if temp_phi == 1:
        return d + phi

'''
Tests to see if a number is prime.
'''
def is_prime(num):
    if num == 2:
        return True
    if num < 2 or num % 2 == 0:
        return False
    for n in xrange(3, int(num**0.5)+2, 2):
        if num % n == 0:
            return False
    return True

def generate_keypair(p, q):
    if not (is_prime(p) and is_prime(q)):
        raise ValueError('Both numbers must be prime.')
    elif p == q:
        raise ValueError('p and q cannot be equal')
    #n = pq
    n = p * q

    #Phi is the totient of n
    phi = (p-1) * (q-1)

    #Choose an integer e such that e and phi(n) are coprime
    e = random.randrange(1, phi)

    #Use Euclid's Algorithm to verify that e and phi(n) are comprime
    g = gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = gcd(e, phi)

    #Use Extended Euclid's Algorithm to generate the private key
    d = multiplicative_inverse(e, phi)
    
    #Return public and private keypair
    #Public key is (e, n) and private key is (d, n)
    return ((e, n), (d, n))

def encrypt(pk, plaintext):
    #Unpack the key into it's components
    key, n = pk
    #Convert each letter in the plaintext to numbers based on the character using a^b mod m
    cipher = [(ord(char) ** key) % n for char in plaintext]
    #Return the array of bytes
    return cipher

def decrypt(pk, ciphertext):
    #Unpack the key into its components
    key, n = pk
    #Generate the plaintext based on the ciphertext and key using a^b mod m
    plain = [chr((char ** key) % n) for char in ciphertext]
    #Return the array of bytes as a string
    return ''.join(plain)
    

if __name__ == '__main__':
    '''
    Detect if the script is being run directly by the user
    '''
    print "RSA Encrypter/ Decrypter"
    p = int(raw_input("Enter a prime number (17, 19, 23, etc): "))
    q = int(raw_input("Enter another prime number (Not one you entered above): "))
    print "Generating your public/private keypairs now . . ."
    public, private = generate_keypair(p, q)
    print "Your public key is ", public ," and your private key is ", private
    message = raw_input("Enter a message to encrypt with your private key: ")
    encrypted_msg = encrypt(private, message)
    print "Your encrypted message is: "
    print ''.join(map(lambda x: str(x), encrypted_msg))
    print "Decrypting message with public key ", public ," . . ."
    print "Your message is:"
    print decrypt(public, encrypted_msg)

The multiplicative_inverse() can return None right? How do you deal with that?

Also, please can you explain that function? Isn't a multiplicative inverse of a number p/q supposed to be q/p so that it's product is 1?

why are u taking input from user it should be randomly generated

Your code looks good!

The multiplicative_inverse() can return None right? How do you deal with that?

Also, please can you explain that function? Isn't a multiplicative inverse of a number p/q supposed to be q/p so that it's product is 1?

If all previous numbers are correct, it should give a number as output. I haven't seen a None return in my calculations yet.

Your confusion comes from the function name: Actually, the modular multiplicative inverse is calculated here, which is far more complicated than the "normal" inverse you described. Look at Wikipedia's articles about this and the Extended Euclidean algorithm, but you can use existing algorithms like I did (and also @djego, probably).

why are u taking input from user it should be randomly generated

The script seems to be for demonstrating the algorithm, not to fulfil security standards. Random prime generation would make the demonstration easier, though, since you don't need to remember any primes to use the script.

I replaced the inverse function with this and it's working fine. This will never return None.

def multiplicative_inverse(e,r):
for i in range(r):
if((e*i)%r == 1):
return i

I replaced the inverse function with this and it's working fine. This will never return None.

def multiplicative_inverse(e,r): for i in range(r): if((e*i)%r == 1): return i

i have replaced with this function, im still not getting the correct ans ,what should i do?

I replaced the inverse function with this and it's all good now

def eea(a,b):
if b==0:return (1,0)
(q,r) = (a//b,a%b)
(s,t) = eea(b,r)
return (t, s-(q*t) )

Find the multiplicative inverse of x (mod y)

def find_inverse(x,y):
inv = eea(x,y)[0]
if inv < 1: inv += y #we only want positive values
return inv

I replaced the inverse function with this and it's all good now

def eea(a,b): if b==0:return (1,0) (q,r) = (a//b,a%b) (s,t) = eea(b,r) return (t, s-(q*t) )

Find the multiplicative inverse of x (mod y)

def find_inverse(x,y): inv = eea(x,y)[0] if inv < 1: inv += y #we only want positive values return inv

Where do you get eea from?

what is the complexity of this RSA algorithm?

I've been trying to make a public / private key encryption from scratch, I was failing so I look for some code to help me out and here's a whole RSA algorithm from scratch.

Thanks a lot dude.

I've been trying to make a public / private key encryption from scratch, I was failing so I look for some code to help me out and here's a whole RSA algorithm from scratch.

Thanks a lot dude.
Glad to help🙌🏽