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

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

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

История

Первая версия алгоритма от 1971 года использовала блоки и ключи длиной по 48 бит и основывалась на SP-сетях. Последующая модификация алгоритма была запатентована в ноябре того же года ([www.google.com/patents/US3,796,830 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-блок.

Ссылки

• Хорст Файстель. [www.enlight.ru/crypto/articles/feistel/feist_i.htm Криптография и компьютерная безопасность] Перевод Андрея Винокурова
• [cartman-cipher.narod.ru/mirror/lucifer.c Пример реализации Lucifer 128/128]

Отрывок, характеризующий Lucifer (криптография)

Воззрение это, сильно распространенное в высших сферах армии, находило себе поддержку и в Петербурге, и в канцлере Румянцеве, по другим государственным причинам стоявшем тоже за мир.
Пятые были приверженцы Барклая де Толли, не столько как человека, сколько как военного министра и главнокомандующего. Они говорили: «Какой он ни есть (всегда так начинали), но он честный, дельный человек, и лучше его нет. Дайте ему настоящую власть, потому что война не может идти успешно без единства начальствования, и он покажет то, что он может сделать, как он показал себя в Финляндии. Ежели армия наша устроена и сильна и отступила до Дриссы, не понесши никаких поражений, то мы обязаны этим только Барклаю. Ежели теперь заменят Барклая Бенигсеном, то все погибнет, потому что Бенигсен уже показал свою неспособность в 1807 году», – говорили люди этой партии.
Шестые, бенигсенисты, говорили, напротив, что все таки не было никого дельнее и опытнее Бенигсена, и, как ни вертись, все таки придешь к нему. И люди этой партии доказывали, что все наше отступление до Дриссы было постыднейшее поражение и беспрерывный ряд ошибок. «Чем больше наделают ошибок, – говорили они, – тем лучше: по крайней мере, скорее поймут, что так не может идти. А нужен не какой нибудь Барклай, а человек, как Бенигсен, который показал уже себя в 1807 м году, которому отдал справедливость сам Наполеон, и такой человек, за которым бы охотно признавали власть, – и таковой есть только один Бенигсен».
Седьмые – были лица, которые всегда есть, в особенности при молодых государях, и которых особенно много было при императоре Александре, – лица генералов и флигель адъютантов, страстно преданные государю не как императору, но как человека обожающие его искренно и бескорыстно, как его обожал Ростов в 1805 м году, и видящие в нем не только все добродетели, но и все качества человеческие. Эти лица хотя и восхищались скромностью государя, отказывавшегося от командования войсками, но осуждали эту излишнюю скромность и желали только одного и настаивали на том, чтобы обожаемый государь, оставив излишнее недоверие к себе, объявил открыто, что он становится во главе войска, составил бы при себе штаб квартиру главнокомандующего и, советуясь, где нужно, с опытными теоретиками и практиками, сам бы вел свои войска, которых одно это довело бы до высшего состояния воодушевления.
Восьмая, самая большая группа людей, которая по своему огромному количеству относилась к другим, как 99 к 1 му, состояла из людей, не желавших ни мира, ни войны, ни наступательных движений, ни оборонительного лагеря ни при Дриссе, ни где бы то ни было, ни Барклая, ни государя, ни Пфуля, ни Бенигсена, но желающих только одного, и самого существенного: наибольших для себя выгод и удовольствий. В той мутной воде перекрещивающихся и перепутывающихся интриг, которые кишели при главной квартире государя, в весьма многом можно было успеть в таком, что немыслимо бы было в другое время. Один, не желая только потерять своего выгодного положения, нынче соглашался с Пфулем, завтра с противником его, послезавтра утверждал, что не имеет никакого мнения об известном предмете, только для того, чтобы избежать ответственности и угодить государю. Другой, желающий приобрести выгоды, обращал на себя внимание государя, громко крича то самое, на что намекнул государь накануне, спорил и кричал в совете, ударяя себя в грудь и вызывая несоглашающихся на дуэль и тем показывая, что он готов быть жертвою общей пользы. Третий просто выпрашивал себе, между двух советов и в отсутствие врагов, единовременное пособие за свою верную службу, зная, что теперь некогда будет отказать ему. Четвертый нечаянно все попадался на глаза государю, отягченный работой. Пятый, для того чтобы достигнуть давно желанной цели – обеда у государя, ожесточенно доказывал правоту или неправоту вновь выступившего мнения и для этого приводил более или менее сильные и справедливые доказательства.
Все люди этой партии ловили рубли, кресты, чины и в этом ловлении следили только за направлением флюгера царской милости, и только что замечали, что флюгер обратился в одну сторону, как все это трутневое население армии начинало дуть в ту же сторону, так что государю тем труднее было повернуть его в другую. Среди неопределенности положения, при угрожающей, серьезной опасности, придававшей всему особенно тревожный характер, среди этого вихря интриг, самолюбий, столкновений различных воззрений и чувств, при разноплеменности всех этих лиц, эта восьмая, самая большая партия людей, нанятых личными интересами, придавала большую запутанность и смутность общему делу. Какой бы ни поднимался вопрос, а уж рой этих трутней, не оттрубив еще над прежней темой, перелетал на новую и своим жужжанием заглушал и затемнял искренние, спорящие голоса.