Первоначальный вариант алгоритма IDEA появился в 1990 г. Разработчики алгоритма, Ксуеджа Лай (Xuejia Lai) и Джеймс Мэсси (James Massey) из Швейцарского института ETH Zurich, дали ему название PES (Proposed Encryption Standard - предлагаемый стандарт шифрования), поскольку данный алгоритм был предложен на замену стандарта DES. Стоит отметить, что институт ETH Zurich и профессор Джеймс Мэсси известны также благодаря разработанным ими алгоритмам семейств SAFER/SAFER+/SAFER++.

Через год алгоритм был модифицирован с целью усиления криптостойкости к дифференциальному криптоанализу. Новая версия получила название IPES (Improved PES - улучшенный PES), а еще через год алгоритм сменил название на IDEA (International Data Encryption Algorithm - международный алгоритм шифрования данных).

Основные характеристики и структура

Алгоритм IDEA шифрует данные блоками по 64 бит, а ключ шифрования алгоритма имеет размер 128 бит. Блок шифруемых данных разбивается на четыре 16-битных субблока A, B, C и D (рис. 1), над которыми выполняется восемь раундов преобразований:

A = A [x] Kr1 B = B + Kr2 C = C + Kr3 D = D [x] Kr4 T1 = A [+] C T2 = B [+] D T1 = T1 [x] Kr5 T2 = T1 + T2 T2 = T2 [x] Kr6 T1 = T1 + T2 A = A [+] T2 B = B [+] T1 C = C [+] T2 D = D [+] T1,

где Krn - подключ n раунда r, "+" - операция сложения 16-битных операндов по модулю 2{в 16-й степени}, [+] - побитовая логическая операция "исключающее или" (XOR), [x] - умножение 16-битных операндов по модулю (2{в 16-й степени} + 1), причем в качестве значения субблока, состоящего из одних нулей, берется значение 2{в 16-й степени}.

После выполнения описанных выше действий два внутренних субблока (B и C) меняются местами - во всех раундах, кроме последнего. По завершении восьми раундов выполняются дополнительные преобразования (иногда называемые девятым раундом алгоритма):

A" = A [x] K91 B" = B + K92 C" = C + K93 D" = D [x] K94

Шифртекст представляет собой результат конкатенации полученных значений A", B", C" и D".

Операция расшифрования аналогична зашифрованию, с той разницей, что при расшифровании используются модифицированные подключи и в другой последовательности:

K"r1 = (K(10-r)1)-1 K"r2 = -K(10-r)3 K"r3 = -K(10-r)2 K"r4 = (K(10-r)4)-1 K"r5 = K(9-r)5 K"r6 = K(9-r)6,

за исключением раундов 1 и 9, в которых подключи K"r2 и K"r3 меняются местами. Здесь K"rn - подключ n раунда расшифрования r, -x и x-1 - обратные значения x относительно описанных выше операций сложения по модулю 2{в 16-й степени} и умножения по модулю (2{в 16-й степени} + 1) соответственно. При этом 0{в -1-й степени} = 0.

Процедура расширения ключа

Задача процедуры расширения ключа - формирование 52 16-битных подключей, используемых в раундах шифрования и дополнительных преобразованиях (т. е. всего 832 бита ключевой информации). Данная процедура весьма проста, и выполняется она следующим образом:

1. 128-битный ключ шифрования делится на восемь подключей по 16 бит; они становятся первыми восемью подключами алгоритма (K11, K12, K13, K14, K15, K16, K21, K22).
2. Ключ шифрования циклически сдвигается влево на 25 бит.
3. Результат делится на восемь следующих подключей.
4. Ключ шифрования циклически сдвигается влево на 25 бит, и так далее до выработки необходимого количества подключей.

Криптостойкость алгоритма

Уже в следующем году после появления алгоритма PES его авторы опубликовали работу, в которой была доказана слабость алгоритма по отношению к дифференциальному криптоанализу (см., например, статью , "BYTE/Россия" No 11"2004): для определения ключа шифрования достаточно выполнения 2{в 64-й степени} операций шифрования, тогда как полный перебор значений 128-битного ключа потребовал бы выполнения 2{в 128-й степени} операций.

Алгоритм IDEA появился в результате достаточно незначительных модификаций алгоритма PES (рис. 2). Если сравнить схемы алгоритмов IDEA и PES, видно не так уж много отличий:

• операция умножения субблока B со вторым подключом раунда заменена операцией сложения,
• операция сложения субблока D с четвертым подключом раунда заменена операцией умножения,
• по-другому выполняется сдвиг субблоков в конце раунда.

Как заметил один из наиболее известных в мире специалистов-криптологов Брюс Шнайер (Bruce Schneier) в своей книге "Прикладная криптография", "...удивительно, как такие незначительные изменения могут привести к столь большим различиям". Алгоритм IDEA оказался фактически неуязвим к дифференциальному криптоанализу, а в той же книге (вышедшей в 1996 г.) Брюс Шнайер отозвался о нем следующим образом: "Мне кажется, это самый лучший и надежный блочный алгоритм, опубликованный до настоящего времени".

Однако в том же 1996 г. известный криптоаналитик Пол Кохер (Paul Kocher) изобрел достаточно сложно реализуемую атаку, позволяющую путем многократных высокоточных замеров времени выполнения шифрования 2{в 20-й степени} случайно выбранных открытых текстов на ключах, связанных определенным соотношением с искомым ключом, и последующего анализа результатов вычислить искомый ключ шифрования. Данная атака (как и другие атаки на связанных ключах) предполагает, что криптоаналитик не имеет прямого доступа к искомому ключу (например, ключ прошит в каком-либо аппаратном шифраторе или смарт-карте), но может изменять определенным образом различные фрагменты ключа.

А ранее, в 1993 г., несколько криптологов из Бельгии обнаружили в алгоритме IDEA несколько классов слабых ключей (всего 2{в 23-й степени} + 2{в 35-й степени} + 2{в 51-й степени} ключей различной степени слабости), часть из которых, например, можно вычислить криптоаналитической атакой с подобранным открытым текстом. Однако сами авторы данной атаки предложили "противоядие" - слабые ключи исключаются путем наложения операцией XOR специальной шестнадцатеричной константы 0DAE на каждый подключ перед его использованием.

Таким образом, несмотря на обнаруженные недостатки, алгоритм IDEA считается алгоритмом с высокой криптостойкостью. Неоспоримое же достоинство данного алгоритма - высокая скорость зашифрования, не менее, чем в два раза больше, чем у алгоритма DES (в зависимости от платформы, на которой выполняется шифрование). А возможность выполнения операции расширения ключа "на лету" (т. е. параллельно с выполнением раундов шифрования) весьма приветствуется и в более современных алгоритмах шифрования. Однако стоит сказать, что скорость расшифрования несколько снижается из-за наличия ресурсоемких операций вычисления мультипликативных обратных величин по модулю (2{в 16-й степени}+ 1).

***

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

Алгоритм IDEA (International Data Encryption Algorithm ) является блочным шифром. Он оперирует 64-битовыми блоками открытого текста. Несомненным достоинством алгоритма IDEA является то, что его ключ имеет длину 128 бит. Один и тот же алгоритм используется и для шифрования, и для дешифрования.

Первая версия алгоритма IDEA была предложена в 1990 г., ее авторы - Х.Лей и Дж.Мэсси. Первоначальное алгоритм назывался PES (Proposed Encryption Standard). Улучшенный вариант этого алгоритма, разработанный в 1991 г., получил название IPES (Improved Proposed Encryption Standard). В 1992 г. IPES изменил свое имя на IDEA. Алгоритм IDEA использует при шифровании процессы смешивания и рассеивания, которые легко реализуются аппаратными и программными средствами.

В IDEA используются следующие математические операции:
• поразрядное сложение по модулю 2 (операция "исключающее ИЛИ"); операция обозначается как (+);
• сложение беззнаковых целых по модулю 2 16 ; операция обозначается как [+];
• умножение беззнаковых целых по модулю (2 16 +1), причем блок из 16 нулей рассматривается как 2 16 ; операция обозначается как (·).

Все операции выполняются над 16-битовыми субблоками.

Эти три операции несовместимы в том смысле, что:
• никакая пара из этих трех операций не удовлетворяет ассоциативному закону,
  например a[+] (b(+)c) # (a[+]b) (+)c;
• никакая пара из этих трех операций не удовлетворяет дистрибутивному закону,
  например a[+] (b(·)c) # (a[+]b) (·) (a[+]с) .

Комбинирование этих трех операций обеспечивает комплексное преобразование входных данных, существенно затрудняя крипто-анализ IDEA по сравнению с DES , который базируется исключительно на операции "исключающее ИЛИ".

Общая схема алгоритма IDEA приведена на рис.1. 64-битовый блок данных делится на четыре 16-битовых субблока. Эти четыре субблока становятся входом в первый цикл алгоритма. Всего выполняется восемь циклов. Между циклами второй и третий субблоки меняются местами. В каждом цикле выполняется следующая последовательность операций:

1. (+) - сложение результатов шагов 1 и 3.
2. (+) - сложение результатов шагов 2 и 4.
3. (·) - умножение результата шага 5 и пятого подключа.
4. [+] - сложение результатов шагов 6 и 7.
5. (·) - умножение результата шага 8 и шестого подключа.
6. [+] - сложение результатов шагов 7 и 9.
7. (+) - сложение результатов шагов 1 и 9.
8. (+) - сложение результатов шагов 3 и 9.
9. (+) - сложение результатов шагов 2 и 10.
10. (+) - сложение результатов шагов 4 и 10.

Рис.1. Cхема алгоритма IDEA (режим шифрования)

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

После восьмого цикла осуществляется заключительное преобразование выхода:
1. (·) - умножение субблока X 1 и первого подключа.
2. [+] - сложение субблока X 2 и второго подключа.
3. [+] - сложение субблока X 3 и третьего подключа.
4. (·) - умножение субблока X 4 и четвертого подключа.

Полученные четыре субблока Y 1 ...Y 4 объединяют в блок шифртекста.

Создание подключей Z 1 ...Z 6 также относительно несложно. Алгоритм использует всего 52 подключа (по шесть для каждого из восьми циклов и еще четыре для преобразования выхода). Сначала 128-битовый ключ делится на восемь 16-битовых подключей. Это - первые восемь подключей для алгоритма (шесть подключей - для первого цикла и первые два подключа - для второго). Затем 128-битовый ключ циклически сдвигается влево на 25 бит и снова делится на восемь подключей (четыре подключа - для второго цикла и четыре подключа - для третьего). Ключ снова циклически сдвигается влево на 25 бит для получения следующих восьми подключей и т.д., пока выполнение алгоритма не завершится.

Дешифрование осуществляется аналогичным образом, за исключением того, что порядок использования подключей становится обратным, причем ряд подключей дешифрования являются или аддитивными (-x), или мультипликативными (1/x) обратными величинами подключей шифрования (табл.1).

Таблица 1 Подключи шифрования и дешифрования алгоритма IDEA

Цикл Подключи шифрования Подключи дешифрования 1 Z 1 (1) Z 2 (1) Z 3 (1) Z 4 (1) Z 5 (1) Z 6 (1) Z 1 (9)-1 -Z 2 (9) -Z 3 (9) Z 4 (9)-1 Z 5 (8) Z 6 (8) 2 Z 1 (2) Z 2 (2) Z 3 (2) Z 4 (2) Z 5 (2) Z 6 (2) Z 1 (8)-1 -Z 3 (8) -Z 2 (8) Z 4 (8)-1 Z 5 (7) Z 6 (7) 3 Z 1 (3) Z 2 (3) Z 3 (3) Z 4 (3) Z 5 (3) Z 6 (3) Z 1 (7)-1 -Z 2 (7) -Z 3 (7) Z 4 (7)-1 Z 5 (6) Z 6 (6) 4 Z 1 (4) Z 2 (4) Z 3 (4) Z 4 (4) Z 5 (4) Z 6 (4) Z 1 (6)-1 -Z 3 (6) -Z 2 (6) Z 4 (6)-1 Z 5 (5) Z 6 (5) 5 Z 1 (5) Z 2 (5) Z 3 (5) Z 4 (5) Z 5 (5) Z 6 (5) Z 1 (5)-1 -Z 2 (5) -Z 3 (5) Z 4 (5)-1 Z 5 (4) Z 6 (4) 6 Z 1 (6) Z 2 (6) Z 3 (6) Z 4 (6) Z 5 (6) Z 6 (6) Z 1 (4)-1 -Z 3 (4) -Z 2 (4) Z 4 (4)-1 Z 5 (3) Z 6 (3) 7 Z 1 (7) Z 2 (7) Z 3 (7) Z 4 (7) Z 5 (7) Z 6 (7) Z 1 (3)-1 -Z 2 (3) -Z 3 (3) Z 4 (3)-1 Z 5 (2) Z 6 (2) 8 Z 1 (8) Z 2 (8) Z 3 (8) Z 4 (8) Z 5 (8) Z 6 (8) Z 1 (2)-1 -Z 3 (2) -Z 2 (2) Z 4 (2)-1 Z 5 (1) Z 6 (1) Преобра- зование выхода Z 1 (9) Z 2 (9) Z 3 (9) Z 4 (9) Z 1 (1)-1 -Z 2 (1) -Z 3 (1) Z 4 (1)-1

Для реализации алгоритма IDEA было принято соглашение, что мультипликативная обратная величина (1/x) от 0 равна 0.

Алгоритм IDEA обладает рядом преимуществ перед алгоритмом DES . Он зачительно безопаснее алгоритма DES, поскольку 128-битовый ключ алгоритма IDEA вдвое больше ключа DES. Внутренняя структура алгоритма IDEA обеспечивает лучшую устойчивость к криптоанализ у. Существующие программные реализации примерно вдвое быстрее реализаций алгоритма DES. Алгоритм IDEA запатентован в Европе и США.

ВВЕДЕНИЕ

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

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

Классическим примером таких алгоритмов являются симметричные криптографические алгоритмы, перечисленные ниже:- простая подстановка;

Одиночная перестановка по ключу;

Двойная перестановка;

Перестановка "Магический квадрат";

Простая перестановка.

Полная утрата всех статистических закономерностей исходного сообщения является важным требованием к симметричному шифру. Для этого шифр должен иметь «эффект лавины», т.е. должно происходить сильное изменение шифроблока при 1битном изменении входных данных (в идеале должны меняться значения 1/2 бит шифроблока).

В настоящее время симметричные шифры это:

· блочные шифры. Обрабатывают информацию блоками определённой длины (обычно 64, 128 бит), применяя к блоку ключ в установленном порядке, как правило, несколькими циклами перемешивания и подстановки, называемыми раундами. Результатом повторения раундов является лавинный эффект - нарастающая потеря соответствия битов между блоками открытых и зашифрованных данных.

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

Существует множество алгоритмов симметричных шифров, существенными параметрами которых являются:

· стойкость;

· длина ключа;

· число раундов;

· длина обрабатываемого блока;

· сложность аппаратной/программной реализации;

· сложность преобразования.

АНАЛИТИЧЕСКАЯ ЧАСТЬ

Алгоритм IDEA

IDEA (англ. International Data Encryption Algorithm, международный алгоритм шифрования данных) -- симметричный блочный алгоритм шифрования данных, запатентованный швейцарской фирмой Ascom. Это алгоритм блочного симметричного шифрования, который был предложен на замену стандарта DES. Начальная версия алгоритма IDEA появилась в 1990г. Разработчики алгоритма, Ксуеджа Лай (Xuejia Lai) и Джеймс Мэсси (James Massey) из Швейцарского института ETH Zurich, дали ему название PES (Proposed Encryption Standard -предлагаемый стандарт шифрования).

Так как IDEA использует 128-битный ключ и 64-битный размер блока, открытый текст разбивается на блоки по 64 бит. Если такое разбиение невозможно, последний блок дополняется различными способами определённой последовательностью бит. Для избежания утечки информации о каждом отдельном блоке используются различные режимы шифрования. Каждый исходный незашифрованный 64-битный блок делится на четыре подблока по 16 бит каждый, так как все алгебраические операции, использующиеся в процессе шифрования, совершаются над 16-битными числами. Для шифрования и дешифрования IDEA использует один и тот же алгоритм.

В IDEA используются следующие математические операции:

Поразрядное сложение по модулю 2 (операция "исключающее ИЛИ");

Сложение беззнаковых целых по модулю 2 16 ;

Умножение беззнаковых целых по модулю (2 16 +1), причем блок из 16 нулей рассматривается как 2 16 ;

Существенным недостатком является то, что IDEA запатентован, так как это препятствует его свободному распространению. IDEA не предусматривает увеличение длины ключа. Недостатком можно также считать тот факт, что не все работы по криптоанализу были опубликованы, то есть вполне возможно, что шифр взломан, или будет взломан в будущем.

Структура алгоритма IDEA представлена ниже (рис. 1).

· режим электронной кодовой книги (ECB -- Electronic Code Book)

· режим сцепления блоков (СВС -- Cipher Block Chaining)

· режим обратной связи по шифртексту (CFB -- Cipher Feed Back)

· режим обратной связи по выходу (OFB -- Output Feed Back).

В данной курсовой работе рассматривается программная реализация алгоритма шифровании IDEA (режим Cipher Feed Back).

Алгоритм шифрования RC6

RC6 -- симметричный блочный криптографический алгоритм, производный от алгоритма RC5. Был создан Роном Ривестом, Мэттом Робшау и Рэем Сиднеем для удовлетворения требований конкурса Advanced Encryption Standard (AES). Алгоритм был одним из пяти финалистов конкурса, был также представлен NESSIE и CRYPTREC.

RC6 -- полностью параметризированная семья алгоритмов шифрования. Для спецификации алгоритма с конкретными параметрами, принято обозначение

w -- длина машинного слова в битах;

r -- число раундов;

b -- длина ключа в байтах. Возможные значения 0..255 байт.

Общая схема реализации алгоритма RC6 представлена на Рисунке 8.

Рисунок 8 - Общая схема RC6.

Вариант алгоритма RC6, который был заявлен на AES, как уже было сказано, поддерживает блоки длиной 128 бит и ключи длиной 128, 192 и 256 бит, а также содержит 20 раундов. То есть

криптосистема шифрование данные

где b=128,192 или 256 бит. В отношении такого алгоритма никаких атак не было обнаружено. Были обнаружены атаки только против упрощенных версий алгоритма, то есть алгоритма с уменьшенным количеством раундов.

Полагается, что лучший вариант нападения на RС6, доступный для криптоаналитика, является полным перебором b-байтового ключа шифрования (или расширенный ключевой массив S , когда предоставленный пользователем ключ шифрования особенно длинный). Таким образом, можно заключить, что RC6 можно считать полностью безопасным алгоритмом.

Алгоритм шифрования IDEA

IDEA -- симметричный блочный алгоритм шифрования данных, запатентованный швейцарской фирмой Ascom. Известен тем, что применялся в пакете программ шифрования PGP. В ноябре 2000 года IDEA был представлен в качестве кандидата в проекте NESSIE в рамках программы Европейской комиссии IST .

Общая структура алгоритма приведена на рисунке 9.

Рисунок 9 - Общая схема IDEA

Первую версию алгоритма разработали в 1990 году Лай и Джеймс Мэсси из Швейцарского института ETH Zьrich в качестве замены DES. Алгоритм использует 128 бит ключевой информации и оперирует блоками данных длиной 64 бита.

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

Принципиальным нововведением в IDEA является использование операций из разных алгебраических групп, а именно:

сложение по модулю;

умножение по модулю;

побитовое исключающее ИЛИ (XOR).

Эти три операции несовместимы в том смысле, что:

никакие две из них не удовлетворяют дистрибутивному закону, то есть:

a*(b+c) <> (a*b)+(a*c)

никакие две из них не удовлетворяют ассоциативному закону, то есть:

a+(b XOR c) <> (a+b) XOR c.

Применение этих трех операций затрудняет криптоанализ IDEA по сравнению с DES, который основан исключительно на операции исключающее ИЛИ, а также позволяет отказаться от использования S-блоков и таблиц замены .

Сам процесс шифрования состоит из восьми одинаковых раундов шифрования и одного выходного преобразования. Исходный незашифрованный текст делится на блоки по 64 бита. Каждый такой блок делится на четыре подблока по 16 бит каждый. В каждом раунде используются свои подключи согласно таблице подключей. Над 16-битными подключами и подблоками незашифрованного текста производятся следующие операции:

умножение по модулю 216 + 1 = 65537, причем вместо нуля используется 216;

сложение по модулю 216;

побитовое исключающее ИЛИ.

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

умножение по модулю 216 +1;

сложение по модулю 216.

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

К неоспоримым достоинствам IDEA стоит отнести практическую устойчивость ко всем атакам и хорошую скорость шифрования. К недостаткам алгоритма принято относить медленную скорость шифрования по сравнению с новейшими алгоритмами .

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

Алгоритм шифрования 3DES

Итак, первым в ряду зарубежных шифров рассмотрим 3DES, а точнее его ближайшего родственника DES (Data Encryption Standard), который хоть уже и не используется как таковой, но является предком 3DES.

DES разработан командой математиков научной лаборатории IBM, в которую входил уже знакомый нам Фейстель. Первая версия шифра получила имя «Люцифер», но затем он был модифицирован и в результате принят как официальный алгоритм шифрования данных (DEA). На протяжении более двадцати лет он оставался мировым стандартом, прежде чем его сменил Triple DES.

Рассмотрим, как работает алгоритм шифрования DES. Для этого необходимо вспомнить работу сети Фейстеля. DES - это сеть Фейстеля из 16 раундов с симметричными ключами шифрования. Длина блока текста - 64 бита, длина раундового ключа - 48 бит. Итак, пройдем основные этапы шифрования DES, опуская суровую математическую сторону:

1. Текст, как и при любом другом шифровании, разбивается на блоки по 64 бита.
2. Из 56-битного ключа генерируется 16 48-битных раундовых ключиков.
3. Каждый блок подвергается перестановке, тоесть все биты входного блока перемешиваются согласно определенной таблице.
4. Блок расщепляется на половинки и поступает в знакомую нам сеть Фейстеля, где прокручивается 16 раундов.
5. Соединяем половинки.
6. И еще одна перестановка.

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

Вот, собственно, все, что надо знать о работе алгоритма DES. Если углубляться в то, как работает функция, заданная в сети Фейстеля, то в ней все прекрасно. Она осуществляет и перестановку, и замену (S-боксы, как ты можешь помнить из предыдущей статьи), и сложение с раундовым ключом.

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

Но если взять компьютер с одним миллионом процессорных ядер, которые будут параллельно обрабатывать ключи, мы сможем проверить все множество ключей приблизительно за 20 часов. Когда был введен DES, стоимость такого компьютера равнялась нескольким миллионам долларов, но она быстро снизилась. Специальный компьютер был создан в 1998 году - и нашел ключ за 112 часов.

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

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

Тем не менее на практике атака осуществима, что делает алгоритм Double DES непригодным.

Совсем иначе дела обстоят с Triple DES. Использование трех ключей и применение алгоритмов в указанной на схеме последовательности продлило DES жизнь еще на несколько лет.

Алогоритм шифрования DES

Так что же в DES такого замечательного? Этот алгоритм шифрования был подвергнут тщательному анализу. DES обладал двумя очень важными качествами блочных шифров - лавинностью и полнотой. Настало время расширить свой криптографический словарик!

Где же применяется DES? Да почти везде, его реализации присутствуют в большинстве программных библиотек. Однако кто знает, насколько использование DES безопасно в наше время? Хотя IBM утверждала, что работа алгоритма была результатом 17 человеко-лет интенсивного криптоанализа, некоторые люди опасались, не вставило ли NSA в алгоритм лазейку, которая позволяет агентству легко дешифровывать перехваченные сообщения.

Комитет по разведке сената США тщательно изучал этот вопрос и, разумеется, ничего не обнаружил, обвинения с NSA были сняты, результаты исследования тем не менее засекречены. Одним словом, в Америке еще долго крутились слухи и домыслы насчет того, стоит доверять DES или нет. Но, как я считаю, здесь ситуация описывается поговоркой «Умный не скажет, дурак не поймет». В конце концов NSA признало, что не могло доверить IBM столь важную миссию и внесло несколько корректировок вроде задания S-боксов.

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

Алгоритм шифрования AES

Победитель конкурса AES, объявленный в конце 1997 года, алгоритм Rijndael был разработан двумя бельгийскими криптографами - Йоаном Даменом (Joan Daemen) и Винсентом Рейменом (VincentRijmen).

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

AES оперирует 128-битными блоками данных и ключами по 128, 192 и 256 бит. Концептуально он отличается от DES, так как не базируется на сети Фейстеля, а представляет собой подстановочно-перестановочную сеть (SP-сеть), которую мы сейчас рассмотрим подробнее.

В AES байты открытого текста не делятся на две части, как в сети Фейстеля, а записываются в форму - матрицу (двумерный массив) байтов, расположенных таким образом:

AES действует следующими операциями:
1. ExpandKey - вычисление раундовых ключей для всех раундов.
2. SubBytes - замена битов по таблице замены (S-боксу).
3. ShiftRows - циклический сдвиг строк в форме на различные величины. 4. MixColumns - смешивание данных внутри каждого столбца формы.
5. AddRoundKey - сложение ключа раунда с формой.

Сегодня AES является официальным стандартом правительства США для симметричного шифрования и применяется повсеместно. Фактически это один из самых универсальных зарубежных шифров на данный момент. Что касается безопасности AES, то и у него, как и большинства шифров, есть некоторые уязвимости, и криптоаналитики продолжают их искать. Однако, несмотря на это, AES живее всех живых.

Алгоритм шифрования IDEA

IDEA (International Data Encryption Algorithm) - алгоритм блочного симметричного шифрования, который был предложен на замену стандарта DES. Начальная версия алгоритма IDEA появилась в 1990 году. Алгоритм запатентован в США и в большинстве европейских стран. Владеет патентом Ascom Tech, но в некоммерческих целях алгоритм можно использовать бесплатно.

Размер блока в этом шифре - 64 бита, длина ключа - 128. Стоит сразу сказать, что алгоритм IDEA - самый молодой из перечисленных и его математика очень сложна. Минутка криптографического словарика.

В IDEA эти свойства достигаются за счет применения независимых математических операций. В отличие от DES, главной операцией которого является XOR (сложение по модулю 2), IDEA предусматривает наличие:

XOR;
сложения по модулю 2¹6;
умножения по модулю (2¹6; + 1).

Комбинирование этих трех операций обеспечивает комплексное преобразование входных данных, затрудняя криптоанализ IDEA по сравнению с DES.

В шифре IDEA выполняется восемь раундов, и в каждом раунде блок открытого текста подвергается преобразованию посредством математических операций. Любители «зреть в корень» могут позреть на схему одного раунда шифра IDEA, приведенную ниже. Блок текста, длиной 64 бита, делится на подблоки по 16 бит. Каждый такой полученный блочок поступает на вход раунда и подвергается сложному преобразованию.

Неповторимая IDEA

«Мне кажется, это самый лучший и надежный блочный алгоритм, опубликованный до настоящего времени», - говорит Брюс Шнайер об алгоритме IDEA.

Действительно, IDEA отличается высокой стойкостью благодаря своим многочисленным математическим операциям. Кроме того, к достоинствам данного алгоритма относится высокая скорость зашифрования - почти в два раза выше, чем у алгоритма DES (в зависимости от платформы, на которой выполняется шифрование). Однако скорость расшифровки снижается из-за тяжелых операций вычисления, обратных умножению по модулю (216 + 1).

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

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

РЫБЫ БРЮСА ШНАЙЕРА

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

Мы вкратце познакомимся с одними из самых известных его детищ - алгоритмами шифрования Blowfish, Twofish и Threefish.

Алгоритм шифрования Blowfish

Первым на свет появился Blowfish. Как говорит сам Шнайер, этот алгоритм был разработан для реализации на больших микропроцессорах. Поэтому он компактен (всего 5 Кбайт памяти) и прост (использует простые математические операции - сложение, XOR и выборку из таблицы). Также алгоритм позволяет настраивать длину ключа (до 448 бит).

На 32-битных процессорах Blowfish выполняет шифрование значительно быстрее, нежели DES, однако на интеллектуальных платах в силу своей упрощенности он не особо применим. В основе Blowfish сеть Фейстеля из 16 раундов, которую ты уже должен хорошо понимать.

Алгоритм реализован в некоторых программных продуктах (FolderBolt, Nautilus, PGPfone), однако сейчас он уже теряет свою актуальность.

Алгоритм шифрования Twofish

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

128-битный блочный симметричный шифр;
длина ключей: 128, 192 и 256 бит;
эффективная программная (в первую очередь на 32-битных процессорах) и аппаратная реализация;
гибкость (возможность использования ключа большей длины, применимость для поточного шифрования, хеш-функций и так далее); простота алгоритма - его удобно анализировать.

Однако по сравнению с Rijndael, занявшим пьедестал AES, Twofish был более сложным для анализа и обладал более низкой скоростью шифрования. Разработан этот алгоритм на основе Blowfish с некоторыми дополнениями и также представляет собой сеть Фейстеля.

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

Алгоритм шифрования Threefish

«В третий раз закинул старик в море невод…» и десять лет спустя получился шифр Threefish. На этот раз Шнайер решил переплюнуть AES и учел все недостатки предыдущего опыта. Криптограф не стал брать за основу сеть Фейстеля, а реализовал шифр на основе подстановочно-перестановочной сети (SP-сети), как в AES. Такая сеть основана на комбинации операций исключающего ИЛИ, сложения и циклического сдвига. В упрощенном виде все это выглядит так:

За счет простых операций Threefish значительно опережает в скорости AES. Кроме того, по заявлениям авторов, алгоритм имеет более высокий уровень безопасности, чем AES. Существует атака на 25 из 72 раундов Threefish, в то время как для AES - на 6 из 10. Так что Брюс Шнайер добился-таки своей победы, хоть и с опозданием.

Шифр послужил основой для создания хеш-функции Skein, которая участвовала в конкурсе на должность SHA-3. Сам Threefish широко используется и реализован в библиотеках для многих языков программирования.

ВЫВОДЫ

В заключение стоит сказать, что все западные криптографы, конечно, молодцы, разработали вагон и маленькую тележку различных алгоритмов шифрования. Какой-то более стойкий, какой-то более быстрый. Но пока все будут сравнивать их с DES и AES, потому что это классика.

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

Ссылки:

Это первый урок из цикла «Погружение в крипту». Все уроки цикла в хронологическом порядке:

• Основы, исторические шифраторы, как работают (и анализируются) шифры сдвига, замены, Рихарда Зорге, шифр Вернама и шифровальные машины (ты здесь)
• . часть 2. Что это такое, как выполняется распределение ключей и как выбрать криптостойкий ключ
• Что тaкое сеть Фейстеля, какими бывают отечественные блочные шифры, используемые в современных протоколах, - ГОСТ 28147-89, «Кузнечик»
• Современные зарубежные шифры . Часть 4. Что такое, как работают и в чем разница между 3DES, AES, Blowfish, IDEA, Threefish от Брюса Шнайдера
• Электронная подпись . Виды ЭП, как они работают и как их использовать
• Квантовая криптография . Что это такое, где используется и как помогает в распределении секретных ключей, генерации случайных чисел и электронной подписи

Last updated by at Июль 12, 2016 .