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

Question

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 None value.

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 in the following line d = multiplicative_inverse(e, phi) contains None value, then during encryption I receive the following error:

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)

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

The pseudo-code for Computing multiplicative inverses in modular structures is relatively simple and easy to map to Python. Is suggest you look again. There are many mistakes that you made. Forgetting to return something useful on the else branch is only the beginning of your problems. — Artjom B.
– Artjom B., Commented Sep 24, 2016 at 13:11

Pavel Gurkov · Accepted Answer · 2016-09-24 13:04:22Z

2

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.

answered Sep 24, 2016 at 13:04

Pavel Gurkov

7585 silver badges18 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Kamil Rymarz · Accepted Answer · 2016-09-24 13:06:21Z

1

I think that this is a problem:

if temp_phi == 1:
   return d + phi

This function return some value only under condition that temp_phi is equal to 1, otherwise it will not return any value.

answered Sep 24, 2016 at 13:06

Kamil Rymarz

4084 silver badges9 bronze badges

Comments

Julian Barnes · Accepted Answer · 2019-04-11 13:16:34Z

0

This looks like you are converting from python 2 to 3. In 2 temp_phi/e will be an integer, but in 3 it's a float. As the multiplative inverses method of division uses integers you need to change the line to int(temp_phi / e) or temp_phi // e

answered Apr 11, 2019 at 13:16

Julian Barnes

1

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related