Erba Aitbayev 'KZ' - 2 months ago 22

Python Question

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

`multiplicative_inverse(e, phi)`

`None`

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

`d`

`d = multiplicative_inverse(e, phi)`

`None`

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

'int'

Output for the code that I provided in the question:

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

`None`

Answer

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.

Source (Stackoverflow)

Comments