Шифр ЭльГамаля

Шифр ЭльГамаля

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

Отправитель сообщения А и получатель В знают лишь р. А генерирует случайное число X из интервала (1,р). В генерирует случайное число Y из того же интервала.

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

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

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

Шифр ЭльГамаля

Криптографическая система с открытым ключом Ривеста — Шамира — Алдемана (RSA)

Криптографическая система с открытым ключом Ривеста — Шамира — Алдемана (RSA)

Криптографическая система с открытым ключом Ривеста — Шамира — Алдемана (RSA). Она основана на трудности разложения очень больших целых чисел на простые сомножители. Алгоритм ее работы предусматривает следующие действия:

1.    Источник сообщения выбирает два очень больших простых числа p и q и вычисляет два произведения , а также некоторое целое число d, взаимно простое с m. На основе этой тройки он вычисляет е

2.    Число е сохраняется в секрете, a d и e сообщаются всем абонентам как открытый ключ шифрования (публикуются в справочнике вроде телефонного).

3.    Сообщение С, длина которого, определяемого по длине выражаемого им целого числа, находится в интервале [1;n], преобразуется в шифрограмму по правилу

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

Авторы RSA в примере из своей первой публикации использовали d=9007 и n= 1143816257578888676692357799761466120102182967212423625625618429357 069352457338978305971235639587050589 8907514 7599290026879543541. Но для иллюстрации работы алгоритма шифрации RSA  рассматривается более простой пример на малых простых числах р= 211 и q= 223. В этом случае n = 47053 и m = 46620. При выборе открытого ключа шифрования d= 6813 вычисляется секретный ключ расшифровки е= 19837. Теперь, взяв за сообщение название метода RSA, его следует перевести в число. Для этого будем буквам латинского алфавита ставить в соответствие их порядковые номера. Поэтому R:= 18, S:= 19, А:= 1. На двоичное представление каждой буквы отводится по 5 бит, как в коде Бодо.

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

Криптостойкость системы RSA основана на том, что m не может быть просто вычислена без знания простых сомножителей p и q, а нахождение этих сомножителей из n считалось трудно разрешимой задачей. Однако недавние работы по разложению больших чисел на сомножители показали, что для этого могут быть использованы разные и даже совершенно неожиданные средства. Сначала авторы RSA предлагали выбрать простые числа р и q случайно, по 50 десятичных знаков каждое. Считалось, что такие большие числа очень трудно разложить на простые сомножители при криптоанализе. Оказалось, что это не так.

Теперь разработчикам криптографических алгоритмов с открытым ключом на базе RSA приходится избегать применения разложимых чисел длиной менее 200 десятичных разрядов. Самые последние публикации предлагают для этого применять числа в 250 и даже 300 десятичных разрядов. А так как для шифрования каждого блока информации приходится соответствующее число возводить в колоссально большую степень по модулю n, то для современных компьютеров это задача на грани возможного. Поэтому для практической реализации шифрования RSA приходится разрабатывать специальные процессоры. Чрезвычайно слабое быстродействие криптографических систем на основе RSA лишь ограничивает область применения, но вовсе не перечеркивает их ценность.

Традиционные (одноключевые) криптосистемы

Традиционные (одноключевые) криптосистемы

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

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

Для шифрации с открытым ключом применяются криптопреобразования на основе односторонних функций с потайным ходом. Это такие функции F с параметром z, что для данного z можно найти алгоритмы Ez и Dz, позволяющие легко вычислить значение Fz (x).

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

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

В настоящее время два метода шифрования с открытым ключом получили признание и закреплены в стандартах. Национальный институт стандартов и технологий США NIST принял стандарт MD 20899, основанный на алгоритме ЭльГамаля, а на основе алгоритма RSA приняты стандарты ISO/IEC/DIS 9594-8 международной организацией по стандартизации и Х.509 международным комитетом по связи.

Яндекс.Метрика