Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии

Системы с открытыми ключами

сделать легче, чем обеспечить рассылку и сохранность сек­ ретных ключей.

Как мы уже отмечали ранее, системы шифрования с от­ крытыми ключами осуществляют блочное шифрование, по­ этому открытый текст перед зашифрованием разбивается на блоки выбранного размера, которые последовательно преоб­ разуются таким же образом, как это происходит при исполь­ зовании блочного шифра в режиме простой замены (см. § 8.3).

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

Рассмотрим конкретные примеры систем шифрования с открытыми ключами.

§ 11.1. Шифрсистема К8А

Система Я8А была предложена в 1978 г. [Клу78] и в на­ стоящее время является наиболее распространенной системой шифрования с открытым ключом. Напомним ее определение, приведенное в гл. 2 (определение 4).

Пусть п — # — целое число, представимое в виде про­

изведения двух больших простых чисел р, с] . Выберем числа

е и с/ из условия

е-с! = 1(шо&(р{п)),

(1)

где ф(п) = (р —1) • (д -1 ) — значение функции Эйлера от

числа п. Пусть к = (п,р^,е,с1) — выбранный ключ, со­

стоящий из открытого ключа къ = (п,е) и секретного ключа

311

/лава 17

кр = (п,р,д,с1) . Пусть М — блок открытого текста и С —

соответствующий блок шифрованного текста. Тогда правила зашифрования и расшифрования определяются формулами:

С = Е к( М ) = М е(тоАп), Э к(С) = С а( т о й п ) .

(2)

Заметим, что в соответствии с (2) Ик(С) = М .Это выте­

кает из следующих рассуждений. Для любого целого числа М и любого простого р справедливо сравнение

	М р = М (ш оё р ) .		(3)
	В самом деле, (3) равносильно сравнению
	М р - М = 0(шо<1 р)
или сравнению
	М ( М р~' -1) = 0(тос1 р ).		(4)
	Если НОД ( М , р ) = р , то р делит М ,	и поэтому
М	= 0(шо(1 р ) , откуда следует (4). Если же Н О Д (М ,р) —\,
то,	согласно малой теореме Ферма (см. Приложение		3),
М р~х = 1(тос1 р ) , откуда также следует (4).
	Согласно (1), существует целое число г ,	такое,	что
е	= г • ср(п) + 1. Отсюда и из (3) получаем следующую це­
почку равенств и сравнений:
	С а = ( М еУ = М Ы = М Г(р{п)+х = м г{р~т ~])+ =
	= М гр{я~Х) *м~гц^ х = ( М РУ (Я~Х) - М ' Г(1+Г+Х г		(5)
	3 м г(ч~]) - М - гч+г+{ = М{тоА р).

312

Системы с открытыми ключами

Аналогично можно показать, что

с Л = м ш оа ц .

(б>

Поскольку р и ^ — разные простые числа, то на осно­ вании известных свойств сравнений из (5), (6) получаем:

С* =Мшос1и.

Отсюда и следует корректность определения (2).

Для того чтобы лучше представить себе технические де­ тали, возникающие при зашифровании и расшифровании, приведем пример работы с К8А.

Пример
Зашифруем		аббревиатуру К8А,		используя /7 = 17,
<7 = 31.	Для	этого	вычислим	п = р^ = 527	и
ср(п) = ( р	-	-1) = 480 .	Выберем,	далее, в качестве	е

число, взаимно простое с (р{п), например е = 7. С помощью алгоритма Евклида найдем целые числа и и V, удовлетво­ ряющие соотношению е • и + (р{п) • V = 1:

480 = 7-68 + 4,

7 = 4-1 + 3,

4= 3-1 + 1,

1= 4 —31 = 4 —(7 —4-1)-1 =

=4-2-7 -1 = (480-7-68)-2-7-1 =

=480-2-7-137,

у = 2, и = - 137.

313

I лава 11

Поскольку —137 = 343(шо<1480), то <7 = 343. Проверка:

7 • 343 = 2401 = 1(тос1480).

Теперь представим данное сообщение в виде последова­ тельности чисел, содержащихся в интервале 0,526 . Для этого буквы и А закодируем пятимерными двоичными векто­ рами, воспользовавшись двоичной записью их порядковых номеров в английском алфавите:

К = 18 = (10010), 5 = 19 = (10011), А = 1 = (00001).

Тогда К8А = (100101001100001). Укладываясь в заданный интервал 0,526, получаем следующее представление:

К8А = (100101001),(100001) = (М, = 297, М 2 = 33).

Далее последовательно шифруем М х и М 2:

С, = Ек(М,) = М хе = 2977 (той 527) = 474.

При этом мы воспользовались тем, что

2977 = ((2972 )3 297)(шоё527) = = ((2003 (то<1527)297)(тоё527),

С2 = Е к{ М г) = М 2е = 337(тос1527) = 407.

В итоге получаем шифртекст: у х= 474, у 2 —407.

При расшифровании нужно выполнить следующую по­ следовательность действий. Во-первых, вычислить

314

Системы с открытыми ключами

Д (С 1) = (С,)343(шос1527).

Отметим, что при возведении в степень удобно восполь­ зоваться тем, что 343 = 256 + 64 + 16 + 4 + 2 + 1. На основа­ нии этого представления получаем:

4742 яе174(шос1527), 4744(шоё527) е=237, 4748(тос1 527) е=307,474|6(тод527) ее443, 47432(тос1527) ее205, 474м(той 527) ее392, 474128(тос1527) = 307, 474256(тос1527) ее443,

в силу чего

474 343(тос1527) г Э (443 • 392 • 443 • 237 • 174 • 474)(тос1527) ее297.

Аналогично

407343(то<1527) = 33.

Возвращаясь к буквенной записи, получаем после рас­ шифрования К8А.

Проанализируем вопрос о с то й к о сти системы К8А. Нетрудно показать, что сложность нахождения секретно­

го ключа системы К8А определяется сложностью разложения числа п на простые множители. В связи с этим нужно выби­ рать числа р и ^ таким образом, чтобы задача разложения

числа п была достаточно сложна в вычислительном плане. Для этого рекомендуются следующие требования:

315

I лава 11

1) числа р и # должны быть достаточно большими, не

слишком сильно отличаться друг от друга и в то же время быть не слишком близкими друг другу;

2) числа р и # должны быть такими, чтобы наибольший

общий делитель чисел р —1 и # —1 был небольшим; жела­

тельно, чтобы НОД(р -1 , д -1 ) = 2 ;

3) р и д должны быть сильно простыми числами (силь­

но простым называется такое простое число г , что г + 1

имеет большой простой делитель, г —1	имеет большой про­
стой делитель 5, такой, что число 5 - 1	также обладает доста­
точно большим простым делителем).

Вслучае когда не выполнено хотя бы одно из указанных условий, имеются эффективные алгоритмы разложения п на простые множители (см. [Сал96], [Неч99]).

Внастоящее время самые большие простые числа, вида

п— # , которые удается разложить на множители извест­

ными методами, содержат в своей записи 140 десятичных знаков. Поэтому, согласно указанным рекомендациям, числа р и д в системе К.8А должны содержать не менее 100 деся­ тичных знаков.

Следует подчеркнуть необходимость соблюдения осто­ рожности в выборе модуля Я8А (числа п ) для каждого из корреспондентов сети. В связи с этим можно сказать следую­ щее.

Читатель может самостоятельно убедиться в том, что, зная одну из трех величин: /?, # или ср(п), можно легко най­ ти секретный ключ К8А. Известно также, что, зная секретную экспоненту расшифрования с/, можно легко разложить мо­ дуль п на множители. В этом случае удается построить веро­ ятностный алгоритм разложения п . Отсюда следует, что ка­ ждый корреспондент сети, в которой для шифрования исполь­ зуется система Я8А, должен иметь свой уникальный модуль.

316

системы с открытыми ключами

В самом деле, если в сети используется единый для всех модуль п , то такая организация связи не обеспечивает кон­ фиденциальности, несмотря на то что базовая система Я8А может быть стойкой. Выражаясь другими словами, говорят о несостоятельности протокола с общим модулем. Несостоя­ тельность следует из того, что знание произвольной пары экспонент (е19с!{) позволяет, как было отмечено, разложить

п на множители. Поэтому любой корреспондент данной сети имеет возможность найти секретный ключ любого другого корреспондента. Более того, это можно сделать даже без раз­ ложения п на множители [Сал96].

Как отмечалось ранее, системы шифрования с открытыми ключами работают сравнительно медленно. Для повышения скорости шифрования Я8А на практике используют малую экспоненту зашифрования.

Если выбрать число е небольшим или таким, чтобы в его двоичной записи было мало единиц, то процедуру шифрова­ ния можно значительно ускорить. Например, выбрав е = 3 (при этом ни р —1 , ни # - 1 не должны делиться на 3), мы

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

е = 216 4-1 = 65537 — число, двоичная запись которого со­ держит только две 1, мы сможем реализовать шифрование с помощью 16 возведений в квадрат по модулю п и одного пе­ ремножения. Если экспонента е выбирается случайно, то реализация шифрования по алгоритму Я8А потребует 5 воз­ ведений в квадрат по модулю п и в среднем х/2 умножений по тому же модулю, где 5 — длина двоичной записи числа п . Вместе с тем выбор небольшой экспоненты е может при­ вести к негативным последствиям. Дело в том, что у несколь­ ких корреспондентов могут оказаться одинаковые экспоненты

е .

317

Глава 11

Пусть, например, три корреспондента имеют попарно взаимно простые модули п}, п 2, п 3 и общую экспоненту

е = 3. Если еще один пользователь посылает им некое цирку­

лярное сообщение	М , то криптоаналитик противника может
получить в свое	распоряжение три шифрованных текста
у 1 = М 3(тойП'),	I = 1,2,3. Далее он может найти решение у

системы сравнений

у = У^тойщ),

<у = у 2(тойп2), у = у г(то&пг),

лежащее в интервале 0 < у < щ *п2 • пъ. По китайской теореме об остатках (см. Приложение 3) такое решение единственно, а так как М ъ < щ •п2 • л3, то у = М 3. Само М можно найти,

вычисляя кубический корень: М = \[у .

Отметим, что выбор малой экспоненты расшифрования с1 также нежелателен в связи с возможностью определения

с1 простым перебором. Известно также, что если с! <л[п , то экспоненту с1 легко найти, используя непрерывные дроби.

§11.2. Шифрсистема Эль-Гамаля

Шифрсистема Эль-Гамаля была предложена в 1985 г. [Е1085] и является фактически одним из вариантов метода выработки открытых ключей Диффи-Хеллмана (который бу­ дет рассмотрен далее). Криптографическая стойкость данной системы основана на сложности проблемы логарифмирования в мультипликативной группе конечного простого поля.

318

системы с открытыми ключами

В соответствии с терминологией, введенной в гл. 2, шиф­ рсистема Эль-Гамаля ( Х , К , У , Е , 0 ) определяется следую­ щим образом. Для нее

Х = ? р, У = Г р х Г р, К = { ( р , а , р , а ) \ а а = Р( т о й р ) } ,

где р — достаточно большое простое число, а — порож­ дающий элемент группы %*р , а — целое число из интервала 1 < а < р —2 . Ключ к = (/?, а , /?, а) представляется в виде открытого ключа къ= ( р 9а,/3) и секретного ключа кр = (а ).

Правило зашифрования на ключе к определяется форму­

лой

Ек( М ) = (СРС2),

где

С, = а г(тод. р \ С2 = М • /Зг(той р ) ,

а г — случайно выбираемое число (рандомизатор) из интер­ вала 0 < г < р —2 .

Правило расшифрования на ключе к определяется фор­ мулой

Д (С 1,С2) = С2-(СГГ1(шос1/7).

Несложно проверить, что такое определение корректно, то есть что выполняется равенство й к{Ек{М)) = М при лю­

бых к в К и М € X .

Введение в правило зашифрования рандомизатора г де­ лает шифр Эль-Гамаля шифром многозначной замены (см. гл. 5). В связи со случайным характером выбора параметра г подобную схему шифрования называют еще схемой вероят­ ностного шифрования. Для нее открытый текст и ключ не определяют шифртекст однозначно.

319

	Iлава 11
Для выработки открытого и секретного ключей каждый
из абонентов системы осуществляет следующие операции:
1) выбирает большое простое число	р и некоторый по­
рождающий элемент а группы 2 ^;
2) случайно выбирает целое число а,	\ < а< р —2 ,и вы­

числяет (3 = а а(тоб р ) ;

3) публикует открытый ключ (р ,а ,/? ), оставляя в секре­

те число а .

Следует отметить, что в приведенной системе необходи­ мо использовать различные значения рандомизатора г для зашифрования различных открытых текстов М и М \ В самом деле, в противном случае соответствующие шифртек-

сты (С],С2) и (С],С2) оказываются связанными соотноше­ нием С2 -(С2)~1 = М -(Л / ’)~1 и М 1 может быть легко вы­

числен, если известен М .

Как уже отмечалось, стойкость системы Эль-Гамаля оп­ ределяется сложностью решения задачи дискретного лога­

рифмирования в X* . В настоящее время эта задача практиче­ ски нереализуема для значений р , содержащих не менее 150

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

Система Эль-Гамаля может быть обобщена для примене­ ния в любой конечной циклической группе С . Криптогра­ фическая стойкость такой обобщенной схемы определяется сложностью задачи логарифмирования в группе С . При этом групповая операция в С должна быть легко реализуемой. В качестве С чаще всего выбираются следующие три группы:

1 ) мультипликативная группа Х*р целых чисел по модулю

простого числа р\

320