3.2. Трехпроходный протокол Шамира

Данный протокол [9] в отличие от предыдущего, где ключ получается в процессе выполнения, позволяет передать заранее сгенерированный секретный ключ k. В основе протокола лежат свойства ассоциативности и коммутативности операций модульного экспоненцирования и извлечения корней в конечном поле. Общим параметром системы является простое число P. На практике значение P занимает не менее 1024 бит.

Каждый из двух абонентов A и Б соответственно выбирают секретные ключи x_А и x_Б.

При этом и .

Далее каждый из двух абонентов A и Б соответственно вычисляют секретные ключи y_А и y_Б:

1 проход. Абонент A генерирует секретный сеансовый ключ k и передает абоненту Б:

2 проход. Абонент Б передает абоненту A:

3 проход. Абонент A передает абоненту Б: , что фактически равно .

После этого абоненту Б остается восстановить ключ k’:

Соблюдение требований а также является обязательным, так как без этого корректное восстановление k невозможно.

Противник, зная только модуль, по которому производились вычисления, но не зная ни основания, ни показателя степени, не может решить ни задачу логарифмирования, ни задачу извлечения корня. Фактически протокол Шамира уже является асимметричной системой шифрования, но отнести его к алгоритмам шифрования мешает его «трехпроходность».

Задача 3.2. Для заданного простого числа P и сеансового ключа k, определить самостоятельно пары секретных ключей обоих абонентов и осуществить передачу сеансового ключа при помощи трехпроходного протокола Шамира. Проверить совпадение сеансовых ключей обоих абонентов.

Пример решения.

Дано: P = 113 k = 37	Решение:
Найти: xA, yA, xБ, yБ, , Проверить: k = k’
;

3.3. Криптосистема rsa

Это первая полноценная асимметричная система шифрования. Основу системы составляет трудность извлечения корней по модулю составного числа без знания разложения этого числа на два простых множителя. В отличие от предыдущих протоколов система не имеет общих параметров, наоборот, для обеспечения стойкости необходимо, чтобы каждый абонент имел свой модуль для вычислений.

Абонент, желающий получать сообщения, зашифрованные на открытом ключе, выбирает два простых числа p и q и вычисляет

Открытая экспонента шифрования выбирается из условия . Соблюдение данного требования обязательно по условию возможности расшифрования.

Закрытая экспонента находится при помощи обобщенного алгоритма Евклида:

Открытым ключом является пара:

Закрытым ключом является набор:

Зашифрование сообщения m производится как

Для расшифрования производят извлечение корня

Так как для удобства абонентов, выполняющих зашифрование на открытом ключе, предлагается выбирать малые экспоненты E, значение d может иметь значительно больший размер, поэтому удобнее выполнять извлечение корня по методу «разделяй и властвуй» по модулям простых чисел p и q:

.

Значение затем восстанавливается при помощи китайской теоремы об остатках из системы сравнений:

Подобным образом и следует выполнять расшифрование при решении следующей задачи, так как калькулятор Windows может дать переполнение регистра.

Главным недостатком канонической RSA является то, что один и тот же открытый текст m всегда зашифровывается одинаковым C, что открывает возможности анализа трафика [10,13].

Задача 3.3. Для заданной пары простых чисел p и q и открытого текста m определить самостоятельно остальные параметры шифрсистемы RSA и осуществить зашифрование и расшифрование. Проверить совпадение исходного m и полученного значений открытого текста.

Пример решения.

Дано: p = 113 q = 127 m = 59	Решение:
Найти: N, φ(N), E, d, C, m’ Проверить: m’ = m
дает переполнение .