Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
3) р и q должны быть сильно простыми числами (сильно простым называется такое простое число г, что г +1 имеет большой простой делитель, г —I имеет большой простой делитель Sf такой, что число s-І также обладает достаточно большим простым делителем).
В случае когда не выполнено хотя бы одно из указанных условий, имеются эффективные алгоритмы разложения п на простые множители (см. [Сал96], [Неч99]).
В настоящее время самые большие простые числа, вида п — p-q, которые удается разложить на множители известными методами, содержат в своей записи 140 десятичных знаков. Поэтому, согласно указанным рекомендациям, числа р и q в системе RSA должны содержать не менее 100 десятичных знаков.
Следует подчеркнуть необходимость соблюдения осторожности в выборе модуля RSA (числа п) для каждого из корреспондентов сети. В связи с этим можно сказать следующее.
Читатель может самостоятельно убедиться в том, что, зная одну из трех величин: /?, q или (р{п), можно легко найти секретный ключ RSA. Известно также, что, зная секретную экспоненту расшифрования d, можно легко разложить модуль п на множители. В этом случае удается построить вероятностный алгоритм разложения п. Отсюда следует, что каждый корреспондент сети, в которой для шифрования используется система RSA, должен иметь свой уникальный модуль.
316
системы с открытыми ключами
В самом деле, если в сети используется единый для всех модуль п, то такая организация связи не обеспечивает конфиденциальности, несмотря на то что базовая система RSA может быть стойкой. Выражаясь другими словами, говорят о несостоятельности протокола с общим модулем. Несостоятельность следует из того, что знание произвольной пары экспонент (endt) позволяет, как было отмечено, разложить
п на множители. Поэтому любой корреспондент данной сети имеет возможность найти секретный ключ любого другого корреспондента. Более того, это можно сделать даже без разложения п на множители [Сал96].
Как отмечалось ранее, системы шифрования с открытыми ключами работают сравнительно медленно. Для повышения скорости шифрования RSA на практике используют малую экспоненту зашифрования.
Если выбрать число е небольшим или таким, чтобы в его двоичной записи было мало единиц, то процедуру шифрования можно значительно ускорить. Например, выбрав е = 3 (при этом ни р — 1, ни q -I не должны делиться на 3), мы сможем реализовать шифрование с помощью одного возведения в квадрат по модулю п и одного перемножения. Выбрав
е = 216 4-1 = 65537 — число, двоичная запись которого содержит только две 1, мы сможем реализовать шифрование с помощью 16 возведений в квадрат по модулю п и одного перемножения. Если экспонента е выбирается случайно, то реализация шифрования по алгоритму RSA потребует s возведений в квадрат по модулю п ив среднем s/ 2 умножений по тому же модулю, где s — длина двоичной записи числа п . Вместе с тем выбор небольшой экспоненты е может привести к негативным последствиям. Дело в том, что у нескольких корреспондентов могут оказаться одинаковые экспоненты е.
317
Глава 11
Пусть, например, три корреспондента имеют попарно взаимно простые модули п},п2,п3 и общую экспоненту
е = 3. Если еще один пользователь посылает им некое циркулярное сообщение M , то криптоаналитик противника может получить в свое распоряжение три шифрованных текста
У' = M3 (mod /7,), і = 1,2,3. Далее он может найти решение у
системы сравнений
'у = у, (mod и,), < у = у2(то&п2), у a ^3(Hiodn3),
лежащее в интервале О < у < щ * п2 • пъ. По китайской теореме об остатках (см. Приложение 3) такое решение единственно, а так как M3 < щ -п2 -и3, то j/ = M3. Само M можно найти,
вычисляя кубический корень: M = \[у .
Отметим, что выбор малой экспоненты расшифрования d также нежелателен в связи с возможностью определения
d простым перебором. Известно также, что если d < ^fn , то экспоненту d легко найти, используя непрерывные дроби.
§11.2. Шифрсистема Эль-Гамаля
Шифрсистема Эль-Гамаля была предложена в 1985 г. [E1G85] и является фактически одним из вариантов метода выработки открытых ключей Диффи-Хеллмана (который будет рассмотрен далее). Криптографическая стойкость данной системы основана на сложности проблемы логарифмирования в мультипликативной группе конечного простого поля.
318
системы с открытыми ключами
В соответствии с терминологией, введенной в гл. I9 шифрсистема Эль-Гамаля (X9K9Y9E9D) определяется следующим образом. Для нее
X = Ztpt Y = ZtpXZtp, К = {{p,cc,J3,a)\aa =Р(то&р)},
где р — достаточно большое простое число, a — порождающий элемент группы Z^7, a — целое число из интервала I < a < р — 2 . Ключ k = (р9 а9 JS9 а) представляется в виде открытого ключа къ = (p9a9f3) и секретного ключа кр = (а).
Правило зашифрования на ключе к определяется формулой
Ek(M) = (Cl9C2)9
где
C1 = аг (mod р)9 C2=M- /Г (mod р),
а г — случайно выбираемое число (рандомизатор) из интервала 0 < г < р — 2.
Правило расшифрования на ключе к определяется формулой
Dk(Cx,C2) = C2-(Crr1(Itiodp).
