<< Предыдущая

стр. 12
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

ники недалеко то время, когда машины поиска ключа DES методом полного перебора станут эконо-
мичными для мощных в финансовом отношении государственных и коммерческих организаций.
Возникает естественный вопрос: нельзя ли использовать DES в качестве строительного блока
для создания другого алгоритма с более длинным ключом?
В принципе существует много способов комбинирования блочных алгоритмов для получения
новых алгоритмов. Одним из таких способов комбинирования является многократное шифрование,
т.е. использование блочного алгоритма несколько раз с разными ключами для шифрования одного и
того же блока открытого текста. Двухкратное шифрование блока открытого текста одним и тем
же ключом не приводит к положительному результату. При использовании одного и того же алго-
ритма такое шифрование
не влияет на сложность криптоаналитической атаки полного перебора.
Рассмотрим эффективность двухкратного шифрования блока открытого текста с помощью
двух разных ключей. Сначала шифруют блок Р ключом К1, а затем получившийся шифртекст ЕК1(Р)
шифруют ключом К2. В результате двухкратного шифрования получают криптограмму
С = ЕК2(ЕК1(Р)).
Расшифрование является обратным процессом:
11
Р = DК1(DК2(C)).
Если блочный алгоритм обладает свойствами группы [125], то всегда найдется такой ключ К3,
что
С = ЕК2(ЕК1(Р)) = ЕК3(Р).
Если же блочный алгоритм не является группой, то результирующий двухкратно шифрован-
ный блок текста окажется намного сложнее для взламывания методом полного перебора вариантов.
Вместо 2n попыток, где n – длина ключа в битах, потребуется 22n попыток. В частности, если n=64, то
двухкратно зашифрованный блок текста потребует 2128 попыток для нахожде-ния ключа.
Однако Р.Меркль и М.Хеллман показали на примере DES, что, используя метод "обмена вре-
мени на память" и криптоаналитическую атаку "встреча посредине", можно взломать такую схему
двухкратного шифрования за 2n+1 попыток [34]. Хотя эта атака потребует очень большого объема па-
мяти (для алгоритма с 56-битовым ключом потребуется 256 64-битовых блоков или 1017 бит памяти).
Более привлекательную идею предложил У.Тачмен [125]. Суть этой идеи состоит в том, чтобы
шифровать блок открытого текста Р три раза с помощью двух ключей К1 и К2 (рис.3.9). Процедура
шифрования:
С = ЕК1(DК2 (EК1(Р))),
т.е. блок открытого текста Р сначала шифруется ключом К1, затем расшифровывается ключом К2 и
окончательно зашифровывается ключом К1.
К1 К2 К1

P A B C
DES DES DES
ЕК DК ЕК

Шифрование

К1 К2 К1

C B A P
DES DES DES
DК EК DК

Расшифрование

Рис.3.9. Схемы трехкратного применения алгоритма DES
с двумя разными ключами


Этот режим иногда называют режимом EDE (encrypt-decrypt-encrypt). Введение в данную схе-
му операции расшифрования DК2 позволяет обеспечить совместимость этой схемы со схемой одно-
кратного использования алгоритма DES. Если в схеме трехкратного использования DES выбрать все
ключи одинаковыми, то эта схема превращается в схему однократного использования DES. Процеду-
ра расшифрования выполняется в обратном порядке:
Р = DК1(ЕК2(DК1(C))),
т.е. блок шифртекста С сначала расшифровывается ключом К1, затем зашифровывается ключом К2 и
окончательно расшифровывается ключом К1.
Если исходный блочный алгоритм имеет n-битовый ключ, то схема трехкратного шифрования
имеет 2n-битовый ключ. Чередование ключей К1 и К2 позволяет предотвратить криптоаналитическую
атаку "встреча посредине". Данная схема приводится в стандартах Х9.17 и ISO 8732 в качестве сред-
ства улучшения характеристик алгоритма DES.
При трехкратном шифровании можно применить три различных ключа. При этом возрастает
общая длина результирующего ключа. Процедуры шифрования и расшифрования описываются вы-
ражениями:
С = ЕК3(DК2(EК1(P))),
Р = DК1(ЕК2(DК3(C))).
Трехключевой вариант имеет еще большую стойкость. Очевидно, что если требуется повы-
сить безопасность большого парка оборудования, использующего DES, то гораздо дешевле переклю-
читься на схемы трехкратных DES, чем переходить на другой тип криптосхем.


3.4. Алгоритм шифрования данных IDEA
12
Алгоритм 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 (модуль 65536); операция обозначается как ? ;
• умножение целых по модулю (216+1) (модуль 65537), рассматриваемых как беззнаковые целые, за
исключением того, что блок из 16 нулей рассматривается как 216; операция обозначается как ?.
Все операции выполняются над 16-битовыми субблоками.
Эти три операции несовместимы в том смысле, что:
• никакая пара из этих трех операций не удовлетворяет ассоциативному закону,
например a ? (b ? c) ? (a ? b) ? c;
• никакая пара из этих трех операций не удовлетворяет дистрибутивному закону,
например a ? (b? c) ? (a ? b)? (a ? c).
Комбинирование этих трех операций обеспечивает комплексное преобразование входа, су-
щественно затрудняя крипто-анализ IDEA по сравнению с DES, который базируется исключительно
на операции "исключающее ИЛИ".
Общая схема алгоритма IDEA приведена на рис.3.10. 64-битовый блок данных делится на че-
тыре 16-битовых субблока. Эти четыре субблока становятся входом в первый цикл алгоритма. Всего
выполняется восемь циклов. Между циклами второй и третий субблоки меняются местами. В каждом
цикле имеет место следующая последовательность операций:
(1) ? – умножение субблока Х1 и первого подключа.
(2) ? – сложение субблока Х2 и второго подключа.
(3) ? – сложение субблока Х3 и третьего подключа.
(4) ? – умножение субблока Х4 и четвертого подключа.
(5) ? – сложение результатов шагов (1) и (3).
(6) ? – сложение результатов шагов (2) и (4).
(7) ? – умножение результата шага (5) и пятого подключа.
(8) ? – сложение результатов шагов (6) и (7).
(9) ? – умножение результата шага (8) с шестым подключом.
(10) ? – сложение результатов шагов (7) и (9).
(11) ? – сложение результатов шагов (1) и (9).
(12) ? – сложение результатов шагов (3) и (9).
(13) ? – сложение результатов шагов (2) и (10).
(14) ? – сложение результатов шагов (4) и (10).
Выходом цикла являются четыре субблока, которые получают как результаты выполнения
шагов (11), (12), (13) и (14). В завершение цикла переставляют местами два внутренних субблока (за
исключением последнего цикла), и в результате формируется вход для следующего цикла.
X1 X2 X3 X4

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




Z5(9)
1-й
цикл
Z6(1)


13
Обозначения:
Xi – 16-битовый субблок открытого текста, i = 1…4
Yi – 16-битовый субблок шифртекста, i = 1…4
Zj(r) – 16-битовый подключ (субблок ключа), j = 1…6, r = 1…8
– поразрядное суммирование по модулю 2 16-битовых субблоков
16
– сложение по модулю 2 16-битовых целых
16
– умножение по модулю 2 16-битовых целых (с нулевым субблоком,
16
соответствующим 2 )

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

После восьмого цикла осуществляют заключительное преобразование выхода:
(1) ? – умножение субблока Х1 и первого подключа.
(2) ? – сложение субблока Х2 и второго подключа.
(3) ? – сложение субблока Х3 и третьего подключа.
(4) ? – умножение субблока Х4 и четвертого подключа.
Наконец, эти результирующие четыре субблока Y1…Y4 вновь объединяют для получения
блока шифртекста.
Создание подключей Zj также относительно несложно. Алгоритм использует всего 52 подклю-
ча (по шесть для каждого из восьми циклов и еще четыре для преобразования выхода). Сначала 128-
битовый ключ делят на восемь 16-битовых подключей. Это – первые восемь подключей для алгорит-
ма (шесть подключей – для первого цикла и первые два подключа – для второго цикла). Затем 128-
битовый ключ циклически сдвигается влево на 25 бит и снова делится на восемь подключей. Первые
четыре из них используют во втором цикле; последние четыре – в третьем цикле. Ключ снова цикли-
чески сдвигается влево еще на 25 бит для получения следующих восьми подключей и т.д., пока вы-
полнение алгоритма не завершится.
Расшифрование осуществляют аналогичным образом, за исключением того, что порядок ис-
пользования подключей становится обратным, причем ряд значений подключей заменяется на об-
ратные значения. Подключи расшифрования являются в основном либо аддитивными, либо мультип-
ликативными обратными величинами подключей шифрования (табл.3.10).
Таблица 3.10
Подключи шифрования и расшифрования алгоритма IDEA
Цикл Подключи шифрования Подключи расшифрования

(1) (1) (1) (1) (1) (1) (9)–1 (9) (9) (9)–1 (8) (8)
1 Z1 Z2 Z3 Z4 Z5 Z6 Z1 –Z2 –Z3 Z4 Z5 Z6
(2) (2) (2) (2) (2) (2) (8)–1 (8) (8) (8)–1 (7) (7)
2 Z1 Z2 Z3 Z4 Z5 Z6 Z1 –Z3 –Z2 Z4 Z5 Z6
(3) (3) (3) (3) (3) (3) (7)–1 (7) (7) (7)–1 (6) (6)
3 Z1 Z2 Z3 Z4 Z5 Z6 Z1 –Z3 –Z2 Z4 Z5 Z6
(4) (4) (4) (4) (4) (4) (6)–1 (6) (6) (6)–1 (5) (5)
4 Z1 Z2 Z3 Z4 Z5 Z6 Z1 –Z3 –Z2 Z4 Z5 Z6
(5) (5) (5) (5) (5) (5) (5)–1 (5) (5) (5)–1 (4) (4)
5 Z1 Z2 Z3 Z4 Z5 Z6 Z1 –Z3 –Z2 Z4 Z5 Z6
(6) (6) (6) (6) (6) (6) (4)–1 (4) (4) (4)–1 (3) (3)
6 Z1 Z2 Z3 Z4 Z5 Z6 Z1 –Z3 –Z2 Z4 Z5 Z6
(7) (7) (7) (7) (7) (7) (3)–1 (3) (3) (3)–1 (2) (2)
7 Z1 Z2 Z3 Z4 Z5 Z6 Z1 –Z3 –Z2 Z4 Z5 Z6
(8) (8) (8) (8) (8) (8) (2)–1 (2) (2) (2)–1 (1) (1)
8 Z1 Z2 Z3 Z4 Z5 Z6 Z1 –Z3 –Z2 Z4 Z5 Z6
(9) (9) (9) (9) (1)–1 (1) (1) (1)–1
Преобра- Z1 Z2 Z3 Z4 Z1 –Z2 –Z3 Z4
зование
выхода


14
Для реализации алгоритма IDEA было принято предположение, что нулевой субблок равен
16
2 = –1; при этом мультипликативная обратная величина от 0 равна 0 [121]. Вычисление значений
мультипликативных обратных величин требует некоторых затрат, но это приходится делать только
один раз для каждого ключа расшифрования.
Алгоритм IDEA может работать в любом режиме блочного шифра, предусмотренном для ал-
горитма DES. Алгоритм IDEA обладает рядом преимуществ перед алгоритмом DES. Он значительно
безопаснее алгоритма DES, поскольку 128-битовый ключ алгоритма IDEA вдвое больше ключа DES.
Внутренняя структура алгоритма IDEA обеспечивает лучшую устойчивость к криптоанализу. Сущест-
вующие программные реализации алгоритма IDEA примерно вдвое быстрее реализаций алгоритма
DES. Алгоритм IDEA шифрует данные на IBM PC/486 со скоростью 2,4 Мбит/с. Реализация IDEA на
СБИС шифрует данные со скоростью 177 Мбит/с при частоте 25 Мгц. Алгоритм IDEA запатентован в
Европе и США.


3.5. Отечественный стандарт шифрования данных
В нашей стране установлен единый алгоритм криптографического преобразования данных
для систем обработки информации в сетях ЭВМ, отдельных вычислительных комплексах и ЭВМ, ко-
торый определяется ГОСТ 28147-89 [81]. Стандарт обязателен для организаций, предприятий и уч-
реждений, применяющих криптографическую защиту данных, хранимых и передаваемых в сетях
ЭВМ, в отдельных вычислительных комплексах и ЭВМ.
Этот алгоритм криптографического преобразования данных предназначен для аппаратной и
программной реализации, удовлетворяет криптографическим требованиям и не накладывает ограни-
чений на степень секретности защищаемой информации. Алгоритм шифрования данных представля-
ет собой 64-битовый блочный алгоритм с 256-битовым ключом.
При описании алгоритма используются следующие обозначения:
L и R – последовательности битов;
LR – конкатенация последовательностей L и R, в которой биты последовательности R следуют за би-
тами последовательности L;
? – операция побитового сложения по модулю 2;
? – операция сложения по модулю 232 двух 32-разрядных двоичных чисел;
??– операция сложения двух 32-разрядных чисел по модулю 232 –1.
Два целых числа a, b, где 0 ? a, b ? 232 –1,
a= (a32a31 ... a2a1), b = (b32, b31, ..., b2, b1),
представленные в двоичном виде, т.е.
a= a32?231 + a31?230 +...+ a2?21 + a1,
b = b32?231 + b31?230 +...+ b2?21 + b1,
(операция ?) по следующему правилу:
суммируются по модулю 232
a ? b = a + b, если a + b < 232,
a ? b = a + b – 232, если a + b ? 232.
Правила суммирования чисел по модулю 232 – 1:
a ?? b = a + b, если a + b < 232– 1,
a ?? b = a + b – (232 – 1), если a + b ? 232 – 1.
Алгоритм предусматривает четыре режима работы:
шифрование данных в режиме простой замены;

шифрование данных в режиме гаммирования;

шифрование данных в режиме гаммирования с обратной связью;

выработка имитовставки.


Режим простой замены
Для реализации алгоритма шифрования данных в режиме простой замены используется
только часть блоков общей криптосистемы (рис.3.11). Обозначения на схеме:
N1, N2 – 32-разрядные накопители;
СМ1 – 32-разрядный сумматор по модулю 232 (?);
СМ2 – 32-разрядный сумматор по модулю 2 (?);
R – 32-разрядный регистр циклического сдвига;


15
КЗУ – ключевое запоминающее устройство на 256 бит, состоящее из восьми 32-разрядных накопите-
лей Х0, Х1, Х2, ..., Х7;
S – блок подстановки, состоящий из восьми узлов замены (S-блоков замены) S1, S2, S3, ..., S7, S8.
Зашифрование открытых данных в режиме простой замены. Открытые данные, подле-
жащие зашифрованию, разбивают на 64-разрядные блоки Т0. Процедура зашифрования 64-
разрядного блока Т0 в режиме простой замены включает 32 цикла (j = 1…32). В ключевое запоми-
нающее устройство вводят 256 бит ключа К в виде восьми 32-разрядных подключей (чисел) Кi:

<< Предыдущая

стр. 12
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>