Generating and using RSA keys with Python

Question

I'm working on a Python project which is supposed to encrypt, send and then decrypt messages with RSA. (I precise it's not a professional project) I've written a small program to create these keys, and I thought it would work however I think there's a problem in my keys.

The keys are created this way :

def generate_integer ():

    i = 0
    number = ""
    number += str(randrange(1,10))
    while i < 1:
        number += str(randrange(0,10))
        i += 1

    return int (number)

def generate_prime_integers ():


    p = generate_integer ()
    q = 0
    premiers = False

    while not prime:
        q = generate_integer ()
        prime = extended_euclide (p, q, False)
        if p == q:
            prime = False

    return p, q

def generate_prime_with_Euler (i_Euler):

    prime_with_Euler = False
    while not prime_with_Euler:
        e = randrange(2,100)
        prime_with_Euler = extended_euclide (e, i_Euler, False)

    return e

def extended_euclide (a,b,calculate_bezout):

    r = a
    u = 1
    v = 0
    r2 = b
    u2 = 0
    v2 = 1
    quotient = 0

    while r2 != 0:
        q = r // r2
        (r, u, v, r2, u2, v2) = (r2, u2, v2, r - q * r2, u - q * u2, v - q * v2)

    prime = False
    if r == 1:
        prime = True

    if calculate_bezout:
        return u
    else:
        return prime


def calculate_d (e, i_Euler):

    u = extended_euclide (e, i_Euler, True)
    return u

def create_keys():
    d = -1
    while d < 0:
        p, q = generate_prime_integers()
        n = p*q
        i_Euler = (p-1) * (q-1)
        e = generate_prime_with_ Euler (i_Euler)
        d = calculate_d (e, i_Euler)

    return n, e, d

A few explanations : e is the encrypting exponent, d is the decrypting exponent, i_Euler is the Phi(n) function. The function called is create_keys (), it uses all the functions above to create the 2 keys, public and private. I took the function 'extended_euclide' from Wikipedia, because I had no idea how to code the algorithm of Euclide, and modified it a bit so that it either gives me d (when I give True as third parameter) or tells if the two integers are relatively prime (when giving False).

So, the problem is : when I create my keys and try to encrypt/decrypt any value, it's not working

>>> n,e,d = create_keys()
n : 1634
e :  47
d :  293
>>> message = 64
>>> encrypted_message = pow (message, e, n)
>>> encrypted_message
1208
>>> decrypted_message = pow (encrypted_message, d, n)
>>> decrypted_message
140

Here, decrypted_message should be equal to message, that is to say, 64. Why is it not working ? Is there a problem in the creation of my keys, or is this another issue ?

Edit: Thanks @BurningKarl I had indeed forgoten to check if p and q were prime numbers. Here's the new function which replaces generate_integer ()

def generate_prime_integer ():

    prime= False
    while not prime:
        number= randrange (10,100)
        square_root= int (sqrt (nombre))
        if square_root< sqrt (nombre):
            square_root+= 1
        square_root+= 1

        prime= True
        for i in range (2, square_root):
            if number % i == 0: 
                prime = False


    return number

With that code it seems to be working properly.

I think RSA works only if p and q are prime. extended_euclide (p, q, False) checks whether p and q are coprime (i.e. the greatest common divisor is 1) and not whether both numbers are really prime numbers. Also, instead of generate_integer() you could use randrange(10,100) — BurningKarl
– BurningKarl, Commented Mar 31, 2017 at 20:51
A flame war, really @MaartenBodewes ? I only meant that Python is not the most efficient language to compute operations with very large numbers, not to launch a 'war' of languages. I've changed :) — Dolly2929
– Dolly2929, Commented Apr 1, 2017 at 7:18
@BurningKarl You're probably be right, when I added the extended_euclide function, I deleted the former I had created and forgot to check if p and q were prime numbers... I will try and tell you — Dolly2929
– Dolly2929, Commented Apr 1, 2017 at 7:21
The best thing to do is to ask @BurningKarl to convert his comment into an answer, so you can vote up / accept the answer. You could also edit that answer and include the final code. If BurningKarl doesn't want to add an answer you can answer yourself and accept your answer after 2 days. — Maarten Bodewes
– Maarten Bodewes, Commented Apr 1, 2017 at 9:37

BurningKarl · Accepted Answer · 2017-04-01 12:48:34Z

1

Here is my comment as an answer:

When looking at the RSA Wikipedia page it states:

A user of RSA creates and then publishes a public key based on two large prime numbers, along with an auxiliary value.

So for the encryption to work prime numbers are needed while extended_euclide (p, q, False) only checks whether p and q are comprime, i.e. whether their greatest common divisor is 1.

answered Apr 1, 2017 at 12:48

BurningKarl

1,20610 silver badges12 bronze badges

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

1 Comment

Dolly2929 Over a year ago

That's right, as I said I forgot to check if p and q were prime numbers before testing if they were relatively prime, thanks for your help

Collectives™ on Stack Overflow

Generating and using RSA keys with Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related