How to calculate the Modular Multiplicative inverse of a number in the context of RSA encryption?

How to calculate开发者_JAVA百科 the Modular Multiplicative inverse of a number in the context of RSA encryption?

---

Use the Extended Euclidean Algorithm, which is significantly faster than direct modular exponentiation in practice.

---

Direct Modular Exponentiation

The direct modular exponentiation method, as an alternative to the extended Euclidean algorithm, is as follows:

Source: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

---

There are two algorithms explained in detail in the Modular multiplicative inverse Wikipedia article.

---

If You need to calculate w for DSA alghoritm, you can use this:

w = s^-1 mod q

is actually

w = s^(q-2) mod q

See: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse#Using_Euler.27s_theorem

---

I worked out a an simpler inverse function

def privateExponent(p,q,e):
    totient=(p-1)*(q-1)
    for k in range(1,e):
        if (totient*k+1) % e==0:
            return (totient*k+1)/e
    return -1 # shouldnt get here

The equation d*e=1 (mod totient) can be rewritten as d*e=1+k*totient (for some value of k) and the program just searches for first value of k which makes the equation divisible by e (the public exponent). This will work if e is small (as is usually recommended).

We can move all the bignum operations out of the loop to improve its performance.

def privateExponent(p,q,e):
    totient=(p-1)*(q-1)
    t_mod_e=totient % e
    k=0
    total=1
    while total!=0:
        k+=1
        total=(total+t_mod_e) % e
    return (k*totient+1)/e

It turns out that for e=3, we don't really have to search as the answer is always 2*((p-1)*(q-1)+1)/3