Lucifer (криптография)

У этого термина существуют и другие значения, см. Lucifer.

Lucifer
Создатель:	Хорст Фейстель
Создан:	1971—1973 годы
Опубликован:	1971—1973 годы
Размер ключа:	48/64/128 бит
Размер блока:	48/32/128 бит
Число раундов:	16
Тип:	Подстановочно-перестановочная сеть, сеть Фейстеля

Lucifer — исследовательский проект фирмы IBM 1970-х годов по созданию криптоустойчивого блочного шифра. Результаты исследования привели к созданию двух методов построения устойчивых ко взлому симметричных шифров — сети Фейстеля и подстановочно-перестановочной сети. «Люцифер» заложил основы современной симметричной криптографии. В проекте участвовали ставшие позднее известными криптографами Хорст Фейстель (англ. Horst Feistel) и Дон Копперсмит (англ. Don Coppersmith). Развития «Люцифера» привело к созданию алгоритма DES.

История

Первая версия алгоритма от 1971 года использовала блоки и ключи длиной по 48 бит и основывалась на SP-сетях. Последующая модификация алгоритма была запатентована в ноябре того же года (U.S. Patent 3 796 830; Nov 1971) и использовала сеть Фейстеля. В патенте содержится как описание собственно самого алгоритма, так и сети Фейстеля. В этом шифре использовались 64-разрядные ключи и 32-битные блоки. И, наконец, последняя версия предложена в 1973 году и оперировала с 128-битными блоками и ключами.

Первая версия

Модуль, выбирающий используемую таблицу подстановок по битовому ключу

Упрощённая схема S- и P-слоёв в алгоритме «Люцифер» (июнь 1971)

Схема генерации и распространения единиц

Структура алгоритма Люцифер образца июня 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-блок.

Ссылки

• Хорст Файстель. Криптография и компьютерная безопасность Перевод Андрея Винокурова
• Пример реализации Lucifer 128/128

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.