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