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?)
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/