Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
c'd = rm(modN).
Это число может показаться Алисе совершенно случайным, поскольку умножение на число г является перестановкой над группой Щ^. Итак, Алиса возвращает результат расшифровки гт Злоумышленнику. Увы! Злоумышленнику известно число г, и он может вычислить число тп с помощью деления по модулю N. ?
Примеры 8.3-8.5 демонстрируют, что учебный алгоритм RSA слишком слаб для реальных приложений. Необходимо систематически исправлять его недостатки. Эта работа выполняется за два этапа.
• В главе 14 вводятся понятия повышенной стойкости схем шифрования с открытым ключом, пригодные для реальных приложений.
316
Часть III. Основные методы криптографии
• В главе 15 изучается реальная версия алгоритма шифрования RSA, который является стандартным. В ней приводится формальное доказательство стойкости алгоритма RSA на основе понятия сильной стойкости.
8.10 Криптосистема Рабина (учебный вариант)
Криптосистема, разработанная Рабином (Rabin), основана на сложности вычисления квадратного корня по модулю составного числа [240]. Работа Рабина носила теоретический характер. В ней впервые приводилось доказательство стойкости криптосистем с открытым ключом: стойкость криптосистемы Рабина эквивалентна неразрешимости задачи о разложении целых чисел на множители. (На-< помним, что эквивалентность разрешимости задачи RSA и разрешимости задачи о разложении целых чисел на множители еще не доказана.) Алгоритм шифров вания в криптосистеме Рабина чрезвычайно эффективен и пригоден для многих, практических приложений, например, для шифрования с помощью портативны^ устройств.
Криптосистема Рабина описывается алгоритмом 8.2.
Алгоритм 8.2. Криптосистема Рабина Ключ
Для создания ключа Алиса должна выполнить следующие действия.
1. Выбрать два случайных простых числа р и q, удовлетворяющих условию1
Ь1и Ы-
(* Этот этап совпадает с вычислением модулей алгоритма RSA в алгорит-1 ме 8.1. *)
2. Найти число N = pq.
3. Извлечь случайное целое число Ъ G иЩу-
4. Использовать пару (Л7, Ь) в качестве параметров открытого ключа и запомнить пару (р, q) в качестве параметров закрытого ключа.
Шифрование
Для того чтобы послать Алисе секретное сообщение т G Z*N, Боб создает зашиф-j рованный текст с:
с <— т(т + b)(mod N).
Расшифровка
Для того чтобы расшифровать зашифрованный текст с, Алиса решает квадратное! уравнение
тп2 + Ьт - с ее 0(mod N),
где т< N.
Глава 8. Шифрование — асимметричные методы
317
Покажем, что алгоритм 8.2 действительно описывает криптосистему, т.е. процедура расшифровки, выполняемая Алисой, действительно восстанавливает исходный текст, зашифрованный Бобом.
Из элементарной математики известно, что общее решение квадратного уравнения имеет вид:
имеет решения в группе Z*N. Одним из этих решений является число т, посланное Бобом. Отсюда следует, что число Дс должно быть квадратичным вычетом по модулю N, т.е. элементом группы QR^.
Вычисления, связанные с расшифровкой, содержат операцию извлечения квад-Ьатного корня по модулю N. В разделе 6.6.2 показано, что вычислительная сложность этой задачи эквивалентна факторизации числа N (следствие 6.3). Следовательно, Алиса является единственным пользователем, который может вычислить [формулу (8.10.1), поскольку только ей известно разложение числа N на простые Ииножители. Алиса может найти число у/А^., используя алгоритм 6.5. В разделе 6.6.2 показано, что для каждого зашифрованного текста с, посланного Бобом, существует четыре разных значения у/А^., и, следовательно, существует четыре разных результата шифрования. Как правило, реальное исходное сообщение содержит избыточную информацию (redundant information), позволяющую Алике отличать правильные тексты от неправильных. Смысл понятия "избыточная информация" и способ ее внедрения в текст изложены в разделе 10.4.3.
Отметим, что, если число N является целым числом Блюма (Blum integer), fee. N = pq, где p = q = 3(mod 4), вычисление квадратных корней по модулю N упрощается и сводится к вычислению квадратных корней по модулю р и q 1с помощью алгоритма 6.3 для р = 3,7(mod 8) и применения китайской теоремы об остатках. Следовательно, на практике открытые модули, применяемые в криптосистеме Рабина, должны быть целыми числами Блюма.
В алгоритме шифрования Рабина используется только одно умножение и одно сложение. Следовательно, этот алгоритм работает быстрее, чем алгоритм шифрования RSA.
Пример 8.6. Допустим, что Алиса выбирает числа Аг = 11х19 = 209 и Ъ = = 183. Она объявляет пару {N,b) = (209,183) параметрами открытого ключа криптосистемы Рабина.
(8.10.1)
Ас = 62 + 4c(modAT).
(8.10.2)
Поскольку число с зависит от элемента т € "L*N, квадратное уравнение
т2 + Ьт- с = 0(mod N)
Глава 8. Шифрование — асимметричные методы
319
Выберем случайное сообщение т, определим число с = m(m + b)(mod N) и вызовем оракула С(с, N), который возвращает число т' = ~b+v/AT (mod N) с преимуществом е. Здесь \fK^ обозначает один из четырех квадратных корней числа Лс. Из теоремы 6.17 (раздел 6.6.2) следует, что с вероятностью 1/2 выполняется неравенство
