Вычислительные аспекты

Открытое шифрование RSA.

2.10.3.1. Математическая модель..

1. Генерация ключей

Выбрать простые р и q

Вычислить n = p · q

Выбрать e gcd (Φ(n), e) = 1; 1 < e < Φ(n)

Вычислить d d = e^-1 mod Φ(n)

Открытый ключ KU = {e, n}

Закрытый ключ KR = {d}

2. Зашифрование

Открытый текст: М < n

Зашифрованный текст: С = М ^е (mod n)

3. Расшифрование

Зашифрованный текст: С

Восстановленный открытый текст: М = С^d (mod n)

Док-во:

С^d (mod n) = (М ^е)^d (mod n) = (М ^еd) (mod n) = М ^{(k Φ(n) +1)} (mod n) =

= (М· (mod n) (М ^{k Φ(n)} ) (mod n)) (mod n) = (М· (М ^Φ(n) ) (mod n)) ^k(mod n)) = (по теореме Эйлера) = М

ч.т.д.

Пример

1. Генерация ключей

Выбрать два простых числа: р = 7, q = 17.

Вычислить n = p · q = 7 · 17 = 119.

Вычислить Φ(n) = (p - 1) · (q - 1) = 96.

Выбрать е так, чтобы е было взаимнопростым с Φ(n) = 96 и меньше, чем Φ(n): е = 5.

Вычислить d из условия d · e 1 mod 96 и d < 96.

d = 77, так как 77 · 5 = 385 = 4 · 96 + 1.

Таким образом, открытый ключ KU = {5, 119, а закрытыйключ KR = 77.

2.Зашифрование

Сообщение М = 19.

С = 19⁵ = 66 (mod 119).

3.Расшифрование

М= 66⁷⁷ (mod 119) = 19.

1.Возведение целого числа в целую степень по модулю n. При этом промежуточные значения будут громадными. Для того чтобы частично этого избежать, используется следующее свойство модульной арифметики:

[(a mod n) · (b mod n)] mod n = (a · b) mod n

2. Разложение показателя по степеням 2

Предположим, что необходимо вычислить х³⁷. Прямой подход требует 36 умножений. Однако можно добиться того же конечного результата с помощью только семи умножений, если использовать квадрат каждого промежуточного результата: х², х⁴, х⁸, х¹⁶

х³⁷ = х (х²) (х²)²)²)²)²).

3. Для вычисления d = e^-1 mod Φ(n) используется расширенный алгоритм Евклида, который относится к классу эффективных (вычислительно простых).

Таким образом, алгоритмы зашифрования и расшифрования являются эффективными.

Дата добавления: 2013-12-13