Skip to content

Instantly share code, notes, and snippets.

@djego
Created September 30, 2017 23:20
Show Gist options
  • Save djego/97db0d1bc3d16a9dcb9bab0930d277ff to your computer and use it in GitHub Desktop.
Save djego/97db0d1bc3d16a9dcb9bab0930d277ff to your computer and use it in GitHub Desktop.
A simple RSA implementation in Python
'''
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)
@VaticanCameos99
Copy link

VaticanCameos99 commented May 9, 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?

@AnkushRoy71
Copy link

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

@arth3mis
Copy link

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.

@kadulkaryash71
Copy link

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
Copy link

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?
Screenshot 2021-09-29 175810

@OthTazi
Copy link

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

@Mikecraft1224
Copy link

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?

@DeadGrigory
Copy link

DeadGrigory commented Jun 1, 2022

what is the complexity of this RSA algorithm?

@DarkBlueStealth
Copy link

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.

@djego
Copy link
Author

djego commented Sep 16, 2023

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🙌🏽

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment