Асимметричные криптосистемы 2 страница

.

Согласно теореме 1.3

.

На основании этого, и следуя теоремe 1.6, имеем:

. ■

На основании вышесказанного можно сделать следующие выводы:

1) протокол криптосистемы RSA шифрует и расшифровывает информацию корректно;

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

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

С другой стороны односторонняя функция , также применяемая в RSA, обладает «секретом», позволяющим легко вычислить обратную функцию , если известно разложение на множители числа . Действительно, это легко сделать, вычислив сначала , а затем . Таким образом, параметры и являются «секретом» или, как еще говорят, «лазейкой».

Иногда рекомендуется выбирать открытый ключ одинаковым для всех абонентов сети, например =3. Это обеспечивает увеличение скорости шифрования.

Рассмотренная криптосистема обладает одним существенным недостатком. Рассмотрим схему на рис.1.1. Злоумышленник, под видом абонента , либо самостоятельно инициирует обмен информацией между абонентами и , либо «встраивается» между абонентами в процессе обмена ими информацией. Абонент шифрует сообщение для передачи его абоненту используя при этом «подставленные» злоумышленником параметры . Перехваченная криптограмма расшифровывается злоумышленником с помощью его закрытого ключа . Полученный открытый текст злоумышленник снова зашифровывает используя параметры абонента . Абонент расшифровывает полученную криптограмму, используя закрытый ключ . Затем абонент формирует ответное сообщение, которое аналогично перехватывается злоумышленником. Таким образом, злоумышленник, находясь «посередине» между абонентами читает передаваемые ими сообщения. Избежать такой ситуации можно за счет использования более сложных протоколов, например следующего.

Рис. 1.1. Схема «активный злоумышленник посередине»

Пусть абонент хочет передать сообщение абоненту . Сначала абонент вычисляет:

.

Затем абонент вычисляет

,

и передает его абоненту . Абонент получив криптограмму последовательно вычисляет

и .

При таком протоколе злоумышленник уже не может реализовать схему перехвата сообщений, представленную на рис.1.1.

Рассмотрим пример шифрования при помощи алгоритма криптосистемы RSA. Пусть открытое сообщение, подлежащее шифрованию =15. Сеть состоит из двух абонентов. Параметры второго абонента, которому адресуется шифрованное сообщение следующие: =3, =11, 33, =3 (число 3 взаимно простое с 20). Закрытый ключ, определенный с помощью алгоритма Евклида =7 (). Шифруем открытый текст:

.

Расшифруем сообщение:

.

1.4. Криптосистема Шамира

Криптосистема, предложенная Ади Шамиром, была первой криптосистемой с открытым ключом.

Определение 1.9. Криптосистема Шамира формально определяется следующим образом [6-9]:

, (1.15)

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

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

.

Эти числа абонент держит в секрете и передавать не будет. Абонент тоже выбирает два числа и , такие что

.

и держит их в секрете.

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

Дадим описание трехступенчатого протокола (см. рис. 1.2.). Абонент вычисляет число

.

Абонент , получив , вычисляет

и передает его абоненту . Абонент вычисляет следующее число

и передает его абоненту . Абонент , получив , вычисляет

,

которое является передаваемым исходным сообщением.

□ Для доказательства корректности протокола заметим, что любое целое число может быть представлено в виде:

, где .

На основании теоремы 1.4 (теоремы Ферма) можно записать:

.

Тогда:

. ■

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

Рис. 1.2. Схема алгоритма Шамира

Рассмотрим пример шифрования при помощи алгоритма Шамира. Пусть открытое сообщение, подлежащее шифрованию =10. Сеть состоит из двух абонентов. Первый абонент выбирает 23, и параметры =19, =7 (). Аналогично второй абонент выбирает параметры =9, =5 (). Протокол Шамира:

.

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

1.5. Криптосистема Эль Гамаля

Определение 1.10. Криптосистема с открытым ключом Эль Гамаля формально определяется следующим образом [6-9]:

, (1.16)

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

Для всей группы абонентов сети выбирается некоторое большое простое число и число . Выбор числа может оказаться трудной задачей при произвольно заданном числе , т.к. это связано с разложением на простые множители числа . Дело в том, что для обеспечения высокой стойкости алгоритма шифрования число должно обязательно содержать большой простой множитель, в противном случае с помощью алгоритма Полига-Хеллмана быстро вычисляется дискретный логарифм. В связи с этим простое число выбирается таким, чтобы выполнялось равенство:

, (1.17)

где - простое число. Тогда в качестве можно взять любое число, для которого справедливы неравенства:

, . (1.18)

Числа и передаются абонентам сети в открытом виде. Затем каждый абонент сети выбирает секретный ключ , , удовлетворяющее условию: , и вычисляет открытый ключ:

, . (1.19)

Пусть абонент хочет передать абоненту сообщение , при этом необходимо выполнение условия: .

Шифрование исходного сообщения происходит следующим образом. Абонент формирует случайное число , причем (эту операцию выполняют все абоненты сети), и вычисляет числа

, (1.20)

, (1.21)

а затем передает пару абоненту .

Абонент получив криптограмму вычисляет исходный текст

. (1.22)

□ Подставим в (1.22) выражение (1.21) и получим

.

Теперь в полученное выражение подставим (1.19) и (1.20)

По теореме 1.4 (теореме Ферма) , тогда

.■

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

Особенностью криптосистемы Эль Гамаля является то, что объем передаваемой криптограммы в два раза превышает объем исходного сообщения. Это объясняется тем, что для вычисления криптограммы требуется выполнить операции (1.18) и (1.19). Следствием этого является большее, по сравнению с алгоритмом RSA, время шифрования и больший объем вычислений.

Рассмотрим пример шифрования при помощи алгоритма Эль Гамаля. Пусть требуется передать исходный открытый текст 15 от абонента к абоненту . Выберем в соответствии с (1.17) параметр 23 ( 11). Определим параметр . Возьмем 3, проверим: и, значит, такое число не подходит. Возьмем 5, проверим: , такое число подходит. Таким образом, параметрами криптосистемы являются 23 и 5. Пусть абонент выбрал закрытый ключ 13 и вычислил открытый ключ .

Абонент выбирает случайное число 7 и вычисляет

,

.

Абонент пересылает абоненту зашифрованное сообщение , которое абонент расшифровывает

.

1.6. Криптосистема Рабина

Определение 1.11. Криптосистема с открытым ключом Рабина формально определяется следующим образом [6]:

, (1.23)

где - множество открытых текстов, - множество криптограмм, - некоторый открытый текст, - некоторая криптограмма, - RSA-модуль (является открытым ключом криптосистемы), где и - секретные ключи криптосистемы, - функция шифрования, - функция расшифрования.

В криптосистеме Рабина используется RSA-модуль , в котором числа и сравнимы с числом 3 по модулю 4:

, ,

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

Шифрование осуществляется по формуле

,

причем должно выполняться условие: .

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

, ;

,

.

На основе полученных значений вычисляются четыре возможных корня из по модулю :

,

,

,

,

где и .

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

1.7. Криптосистемы на эллиптических кривых

Криптосистемы на эллиптических кривых – одно из новых направлений в криптографии. Эллиптические кривые давно изучаются математикой, но их использование в криптографии впервые было предложено Коблицом и Миллером в 1985 году. Прошедшие два с половиной десятилетия подтвердили эффективность этих криптосистем и привели к открытию множества их реализации. Основным достоинством криптосистем на эллиптических кривых является их более высокая стойкость по сравнению с традиционными асимметричными криптосистемами, при равных вычислительных затратах.

Детальное изучение эллиптических кривых требует знаний высшей алгебры, в особенности алгебраической геометрии. Рассмотрим математические основы теории эллиптических кривых, достаточных для понимания принципов построения и работы криптосистем [6-9].

Дата добавления: 2014-12-26