Erba Aitbayev 'KZ' Erba Aitbayev 'KZ' - 1 year ago 103
Python Question

RSA Python & Extended Euclidean algorithm to generate the private key. Variable is None

Problem with simple RSA encryption algorithm. Extended Euclidean algorithm is used to generate the private key. The problem with

multiplicative_inverse(e, phi)
method. It is used for finding the multiplicative inverse of two numbers. The function does not return private key correctly. It returns

I have the following code:

import random

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

#Euclidean 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

def generate_keypair(p, q):
n = p * q

#Phi is the totient of n
phi = (p-1) * (q-1)

#An integer e such that e and phi(n) are coprime
e = random.randrange(1, phi)

#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)

#Extended Euclid's Algorithm to generate the private key
d = multiplicative_inverse(e, phi)

#Public key is (e, n) and private key is (d, n)
return ((e, n), (d, n))

if __name__ == '__main__':
p = 17
q = 23

public, private = generate_keypair(p, q)
print("Public key is:", public ," and private key is:", private)

Since the variable
in the following line
d = multiplicative_inverse(e, phi)
value, then during encryption I receive the following error:

TypeError: unsupported operand type(s) for pow(): 'int', 'NoneType',

Output for the code that I provided in the question:

Public key is: (269, 391) and private key is: (None, 391)

Question: Why the variable contains
value. How to fix that?

Answer Source

Well I'm not sure about the algorithm itself, and can't tell if you if it's wrong or right, but you only return a value from multiplicative_inverse function when if temp_phi == 1. Otherwise, the result is None. So I bet your temp_phi != 1 when you run the function. There's probably some mistake in the function's logic.