Как рассчитать модульное мультипликативное обратное число в контексте шифрования RSA?

Question

Как вычислить модульное мультипликативное обратное число в контексте шифрования RSA?

Answer 1

Используйте Расширенный евклидов алгоритм , который на практике значительно быстрее, чем прямое модульное возведение в степень.

Answer 2

Прямое модульное экспонирование

Метод прямого модульного возведения в степень, альтернативный расширенному евклидову алгоритму, выглядит следующим образом:

Источник: http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

Answer 3

Есть два алгоритма, подробно объясненных в Модульном мультипликативном обратном Статья Википедии.

Answer 4

Я разработал более простую обратную функцию

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

Уравнение d * e = 1 (mod totient) можно переписать как d * e = 1 + k * totient (для некоторого значения k) и программа просто ищет первое значение k, что делает уравнение делимым на e (открытый показатель).Это будет работать, если e мало (как обычно рекомендуется).

Мы можем переместить все операции bignum из цикла, чтобы улучшить его производительность.

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

Оказывается, что для e = 3 нам не нужно искать, так как ответ всегда 2 * ((p-1) * (q-1) +1) / 3

Answer 5

Если вам нужно вычислить w для DSA alghoritm, вы можете использовать это:

w = s^-1 mod q

на самом деле

w = s^(q-2) mod q

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