CODEWITHSUNDEEP
rsaprivate-keypublic-key
A. Szokalski
A. Szokalski

Reputation: 65

Calculating d value in RSA

I saw a couple questions about this but most of them were answered in unhelpful way or didn't get a proper answer at all.
I have these variables:

Now I need to calculate d variable (which I know is equal 367). The problem is that I don't know how. I found this equation on the internet but it doesn't work (or I can't use it):

e⋅d=1modϕ(n)

When I see that equation i think that it means this:

d=(1modϕ(n))/e

But apparently it doesn't because 367 (1modϕ(n))/e = 1%660/223 = 1/223 != 367
Maybe I don't understand and I did something wrong - that's why I ask.

I did some more research and I found second equation:

d=1/e mod ϕ(n)
or
d=e^-1 mod ϕ(n)

But in the end it gives the same result: 1/e mod ϕ(n) = 1/223 % 660 = 1/223 != 367

Then I saw some guy saying that to solve that equation you need extended Euclidean algorithm If anyone knows how to use it to solve that problem then I'd be very thankful if you help me.

Upvotes: 1

Views: 5349

Answers (1)

plazer
plazer

Reputation: 26

If you want to calculate something like a / b mod p, you can't just divide it and take division remainder from it. Instead, you have to find such b-1 that b-1 = 1/b mod p (b-1 is a modular multiplicative inverse of b mod p). If p is a prime, you can use Fermat's little theorem. It states that for any prime p, ap = a mod p <=> a(p - 2) = 1/a mod p. So, instead of a / b mod p, you have to compute something like a * b(p - 2) mod p. b(p - 2) can be computed in O(log(p)) using exponentiation by squaring. If p is not a prime, modular multiplicative inverse exists if and only if GCD(b, p) = 1. Here, we can use extended euclidean algorithm to solve equation bx + py = 1 in logarithmic time. When we have bx + py = 1, we can take it mod p and we have bx = 1 mod p <=> x = 1/b mod p, so x is our b-1. If GCD(b, p) ≠ 1, b-1 mod p doesn't exist.

Using either Fermat's theorem or the euclidean algorithm gives us same result in same time complexity, but the euclidean algorithm can also be used when we want to compute something modulo number that's not a prime (but it has to be coprime with numer want to divide by).

Upvotes: 1

Related Questions