Презентация на тему I have an IDEA. Международный алгоритм шифрования данных

международный алгоритм шифрования данных) — симметричный блочный алгоритм шифрования

данных.
Ранее известный как PES(proposed encryption standard), IPES(improved PES), после чего переименованный в IDEA
Создатель: Ascom, Xuejia Lai, James Massey
Создан: 1991 год
Опубликован: 1991 год
Размер ключа: 128 бит
Размер блока: 64 бит
Число раундов: 8.5
Тип: модификация сети Фейстеля

и bit-serial(последовательно-двоичная) их отличие заключается в способе передачи данных

в отдельные моменты времени. Bit-serial передаёт один бит данных по одному каналу, bit-parallel сразу все значения по группе проводов.
На Xilinx Virtex XCV300-6 FPGA параллельная реализация обеспечивает шифрование равное 1166 Мб./сек. с частотой 82 МГц, в то время, как у последовательной реализации эти значения равны 600 Мб./сек. и 150 МГц. Оба варианта подходят для приложений в реальном времени(RTA — real-time applications) и высокоскоростных соединений(online high-speed networks). Также пропускная способность может быть увеличена за счёт повышения производительности вычислительной системы.
На плате XCV1000-6 характеристики у обоих подходов: 5,25 Gb/sec. и 2,4 Gb/sec. соответственно.

16ти битные операции, его программные реализации до сих пор

не могут достичь показатель шифрования требуемый для высокоскоростных сетей. Компания Ascom смогла добиться 0,37 * 106 шифрования за секунду или 23,53 Мб/сек. на Пентиуме II 450 МГц.
Реализация алгоритма с использованием мультимедийных инструкций Intel MMX предложенных Хелгером достигла скорости 0,51 * 106 шифрования за секунду или 32,9 Мб/сек. на Пентиуме II 233 МГц.
Ещё одна, приведённая ниже реализация достигает 2,3 * 106 шифр./сек. или 147,13 Мб/сек. реализованная на Sun Enterprise E4500 с 12ю 400 МГц Ultra-Iii процессором.
Все они не могут быть применены к ATM(Asynchronous Transfer Mode) сетям со скоростью 155 Мб/сек.
Короче, всё это плохо, но проблема решается.

и использования распараллеливания между операторами. В совокупности они дешевле,

меньше жрут энергию и меньше занимают место.
Менсером был предложен макет(paper design) процессора IDEA достигающий скорости 528 Мб/сек. на 4ёх XC4020XL устройствах. Ништяк, да? Дальше больше...
Первая реализация IDEA на VLSI была предложена и разработана Бонненбергом в 1992 году и использовала 1,5 мкм CMOS технологию. Короче достигала она скорости шифрования порядка 44 Мб/сек.
Сюригер, 1994 г. VINCI 177 Мб/сек. VLSI реализация на 1,2 мкм CMOS.
Вольтер, 1995 г. 355 Мб/сек. на 0,8 мкм CMOS.
Саломао, 1995 г. 424 Мб/сек. на одночипном 0,7 мкм CMOS.

IDEA на Xilinx Virtex XCV300-6 FPGA, который можно улучшить

за счёт дополнительных ресурсов.
Голдштейн, какой то год, 1013 Мб/сек. на PipeRench FPGA.
Коммерческие реализации алгоритма носят название IDEACrypt kernel, разработанные Ascom со скоростью 720 Мб/сек. на технологии 0,25 мкм и последовавший за ним сопроцессор IDEACrypt coprocessor с пропускной способностью 300 Мб/сек.

идентичных блоков, называемых раундами, сопровождающимися полураундом или конечным преобразованием.

На каждом раунде присутствуют операции XOR, сложение и умножение по модулю.

IDEA принадлежит классу криптосистем с закрытым ключом. На входе алгоритма 64 битный текст на выходе 64 битная криптограмма с применением 128 битного ключа.
В философии алгоритма — смешивание операций из самых разных алгебраических групп (XOR, сумма по модулю 216, и умношение по модулю простого числа Ферма 216 + 1) все они работают на 16 битных подблоках.

нём заложены примитивные операции трёх отдельных алгебраических групп 216

элементов
Умножение по модулю 216 + 1 даёт эффект статистической независимости между текстом и криптограммой
Свойство раундов усложняет дифференциальные атаки
Три операции(⊕, +, *) несовместимы в плане: никакие две из них не удовлетворяют дистрибутивному закону: a * (b + c) ≠ (a * b) + (a * c) никакие две из них не удовлетворяют ассоциативному закону: a + (b ⊕ c) ≠ (a + b) ⊕ c
запутывание — шифрование зависит от ключа сложным и запутанным образом
рассеяние — каждый бит незашифрованного текста влияет на каждый бит зашифрованного текста

на 4 подблока( X1, …, X4 ) по 16

бит каждый
Далее каждый блок превращается в криптограммы по 16 бит( Y1, …, Y4 )
Вычисляются 52 16 битных подключа Zi(r) из 128 битного секретного ключа, i и r — номера подключа и раунда, соответственно.
Каждый раунд использует 6 подключей, а оставшиеся 4 используются в конечном преобразовании.
Процесс расшифрования схож с шифрованием за исключением, что ключи вычисляются иначе

шифрования (key-schedule):
Упорядочим 52 подключа таким образом: Z1(1), …, Z6(1),

…, Z1(8), …, Z6(8), Z1(9), …, Z4(9)
Процедура начинается с деления 128 битного секретного ключа Z на 8 16 битных блоков и назначения их прямо в первые 8 подключей.
Далее Z поворачивается налево на 25 бит, разбитых на 8 блоков по 16 бит и снова назначаются следующим 8 подключам.
Процесс продолжается, пока все 52 подключа не будут назначены.
Получается 128ми битный ключ разбивается на 8 подключей таким образом: Z1(1), Z2(1), …, Z6(1), Z1(2), Z2(2) и соответствует следующему представлению: 1: Z1(1), Z2(1), Z3(1), Z4(1), Z5(1), Z6(1) 2: Z1(2), Z2(2) После чего ключ Z циклически сдвигается влево на 25 бит и процедура деления повторяется, откуда получается уже такое представление: 1: Z1(1), Z2(1), Z3(1), Z4(1), Z5(1), Z6(1) 2: Z1(2), Z2(2), Z3(2), Z4(2), Z5(2), Z6(2) 3: Z1(3), Z2(3), Z3(3), Z4(3) и так далее, пока не заполнятся все 9 раундов и 52 ключа

расшифрования иллюстрирует следующая таблица:

Zi(r)-1 * Zi(r) = 1 (mod

216+1); (-Zi(r)) + Zi(r) = 0 (mod 216);

Y1(1) = X1, …, Y4(1) = X4
Y1(r) = Y1(r)

* Z1(r)
Y2(r) = Y2(r) + Z2(r)
Y3(r) = Y3(r) + Z3(r)
Y4(r) = Y4(r) * Z4(r)
A1(r) = Y1(r) ⊕ Y3(r)
A2(r) = Y2(r) ⊕ Y4(r)
A1(r) = A1(r) * Z5(r)
A2(r) = A1(r) + A2(r)
A2(r) = A2(r) * Z6(r)
A1(r) = A1(r) * A2(r)
Y1(r+1) = Y1(r) ⊕ A2(r), Y2(r+1) = Y3(r) ⊕ A2(r)
Y3(r+1) = Y2(r) ⊕ A1(r), Y4(r+1) = Y4(r) ⊕ A1(r)
Следующий раунд

раунд:
Y1(9) = Y1(9) * Z1(9)
Y2(9) = Y2(9) + Z2(9)
Y3(9)

= Y3(9) + Z3(9)
Y4(9) = Y4(9) * Z4(9)
Конец.

— это камень преткновения этого алгоритма. В каждом раунде

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

+ 1
В этом алгоритме передаются два аргумента x и

y, y — это подключ, так как все ключи уже заранее меньше, то одно вычитание лишнее, убираем его.
Далее, чтобы увеличить пропускную способность этого алгоритма добавляются дополонительные дорожки (pipeline stages?). В приведённом алгоритме строку 7 выполняет Xilinx CORE generator у которого задержка 4 цикла. И у умножения по модулю 216 + 1 задержка 7 циклов.

Реализация умножения по модулю 2n + 1

каждый раунд выполняется на одном устройстве, но с разными

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

по модулю с задержкой в 7 циклов, в общей

сложности задержка раунда получается 7 * 3 = 21, количество раундов 8,5 => 21 * 8 = 168, на конечном раунде, в преобразовании потребуется одно умножение по модулю => 168 + 7 = 175, в итоге такая реализация будет давать задержку в 175 циклов. Плата хавает 21 64 битных текстов(plaintext) за 21 * 9 = 189 циклов, что означает: (21/189) * 64 * f Мб/сек. с частотой f МГц.
Для примера дано 89 МГц, тогда такая реализация будет приносить в скорости шифрования 583 Мб/сек. с задержкой 2,134 мкс.

реализация классической модели путём перемещения и копирования регистров. Такое

представление даёт пропускную способность шифрования равную 600 Мб/сек., что на 20% больше.
Характеризуется свойством, что операторы выполняют вычисления в побитовом режиме и их взаимодействие мультиплексированно во времени по одному проводу. Поток данных начинается либо с менее значимого бита, либо с более значимого, но последнее используется чаще из-за совместимости с двоичным дополнением(дополнительным кодом).
В типичном последовательно-двоичном представлении каждая переменная ассоциируется с контрольным сигналом, который выставляется высоким, только когда первый бит передаётся через ассоциированную шину данных. Для уменьшения размеров, доступ к контрольным сигналам может быть распределён среди переменных. Так как операторы в этой реализации обычно требуют первые биты их операндов, чтобы войти в оператор, в тот же момент времени цикла, соответствующие замки на этапах должны быть закрыты для выравнивания времени.
Xor и сумма по модулю 216 могут быть запросто реализованы для последовательно-двоичной архитектуры. У этих двух операторов задержка равна 1 и они могут принимать последовательно последовательно-двоичные операнды. У умножения задержка равна 35 временным циклам, как и в параллельно-двоичной реализации замки на этапах и постоянные(const) реализует SRL16E. У постоянных соединёны поток ввода с потоком вывода для возможности циклического сдвига.

параллельно-двоичной архитектуре в последовательно-двоичной будет мало эффективен, поэтому используется

не изменённый 2n + 1
При умножении N * N бит получается 2N бит на выходе и требуется 2N циклов, чтобы получить результат. Пропускная способность операторов умножения в этой архитектуре ограничена, потому что минимальный диапазон между последовательными умножителями должен быть хотя бы 2N циклов. В алгоритме IDEA один из сомножителей каждого умножения по модулю это подключ, а он всегда одного размера, можно принять его за постоянную величину.

значение t в умножении разделено на 2 части(строки 7-9),

это старшая и младшая части этого числа, они понадобятся нам далее, желательно, чтобы дизайн позволял считать старшие и младшие части независимо, не запрещяя чтобы все входные, выходные и промежуточные переменные оператора были 16 бит в длину. Используя эту схему и отразив аппаратное воплощение, как будет показано далее, пропускная способность оператора умножения может быть удвоена.

схема последовательного умножителя Лиона которая решила эту проблему. Для

того, чтобы сгенерировать 2 16 битных результата за 16 циклов пропускная способность должна быть удвоена. Это достигается путём дублирования устройства умножения, как показано на картинке выше. Регистры в которых находятся константы доступны для двух частей оператора. Выходные значения p и q соответствуют двум последовательным умножениям, где у двух 32ух битных переменных разница во времени 16 циклов. [Контрольный сигнал, который был выше одного цикла, до того, как наименее значимый бит вошёл в модуль, захватывает контроль над регистром?]. Вектор из входных значений an-1 …a0 из-за этого попеременно перенаправляется на два провода, ведущих в умножители.

был перенаправлен на одну из дорожек, логический ноль выбрал

другую дорожку, чтобы тот нёс дополнительные нули.
Чтобы в итоге старшие и младшие значения t получились выровненными во времени, требуется сдвиг на 16 позиций. Входящие и исходящие значения регистра сдвига это старшие и младшие значения переменной t, соответственно, 16 циклов после t действительны. Сам регистр сдвига реализуется через SRL16E.

архитектура для оператора умножения по модулю. После инициализации подключ,

ассоциируемый с оператором, проходит на него двоично-последовательно. Заранее уменьшенный подключ движется на регистры умножителя и в то же время сохраняется в SRL16E, который должен их хранить.
Используя идею множества дорожек(каналов) умножение достигает 16 циклов и даже считается 32ух битный промежуточный результат. Такая схема увеличивает вдвое пропускную способность, но так как происходит общее использование регистров b цена устройства меньше чем double.

текст каждые 16 циклов, выдавая показатель шифрования: f *

64/16 Мб/сек. на системе с частотой процессора f МГц.
Пример: для 150 МГц это будет 600 Мб/сек.
У каждого раунда задержка равна 109 циклам, задержка конечного преобразования 35 циклов. У каждого преобразователя с последовательной в параллельную архитектуру на выходе задержка получается 16 циклов.
Следовательно в среднем у платы IDEA задержка: 109 * 8 + 35 + 16 = 923 циклов, с чистотой 150 МГц задержка 6,153 мкс.

Плата с 8,5 раундами реализованных нисходящей структурой

в том смысле, что существуют процедуры, позволяющие определить, относится

ли ключ к данному классу, а затем и сам ключ. В настоящее время известны следующие:
223 + 235 + 251 слабых к дифференциальному криптоанализу ключей. Принадлежность к классу 251 можно вычислить за 212 операций с помощью подобранного открытого текста. Авторы данной атаки предложили модификацию алгоритма IDEA. Данная модификация заключается в замене подключей Zi(r) на соответствующие Z′i(r) = a ⊕ Zi(r), где r — номер раунда шифрования. Точное значение a не критично. Например при a = 0xdae данные слабые ключи исключаются[стойкость 6].
263 слабых к линейному дифференциальному криптоанализу ключей[стойкость 7]. Принадлежность к данному классу выясняется с помощью теста на связанных ключах.
253 + 256 + 264 слабых ключей было найдено с использованием метода бумеранга(boomerang attack), предложенного Дэвидом Вагнером(David Wagner)[стойкость 8]. Тест на принадлежность к данному классу выполняется за 216 операций и потребует 216 ячеек памяти [стойкость 9].
Существование столь больших классов слабых ключей не влияет на практическую криптостойкость алгоритма IDEA, так как полное число всех возможных ключей равно 2128.

Шнайер в своей книге «Прикладная криптография», 1996 г. заметил:
«…удивительно,

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