Lucifer — исследовательский проект фирмы IBM 1970-х годов по созданию криптоустойчивого блочного шифра. Результаты исследования привели к созданию двух методов построения устойчивых ко взлому симметричных шифров — сети Фейстеля и подстановочно-перестановочной сети. «Люцифер» заложил основы современной симметричной криптографии. В проекте участвовали ставшие позднее известными криптографами Хорст Фейстель (англ. Horst Feistel) и Дон Копперсмит (англ. Don Coppersmith). Развитие «Люцифера» привело к созданию алгоритма DES.
| Lucifer | |
|---|---|
| Создатель | Хорст Фейстель |
| Создан | 1971—1973 годы |
| Опубликован | 1971—1973 годы |
| Размер ключа | 48/64/128 бит |
| Размер блока | 48/32/128 бит |
| Число раундов | 16 |
| Тип | Подстановочно-перестановочная сеть, сеть Фейстеля |
История
Первая версия алгоритма от 1971 года использовала блоки и ключи длиной по 48 бит и основывалась на SP-сетях. Последующая модификация алгоритма была запатентована в ноябре того же года (U.S. Patent 3 796 830; Nov 1971) и использовала сеть Фейстеля. В патенте содержится как описание собственно самого алгоритма, так и сети Фейстеля. В этом шифре использовались 64-разрядные ключи и 32-битные блоки. И, наконец, последняя версия предложена в 1973 году и оперировала с 128-битными блоками и ключами.
Первая версия
Структура алгоритма Люцифер образца июня 1971 года представляет собой SP-сеть (или подстановочно-перестановочная сеть) — «сэндвич» из слоёв двух типов, используемых по очереди. Первый тип слоя — P-блок разрядности 128 бит, за ним идёт второй слой, представляющий собой 32 модуля, каждый из которых состоит их двух 4-битных S-блоков, чьи соответствующие входы закорочены и на них подаётся одно и то же значение с выхода предыдущего слоя. Но сами блоки подстановок различны (отличаются таблицами замен). На выход модуля подаются значения только с одного из S-блоков, какого конкретно — определяется одним из битов в ключе, номер которого соответствовал номеру S-блока в структуре. Упрощённая схема алгоритма меньшей разрядности и неполным числом раундов приведена на рисунке. В ней используется 16 модулей выбора S-блоков (всего 32 S-блока), таким образом такая схема использует 16-битный ключ.
Рассмотрим теперь, как будет меняться шифротекст в приведённом выше алгоритме при изменении всего одного бита. Для простоты возьмём таблицы замен S-блоков такими, что если на вход S-блока подаются все нули, то и на выходе будут все нули. В реальных системах такие таблицы замен не используются, так как они сильно упрощают работу криптоаналитика, но в нашем примере они наглядно иллюстрируют сильную межсимвольную взаимосвязь при изменении одного бита шифруемого сообщения. Видно, что благодаря первому P-блоку единственная единица сдвигается в центр блока, затем следующий нелинейный S-блок «размножает» её и уже две единицы за счёт следующего P-блока изменяют своё положение и т. д. В конце устройства шифрования благодаря сильной межсимвольной связи выходные биты стали сложной функцией от входных и от используемого ключа. В среднем, на выходе половина бит будет равна «0» и половина — «1».
Вторая и третья версии
В следующей версии алгоритма вместо SP-сети использовалась сеть Фейстеля. По своей сути сеть Фейстеля является альтернативой SP-сетям и используется намного шире. С теоретической точки зрения раундовая функция шифрования может быть сведена к SP-сети, однако сеть Фейстеля является более практичной, так как шифрование и расшифрование может вестись одним и тем же устройством, но с обратным порядком используемых ключей. Вторая и третья версия алгоритма (использующие сеть Фейстеля) оперировали над 32-битными блоками с 64-битным ключом и 128-битными блоками со 128-битными ключами. В последней (третьей) версии раундовая функция шифрования была устроена очень просто — сначала шифруемый подблок пропускался через слой 4-битных S-блоков (аналогично слоям в SP-сетях, только S-блок является константным и не зависит от ключа), затем к нему по модулю 2 добавлялся раундовый ключ, после чего результат пропускался через P-блок.
Примечания
Литература
Ссылки
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
