KHAFRE

KHAFRE

В 1990 году Ральф Меркл (Ralf Merkle) предложил два алгоритма. В основе их проектирования лежали следующие принципы:

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

К этому перечню Меркл, возможно, теперь добавил бы «устойчивость к дифференциальному и линейному криптоанализу», ведь в то время эти способы вскрытия не были известны.

KHUFU

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

Хотя части ключа используются для XOR с блоком шифрования в начале и в конце алгоритма, главная цель ключа — генерация S-блоков. Эти S-блоки секретны, по сути они являются частью ключа. Полный размер ключа Khufu равен 512 битам (64 байтам), алгоритм представляет способ генерации S-блоков по ключу. Количество этапов алгоритма остается открытым текстом и рекомендует 16, 24 или 32 этапа. (Он ограничивает выбор количества этапов числами, кратными восьми.)

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

KHAFRE

Khafre — вторая из криптосистем, предложенных Мерклом. (Khufu (Хуфу) и Khafre (Хафр) — это имена египетских фараонов.) По конструкции этот алгоритм похож на Khufu, но он спроектирован для приложений не использующих предварительных вычислений. S-блоки не зависят от ключа. Вместо этого Khafre использует фиксированные S-блоки. Блок шифрования подвергается операции XOR с ключом не только перед первым этапом и после последнего, но и после каждых 8 этапов шифрования.

Меркл предположил, что с Khafree должны использоваться 64- или 128-битовые ключи, и что для Khafre потребуются больше этапов, чем для Khufru. Это наряду с тем, что каждый этап Khafre сложнее этапа Khufu, делает Khafre более медленным. Зато для Khafre не нужны никакие предварительные расчеты, что позволяет быстрее шифровать небольшие порции данных.

В 1990 году Бихам и Шамир применили свой метод дифференциального анализа против Khafre. Им удалось взломать 16-этапный Khafre с помощью вскрытия с выбранным открытым текстом после 1500различных шифрований. На их персональном компьютере это заняло около часа. Преобразование этого вскрытия во вскрытие с известным открытым текстом потребует около 238 шифрований. Khafre с 24 этапами может быть вскрыт с помощью вскрытия с выбранным открытым текстом за 253 шифрования, а с помощью вскрытия с известным открытым текстом — за 259 шифрования.