Instantly share code, notes, and snippets.

# djego/rsa.py

Created September 30, 2017 23:20
A simple RSA implementation in Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 ''' 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)

can i kill it

### djego commented May 2, 2021

I don’t understand why do you like to kill this script?

### VaticanCameos99 commented May 9, 2021 • edited

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?

### AnkushRoy71 commented May 18, 2021

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

### arth3mis commented May 19, 2021

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.

### kadulkaryash71 commented Sep 27, 2021

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

### vishal007-0 commented Sep 29, 2021

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? ### OthTazi commented Oct 28, 2021

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)
if inv < 1: inv += y #we only want positive values
return inv

### Mikecraft1224 commented Oct 31, 2021

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) if inv < 1: inv += y #we only want positive values return inv

Where do you get eea from?

### DeadGrigory commented Jun 1, 2022 • edited

what is the complexity of this RSA algorithm?