RSA calculate d

问题:

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

edit: an example would be e = 17, d = 2753, øn = 3120

17 * 2753 mod 3120 = 1

回答1:

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.

回答2:

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.

回答3:

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