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-блок.

Литература

• Alan G. Konheim. Computer Security and Cryptography. — United States of America: WILEY, 2007. — С. 283—287. — 544 с. — ISBN 978-0-471-94783-7.
• Horst Feistel. Cryptography and Computer Privacy // Scientific American. — 1973. — Vol. 228, № 05. — С. 15—23.
• Сергей Панасенко. Аглоритмы шифрования. Специальный справочник. — Санкт-Петербург: БХВ-Петербург, 2009. — С. 301—312. — 576 с. — ISBN 978-5-9775-0319-8.

Ссылки

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