Using Extended Euclidean Algorithm to create RSA private key

Question

This is for an assignment I'm doing through school. I am having trouble generating a private key. My main problem is understanding the relation of my equations to each other. To set everything up, we have:

p = 61
q = 53
n = p * q (which equals 3233)

From here we have the totient of n (phi(n)) which equals 3120, now we can choose prime e; where 1 < e < 3120

e = 17

Okay easy enough.

For my assignment we've been made aware that d = 2753, however I still need to be able to arbitrarily generate this value.

Now here is where I am having trouble. I've been perusing wikipedia to understand and somewhere something isn't connecting. I know that I need to find the modular multiplicative inverse of e (mod phi(n)) which will be d, our private exponent.

Reading though wikipedia tells us to find the mmi we need to use the Extended Euclidian Algorithm. I've implemented the algorithm in python as follows:

def egcd(a, b):
    x, lastX = 0, 1
    y, lastY = 1, 0
    while (b != 0):
        q = a // b
        a, b = b, a % b
        x, lastX = lastX - q * x, x
        y, lastY = lastY - q * y, y
    return (lastX, lastY)

This is where I am lost. To my understanding now, the equation ax + bx = gcd(a, b) = 1 is the same e*x + phi(n)*y = gcd(e, phi(n)) = 1. So we call egcd(e, phi(n)), and now I get [-367, 2] for my x and y.

From here I honestly don't know where to go. I've read this similar question and I see that there are some substitutions that happen, but I don't understand how those number relate to the answer that I got or the values I have started out with. Can someone explain to me pragmatically what I need to do from here? (When I say pragmatically, I mean without actual code. Pseudo code is fine, but if I get actual code I won't be able to learn without plagiarism on my assignment which is a big no-no).

As always, any help is genuinely appreciated. Thanks everyone!

(And yes, I have seen these:RSA: Private key calculation with Extended Euclidean Algorithm and In RSA encryption, how do I find d, given p, q, e and c?)

Answer 1

The implementation of the Extended Euclidean algorithm you have is not complete, since it is generating a negative number for the private key. Use this code instead:

https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm

For your example the private key, d, is 2753.

p=61
q=53
n = 3233
phi(n)=3120
e=17
d=modinv(17,3120)=2753

Try it out:

message m m=65


encryption: m^e mod n = c    (65**17) % 3120 =  65
decryption: c^d mod n = m      (65**2753) % 3120 =   65

Its all explained here:

http://southernpacificreview.com/2014/01/06/rsa-key-generation-example/

Answer 2

def egcd(a,b):   
    s1, s2 = 1, 0   
    t1, t2 = 0, 1   
    while b!=0:   
        q = a//b    
        r = a%b   
        a, b = b, r     
        s = s1-q*s2    
        s1, s2 = s2, s      
        t = t1-q*t2    
        t1, t2 = t2, t    
    return (s1, t1)

try comparing above.

i will tell you where was your mistake:

a, b = b, a % b

a has the value of b now (b=a%b)==(b=b%b)
and similar reason for proceeding two lines