Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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)
@iamibi

This comment has been minimized.

Copy link

iamibi commented Dec 4, 2015

Can you please explain why you have encrypted the message using private key, as it should have been encrypted by the public key and decrypted by the private key.

@AndreiD

This comment has been minimized.

Copy link

AndreiD commented Jan 30, 2016

or vice-versa

@atakanyenel

This comment has been minimized.

Copy link

atakanyenel commented Apr 22, 2016

This code takes too much time to compute when given prime numbers are too big.( I used openssl to generate prime numbers for me). The time taking part is (ord(char)**key) %n in encrypt and decrypt. You can use pow(ord(char),key,n) instead to have very fast results with big primes.

@machanit

This comment has been minimized.

Copy link

machanit commented Aug 4, 2016

the message in asymmetric encryption is encrypt by the public key and is decrypt by the private key.

@Carles-Figuerola

This comment has been minimized.

Copy link

Carles-Figuerola commented Aug 23, 2016

@sumiibi: encrypting with the public key makes it confidential while encrypting with the private key provides authenticity to the message. It's just a different use of rsa

@raphaelbernardino

This comment has been minimized.

Copy link

raphaelbernardino commented Sep 17, 2016

@atayenel thanks! saved me a lot of trouble!

btw
enc is [pow(ord(char),key,n) for char in plaintext]
dec is [chr(pow(char, key, n)) for char in ciphertext]

@AndrewTalansky

This comment has been minimized.

Copy link

AndrewTalansky commented Sep 24, 2016

The variable d in the line d = multiplicative_inverse(e, phi) contain None. So the program fails.

@JekaDeka

This comment has been minimized.

Copy link

JekaDeka commented Oct 10, 2016

fixed def multiplicative_inverse(e, phi): in my fork, so d contain a properly value.

@UrsaEli

This comment has been minimized.

Copy link

UrsaEli commented Apr 11, 2017

Inputs at __main__ amend to this:

while not(q > p):
    p = int(raw_input("Enter a prime number (17, 19, 23, etc): "))
    q = int(raw_input("Enter another prime number > the 1 you entered above : "))
    print(not(q > p))	

else the deciphering will not be correct.

@7eXx

This comment has been minimized.

Copy link

7eXx commented May 22, 2017

using high p, q this code takes a little while to generate encryption message. so it's better replace ** with pow function

@giuliettiseba

This comment has been minimized.

Copy link

giuliettiseba commented Sep 24, 2017

keep private the private, or public the private... nvm.... is a nice code anyways, thanks.

@lgommans

This comment has been minimized.

Copy link

lgommans commented Oct 12, 2017

Note that you're basically using ECB here, so it's insecure.

Not a bad example though! The RSA part seems okay, just the encryption function.

@tezlas

This comment has been minimized.

Copy link

tezlas commented Oct 22, 2017

bitmoji
I was nearly crying

@Magalame

This comment has been minimized.

Copy link

Magalame commented Oct 27, 2017

If you encrypt each character individually with the same key they you've used no more than a Caesar cipher.

@Karel-Chramosil

This comment has been minimized.

Copy link

Karel-Chramosil commented Dec 8, 2017

30 temp1 = temp_phi / e

30 temp1 = temp_phi // e

@ScientificX

This comment has been minimized.

Copy link

ScientificX commented Dec 28, 2017

hmm.Nice one

@mounikanadimpalli

This comment has been minimized.

Copy link

mounikanadimpalli commented Feb 6, 2018

File "rsa.py", line 114, in
encrypted_msg = encrypt(private, message)
File "rsa.py", line 90, in encrypt
cipher = [(ord(char) ** key) % n for char in plaintext]
File "rsa.py", line 90, in
cipher = [(ord(char) ** key) % n for char in plaintext]
TypeError: unsupported operand type(s) for ** or pow(): 'int' and 'NoneType'

I am getting following error can any one help me.I am using python 3.6

@Unusual229

This comment has been minimized.

Copy link

Unusual229 commented Feb 28, 2018

It means your version of Python doesn't support power as '**'. Search online how to do power in your python version.

@youben11

This comment has been minimized.

Copy link

youben11 commented Mar 2, 2018

This implementation have a big flaw. It encrypt each char individually, which let an attacker to try 2**8 possible value to get each char of the message. You should encrypt the entire message as a number.

@Deisman18

This comment has been minimized.

Copy link

Deisman18 commented Mar 27, 2018

I am having trouble running the encrypt() and decrypt() portions of the code. I keep getting the following

TypeError: unsupported operand type(s) for ** or pow(): 'int' and 'NoneType'

on the cipher = [(ord(char) ** key) % n for char in plaintext] and plain = [chr((char ** key) % n) for char in ciphertext] lines of the code. Does anyone have any ideas as to what my problem is? It has something to do with the fact that my private key (pk) isn't giving both key and n a value in the line

#Unpack the key into it's components
key, n = pk

help??

@dendisuhubdy

This comment has been minimized.

Copy link

dendisuhubdy commented Apr 8, 2018

@KirillMysnik

This comment has been minimized.

Copy link

KirillMysnik commented Apr 25, 2018

@mounikanadimpalli @Unusual229 @Deisman18
This exception:
TypeError: unsupported operand type(s) for ** or pow(): 'int' and 'NoneType'
Means that the ** operator fails because its second operand is of NoneType (that's basically None value). That happens on line #90:

cipher = [(ord(char) ** key) % n for char in plaintext]

Let's track it.

Its second operand (with an invalid value) is the key variable. This variable contains None when the script tries to encrypt the message.

Where does it come from? Line #88:

key, n = pk

key's value is unpacked from the pk variable which is passed to encrypt() as an argument. We know by now that pk is a tuple of 2 values (it unpacks without errors), but its 1st item is None - that's where key gets its invalid value.

Let's check the function invocation. Line #114:

encrypted_msg = encrypt(private, message)

It says that the 1st argument that is passed to the function is a private variable. We know that this variable is some sort of a tuple and its 1st item is None.

Where does private come from? Just a few lines above (#111):

public, private = generate_keypair(p, q)

The tuple (private) that is guilty of containing None as its 1st item is the 2nd thing that generate_keypair function returns upon its execution.

In the end of generate_keypair we clearly see what it returns:

return ((e, n), (d, n))

It basically returns 2 things, and each is a tuple. We remember that the 2nd tuple, the private key, has None as the 1st item. We also clearly see here that the 1st item in this tuple is d.

Well, d receives its value just 2 lines earlier:

d = multiplicative_inverse(e, phi)

By now we know for sure that multiplicative_inverse function returns None, and this fact messes the whole thing up later, when actual math (**) is used on that value.

So finally we enter the guilty function: #43. The function is supposed to do some calculations, but the reason why it returns None is actually seen after all those calculations:

if temp_phi == 1:
    return d + phi

# End of the function

The function returns d + phi if temp_phi == 1. But what if that condition is unsatisfied? In that case the function just ends without returning any value whatsoever. And in Python that equals to None. If condition was satisfied, the function would return some sort of sum, and that wouldn't result into None.

Why was that condition not satisfied? Most likely because the calculations in this function were written (like the whole program) for Python 2. The author uses division on line #30:

temp1 = temp_phi/e

The division operator (/) works differently in Python 2 and Python 3. In Py2 the result of this division was dependent on the operands. IIRC, if both operands were integer, the result would be integer as well. In Py3, however, it always results in a float value. This algorithm obviously never expected to operate on floating values, and to make it work in Python 3 you should replace / with //.

The condition at the end of the function is misleading. The program will always fail if that condition is not satisfied.

Beware of the issues with the per-character encryption as mentioned in the comments.

@Gustavo6046

This comment has been minimized.

Copy link

Gustavo6046 commented Aug 5, 2018

Uh, Python's math module comes with gcd, doesn't it?

@noobling

This comment has been minimized.

Copy link

noobling commented Aug 19, 2018

d

@ghost

This comment has been minimized.

Copy link

ghost commented Sep 3, 2018

I think so it should be encrypted with public key and decrypted with private key

@mahesans

This comment has been minimized.

Copy link

mahesans commented Nov 19, 2018

line 16 in gcd(a,b) : assumes a > b
line 74 calls gcd with a = e and b = phi but phi > e
so a%b = 0
And thus in the second iteration in gcd
a = phi, b=0
and
a%b will cause an error
line 30: In Python 3, division operator / gives float results, not integer
therefore, line 31 makes temp2 be zero
In Python 3, // is integer division
By the way,
% operator gives remainder
You dont need subtractions to find the remainder of a division

@balasmeh

This comment has been minimized.

Copy link

balasmeh commented Apr 11, 2019

Thank you, this is best algorithm , work prefect , thank you KirillMysnik your solution is so helpful for me

@mj2266

This comment has been minimized.

Copy link

mj2266 commented Apr 20, 2019

Hey, i made some changes on how to calculate value for "d" in my fork link . Source for the theory is given here geeksforgeeks link . Check it our it is rather simpler implementation for calculating value for d. Anyway thank you for providing this code !

@balasmeh

This comment has been minimized.

Copy link

balasmeh commented Apr 24, 2019

can please someone help me how to to make the message encrypt the float and integer??
i try change cipher = [(ord(float) ** key) % n for float in plaintext] but its give me error TypeError: 'float' object is not iterable what dose it mean?? , im selecting how i need to encrypts all data type?? float integer and char ??

@gbrn1

This comment has been minimized.

Copy link

gbrn1 commented Jun 1, 2019

isn't d = int((2*phi+1)/e)

@Anirudhhat61

This comment has been minimized.

Copy link

Anirudhhat61 commented Sep 13, 2019

Thank you, this is best algorithm , work prefect , thank you KirillMysnik your solution is so helpful for me

did it run perfectly

@Aphrodites1995

This comment has been minimized.

Copy link

Aphrodites1995 commented Oct 15, 2019

The thing is that it uses the same result for the same key so it is no stronger than a caesar cipher as someone else said. Here's the solution:
cipher = [pow(ord(char)+i, key, n) for i, char in enumerate(text)]
plain = [chr(pow(char, key, n)-i) for i, char in enumerate(text)]
This way it is different.

@JonCooperWorks

This comment has been minimized.

Copy link
Owner Author

JonCooperWorks commented Oct 15, 2019

@alperendurmus

This comment has been minimized.

Copy link

alperendurmus commented Dec 10, 2019

I am quite impressed when I saw how simple you implemented the gcd() function. Good job.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
@stackola

This comment has been minimized.

Copy link

stackola commented Feb 10, 2020

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.