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 и вычисляет

,

.

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

.