RSA: Private key calculation with Extended Euclidean Algorithm
I'm a high school student writing a paper on RSA, and I'm doing an example with some very small prime numbers. I understand how the system works, but I can't for the life of me calculate the private key using the extended euclidean algorithm.
Here's what I have done so far:
- I have chosen the prime numbers p=37 and q=89 and calculated N=3293
- I have calculated (p-1)(q-1)=3168
- I have chosen a number e so that e and 3168 are relatively prime. I'm checking this with the standard euclidean algorithm, and that works very well. My e=25
Now I just have to calculate the private key d, which should satisfy ed=1 (mod 3168)
Using the Extended Euclidean Algorithm to find d such that de+tN=1 I get -887•25+7•3168=1. I throw the 7 away and get d=-887. Trying to decrypt a message, however, this doesn't work.
I know from my book that d should be 2281, and it works, but I can't figure out how they arrive at that number.
Can anyone help? I've tried solving this problem for the last 4 hours, and have looked for an answer everywhere. I'm doing the Extended Euclidean Algorithm by hand, but since the result works my calculations should be right.
Thanks in advance,
Mads
Answer
You're so close you're going to kick yourself.
3168-887=2281.
Specifically, If you have a mod x, then A must satisfy 0<=a<x. If it doesn't, add or subtract x as many times as necessary until you are in this range. This is called modular arithmetic.
You might want to read up on linear congruences and number theory. These topics are degree level mathematics in the UK (what you'd call college I guess) so don't worry if it seems a bit odd. A linear congruence simply says that -887 mod 3168 and 2281 mod 3168 are actually the same thing because they are part of the same class, the class that turns out as 2281 mod 3168 in the required range. 2281+3168 mod 3168 would also be in that class.
Have fun!
P.S. PARI/GP is a utility number theorists use for calculations. Might be worth a look.