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

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

2) мультипликативная группа ОР{2т)* конечного поля

ОР(2т) характеристики 2 ;

3)группа точек эллиптической кривой над конечным по­

лем.

Вероятностный характер шифрования можно отнести к достоинствам системы Эль-Гамаля, так как схемы вероятно­ стного шифрования обладают, как правило, большей стойко­ стью по сравнению со схемами с детерминированным про­ цессом шифрования. Недостатком системы является удвоение длины открытого текста при шифровании.

§11.3. Шифрсистема Мак-Элиса

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

В системе Мак-Элиса параметрами системы, общими для всех абонентов, являются целые числа к , п и ^. Для получе­ ния открытого и соответствующего секретного ключа каждо­ му из абонентов системы следует осуществить следующую последовательность действий:

1) выбрать порождающую матрицу С = Скхп двоичного

-линейного кода, исправляющего / ошибок, для кото­ рого известен эффективный алгоритм декодирования;

2) случайно выбрать двоичную невырожденную матрицу

=^кхк »

3)случайно выбрать подстановочную матрицу Р - Рпхп;

4) вычислить произведение матриц С х= 8 О Р .

321

[лава 11

Открытым ключом является пара (Сх, ( ) , секретным —

тройка (5, С , Р ) .
Для того чтобы зашифровать сообщение			М , предназна­
ченное для абонента А , абоненту В следует			выполнить сле­
дующие действия:
1 )	представить М в виде двоичного вектора длины к ;
2)	выбрать случайный бинарный вектор ошибок 2 дли­
ны п , содержащий не более / единиц;
3)	вычислить бинарный вектор С = М	Оа + 2 и		напра­
вить его абоненту А.
Получив сообщение С, абонент А		вычисляет		вектор
Сх = С	Р ~ \ с помощью которого, используя алгоритм деко­

дирования кода с порождающей матрицей О, получает далее векторы М х и М = М х -8 ~х.

Чтобы убедиться в корректности приведенного алгоритма расшифрования, достаточно заметить, что

С, = С - Р ~ Х= ( М - С а + 2 ) - Р ~ х =

= ( М -8 - С - Р + 2 ) - Р~х = = ( М - 8 ) в + 2 - Р ~ х,

где 7, ■Р 1 — вектор, содержащий не более I единиц. Поэтому алгоритм декодирования кода с порождающей матрицей С декодирует С в М х= М • 8 .

В качестве кода, исправляющего ошибки в системе МакЭлиса, можно использовать код Гоппы (см., например, [Пит64]). Известно, что для любого неприводимого полинома

%(х) степени I над полем ОР(2т) существует бинарный

код Гоппы длины п —2т и размерности к > п - т1 , исправ­ ляющий до / ошибок включительно, для которого имеется 322

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

эффективный алгоритм декодирования. В настоящее время не известны эффективные алгоритмы дешифрования системы Мак-Элиса, использующей код Гоппы, при правильном выбо­ ре параметров системы.

Вместе с тем рекомендуемые параметры для этой систе­ мы [Меп97 ] — « = 1024, / = 38, А: >644 — приводят к

тому, что открытый ключ имеет размер около 2 19 бит, а дли­ на сообщения увеличивается при шифровании примерно в 1,6 раза, в связи с чем данная система не получила широкого рас­ пространения.

§11.4. Шифрсистемы на основе “проблемы рюкзака"

“Проблема рюкзака” (или “ранца”) может быть сформу­ лирована следующим образом. Пусть задано множество нату­ ральных чисел А = {а1?а 2,...,а„} и натуральное число 5 \

Требуется установить, имеется ли такое подмножество мно­ жества А , сумма элементов которого была бы равна 5 . Эк­ вивалентной является следующая формулировка: существует ли такой набор чисел х7е { 0,1}, /< « , для которого

п

/=1

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

“Проблема рюкзака” является весьма сложной, ее реше­ ние с полиномиальной сложностью в настоящее время не из­ вестно.

323

/ лава 11

Идея построения системы шифрования на основе ‘"про­ блемы рюкзака” заключается в выделении некоторого под­ класса задач об укладке рюкзака, решаемых сравнительно легко, и “маскировки” задач этого класса (с помощью некото­ рого преобразования параметров) под общий случай. Пара­ метры подкласса определяют секретный ключ, а параметры модифицированной задачи — открытый ключ. В качестве легко решаемой задачи Р. Меркль и М. Хеллман в 1978 г. [Мег81] предложили задачу об укладке “супервозрастающе­ го” рюкзака. Изложим ее суть.

Назовем супервозрастающей последовательность нату­ ральных чисел (6,, Ь2 Ъп), обладающую свойством

	/-1
Ъ1 >	, 2 < / < п .
	7=1

Можно убедиться в том, что “проблема рюкзака” для су­ первозрастающей последовательности может быть решена с помощью процедуры, состоящей в выполнении следующих

шагов:	Положить / = п .
1.
2.	Если	/ > 1,	то положить	х 1 равным	1 и 5 равным
5 - Ъ1, если		8 >Ъп	и положить	х г равным	0 в противном
случае.	Положить г равным / -1
3.				и возвратиться к шагу 2.

В системе, основанной на проблеме рюкзака, величина п является параметром системы.

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

324

Системы с открытыми ключами
1.	Выбирает	супервозрастающую последовательность
		п
(ЪХ,Ъ2	) и модуль т , такой, что т > У^ Ъ 1 .
		/=1
2.	Выбирает	случайное число IV, I <РГ < т —1,	такое,
что Н ОД (1Г,т) = 1.
3.	Выбирает	случайную перестановку к	чисел
{1,2 ,...,и}.
4.	Вычисляет	= Ж • 6^ /) тоб/я для / = 1, л .

Открытым ключом является набор (а ,,а 2,...,аЛ), секрет­

ным ключом — набор (7Г,т,1У,(Ъх,...,ЪпУ) .

Чтобы зашифровать сообщение М 9 предназначенное для абонента А , абонент В осуществляет следующие шаги с по­ мощью открытого ключа (а 15а 2,...,а„) абонента А :

1. Представляет М в виде бинарной последовательности

М = М хМ 2...М п длины п .

п

2. Вычисляет С = ^ /М 1 •а1 и направляет его к А .

/=1

Абонент А , получив С , вычисляет Н = С тюб т , а затем, решая “проблему рюкзака” для супервозрастающей последовательности, находит числа е {0,1}, такие, что

1=1

Биты последовательности М 1 вычисляются по формуле

= г *(,)> 1= Ъп.

Корректность проведенной процедуры расшифрования вытекает из следующих рассуждений. Поскольку

325

Iлава 11

Н ш К - ' - С ш Ц Г - ' ^ М г ч ш ^ М , - К и)(тойт)

1=1

1=1

п

и 0 < Н <т,то Н = ^ М Г Ъя^ , и, следовательно, алгоритм

/=1

решения “проблемы рюкзака” действительно находит биты открытого текста, переставленные в соответствии с переста­ новкой п .

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

чисел их,т], ч то отношение щ / щ близко к отношению и/т

(где и = И/'~1 тодт,	а IV, т являются частью секретного
ключа). Кроме того,	числа Вг = щ • а1(тос!т), 1 < / < п , обра­

зуют супервозрастающую последовательность. Эта последо­ вательность затем используется противником вместо (&1 для дешифрования сообщения.

Контрольные вопросы

1.В чем состоят преимущества систем с открытыми ключа­ ми перед симметричными шифрсистемами?

2.Сложностью какой математической задачи определяется стойкость системы К8А?

3.К какому типу принадлежит схема шифрования, исполь­ зуемая в системе Эль-Гамаля? В чем ее преимущества?

4.Чем вызваны трудности в практической реализации сис­ темы Мак-Элиса?

5.Придумайте алгоритм вычисления аа(шос1 «), имеющий сложность 0 (1п п).

6. Постройте пример шифра Эль-Гамаля для р = 127. За­ шифруйте и расшифруйте выбранное Вами т < 126.

326

Глава 12

Идентификация

Все протоколы идентификации включают двух участни­

ков:

1) А — доказывающего — участника, проходящего иден­ тификацию,

и

2) В — проверяющего — участника, проверяющего ау­ тентичность доказывающего.

Целью протокола является проверка того, что проверяе­ мым действительно является^.

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

Протоколы идентификации могут быть разбиты на три большие категории в зависимости от того, на чем основана идентификация.

1. Протоколы, основанные на известной обеим сторонам информации. Такой информацией могут быть пароли, личные идентификационные номера (РШ от английского

регзопа1 Шеп1фсаИоп питЪег\ секретные или открытые ключи, знание которых демонстрируется во время вы­ полнения протокола.

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

3.Протоколы, использующие физические параметры, со­ ставляющие неотъемлемую принадлежность доказываю­ щего. В качестве таковых могут выступать подписи, отпе­

327

Глава 12

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

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

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

§12.1. Фиксированные пароли (слабая идентификация)

Обычная парольная схема основывается на не зависящих от времени паролях и устроена следующим образом. Для ка­ ждого пользователя имеется пароль, обычно представляющий собой последовательность длиной от 6 до 10 знаков алфавита, которую пользователь в состоянии запомнить. Эта последова­ тельность выступает в качестве общего секрета пользователя и системы. Для того чтобы получить доступ к системному ресурсу (база данных, принтер и т.д.), пользователь пред­ ставляет свой идентификатор и пароль и прямо или косвенно определяет необходимый ресурс. При этом идентификатор пользователя выступает как заявка на идентификацию, а па­ роль — как подтверждение этой заявки. Различные пароль­

328

Ибентификация'

ные схемы отличаются между собой по методам хранения парольной информации в системе и методам ее проверки.

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

Остановимся подробнее на методах хранения паролей в системе. Наиболее очевидным из них является хранение па­ ролей в открытом виде в файле, защищенном от записи и счи­ тывания системными средствами. При обращении пользова­ теля система сравнивает введенный пароль с паролем данного пользователя, хранимым в файле. Недостаток этого метода состоит в том, что пароли не защищены от привилегирован­ ных пользователей системы.

Для устранения этого недостатка используются зашиф­ рованные файлы паролей пользователей. При этом может использоваться либо непосредственное зашифрование паро­ лей с помощью того или иного криптографического алгорит­ ма, либо вычисление значения хэш-функции (см. гл. 13) паро­ ля. Заметим, что использование шифрования перед передачей пароля по незащищенному каналу связи хотя и защищает сам пароль, но не защищает от возможности вхождения против­ ника в систему путем навязывания перехваченного зашифро­ ванного пароля.

Поскольку степень защиты указанной системы определя­ ется сложностью перебора паролей, то на практике использу­ ется целый ряд приемов для усложнения противнику этой процедуры.

Правила составления паролей

Типичным требованием, предъявляемым при составлении паролей, является ограничение на минимальную длину паро­ лей. Примером может служить требование, чтобы пароль

329

I лава 12

имел длину не менее 9 букв или цифр. Другими требованиями могут быть наличие в пароле хотя бы одного символа из каж­ дого регистра (верхнего, числового, не алфавитно-цифрового и т. д.), а также требование, чтобы пароль не мог быть словом из имеющегося словаря или частью идентификационной ин­ формации доказывающего.

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

Усложнение процедуры проверки паролей

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

“Подсоленные” пароли

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

330