Шифр Lucifer

Шифр Lucifer — это блочный симметричный шифр, разработанный в начале 1970-х годов группой исследователей корпорации IBM под руководством Хорста Фейстеля. Lucifer стал одним из первых блочных шифров, реализованных на практике, и оказал значительное влияние на развитие криптографии, послужив основой для создания первого федерального стандарта шифрования США (DES). Шифр отличался использованием сети Фейстеля и 128-битным ключом, что для своего времени было значительной длиной.

История

Разработка шифра Lucifer началась в 1970 году в исследовательском центре IBM имени Томаса Дж. Уотсона. Основной целью было создание надёжного алгоритма шифрования для защиты электронных транзакций и данных в компьютерных системах. Руководителем проекта выступил Хорст Фейстель, который ранее занимался вопросами криптографии в рамках проекта «Люцифер» (от лат. Lucifer — «светоносный»), что и дало название шифру.

Первая версия шифра, известная как Lucifer 1, была представлена в 1971 году. Она использовала 128-битный ключ и блок данных размером 128 бит. В 1973 году Национальное бюро стандартов США (NBS, ныне NIST) объявило конкурс на создание федерального стандарта шифрования для защиты несекретной правительственной информации. IBM предложила модифицированную версию Lucifer, адаптированную под требования конкурса. В результате доработок, в том числе под влиянием Агентства национальной безопасности США (АНБ), длина ключа была сокращена до 56 бит, а алгоритм получил название DES (Data Encryption Standard). В 1977 году DES был принят в качестве стандарта.

Несмотря на то, что Lucifer не был принят в качестве стандарта, его архитектура стала основой для многих последующих шифров, включая DES, а также более поздние алгоритмы, такие как ГОСТ 28147-89.

Классификация

Lucifer относится к классу симметричных блочных шифров. Это означает, что для шифрования и расшифрования используется один и тот же ключ, а данные обрабатываются блоками фиксированного размера.

Основные характеристики:

• Тип: симметричный блочный шифр.
• Структура: сеть Фейстеля.
• Размер блока: 128 бит.
• Размер ключа: 128 бит (в оригинальной версии).
• Число раундов: 16 (в оригинальной версии).

Устройство и принцип работы

Сеть Фейстеля

Шифр Lucifer построен на основе сети Фейстеля — структуры, в которой блок данных делится на две половины (левую и правую), и на каждом раунде одна из половин преобразуется с помощью функции раунда, а затем объединяется с другой половиной операцией XOR. После каждого раунда половины меняются местами. Эта схема позволяет использовать одну и ту же функцию для шифрования и расшифрования, что упрощает реализацию.

Раундовая функция

Функция раунда в Lucifer включает следующие операции:

1. Подстановка (S-блоки): данные проходят через нелинейные таблицы замен (S-блоки), которые обеспечивают нелинейность шифра. В Lucifer использовались 4-битные S-блоки, то есть каждый S-блок преобразует 4 бита входных данных в 4 бита выходных.
2. Перестановка (P-блоки): после подстановки выполняется перестановка битов, которая перемешивает данные между S-блоками, обеспечивая лавинный эффект.
3. Сложение с ключом: на каждом раунде к данным применяется операция XOR с раундовым ключом, полученным из основного ключа.

Ключевое расписание

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

Применение

Первоначально шифр Lucifer разрабатывался для использования в коммерческих системах IBM, в частности для защиты данных в банковских терминалах и системах электронных платежей. Однако после принятия DES в качестве стандарта, Lucifer утратил практическое значение. Тем не менее, его концепции и архитектура были использованы в более поздних разработках:

• DES: прямой потомок Lucifer, ставший мировым стандартом на десятилетия.
• ГОСТ 28147-89: российский стандарт шифрования, также использующий сеть Фейстеля, хотя и с другими параметрами.
• Blowfish, Twofish и другие: многие современные шифры основаны на идеях, заложенных в Lucifer.

Критика и уязвимости

Основной критике подвергалась версия Lucifer, адаптированная под DES. Сокращение длины ключа с 128 до 56 бит вызвало подозрения в намеренном ослаблении шифра со стороны АНБ. Впоследствии было доказано, что 56-битный ключ DES уязвим для атак полным перебором (brute-force) при наличии достаточных вычислительных мощностей. Однако оригинальный Lucifer с 128-битным ключом считался стойким к таким атакам на момент создания.

Структура сети Фейстеля в Lucifer также подвергалась анализу на предмет уязвимостей к дифференциальному и линейному криптоанализу. Хотя эти методы были разработаны позже, они показали, что при определённых условиях шифр может быть взломан быстрее, чем полным перебором. Тем не менее, для оригинального Lucifer с 16 раундами и 128-битным ключом такие атаки оставались практическими неэффективными.

Интересные факты

• Название «Lucifer» (лат. «светоносный») было выбрано не случайно: проект символизировал «просвещение» в области криптографии, то есть создание открытого, публично документированного алгоритма, в отличие от секретных военных шифров.
• В 1970-е годы IBM запатентовала Lucifer, но после принятия DES патент был передан в общественное достояние.
• Исходные коды и подробные описания Lucifer были опубликованы в открытой печати, что позволило криптографам всего мира изучать и анализировать алгоритм.

Источники

• Feistel, H. (1973). «Cryptography and Computer Privacy». Scientific American, 228(5), 15–23.
• National Bureau of Standards (1977). «Data Encryption Standard (DES)». FIPS PUB 46.
• Diffie, W., & Hellman, M. (1977). «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer, 10(6), 74–84.
• Schneier, B. (1996). «Applied Cryptography: Protocols, Algorithms, and Source Code in C». John Wiley & Sons.