Khufu — в криптографии симметричный блочный криптоалгоритм, разработанный Ральфом Мерклом в 1990 году в качестве альтернативы DES, исправляющий ряд ее недостатков.

Принципы алгоритма

Основным принципом, рассматриваемым при разработке алгоритма было использование накопленного опыта анализа DES и элементы данного алгоритма с исправлением его недостатков и достижение максимальной стойкости к криптоанализу.

1. Однозначно, 56-битовый размер ключа DES слишком мал и должен быть увеличен.
2. Интенсивное использование перестановок в DES удобно только для аппаратных реализаций, но затрудняет программные реализации. Наиболее быстрые реализации DES выполняют перестановки табличным образом. Просмотр таблицы может обеспечить те же характеристики «рассеяния», что и собственно перестановки, и может сделать реализацию намного более гибкой.
3. S-блоки DES, всего с 64 4-битовыми элементами, слишком малы. Должны увеличиться и S-блоки. Более того, все восемь S-блоков используются одновременно. Хотя это и удобно для аппаратуры, для программной реализации это кажется ненужным ограничением. Должны быть реализованы больший размер S-блоков и последовательное (а не параллельное) их использование.
4. Начальная и заключительная перестановки криптографически бессмысленны, поэтому они должны быть устранены.
5. Все быстрые реализации DES заранее рассчитывают ключи для каждого этапа. Нет смысла усложнять эти вычисления.
6. Критерии проектирования S-блоков должны быть общедоступны.

Алгоритм

Khufu имеет 64-битовый (8 байтный блок) блок: 64-битовый исходный открытый текст разбивается на две 32-битовые половины, именуемые автором как L и R. Над половинами L и R, так же как и над некоторыми частями ключа производится операция XOR. Затем, по аналогии с DES над результатом данной операции производится ряд операций в процессе ряда этапов. На каждом этапе младший значащий байт L используется в качестве исходных входных данных S-блока. У каждого S-блока 8 входных битов и 32 выходных бита. Далее над выбранным 32-битовым блоком в S-блоке производятся операции XOR с R. Затем L циклически сдвигается не несколько из восьми битов, L и R взаимозаменяются — этап завершается. S-блок не является статическим и меняется каждые восемь этапов. После последнего этапа над L и R выполняется операция XOR с другими элементами ключа, L и R объединяются, представляя собой блок шифротекста.

Части ключа используются для XOR с блоком шифрования как в начале, так и в конце алгоритма, но главная цель 512-битного ключа — это генерация секретных S-блоков, которые, по сути, являются частью ключа. Алгоритм предоставляет способ генерации S-блоков по ключу. Количество этапов алгоритма четко не определено, однако, автор заметил, что 8-этапный Khufu чувствителен к вскрытию с выбранным открытым текстом и поэтому рекомендуется использовать 16, 24 или 32 этапов. Количество этапов должно быть кратным восьми, что позволяет применять, к примеру, 64-этапный вариант.

Устойчивость

Устойчивость к дифференциальному криптоанализу алгоритма Khufu основана на использовании зависимых от ключа и секретных S-блоков. Произведено дифференциальное вскрытие 16-этапного Khufu, которое открывает ключ после 2³¹ выбранных открытых текстов, но оно не может быть расширено на большее количество этапов. Поскольку лучшим способом вскрыть Khufu является грубая сила, его надежность довольно высока. 512-битовый ключ алгоритма обеспечивает необходимую сложность, 2⁵¹², что исключает практически возможность восстановления открытого текста.

Литература

• Шнайер, Брюс Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms, and Source Code in C. — Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4