How to find d, given p, q, and e in RSA?

Question

I know I need to use the extended euclidean algorithm, but I'm not sure exactly what calculations I need to do. I have huge numbers. Thanks

Answer 1

Well, d is chosen such that d * e == 1 modulo (p-1)(q-1), so you could use the Euclidean algorithm for that (finding the modular multiplicative inverse).

If you are not interested in understanding the algorithm, you can just call BigInteger#modInverse directly.

 d = e.modInverse(p_1.multiply(q_1))

Answer 2

Given that, p=11, q=7, e =17, n=77, φ (n) = 60 and d=?

First substitute values from the formula:-

ed mod φ (n) =1

17 d mod 60 = 1

The next step: – take the totient of n, which is 60 to your left hand side and [e] to your right hand side.

60 = 17

3rd step: – ask how many times 17 goes to 60. That is 3.5….. Ignore the remainder and take 3.

60 = 3(17)

Step 4: – now you need to balance this equation 60 = 3(17) such that left hand side equals to right hand side. How?

60 = 3(17) + 9 <== if you multiply 3 by 17 you get 51 then plus 9, that is 60. Which means both sides are now equal.

Step 5: – Now take 17 to your left hand side and 9 to your right hand side.

17 = 9

Step 6:- ask how many times 9 goes to 17. That is 1.8…….

17 = 1(9)

Step 7:- Step 4: – now you need to balance this 17 = 1(9)

17 = 1(9) + 8 <== if you multiply 1 by 9 you get 9 then plus 8, that is 17. Which means both sides are now equal.

Step 8:- again take 9 to your left hand side and 8 to your right hand side.

9 = 1(8)

9 = 1(8) + 1 <== once you reached +1 to balance your equation, you may stop and start doing back substitution.

Step A:-Last equation in step 8 which is 9 = 1(8) + 1 can be written as follows: 1.= 9 – 1(8)

Step B:-We know what is (8) by simple saying 8 = 17 – 1(9) from step 7. Now we can re-write step A as:-

1=9 -1(17 – 1(9)) <== here since 9=1(9) we can re-write as:-

1=1(9)-1(17) +1(9) <== group similar terms. In this case you add 1(9) with 1(9) – that is 2(9).

1=2(9)-1(17)

Step C: – We know what is (9) by simple saying 9 = 60 – 3(17) from step 4. Now we can re-write step B as:-

1=2(60-3(17) -1(17)

1=2(60)-6(17) -1(17) <== group similar terms. In this case you add 6(17) with 1(17) – that is 7(17).

1=2(60)-7(17) <== at this stage we can stop, nothing more to substitute, therefore take the value next 17. That is 7. Subtract it with the totient.

60-7=d

Then therefore the value of d= 53.

Answer 3

I just want to augment the Sidudozo's answer and clarify some important points.

First of all, what should we pass to Extended Euclidean Algorthim to compute d ?

Remember that ed mod φ(n) = 1 and cgd(e, φ(n)) = 1.

Knowing that the Extended Euclidean Algorthim is based on the formula cgd(a,b) = as + bt, hence cgd(e, φ(n)) = es + φ(n)t = 1, where d should be equal to s + φ(n) in order to satisfy the

ed mod φ(n) = 1 condition.

So, given the e=17 and φ(n)=60 (borrowed from the Sidudozo's answer), we substitute the corresponding values in the formula mentioned above: cgd(e, φ(n)) = es + φ(n)t = 1 ⇔ 17s + 60t = 1.

At the end of the Sidudozo's answer we obtain s = -7. Thus d = s + φ(n) ⇔ d = -7 + 60 ⇒ d = 53.

Let's verify the results. The condition was ed mod φ(n) = 1.

Look 17 * 53 mod 60 = 1. Correct!

Answer 4

The approved answer by Thilo is incorrect as it uses Euler's totient function instead of Carmichael's totient function to find d. While the original method of RSA key generation uses Euler's function, d is typically derived using Carmichael's function instead for reasons I won't get into. The math needed to find the private exponent d given p q and e without any fancy notation would be as follows:

d = e^-1*mod(((p-1)/GCD(p-1,q-1))(q-1))

Why is this? Because d is defined in the relationship

de = 1*mod(λ(n))

Where λ(n) is Carmichael's function which is

λ(n)=lcm(p-1,q-1)

Which can be expanded to

λ(n)=((p-1)/GCD(p-1,q-1))(q-1)

So inserting this into the original expression that defines d we get

de = 1*mod(((p-1)/GCD(p-1,q-1))(q-1))

And just rearrange that to the final formula

d = e^-1*mod(((p-1)/GCD(p-1,q-1))(q-1))

More related information can be found here.

Answer 5

Simply use this formula,

d = (1+K(phi))/e. (Very useful when e and phi are small numbers)

Lets say, e = 3 and phi = 40 we assume K = 0, 1, 2... until your d value is not a decimal

assume K = 0, then d = (1+0(40))/3 = 0. (if it is a decimal increase the K value, don't bother finding the exact value of the decimal)

assume K = 2, then d = (1+2(40)/3) = 81/3 = 27

d = 27.

Assuming K will become exponentially easy with practice.

Answer 6

Here's the code for it, in python:

def inverse(a, n):
    t, newt = 0, 1
    r, newr = n, a

    while newr:
        quotient = r // newr  # floor division
        t, newt = newt, t - quotient * newt
        r, newr = newr, r - quotient * newr
    
    if r > 1:
        return None  # there's no solution
    
    if t < 0:
        t = t + n
    
    return t


inverse(17, 60)  # returns 53

adapted from pseudocode found in wiki: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode

Answer 7

Taken the values p=7, q=11 and e=17. then the value of n=p*q=77 and f(n)=(p-1)(q-1)=60. Therefore, our public key pair is,(e,n)=(7,77) Now for calvulating the value of d we have the constraint,

e*d == 1 mod (f(n)), [here "==" represents the **congruent symbol**].
17*d == 1 mod 60
(17*53)*d == 53 mod 60, [7*53=901, which gives modulus value 1]
1*d == 53 mod 60

hence,this gives the value of d=53. Therefore our private key pair will be, (d,n)=(53,77).

Hope this help. Thank you!