Криптографическая система с открытым ключом Ривеста — Шамира — Алдемана (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 международным комитетом по связи.

Алгоритм ГОСТ 28147—89

Алгоритм ГОСТ 28147—89

Алгоритм ГОСТ 28147—89 предусматривает процесс формирования имитовставки. Этот процесс одинаков для любого из режимов шифрования данных. Имитовставка Ир — криптографическая контрольная комбинация, предназначенная для защиты шифрограммы от изменений (случайных, вызванных помехами, или преднамеренных, обусловленных несанкционированным вмешательством). Ир представляет собой блок из р двоичных символов, который вырабатывается либо перед шифрованием всего сообщения, либо параллельно с шифрованием по блокам. Первые блоки открытых данных, которые участвуют в выработке имитовставки, могут содержать служебную информацию (например, адресную часть, время, синхропосылку) и не зашифровываться.

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

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

Сформированное таким образом 64-разрядное число суммируется по модулю 2 с третьим блоком открытых данных С3 и т. д. Последний блок CN, при необходимости дополненный до полного 64-разрядного блока нулями, суммируется по модулю 2 с результатом работы на N — 1 шаге, после чего зашифровывается в режиме простой замены по первым 16 циклам работы алгоритма. Из полученного 64-разрядного числа выбирается отрезок Ир длиной р бит.

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

Использование алгоритмом ГОСТ 28147 — 89 имитовставки повышает его стойкость к подделкам и искажениям.

Типичные и стандартизованные алгоритмы симметричного шифрования

Типичные и стандартизованные алгоритмы симметричного шифрования

Типичные и стандартизованные алгоритмы симметричного шифрования (одноключевые) — это DES (Data Encryption Stan dard), служащий стандартом шифрования США, европейским стандарт IDEA (International Data Encryption Algorithm) и российский стандарт ГОСТ 28147 — 89.

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

Блочные симметричные алгоритмы допускают как аппаратную, так и программную реализацию. Они осуществляют криптографическое преобразование информации для хранения на любых носителях (бумажных, магнитных и других машинных), для передачи данных в сетях ЭВМ. Алгоритм по ГОСТ 28147 — 89 не накладывает ограничений на степень секретности защищаемой информации.

Алгоритмы DES, IDEA и ГОСТ 28147 — 89 предусматривают несколько режимов работы, но во всех режимах для шифрации используют секретный ключ, единый для шифрации и расшифровки. Отечественный алгоритм, регламентируемый ГОСТом, работает с ключом длиной 256 бит, образованным конкатенацией (сцеплением) восьми 32-разрядных двоичных чисел.

Поступающая на блок подстановки 32-разрядная последовательность двоичных символов разбивается на восемь последовательно идущих четырехразрядных групп, каждая из которых преобразуется в новую четырехразрядную группу соответствующим узлом замены. Каждый узел замены — это таблица из шестнадцати целых чисел в диапазоне 0... 15. Входная последовательность определяет адрес строки в таблице. По этому адресу находится число, являющееся выходной последовательностью. Конкатенация трансформированных таким образом в результате выполнения операции подстановки четырехразрядных выходных групп символов представляет собой 32-разрядные группы символов, сдвинутые на 11 двоичных разрядов влево. Таблица блока подстановки содержит ключевые элементы, общие для сети шифрующего и расшифровывающего алгоритмов.

Схема вычисления функции шифрования представлена на рисунке ниже:

Стандарты симметричных криптосистем

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

Метод шифрования — гаммированием

Метод шифрования — гаммированием

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

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

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

Потенциальный недостаток этого шифра

Потенциальный недостаток этого шифра

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

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

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

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

Страница 2 из 612345...Последняя »
Яндекс.Метрика