Khafre

Khafre
Создатель	Ральф Меркл
Создан	1990 г.
Опубликован	1990 г.
Размер ключа	неограничен (кратен 64 бит)
Размер блока	64 бит
Число раундов	неограниченно (кратно 8 бит)
Тип	Сеть Фейстеля

Khafre — второй (вместе с Khufu) алгоритм, предложенный Ральфом Мерклом (Khufu (Хуфу) и Khafre (Хафра) — имена египетских фараонов). Этот алгоритм похож на Khufu, но не нуждается в предварительных вычислениях. S-блоки не зависят от ключа, в Khafre используется фиксированные S-блоки. Алгоритм Khafre не ограничивает максимальное количество раундов алгоритма и максимальный размер ключа, в отличие от Khufu. Однако, размер ключа должен быть кратен 64 битам, а количество раундов — кратным 8. По предположению Меркла с Khafre должны использоваться 64 или 128 битовые ключи, и что в Khafre будет больше этапов, чем в Khufu. Также, каждый этап Khafre сложнее этапа Khufu, это делает Khafre медленнее. Зато для Khafre не нужны никакие предварительные вычисления, что дает возможность быстрее шифровать небольшие порции данных.

История

Непосредственно перед созданием алгоритма, (конец 1990 г.) большая часть существовавших в то время алгоритмов симметричного шифрования было адаптировано под аппаратные реализации, несмотря на то, что аппаратная реализация алгоритма шифрования является более дорогостоящей, чем программная реализация, Это значит — менее доступной для подавляющего большинства потенциальных пользователей.

Так в конце 1990-х Меркл в составе команды криптографов из компании Xerox разработал шифр — Khafre, названный в честь египетского фараона Хафра сына Хуфы. Через год компания Xerox получила патент на алгоритм Khafre, его коммерческое использование было запрещено держателем патента.

Постулаты алгоритма

Алгоритм Khafre — блочный алгоритм, построен на основе сети Фейстеля и удовлетворяет следующим постулатам:

• Программные реализации алгоритмов имеют практически неограниченный (по сравнению с аппаратными шифраторами) объём оперативной и энергонезависимой памяти. Это позволяет алгоритму шифрования использовать большие объёмы памяти для хранения таблиц замен, ключей раундов и т. д.
• Только оптимизированные элементарные операции для использования в программных реализациях используются в данном алгоритме шифрования.

Принципы создания алгоритма

На основе опыта, полученного при проектировании алгоритма DES, были сформулированы следующие принципы:

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

Алгоритм

Параметры алгоритма

Алгоритм шифрует данные блоками с размером 64 бита. Далее в процессе шифрования каждый блок разбивается на 2 субблока с размерами 32 бита каждый.

Алгоритм имеет следующие параметры:

1. Размер блока шифрования 64 бита.
2. Размер ключа шифрования должен быть кратен 64 битам
3. S-блок имеет 8 входных битов и 32 выходных бита. Является постоянным и не зависит от ключа шифрования. В каждом раунде используется свой S-блок.

Построение стандартной таблицы замен

• В первую очередь создается таблица размером 256 строк на 5 столбцов. В 1-ом столбце записаны все возможные значения байтов (от 00 до FF соответственно). Остальные столбцы заполняются такими же значениями. Ниже приведён фрагмент такой таблицы.

Фрагмент стандартной таблицы

байт	4 байта
00	00	00	00	00
01	01	01	01	01
02	02	02	02	02
…	…	…	…	…
FF	FF	FF	FF	FF

• В каждом столбце переставляются байты, качестве псевдослучайной последовательности здесь используется набор из миллиона случайных чисел фирмы RAND Corporation, опубликованный в 1995 году.

Фрагмент стандартной таблицы после перестановок

байт	4 байта
00	FC	21	23	FF
01	E2	27	71	FA
02	DF	B5	BB	29
…	…	…	…	…
FF	30	24	1C	FB

Генерация подключей

1. На первом этапе происходит инициализация ключа 64 байта, а неиспользуемые биты обнуляются.
2. На втором этапе данный блок шифруется алгоритмом Khafre в режиме сцепления блоков шифра. В качестве подключей для каждого октета берётся нулевая последовательность. Получается псевдослучайная 64-байтная последовательность, которая зависит только от ключа шифрования. Вероятно, что для инициализации подключей может понадобиться большее количество байт, так что данный шаг может быть воспроизведён неоднократно.
3. На третьем этапе из полученного набора бит выбираются подключи (K₀..K_n+3).

Процедура шифрования

Исходный текст делится на блоки по 64 бита. В самом начале процедуры данный блок подвергается следующим операциям:

• 64-битный блок данных разделяется на два подблока по 32 бита, L (левый) и R (правый) соответственно.
• Над подблоками осуществляется побитовое XOR с подключами K₀ и K₁ соответственно (для L — K₀, для R — K₁).

После этого начинается шифрование. Количество повторений шагов равно количеству раундов.

1. На первом шаге последние 8 бит левого подблока проходит через S-блок, на выходе которого получается 32 бита. Также в каждом октете операций используются различный S-блоки, предназначенные для текущего октета.
2. На следующем шаге над значением, которое получили на предыдущем этап, выполняется операция XOR с R.
3. На третьем шаге выполняется циклический сдвиг L влево на разное число бит, зависящее от номера раунда в октете:
   • 8 — для 3 и 4 раундов
   • 24 — для 7 и 8 раундов
   • 16 — для других раундов
4. На четвёртом шаге подблоки меняются местам(левый подблок теперь R, правый — L).
5. Шаги с 1 по 4 повторяются 8 раз, при этом для каждого повторения меняются S-Блок
6. На последнем шаге над подблоками снова осуществляется побитовое XOR с подключами K_n+2 и K_n+3(для L — K_n+3, для R — K_n+2, n — номер октета)

После этого все шаги повторяются заново R раз.

Реализация алгоритма

L: int;
R: int;
standardSBoxes: ARRAY [ 1 .. enough/8] OF ARRAY [0 .. 255] OF int;
key: ARRAY [0 .. keysize-1] OF ARRAY [O .. 1] of int;
keyIndex: [0 .. keysize- 1];
rotateschedule: ARRAY [l .. 8] = [16,16,8,8,16,16,24,24];
L = L XOR key[O][O];
R = R XOR key[O][1];
keyIndex = 1 MOD keysize;
octet = 1;
FOR round = 1 TO enough DO
BEGIN
    L = L XOR standardSBoxes[octet] [R AND #FF];
    R = RotateRight[R, rotateSchedule[round mod 8 + 1] 1;
    SWAP[L,R];
    IF round MOD 8 = 0 THEN
    BEGIN
        L = L XOR rotateRight[ key[keyIndex][O], octet];
        R = R XOR rotateRight[ key[keylndex][1], octet];
        keyIndex = keyIndex + 1;
        IF keyIndex = keysize THEN keyIndex = 0;
        octet = octet+1;
    END;
END;

Литература

• Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• Шаблон:Source
• Ralph C. Merkle. Fast Software Encryption Functions // Advances in Cryptology — CRYPTO '90: proceedings (Lecture Notes in Computer Science) : материалы конф. / Advances in Cryptology - CRYPTO '90, Санта-Барбара, Калифорния, США, 11-15 августа 1991. — Springer Berlin Heidelberg, 1991. — С. 476—501. — ISBN 3-540-54508-5. (недоступная ссылка)