Calculate d from n, e, p, q in RSA?
The algorithm you need is the Extended Euclidean Algorithm. This allows you to compute the coefficients of Bézout's identity which states that for any two non-zero integers a
and b
, there exist integers x
and y
such that:
ax + by = gcd(a,b)
This might not seem immediately useful, however we know that e
and φ(n)
are coprime, gcd(e,φ(n)) = 1
. So the algorithm gives us x
and y
such that:
ex + φ(n)y = gcd(e,φ(n))
= 1
Re-arrange:
ex = -φ(n)y + 1
This is equivalent to saying ex mod φ(n) = 1
, so x = d
.
For example you need to get d in the next:
3*d = 1 (mod 9167368)
this is equally:
3*d = 1 + k * 9167368, where k = 1, 2, 3, ...
rewrite it:
d = (1 + k * 9167368)/3
Your d must be the integer with the lowest k.
Let's write the formula:
d = (1 + k * fi)/e
public static int MultiplicativeInverse(int e, int fi) {
double result;
int k = 1;
while (true) {
result = (1 + (k * fi)) / (double) e;
if ((Math.Round(result, 5) % 1) == 0) {
//integer
return (int)result;
} else {
k++;
}
}
}
let's test this code:
Assert.AreEqual(Helper.MultiplicativeInverse(3, 9167368), 6111579); // passed
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.