How to calculate RSA private key in Python

Question

I am creating a program that encrypts and decrypt data. I need to calculate the secret key but I can't work out how to change the algebra into a expression that can be used in python.

I tried using algebra but I could not figure it out. I'm using python 3.6.1

def genkey():
    p = 3 #prime 1
    q = 11 #prime 2
    n = p * q# pubkey part 1
    z = (p-1)*(q-1)# 20
    k = 7 #coprime to z and pub key part 2
    #j = ?
    return (n,k,j)

j should equal 3 and formula is
k * j = 1 ( mod z )

I am using pre-calculated numbers for testing

Link to site

You need to read up on the extended Euclidean algorithm. It should be covered in any sufficiently complete discussion of RSA. — John Coleman
– John Coleman, Commented Apr 6, 2019 at 22:59

SecurityBreach · Accepted Answer · 2019-04-07 00:12:41Z

For RSA:

I will provide some algorithms and codes from my own Bachelor Thesis

p and q, two prime numbers
n = p*q, n is the part of the public key
e or public exponent should be coprime with Euler function for n which is (p-1)(q-1) for prime numbers

Code for finding public exponent:

def find_public_key_exponent(euler_function):
    """
    find_public_key_exponent(euler_function)

    Finds public key exponent needed for encrypting.
    Needs specific number in order to work properly.

    :param euler_function: the result of euler function for two primes.
    :return:               public key exponent, the element of public key.
    """

    e = 3

    while e <= 65537:
        a = euler_function
        b = e

        while b:
            a, b = b, a % b

        if a == 1:
            return e
        else:
            e += 2

    raise Exception("Cant find e!")

next we need modular multiplicative inverse of Euler function(n) and e, which equals d, our last component:

def extended_euclidean_algorithm(a, b):
    """
    extended_euclidean_algorithm(a, b)

    The result is the largest common divisor for a and b.

    :param a: integer number
    :param b: integer number
    :return:  the largest common divisor for a and b
    """

    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extended_euclidean_algorithm(b % a, a)
        return g, x - (b // a) * y, y


def modular_inverse(e, t):
    """
    modular_inverse(e, t)

    Counts modular multiplicative inverse for e and t.

    :param e: in this case e is a public key exponent
    :param t: and t is an Euler function
    :return:  the result of modular multiplicative inverse for e and t
    """

    g, x, y = extended_euclidean_algorithm(e, t)

    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return x % t

Public key: (n, e) Private key: (n, d)

Encryption: <number> * e mod n = <cryptogram>

Decryption: <cryptogram> * d mon n = <number>

There are some more restrictions so the cipher should be secure but it will work with conditions I provided.

And of course you need to find your way to get large prime numbers, read about prime testing

matthew strange · Accepted Answer · 2023-10-10 16:41:34Z

0

Calculate phi using p and q:

phi = (p-1) * (q-1)

Use built in python function pow passing in public exponent and phi:

pow(e, -1, phi)

answered Oct 10, 2023 at 16:41

matthew strange

111 bronze badge

Comments

Irfan · Accepted Answer · 2024-03-21 14:18:13Z

0

Similar to the solution by Matthew above but using the python module egcd (Extended Euclidean Algorithm)

pip3 install egcd

Then in python window

from egcd import egcd
phi = (p-1) * (q-1)
d = egcd(e, phi)[1] % phi

answered Mar 21, 2024 at 14:18

Irfan

12 bronze badges

Collectives™ on Stack Overflow

How to calculate RSA private key in Python

3 Answers 3

For RSA:

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

For RSA:

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related