Python Forum

my question here

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 range(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(input("Enter a prime number (17, 19, 23, etc): "))
    q = int(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 = 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))

RSA Encrypter/ Decrypter
Enter a prime number (17, 19, 23, etc): 79
Enter another prime number (Not one you entered above): 19
Generating your public/private keypairs now . . .
Your public key is (803, 1501) and your private key is (None, 1501)
Enter a message to encrypt with your private key: 4354543
Traceback (most recent call last):
File "C:/python/program/rsa.py", line 114, in <module>
encrypted_msg = encrypt(private, message)
File "C:/python/program/rsa.py", line 90, in encrypt
cipher = [(ord(char) ** key) % n for char in plaintext]
File "C:/python/program/rsa.py", line 90, in <listcomp>
cipher = [(ord(char) ** key) % n for char in plaintext]
TypeError: unsupported operand type(s) for ** or pow(): 'int' and 'NoneType'

Did you take this from a 'C' or 'C++' program?
char ** key on line 90 looks like pointer to pointer of type char (C code)
did you mean chr ** key as in exponent?

I mean chr ** key as in exponent?
cipher=pow(plain,public_key)mod n
plain=pow(cipher,private_key)mod n

This isn't your issue, but for general knowledge here the python builtin pow actually takes a third argument to mod by to take advantage of modular exponentiation.

So like pow(456, 89700, 17) instead of (456**89700) % 17.

Interestingly enough though the interpreter does seem smart enough to use modular exponentiation in the second case as well but I'm not sure if this is part of spec or just an implementation detail you can't rely on.  If you tried to do the exponentiation in one expression and then the mod in another though your program could take eons.

Edit: Actually on second thought I think the second version is done inefficiently. The first version should always be much faster.