Криптосистемы открытого шифрования

Пример 2. Установим р=3, q=7. Тогда n=р·q=21.

Выбираем d как 5. Из формулы (e·5) mod 12=1 вычисляем e=17. Открытый ключ 17, 21, секретный - 5, 21. Зашифруем последовательность «2345»:

C(2)= 2¹⁷ mod 21 =11

C(3)= 3¹⁷ mod 21= 12

C(4)= 4¹⁷ mod 21= 16

C(5)= 5¹⁷ mod 21= 17

Криптотекст - 11 12 16 17.

Проверим расшифровкой: 

M(2)= 11⁵ mod 21= 2

M(3)= 12⁵ mod 21= 3

M(4)= 16⁵ mod 21= 4

M(5)= 17⁵ mod 21= 5

Как видим, результат совпал.

С момента своего создания RSA постоянно  подвергалась атакам типа Brute-force attack (атака  методом грубой силы, т. е. перебором). Криптостойкость RSA основывается на том  предположении, что исключительно  трудно, если вообще реально, определить закрытый ключ из открытого.

Компания RSA регулярно проводит конкурсы на взлом собственных (и не только собственных) шифров. Предыдущие конкурсы выиграла организация Distributed.net, являющаяся Интернет - сообществом добровольцев.

Участники Distributed.net загружают к  себе на ПК небольшую программу - клиент, которая подсоединяется к центральному серверу и получает кусочек данных для вычислений. Затем все данные загружаются на центральный сервер, и клиент получает следующий блок исходной информации. И так происходит до тех пор, пока все комбинации не будут перебраны. Пользователи, участники системы, объединяются в команды, а на сайте ведется рейтинг как команд, так и стран.

Например, участвующей в конкурсе по взлому RC5-64 (блочный шифр компании RSA, использующий ключ длиной 64 бита) организации Distributed.net удалось осуществить взлом  через пять лет (1757 дней) работы. За это  время в проекте участвовали 327 856 пользователей и было перебрано 15 268 315 356 922 380 288 вариантов ключа. Выяснилось, что была (не без юмора) зашифрована  фраза «some things are better left unread» («некоторые вещи лучше оставлять непрочтенными»).

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

Криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема была предложена Тахером Эль-Гамалем в 1984 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию.

Генерация ключей

Генерируется случайное  простое число  P длины  n битов.

Выбирается произвольное целое число    , являющееся первообразным корнем по модулю P.

Выбирается случайное целое число  x такое, что

Вычисляется

Открытым ключом является тройка              , закрытым ключом — число x.

Шифрование

Сообщение  M шифруется следующим образом:

1. Выбирается сессионный ключ — случайное целое число k такое, что
2. Вычисляются числа                             и
3. Пара чисел            является шифротекстом.

Расшифрование

Зная закрытый ключ x, исходное сообщение можно вычислить из шифротекста (a, b) по формуле:

При этом нетрудно проверить, что                                                  и поэтому 

Для практических вычислений больше подходит следующая формула:

.

 

 

 

 

 

 

 

 

 

 

 

Рис. 2 Схема шифрования Эль-Гамаля

 

Пример 1.

Шифрование 

1. Допустим что нужно зашифровать сообщение M = 5.
2. Произведем генерацию ключей:

• пусть                           . Выберем             - случайное целое число  ;

такое, что ;          

• вычислим ;
• итак, открытым является тройка                             , а закрытым ключом является число ;

3. Выбираем случайное целое число k такое, что 1 < k < (p−1).                   Пусть k = 9.

Вычисляем число  .

Вычисляем число .

Полученная пара                     является шифротекстом.

Расшифрование

1. Необходимо получить сообщение   M = 5 по известному шифротексту и закрытому ключу ;
2. Вычисляем M по формуле:
3. Получили исходное сообщение .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Эллиптические кривые - математический объект, который  может определен над любым  полем (конечным, действительным, рациональным или комплексным). В криптографии обычно используются конечные поля. Эллиптическая  кривая есть множество точек (x,y), удовлетворяющее следующему уравнению:

 

y² = x³ + ax + b,

 

Для точек на кривой довольно легко вводится операция сложения, которая играет ту же роль, что и операция умножения  в криптосистемах RSA и Эль-Гамаля.

В реальных криптосистемах на базе эллиптических  уравнений используется уравнение

 

y² = x³ + ax + b mod p,

 

где р - простое.

Проблема  дискретного логарифма на эллиптической  кривой состоит в следующем: дана точка G на эллиптической кривой порядка r (количество точек на кривой) и другая точка Y на этой же кривой. Нужно найти единственную точку x такую, что Y = xG.

 

 

 

 

 

 

 

Библиографический список

 

1. Аветисян, Д.О. Проблемы информационного поиска: Эффективность, автоматическое кодирование, поисковые стратегии / Д. О. Аветисян. - М.: Финансы и статистика, 1981. - 208 с.
2. Аршинов, М.Н. Коды и математика / М.Н. Аршинов.- М.: Наука, 1983. - 231 с.
3. Герасименко, В.А. Защита информации в автоматизированных системах обработки данных / В.А. Герасименко.- М.: Энергоатомиздат, 1994.
4. Расторгуев, С.П. Программные методы защиты информации в компьютерах и сетях / С. П. Расторгуев. -М.: Яхтсмен. - 1993. - 188 с.
5. Спесивцев, А.В. Защита информации в персональных ЭВМ / А.В. Спесивцев. - М.: Радио и связь, МП "ВЕСТА", 1978.
6. Шеннон, К. Работы по теории информации и кибернетике / К. Шеннон. - М.: Иностранная литература, 1963.