Принципы построения асимметричных криптосистем. – ЧАСТЬ 1

Одним из важнейших вопросов в разработке криптографических систем с большим числом пользователей является задача защищенного распространения и смены ключей. Перехват ключа в процессе его передачи или смены, утечка информации о ключе от одной из сторон лишает секретности все сообщения, им зашифро­ванные. Сеть с S пользователями, где информацией потенциально обменивается «каждый с каждым», содержит ^(-S—1)/2 возможных связей и требует такого же количества защищенных каналов распространения ключей. Причем из работы Шеннона [60] следует, что в теоретически стойкой секретной системе ключи, передаваемые по этим каналам, будут иметь неприемлемо большой объем.

Сенсационной для своего времени оказалась статья «Новые направления в криптологии» Уитфрида Диффи и Мартина Хеллмана, показавших возмож­ность построения практически стойких криптосистем, не требующих пере­дачи ключей [61] (1976 г.). До этого момента традиционные методы крип­тографических преобразований относились к т.н. симметричным шифрам, где один и тот же ключ использовался для шифрования и дешифрования. Основное наблюдение, приведшее Диффи и Хеллмана к идее асимметрич­ной криптографии (или криптографии с открытым ключом) заключалось в следующем: «зашифровавший сообщение не обязательно должен быть спо­собен его расшифровать».

Теория асимметричных криптосистем использует понятие односторонней функции – некоторой легко вычислимой функции y=flx), для которой вычис­ление обратного значения x=f x{y), наоборот, практически неосуществимо. В качестве таковой была предложена функция дискретного возведения в степень /(jt)=a*(modр), где Х- целое число от 1 дор-1 включительно [61]. Вычисления производятся по модулю р, где р – очень большое простое число, a – целое (1<а<р), степени которого а, а2, . ., сГ1 равняются (в некотором порядке) 1, 2, …, р-1. Например, при р=1 можно выбрать а=3, поскольку а=3, а2=2, а3=6 , а4=4, а5=5 , а6=1. Такое а называют примитивным элементом конечного поля Галуа (см. раздел 2.3), причем известно, что оно всегда существует. Если^а* то естественно записать x=loga(y). Подобные функции называют дискретными логарифмами. Отыскать дискретный логарифм при большом/? – задача огром­ной вычислительной сложности.

Диффи и Хеллман предложили чрезвычайно простой способ использования односторонних функций для обмена секретными ключами между пользовате­лями сети по незащищенному каналу. Предположим, что всем пользователям известны а и р. Каждый из них случайным образом выбирает целое число X в интервале между 1 ир-1 и держит его в секрете. Затем вычисляет y=a*(modр) и помещает его в общедоступный открытый справочник.

Если пользователи i и j захотят установить секретную связь, пользователь / возьмет из справочника Y. и с помощью своего секретного значения X. вычислит Z.= (7.)*’=a^ (mod р). Аналогично пользователь j вычислит Z. Однако Z=I так что с этого момента пользователи i и j могут применять Zb качестве секрет­ного ключа в классической криптосистеме.

Если бы некто «умел» решать задачу вычисления дискретных логарифмов, он бы мог, взяв из справочника У. и У., решить уравнение Х.= loga(y) и вычислить ^..подобно пользователю /. По всей видимости, иного способа определить Zнет (хотя это и не доказано). Система открытого распространения ключей Диффи и Хеллмана (DH) и по сей день считается одной из самых стойких и удобных, а открытый справочник теперь должен содержать только S значений ключа «У».

Дальнейшее пояснение идей асимметричной криптографии предполагает ознакомленность читателя с некоторыми фактами из теории чисел.

1.                                                                                                                                                                                 Функция Эйлера ф(п) определяется как число положительных целых г, не превосходящих п и таких, что наибольший общий делитель НОД (/, п) = 1. Легко убедиться, что для пары простых чиселр и q: ф(п)={р-\ )(q-\). Тогда согласно теореме Эйлера о взаимно-простых числах,         l(mod п) для любых целых чисел п их таких, чтох<п. Например, 52= l(mod 6).

2.            Второй полезный факт восходит к Евклиду (около 300 г. до н.э.) Если е и т удовлетворяют условиям 0<е<т и НОД (т, ё)= 1, то существует единствен­ное d, такое что 0<d<m и de= l(mod т), причем d можно вычислить с помо­щью расширенного алгоритма Евклида для нахождения НОД (т, е).

2.1.ъ.2. Криптографическая система RSA. В 1978 г. Р. Ривест, Э. Шамир и Л. Адлеман в своей статье «Метод получения цифровых подписей и криптоси­стем с открытыми ключами» предложили важную разновидность односторон­них функций – функцию с потайным ходом RSA (данная аббревиатура образо­вана первыми буквами фамилий авторов).

Функция RSA с потайным ходом – это т.н. дискретное возведение в степень

где Х- положительное целое число, не превосходящее n=p q\

р и q – большие числа, такие, что функция Эйлера ф(п)=(р-\)^-1) имеет большой простой множитель;

Z={p, q, е) – «потайной ход»;

е – положительное целое, не превосходящее ф{п), наибольший общий дели­тель НОД (е, ф(п)) равен единице [61].

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

где d- единственное положительное целое, меньшее п и удовлетворяющее усло­вию de= 1 по модулю ф{п). То, что функция/’действительно является обратной к Xе по модулю п, следует из теоремы Эйлера, а ее показатель d при известном Z определяется с помощью алгоритма Евклида, который позволяет вычислить НОД (е, Ф(п)).

Приведем пример использования RSA для случая малых р и q:

Выберем два простых числа. Пусть р= 19, q~23.

Определяем n=p-q=437 и ф(п)=(р-1)(^-1)=396.

Находим число етакое, что НОД (е, ф(п))= 1,т.е. е=13 (при большихpnqмы искали бы его с помощью алгоритма Евклида).

функция шифрования: fz{x)=Xe{mod п). Например, при открытом сообще­нии .АМ23 криптограмма имеет вид: Y=fz(\23)=\23u(mod 437) = 386 (т.е., число 123 возводим в 13-ю степень и полученное произведение делим на 437. Остаток от деления равняется 386).

Определяем d из выражения de= l(mod ф{п)): d=6l, поскольку 13×61=193=2ф(п)+1.

Наконец, функция расшифровывания имеет вид: ^y^mod п). Действительно, 38661 (mod 437) = 123.

Очевидно, даже проверка этого результата требует выполнения громоздких вычислений. Легко представить себе, насколько сложно найти d при больших неизвестных р и q, подбираемых с тем, чтобы не предоставить никаких «заце­пок» для криптоаналитика, пользующегося известными алгоритмами фактори­зации (наибольший общий делитель чисел р-1 и q-1 выбирается небольшим’).

Стойкость криптосистемы RSA основана на допущении о том, что любой способ обращения функции fz эквивалентен разложению n=p q на множители. Некто, знающий п и е, имел бы исчерпывающую информацию о «потайном ходе» Z={p, q, е}, если бы разложил n=p q на множители (т.е. осуществил фак­торизацию п). Он так же легко расшифровал бы сообщение, как и законный по­лучатель.

Действительно ли разложение п на множители вычислительно неосуще­ствимо? Пока что это так – если длина выбранных р и q составляет около 100 де­сятичных знаков и если не произойдет революционного прорыва в математике Публикация Ривеста, Шамира и Адлмана вызвала огромный интерес к задачам разложения на множители, но это не дало ощутимых результатов за истекшие 30 лет. Лучшие известные алгоритмы решения задачи дискретных логарифмов (по модулю р) и лучшие алгоритмы разложения п на множители при р~п требуют приблизительно равного объема вычислений, так что функции RS А и DH с при­мерно одинаковым основанием называют «односторонними».

Естественно, RSA намного медленнее любой криптосистемы с секретным ключом. Например, одна из самых быстрых реализаций, предложенных Ому- рой, по скорости шифрования более чем в тысячу раз уступает DES.

Схема Диффи-Хеллмана, основанная на сложности проблемы вычисления дискретных логарифмов в простых конечных полях, стала первым практиче­ским методом распределения секретного ключа по незащищенному каналу. На этой же математической задаче построена и система шифрования Эль-Гамаля (1984 г.). Следующими по распространенности шифрами с открытым ключом являются криптосистемы Меркля-Хеллмана и Хора-Ривеста, основанные на односторонней функции, известной как «задача укладки ранца» [65].

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100