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

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

Алгоритм 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 (операция "исключающее ИЛИ"); операция обозначается как (+); 

сложение беззнаковых целых по модулю 216; операция обозначается как [+]; 

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

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

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

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

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

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

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

(·) - умножение субблока X1 и первого подключа. 

[+] - сложение субблока X2 и второго подключа. 

[+] - сложение субблока X3 и третьего подключа. 

(·) - умножение субблока X4 и четвертого подключа. 

(+) - сложение результатов шагов 1 и 3. 

(+) - сложение результатов шагов 2 и 4. 

(·) - умножение результата шага 5 и пятого подключа. 

[+] - сложение результатов шагов 6 и 7. 

(·) - умножение результата шага 8 и шестого подключа. 

[+] - сложение результатов шагов 7 и 9. 

(+) - сложение результатов шагов 1 и 9. 

(+) - сложение результатов шагов 3 и 9. 

(+) - сложение результатов шагов 2 и 10. 

(+) - сложение результатов шагов 4 и 10. 


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

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

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

(·) - умножение субблока X1 и первого подключа. 

[+] - сложение субблока X2 и второго подключа. 

[+] - сложение субблока X3 и третьего подключа. 

(·) - умножение субблока X4 и четвертого подключа. 

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

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

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

Таблица 1 

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

Цикл

Подключи шифрования

Подключи дешифрования

1

 Z1(1)   Z2(1)   Z3(1)   Z4(1)   Z5(1)   Z6(1)   

 Z1(9)-1   -Z2(9)   -Z3(9)   Z4(9)-1   Z5(8)   Z6(8)   

2

 Z1(2)   Z2(2)   Z3(2)   Z4(2)   Z5(2)   Z6(2)   

 Z1(8)-1   -Z3(8)   -Z2(8)   Z4(8)-1   Z5(7)   Z6(7)   

3

 Z1(3)   Z2(3)   Z3(3)   Z4(3)   Z5(3)   Z6(3)

 Z1(7)-1   -Z2(7)   -Z3(7)   Z4(7)-1   Z5(6)   Z6(6)

4

 Z1(4)   Z2(4)   Z3(4)   Z4(4)   Z5(4)   Z6(4)

 Z1(6)-1   -Z3(6)   -Z2(6)   Z4(6)-1   Z5(5)   Z6(5)

5

 Z1(5)   Z2(5)   Z3(5)   Z4(5)   Z5(5)   Z6(5)

 Z1(5)-1   -Z2(5)   -Z3(5)   Z4(5)-1   Z5(4)   Z6(4)

6

 Z1(6)   Z2(6)   Z3(6)   Z4(6)   Z5(6)   Z6(6)

 Z1(4)-1   -Z3(4)   -Z2(4)   Z4(4)-1   Z5(3)   Z6(3)

7

 Z1(7)   Z2(7)   Z3(7)   Z4(7)   Z5(7)   Z6(7)

 Z1(3)-1   -Z2(3)   -Z3(3)   Z4(3)-1   Z5(2)   Z6(2)

8

 Z1(8)   Z2(8)   Z3(8)   Z4(8)   Z5(8)   Z6(8)

 Z1(2)-1   -Z3(2)   -Z2(2)   Z4(2)-1   Z5(1)   Z6(1)

 Преобра- 
 зование 
 выхода 

 Z1(9)   Z2(9)   Z3(9)   Z4(9)

 Z1(1)-1   -Z2(1)   -Z3(1)    Z4(1)-1



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

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