Алгоритмы и стандарты шифрования

🕛 20.09.2009, 14:14

В зависимости от используемых ключей шифрование условно можно разделить на следующие виды.
- Симметричное шифрование, при котором ключ для шифрования и дешифрования представляет собой один и тот же ключ (на обыденном уровне - просто пароль).
- Асимметричное шифрование: подразумевает использование двух различных ключей - открытого и закрытого. Открытый ключ, как правило, передается в открытом виде, закрытый же всегда держится в тайне.
Известны также и другие виды шифрования, такие, например, как тайнопись. Алгоритмы тайнописи по известным причинам не являются публичными: посторонним лицам неизвестен сам алгоритм шифрования; закон преобразования знают только отправитель и получатель сообщения. Одним из ярких примеров таких систем можно считать одноразовые блокноты. Именно одноразовые блокноты (One‑time Pad, или OTP) можно назвать единственной теоретически невзламываемой системой шифрования. Одноразовый блокнот представляет собой список чисел в случайном порядке, используемый для кодирования сообщения. Как это и следует из названия, OTP может быть использован только один раз. Одноразовые блокноты широко применяются в информационных средах с очень высоким уровнем безопасности (но только для коротких сообщений). Так, в Советском Союзе OTP использовался для связи разведчиков с Москвой.

Симметричное шифрование

Как было уже сказано выше, при симметричном шифровании для шифрования и дешифрования данных используется один и тот же ключ. Понятно, что ключ алгоритма должен сохраняться в секрете обеими сторонами. Говоря простым языком, в данном случае под ключом подразумевается пароль, который, разумеется, должен держаться в тайне.
Популярными алгоритмами симметричного шифрования являются:
- DES (значительно устарел) и TripleDES (3DES);
- AES (Rijndael);
- ГОСТ 28147‑89;
- Blowfish.
Основными параметрами алгоритмов симметричного шифрования можно считать:
- стойкость;
- длину ключа;
- количество раундов;
- длину обрабатываемого блока;
- сложность аппаратной/программной реализации.
Итак, начнем.
Data Encryption Standard (DES).Алгоритм Data Encryption Standard (DES) был разработан компанией IBM в начале 1970‑х гг. Национальный институт стандартов и технологий США (NIST) принял на вооружение алгоритм (публикация FIPS 46) для DES в 1977 году. Дальнейшей модификации алгоритм подвергался в 1983, 1988, 1993 и 1999 годах.
До недавнего времени DES был "стандартом США", поскольку правительство этой страны рекомендовало применять его для реализации различных систем шифрования данных. Однако несмотря на то что изначально DES планировалось использовать не более 10‑15 лет, попытки его замены начались только в 1997 году.
DES использует ключ длиной 56 бит. По сегодняшним меркам, такая длина ключа неприемлема. DES является блочным алгоритмом шифрования, обрабатывающим единовременно один 64‑битный блок открытого текста. В алгоритме DES выполняются 16 циклов шифрования с различным подключом в каждом из циклов. Ключ подвергается действию своего собственного алгоритма для образования 16 подключей (рис. 2.1).

Схема работы DES
Рассмотрим работу алгоритма подробнее. Входной блок данных, состоящий из 64 бит, преобразуется в выходной блок идентичной длины. Ключ шифрования должен быть известен как отправляющей, так и принимающей сторонам. В алгоритме широко используются перестановки битов текста.
Вводится функция F, которая работает с 32‑разрядными словами исходного текста ® и использует в качестве параметра 48‑разрядный ключ (J). Схема работы функции F показана на рис. 2.1. Сначала 32 входных разряда расширяются до 48, при этом некоторые разряды повторяются.
Для полученного 48‑разрядного кода и ключа выполняется операция сложения по модулю 2. Результирующий 48‑разрядный код преобразуется в 32‑разрядный с помощью S‑матриц.
Исходный 48‑разрядный код делится на восемь групп по шесть разрядов. Первый и последний разряды в группе используются в качестве адреса строки, а средние четыре разряда - в качестве адреса столбца. В результате каждые шесть бит кода преобразуются в четыре бита, а весь 48‑разрядный код - в 32‑разрядный (для этого нужно восемь S‑матриц). Существуют разработки, позволяющие выполнять шифрование в рамках стандарта DES аппаратным образом, что обеспечивает довольно высокое быстродействие.
Чтобы все‑таки разобраться во всех тонкостях алгоритма DES, будет вполне уместно привести описание так называемой сети Фейштеля (иногда называют сетью Файстеля), которая и стоит в основе DES.
В 1973 году Хорст Фейштель (Horst Feistel) в журнале Scientific American опубликовал статью "Cryptography and Computer Privacy", в которой раскрыл некоторые важные аспекты шифрования, а также ввел конструкцию, названную впоследствии сетью Фейштеля. Эта схема была использована в проекте Lucifer фирмы IBM, над которым работали Фейштель и Дон Копперсмит (Don Coppersmith). Данный проект был скорее экспериментальным, но стал базисом для Data Encryption Standard (DES). Итеративная структура алгоритма позволяла упростить его реализацию в аппаратных средах.
Уместно заметить, что следующие блочные шифры как раз таки используют классическую или модифицированную сеть Фейштеля в своей основе: Blowfish, Camellia, CAST, DES, FEAL, ГОСТ 28147‑89, KASUMI, LOKI97, Lucifer, MacGuffin, MARS, MAGENTA, MISTY1, RC2, RC5, RC6, Skipjack, TEA, Triple DES, Twofish, XTEA.
TripleDES (3DES).Очевидная нестойкость DES стала причиной поисков некой альтернативы. В 1992 году исследования показали, что DES можно использовать трижды для обеспечения более мощного шифрования. Так появился тройной DES (3DES). Тройной DES используется либо с двумя, либо с тремя ключами. Используемый при этом ключ обеспечивает большую мощность в сравнении с обычным DES.
Advanced Encrypt Standard (AES).Вскоре после выхода DES обнаружилась очевидная слабость алгоритма. Необходимость в принятии нового стандарта была более чем явной: небольшая длина ключа DES (56 бит) позволяла применить метод грубой силы против этого алгоритма. Кроме того, архитектура DES была ориентирована на аппаратную реализацию, и программная реализация алгоритма на платформах с ограниченными ресурсами не давала необходимого быстродействия. Модификация TDES обладала достаточной длиной ключа, но при этом была еще медленнее. TDES не просуществовал столь долго, чтобы можно было говорить о том, что алгоритм стоек и надежен. Ему на смену, как и следовало ожидать, пришел более стойкий и надежный алгоритм - AES, который, между прочим, был выбран в результате конкурса и принят в качестве американского стандарта шифрования правительством США. Немного о самом конкурсе.
2 января 1997 года NIST (Национальный Институт Стандартов и Технологий) объявляет о намерении найти замену DES, являвшемуся американским стандартом с 1977 года. NIST принял достаточное количество предложений от заинтересованных сторон о том, каким образом следует выбирать алгоритм. Активный отклик со стороны открытого криптографического сообщества привел к объявлению конкурса 12 сентября 1997 года. Алгоритм могла предложить практически любая организация или группа исследователей. Минимальные требования к новому стандарту были следующими:
- это должен быть блочный шифр;
- длина блока должна составлять 128 бит;
- алгоритм должен работать с ключами длиной 128, 192 и 256 бит;
- использовать операции, легко реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах);
- ориентироваться на 32‑разрядные процессоры;
- не усложнять без необходимости структуру шифра, чтобы все заинтересованные стороны были в состоянии самостоятельно провести независимый криптоанализ алгоритма и убедиться, что в нем не заложено каких‑либо недокументированных возможностей.
Кроме всего вышеперечисленного, алгоритм, который претендует на то, чтобы стать стандартом, должен распространяться по всему миру без платы за пользование патентом.
20 августа 1998 года на первой конференции AES был объявлен список из 15 кандидатов, а именно: CAST‑256, CRYPTON, DEAL, DFC, E2, FROG, HPC, LOKI97, MAGENTA, MARS, RC6, Rijndael, SAFER+, Serpent и Twofish.
Понятное дело, что в последующих обсуждениях эти алгоритмы подвергались самому тщательному анализу, причем исследовались не только криптографические свойства, такие как стойкость к известным атакам и отсутствие слабых ключей, но и практические аспекты реализации. Так, особое внимание при выборе алгоритма было направлено на оптимизацию скорости выполнения кода на различных архитектурах (от ПК до смарт‑карт и аппаратных реализаций), возможность оптимизации размера кода, возможность распараллеливания.
В марте 1999 года прошла вторая конференция AES, а в августе 1999 года были объявлены пять финалистов, среди которых оказались: MARS, RC6, Rijndael, Serpent и Twofish. Все они были разработаны авторитетными криптографами, имеющими мировое признание. На 3‑й конференции AES в апреле 2000 года все авторы представили свои алгоритмы.
В Нью‑Йорке 13 и 14 апреля 2000 года, незадолго до завершения второго этапа, прошла третья конференция AES. Двухдневная конференция была разделена на восемь сессий по четыре в день. На сессиях первого дня обсуждались вопросы, связанные с программируемыми матрицами (FGPA), проводилась оценка реализации алгоритмов на различных платформах, в том числе PA‑RISC, IA‑64, Alpha, высокоуровневых смарт‑картах и сигнальных процессорах, сравнивалась производительность претендентов на стандарт, анализировалось количество раундов в алгоритмах‑кандидатах. На второй день был проанализирован Rijndael с сокращенным количеством раундов и показана его слабость в этом случае, обсуждался вопрос об интегрировании в окончательный стандарт всех пяти алгоритмов‑претендентов, еще раз тестировались все алгоритмы. В конце второго дня была проведена презентация, на которой претенденты рассказывали о своих алгоритмах, их достоинствах и недостатках. О Rijndael как о лидере рассказал Винсент Риджмен (Vincent Rijmen), заявивший о надежности защиты, высокой общей производительности и простоте архитектуры своего кандидата.
2 октября 2000 года было объявлено, что победителем конкурса стал алгоритм Rijndael, и началась процедура стандартизации. 28 февраля 2001 года был опубликован проект, а 26 ноября 2001 года AES был принят как FIPS 197.
Строго говоря, AES и Rijndael не одно и то же, так как Rijndael поддерживает широкий диапазон длин ключей и блоков.
Особо следует подчеркнуть тот факт, что алгоритм Rijndael не похож на большинство известных алгоритмов симметричного шифрования, в основе которых лежит сеть Фейштеля. Напомним нашим читателям, что особенность сети Фейштеля состоит в том, что входное значение разбивается на два и более субблоков, часть из которых в каждом раунде обрабатывается по определенному закону, после чего накладывается на необрабатываемые субблоки.
В отличие от ГОСТ 28147, который будет рассмотрен ниже, алгоритм Rijndael представляет блок данных в виде двухмерного байтового массива размером 4 х 4, 4 х 6 или 4 х 8 (допускается использование нескольких фиксированных размеров шифруемого блока информации). Все операции выполняются с отдельными байтами массива, а также с независимыми столбцами и строками.
Алгоритм Rijndael предусматривает выполнение четырех последовательных преобразований.
1. BS (ByteSub) - табличная замена каждого байта массива.

Табличная замена каждого байта массива
2. SR (ShiftRow) - сдвиг строк массива. При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное количество байт, зависящее от размера массива. Например, для массива размером 4 х 4 строки 2, 3 и 4 сдвигаются на 1, 2 и 3 байта соответственно (рис. 2.3).
3. Следующим идет MC (MixColumn) - операция над независимыми столбцами массива, когда каждый столбец по определенному правилу умножается на фиксированную матрицу C(X) (рис. 2.4).
4. Заключительный этап - AK (AddRoundKey) - добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования (рис. 2.5).

Сдвиг строк массива

Операция MixColumn

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

Последовательность раундов Rijndael
В алгоритме Rijndael количество раундов шифрования ® переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).
Почему же Rijndael стал новым стандартом шифрования, опередившим другие алгоритмы? Прежде всего, он обеспечивает высокую скорость шифрования, причем на всех платформах: как при программной, так и при аппаратной реализации. Алгоритм отличается удачным механизмом распараллеливания вычислений по сравнению с другими алгоритмами, представленными на конкурс. Кроме того, требования к ресурсам для его работы минимальны, что важно при его использовании в устройствах, обладающих ограниченными вычислительными возможностями.
При всех преимуществах и оригинальности алгоритма AES можно было бы считать абсолютом надежности и стойкости, но, как оно всегда и бывает, совершенных продуктов нет.
26 мая 2006 года на конференции Quo Vadis IV Николя Тадеуш Куртуа (польский криптограф, проживающий во Франции) представил практическое доказательство существования алгебраических атак, оптимизированных против шифра AES‑Rijndael. За полтора часа на своем ноутбуке он осуществил демо‑взлом всего лишь по нескольким шифртекстам близкого аналога Rijndael. Хотя это был только модельный шифр, он являлся таким же стойким, в него не было добавлено существенных слабостей, он имел такие же хорошие диффузионные характеристики и устойчивость ко всем известным до этого видам криптоанализа. Единственным отличием были лишь измененные в рамках модели алгебраических атак параметры S‑блоков и уменьшенное для наглядности количество раундов. Однако этого было достаточно, чтобы убедить скептиков в реальности алгебраических атак и несовершенстве даже такого, казалось бы, совершенного метода шифрования.
ГОСТ 28147.Следующим алгоритмом симметричного шифрования, который мы рассмотрим, станет ГОСТ 28147‑89. Это советский и российский стандарт симметричного шифрования, введенный 1 июля 1990 года. Стандарт обязателен для организаций, предприятий и учреждений, применяющих криптографическую защиту данных, хранимых и передаваемых в сетях ЭВМ, в отдельных вычислительных комплексах или ЭВМ.
Алгоритм был разработан в бывшем Главном Управлении КГБ СССР или в одном из секретных НИИ в его системе. Первоначально имел гриф (ОВ или СС - точно неизвестно), затем гриф последовательно снижался и к моменту официального проведения алгоритма через Госстандарт СССР в 1989 году был снят. Алгоритм остался ДСП (как известно, ДСП не считается грифом). В 1989 году стал официальным стандартом СССР, а позже, после распада СССР, федеральным стандартом Российской Федерации.
С момента опубликования ГОСТа на нем стоял ограничительный гриф "Для служебного пользования", и формально шифр был объявлен "полностью открытым" только в мае 1994 года. По известным причинам, история создания шифра и критерии его проектирования до сих пор неизвестны.
ГОСТ 28147‑89 представляет собой блочный шифр с 256‑битным ключом и 32 циклами преобразования, оперирующий 64‑битными блоками. Основа алгоритма - уже известная нам сеть Фейштеля. Основным режимом шифрования по ГОСТ 28147‑89 является режим простой замены (определены также более сложные режимы гаммирования и гаммирования с обратной связью). Рассмотрим механизм работы алгоритма подробнее.
При работе ГОСТ 28147‑89 информация шифруется блоками по 64 бита (такие алгоритмы называются блочными), которые затем разбиваются на два субблока по 32 бита (N1 и N2). После завершения обработки субблока N1 его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, то есть применяется логическая операция XOR - исключающее ИЛИ), а затем субблоки меняются местами. Данное преобразование выполняется определенное количество раз (раундов): 16 или 32 в зависимости от режима работы алгоритма. В каждом раунде выполняются две операции.

Преобразование выполняется определенное количество раз
Первая операция подразумевает наложение ключа. Содержимое субблока N1 складывается по модулю 2 с 32‑битной частью ключа Kx. Полный ключ шифрования представляется в виде конкатенации 32‑битных подключей: K0, K1, K2, K3, K4, K5, K6, K7. В процессе шифрования используется один из этих подключей, в зависимости от номера раунда и режима работы алгоритма.
Вторая операция осуществляет табличную замену. После наложения ключа субблок N1 разбивается на восемь частей по четыре бита, значение каждой из которых заменяется в соответствии с таблицей замены для данной части субблока. После этого выполняется побитовый циклический сдвиг субблока влево на 11 бит.
Алгоритм, определяемый ГОСТ 28147‑89, может работать в четырех режимах:
- простой замены;
- гаммирования;
- гаммирования с обратной связью;
- генерации имитоприставок.
В генерации имитоприставок используется одно и то же описанное выше шифрующее преобразование, но, поскольку назначение режимов различно, осуществляется это преобразование в каждом из них по‑разному.
В режиме простой замены для зашифровки каждого 64‑битного блока информации выполняются 32 описанных выше раунда. Каждый из блоков шифруется независимо от другого, то есть результат шифрования каждого блока зависит только от его содержимого (соответствующего блока исходного текста). При наличии нескольких одинаковых блоков исходного (открытого) текста соответствующие им блоки шифртекста тоже будут одинаковы, что дает дополнительную полезную информацию для пытающегося вскрыть шифр криптоаналитика. Поэтому данный режим применяется в основном для шифрования самих ключей шифрования (очень часто реализуются многоключевые схемы, в которых по ряду соображений ключи шифруются друг на друге). Для шифрования собственно информации предназначены два других режима работы: гаммирования и гаммирования с обратной связью.
В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бита. Гамма шифра - это специальная последовательность, которая получается в результате определенных операций с регистрами N1 и N2 .
1. В регистры N1 и N2 записывается их начальное заполнение - 64‑битная величина, называемая синхропосылкой.
2. Выполняется зашифровка содержимого регистров N1 и N2 (в данном случае синхропосылки) в режиме простой замены.
3. Содержимое регистра N1 складывается по модулю (232- 1) с константой C1, равной 224 + 216 + 28 + 24, а результат сложения записывается в регистр N1.
4. Содержимое регистра N2 складывается по модулю 232 с константой C2, равной 224 + 216 + 28 + 1, а результат сложения записывается в регистр N2.
5. Содержимое регистров N1 и N2 подается на выход в качестве 64‑битного блока гаммы шифра (в данном случае N1 и N2 образуют первый блок гаммы).
Если необходим следующий блок гаммы (то есть нужно продолжить зашифровку или расшифровку), выполняется возврат к операции 2.
Для расшифровки гамма вырабатывается аналогичным образом, а затем к битам зашифрованного текста и гаммы снова применяется операция XOR.
Для выработки нужной для расшифровки гаммы шифра у пользователя, расшифровывающего криптограмму, должны быть тот же ключ и то же значение синхропосылки, которые применялись при зашифровке информации. В противном случае получить исходный текст из зашифрованного не удастся.
В большинстве реализаций алгоритма ГОСТ 28147‑89 синхропосылка несекретна, однако есть системы, где синхропосылка является таким же секретным элементом, как и ключ шифрования. Для таких систем эффективная длина ключа алгоритма (256 бит) увеличивается еще на 64 бит секретной синхропосылки, которую также можно рассматривать как ключевой элемент.
В режиме гаммирования с обратной связью для заполнения регистров N1 и N2 , начиная со второго блока, используется не предыдущий блок гаммы, а результат зашифровки предыдущего блока открытого текста. Первый же блок в данном режиме генерируется полностью аналогично предыдущему.
Рассматривая режим генерации имитоприставок, следует определить понятие предмета генерации. Имитоприставка - это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выполняются следующие операции: первый 64‑битный блок массива информации, для которого вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.
Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64‑битное содержимое регистров N1 и N2 или его часть и называется имитоприставкой. Размер имитоприставки выбирается исходя из требуемой достоверности сообщений: при длине имитоприставки r бит вероятность, что изменение сообщения останется незамеченным, равна 2^.Чаще всего используется 32‑битная имитоприставка, то есть половина содержимого регистров. Этого достаточно, поскольку, как любая контрольная сумма, имитоприставка предназначена прежде всего для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы - в первую очередь электронная цифровая подпись.
При обмене информацией имитоприставка служит своего рода дополнительным средством контроля. Она вычисляется для открытого текста при зашифровке какой‑либо информации и посылается вместе с шифртекстом. После расшифровки вычисляется новое значение имитоприставки, которое сравнивается с присланной. Если значения не совпадают, значит, шифртекст был искажен при передаче или при расшифровке использовались неверные ключи. Особенно полезна имитоприставка для проверки правильности расшифровки ключевой информации при использовании многоключевых схем.
Алгоритм ГОСТ 28147‑89 считается достаточно сильным - в настоящее время для его раскрытия не существует более эффективных методов, чем упомянутый выше Brute Force. Высокая стойкость алгоритма достигается в первую очередь за счет большой длины ключа, равной 256 бит. К тому же при использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость ГОСТ 28147‑89 уже при 32 раундах можно считать более чем достаточной, и это притом, что полный эффект рассеивания входных данных достигается уже после восьми раундов.
На сегодняшний день алгоритм ГОСТ 28147‑89 полностью удовлетворяет всем требованиям криптографии и обладает теми же достоинствами, что и другие алгоритмы, но лишен их недостатков. К очевидным достоинствам этого алгоритма можно отнести:
- эффективность реализации и, соответственно, высокое быстродействие на современных компьютерах;
- бесперспективность силовой атаки (XSL‑атаки в учет не берутся, так как их эффективность на данный момент полностью не доказана).
Однако же, как оно всегда и бывает, алгоритм не лишен недостатков: тривиально доказывается, что у ГОСТа существуют "слабые" ключи и S‑блоки, но в стандарте не описываются критерии выбора и отсева "слабых". Кроме того, стандарт не специфицирует алгоритм генерации S‑блоков (таблицы замен). С одной стороны, это может являться дополнительной секретной информацией (помимо ключа), а с другой - поднимает ряд проблем: нельзя определить криптостойкость алгоритма, не зная заранее таблицы замен; реализации алгоритма от различных производителей могут использовать разные таблицы замен и могут быть несовместимы между собой.
Кратко рассмотрим некоторые другие алгоритмы симметричного шифрования.
Blowfish.Blowfish представляет собой 64‑битный блочный шифр, разработанный Шнайером (Schneier) в 1993 году. Этот шифр, как и многие другие, основан на алгоритме сети Фейштеля. Отдельный раунд шифрования данного алгоритма состоит из зависимой от ключа перестановки и зависимой от ключа с данными замены. Все операции основаны на операциях XOR и прибавлениях к 32‑битным словам (XORs and additions on 32‑bit words). Ключ имеет переменную длину (максимальная длина 448 бит) и используется для генерации нескольких подключевых массивов (subkey arrays). Шифр был создан специально для 32‑битных машин и существенно быстрее ранее рассмотренного нами алгоритма DES.
IDEA(International Data Encryption Algorithm) был разработан К. Лейем (Lai) и Д. Месси (Massey) в конце 1980‑х годов. Это шифр, состоящий из 64‑битных повторяющихся блоков со 128‑битным ключом и восемью раундами. Следует отметить, что, в отличие от ранее нами рассмотренных алгоритмов шифрования, IDEA не основан на сети Фейштеля, хотя процесс дешифрования аналогичен процессу шифрования. IDEA был сконструирован с учетом его легкого воплощения как программно, так и аппаратно. Ко всему прочему безопасность IDEA основывается на использовании трех несовместимых типов арифметических операций над 16‑битными словами.
Один из принципов создания IDEA заключался в том, чтобы максимально затруднить его дифференциальный криптоанализ, что в настоящее время выражается отсутствием алгебраически слабых мест алгоритма. Даже не смотря на то что найденный неким "Daemen" обширный класс (251) слабых ключей теоретически может скомпрометировать алгоритм, IDEA остается достаточно надежным алгоритмом, так как существует 2128 возможных вариантов ключей, что делает его взлом трудно осуществимым.
RC5представляет собой довольно быстрый блочный шифр, разработанный Ривестом (Ronald Linn Rivest) специально для «RSA Data Security». Этот алгоритм параметричен, то есть его блок, длинна ключа и количество проходов (раундов) переменны.
Размер блока может равняться 32, 64 или 128 бит. Количество проходов может варьироваться от 0 до 2048 бит. Параметричность подобного рода делает RC5 необычайно гибким и эффективным алгоритмом в своем классе.
Исключительная простота RC5 делает его простым в использовании. RC5 с размером блока в 64 бита и 12 или более проходами обеспечивает хорошую стойкость против дифференциального и линейного криптоанализов.

Асимметричное шифрование

В отличие от алгоритмов симметричного шифрования, где используется один и тот же ключ как для расшифровки, так и для зашифровки, алгоритмы асимметричного шифрования используют открытый (для зашифровки) и закрытый, или секретный (для расшифровки), ключи.
На практике один ключ называют секретным, а другой - открытым. Секретный ключ содержится в тайне владельцем пары ключей. Открытый ключ передается публично в открытом виде. Следует отметить тот факт, что если у абонента имеется один из пары ключей, то другой ключ вычислить невозможно.
Открытый ключ вычисляется из секретного: kl = f(k2). Асимметричные алгоритмы шифрования основаны на применении однонаправленных функций. Согласно определению функция y = f(x) является однонаправленной, если ее можно легко вычислить для всех возможных вариантов x, а для большинства возможных значений y достаточно сложно вычислить такое значение x, при котором y = f(x) .
Примером однонаправленной функции может служить умножение двух больших чисел: N = S х G. Само по себе, с точки зрения математики, такое умножение представляет собой простую операцию. Однако обратная операция (разложение N на два больших множителя), называемая также факторизацией, по современным временным оценкам представляет собой достаточно сложную математическую задачу.
Ну что ж, рассмотрим некоторые из алгоритмов асимметричного шифрования.
Алгоритм Диффи-Хеллмана.В 1976 году Уитфилд Диффи (Whitfield Diffie) и Мартин Хеллман (Martin Hellman) разработали свою систему шифрования с открытым ключом. Система Диффи-Хеллмана разрабатывалась для решения проблемы распространения ключей при использовании систем шифрования с секретными ключами. Идея заключалась в том, чтобы применять безопасный метод согласования секретного ключа без передачи ключа каким‑либо другим способом. Следовательно, необходимо было найти безопасный способ получения секретного ключа с помощью того же метода связи, для которого разрабатывалась защита. Суть алгоритма Диффи-Хеллмана заключается в следующем. Предположим, что двум точкам (S1 и S2) требуется установить между собой безопасное соединение, для которого необходимо согласовать ключ шифрования.
- S1 и S2 принимают к использованию два больших целых числа a и b, причем 1 < a < b.
- S1 выбирает случайное число i и вычисляет I = ai × mod b. S1 передает I абоненту S2.
- S2 выбирает случайное число j и вычисляет J = aj × mod b. S2 передает J абоненту S1 .
- S1 вычисляет k1 = Ji × mod b.
- S2 вычисляет k2 = Ij × mod b.
Имеем k1 = k2 = ai × j х mod b, следовательно, k1 и k2 являются секретными ключами, предназначенными для использования при передаче других данных.
Даже если допустить, что злоумышленнику каким‑то образом удастся прослушать передаваемый трафик, то ему будут известны a, b, I и J. Тем не менее остаются в секрете i и j. Уровень безопасности системы зависит от сложности нахождения i при известном I = ai × mod b. Эта задача называется задачей дискретного логарифмирования и считается очень сложной (то есть с помощью современного вычислительного оборудования ее решить практически невозможно), если числа очень велики. Следовательно, a и b необходимо выбирать очень тщательно. Например, оба числа b и (b - 1)/2 должны быть простыми и иметь длину не менее 512 бит. Рекомендуемая длина чисел составляет 1024 бита.
Алгоритм RSAбыл разработан в 1978 году тремя соавторами и получил свое название по первым буквам фамилий разработчиков (Rivest, Shamir, Adleman). В основе стойкости алгоритма стоит сложность факторизации больших чисел и вычисления дискретных логарифмов. Основной параметр алгоритма RSA - модуль системы N, по которому проводятся все вычисления в системе, а N = R х S (R и S - секретные случайные простые большие числа, обычно одинаковой размерности).
Секретный ключ k2 выбирается случайным образом и должен соответствовать следующим условиям: 1 < k2 < F(N) и НОД (k2, F(N))= 1, где НОД - наибольший общий делитель. Иными словами, k1 должен быть взаимно простым со значением функции Эйлера F(N) , причем последнее равно количеству положительных целых чисел в диапазоне от 1 до N, взаимно простых с N, и вычисляется как F(N) = (R - 1) × (S - 1) .
Открытый ключ kl вычисляется из соотношения (k2 х kl) = 1 × mod F(N). Для этого используется обобщенный алгоритм Евклида (алгоритм вычисления наибольшего общего делителя). Зашифровка блока данных M по алгоритму RSA выполняется следующим образом: C = Mkl × mod N. Поскольку в реальной криптосистеме с использованием RSA число k1 весьма велико (в настоящее время его размерность может доходить до 2048 бит), прямое вычисление Mk1 нереально. Для его получения применяется комбинация многократного возведения M в квадрат с перемножением результатов. Обращение данной функции при больших размерностях неосуществимо; иными словами, невозможно найти M по известным C, N и kl. Однако, имея секретный ключ k2, при помощи несложных преобразований можно вычислить M = Ck2 × mod N. Очевидно, что, помимо собственно секретного ключа, необходимо обеспечивать секретность параметров R и S. Если злоумышленник добудет их значения, то сможет вычислить и секретный ключ k2.
В настоящее время криптосистема RSA применяется в самых различных продуктах, на различных платформах и во многих отраслях. Достаточно вспомнить ее использование в операционных системах Microsoft, Apple, Sun и Novell, чтобы представить всю "грандиозность" RSA. В аппаратной составляющей алгоритм RSA широко используется в защищенных телефонах, на сетевых платах Ethernet, на смарт‑картах, в криптографическом оборудовании Zaxus (Racal). Ко всему прочему, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Интернет, в том числе S/MIME, SSL и S/WAN, а также используется во многих правительственных учреждениях, государственных лабораториях и университетах. На осень 2000 года технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями.
Алгоритм Эль‑Гамаля.Эль‑Гамаль (Taher Elgamal) разработал вариант системы Диффи-Хеллмана. Он усовершенствовал этот алгоритм и получил один алгоритм для шифрования и один для обеспечения аутентификации. Алгоритм Эль‑Гамаля не был запатентован (в отличие от RSA) и таким образом стал более дешевой альтернативой, так как не требовалась уплата лицензионных взносов. Поскольку этот алгоритм базируется на системе Диффи-Хеллмана, то его стойкость обеспечивается сложностью решения все той же задачи дискретного логарифмирования.
Алгоритм цифровой подписи (Digital Signature Algorithm).Алгоритм DSA был разработан правительством США как стандартный алгоритм для цифровых подписей (см. разд. 2.3). Данный алгоритм базируется на системе Эль‑Гамаля, но позволяет осуществлять только аутентификацию. Конфиденциальность этим алгоритмом не обеспечивается.
Шифрование с использованием эллиптических кривых.Эллиптические кривые были предложены для использования в системах шифрования в 1985 году. Системы шифрования с использованием эллиптических кривых (ECC) основываются на отличной от факторизации или дискретного логарифмирования математической задаче. Данная задача заключается в следующем: имея две точки A и B на эллиптической кривой, такие что A = kB, очень трудно определить целое число k. Несмотря на некоторую «экзотичность», использование ECC перед алгоритмом RSA или Диффи-Хеллмана в ряде случаев дает существенное преимущество. Самым большим из таких преимуществ является то, что ключи могут иметь существенно меньшую длину (по причине сложности задачи). И это без потери стойкости! Как результат, вычисления производятся быстрее с сохранением того же уровня безопасности. Так, безопасность, обеспечиваемая 160‑битным ключом ECC, может быть приравнена к 1024‑битному ключу RSA.

Достоинства и недостатки симметричного и асимметричного методов шифрования

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