Khufu

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Khufu
Создатель:

Ральф Меркл

Создан:

1990 г.

Опубликован:

1990 г.

Размер ключа:

512 бит

Размер блока:

64 бит

Число раундов:

16-32 (до 64)

Тип:

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

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, которое открывает ключ после 231 выбранных открытых текстов, но оно не может быть расширено на большее количество этапов. Поскольку лучшим способом вскрыть Khufu является грубая сила, его надежность довольно высока. 512-битовый ключ алгоритма обеспечивает необходимую сложность, 2512, что исключает практически возможность восстановления открытого текста.

Литература[править | править вики-текст]

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