Calculate d from n, e, p, q in RSA?
cryptography, encryption, public-key-encryption, rsa
Solution
You are looking for the modular inverse of e (mod n), which can be computed using the extended Euclidean algorithm:
function inverse(x, m)
a, b, u := 0, m, 1
while x > 0
q := b // x # integer division
x, a, b, u := b % x, u, x, a - q * u
if b == 1 return a % m
error "must be coprime"
Thus, in your examples, `inverse(17, 3120)` = 2753 and `inverse(2621, 8736)` = 4373. If you don't want to implement the algorithm, you can ask Wolfram|Alpha for the answer.
Problem
Not sure if this is the correct place to ask a cryptography question, but here goes. I am trying to work out "d" in RSA, I have worked out p, q, e, n and ø(n); ``` p = 79, q = 113, e = 2621 n = pq ø(n) = (p-1)(q-1) n = 79 x 113 = 8927 ø(n) = 78 x 112 = 8736 e = 2621 d = ??? ``` I cant seem to find d, I know that d is meant to be a value that.. ed mod ø(n) = 1. Any help will be appreciated As an example would be e = 17, d = 2753, ø(n) = 3120 ``` 17 * 2753 mod 3120 = 1 ```