Instantly share code, notes, and snippets.

# JonCooperWorks/rsa.py Created Apr 4, 2013

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 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 commented Jan 30, 2016

 or vice-versa

### 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 commented Aug 4, 2016

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

### 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 commented Sep 17, 2016 • edited

 @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 commented Sep 24, 2016

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

### JekaDeka commented Oct 10, 2016

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

### UrsaEli commented Apr 11, 2017 • edited

 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 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 commented Sep 24, 2017

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

### 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 commented Oct 22, 2017 • edited

 I was nearly crying

### 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 commented Dec 8, 2017

 30 temp1 = temp_phi / e 30 temp1 = temp_phi // e

### ScientificX commented Dec 28, 2017

 hmm.Nice one

### mounikanadimpalli commented Feb 6, 2018 • edited

 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 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 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 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 commented Apr 8, 2018

 Redid this for Python 3.6 here https://gist.github.com/dendisuhubdy/e2e67d796605dbf4860aa6e94201690a

### KirillMysnik commented Apr 25, 2018 • edited

 @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 commented Aug 5, 2018

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

 d

### ghost commented Sep 3, 2018

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

### 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 commented Apr 11, 2019

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

### 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 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 commented Jun 1, 2019

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

### 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 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.
Owner Author

### JonCooperWorks commented Oct 15, 2019

 Hi, thanks for the feedback. This was for a school project back in the day. I’m gonna update the repo so nobody thinks to use it for anything. It scares me to think people might have. I apologize. … On Tue, 15 Oct 2019 at 9:06 AM Aphrodites1995 ***@***.***> wrote: 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. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub , or unsubscribe .

### 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 commented Feb 10, 2020

 This is SEVERELY broken https://www.0xkasper.com/articles/hacktm-ctf-2020-qualifiers-write-up#rsa-is-easy-1 DO NOT USE FOR ANYTHING!