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, были сформулированы следующие принципы:
- 56-битовый размер ключа DES стало возможно увеличить, так как цена памяти стала пренебрежимо мала.
- Интенсивное использование перестановок в DES удобно только для аппаратных реализаций, но затрудняет программные реализации. Наиболее быстрые реализации DES выполняют перестановки табличным образом. Просмотр таблицы может обеспечить те же характеристики «рассеяния», что и собственно перестановки и может сделать реализацию более гибкой.
- S-блоки DES, всего с 64 4-битовыми элементами, слишком малы. Так как память стала дешевле, появилась возможность увеличить и S-блоки. Более того, все восемь S-блоков используются одновременно. Хотя это и удобно для аппаратуры, для программной реализации это не нужно. Должно быть реализовано последовательное (а не параллельное) использование S-блоков.
- Необходимо устранить начальные и конечные перестановки, так как они криптографически бессмысленны
- Все быстрые реализации DES заранее рассчитывают ключи для каждого этапа. При данном условии нет смысла усложнять эти вычисления.
- Критерии проектирования S-блоков должны быть общедоступны, в отличие от DES
Алгоритм
[править | править код]Параметры алгоритма
[править | править код]Алгоритм шифрует данные блоками с размером 64 бита. Далее в процессе шифрования каждый блок разбивается на 2 субблока с размерами 32 бита каждый.
Алгоритм имеет следующие параметры:
- Размер блока шифрования 64 бита.
- Размер ключа шифрования должен быть кратен 64 битам
- 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 |
Генерация подключей
[править | править код]- На первом этапе происходит инициализация ключа 64 байта, а неиспользуемые биты обнуляются.
- На втором этапе данный блок шифруется алгоритмом Khafre в режиме сцепления блоков шифра. В качестве подключей для каждого октета берётся нулевая последовательность. Получается псевдослучайная 64-байтная последовательность, которая зависит только от ключа шифрования. Вероятно, что для инициализации подключей может понадобиться большее количество байт, так что данный шаг может быть воспроизведён неоднократно.
- На третьем этапе из полученного набора бит выбираются подключи (K0..Kn+3).
Процедура шифрования
[править | править код]Исходный текст делится на блоки по 64 бита. В самом начале процедуры данный блок подвергается следующим операциям:
- 64-битный блок данных разделяется на два подблока по 32 бита, L (левый) и R (правый) соответственно.
- Над подблоками осуществляется побитовое XOR с подключами K0 и K1 соответственно (для L — K0, для R — K1).
После этого начинается шифрование. Количество повторений шагов равно количеству раундов.
- На первом шаге последние 8 бит левого подблока проходит через S-блок, на выходе которого получается 32 бита. Также в каждом октете операций используются различный S-блоки, предназначенные для текущего октета.
- На следующем шаге над значением, которое получили на предыдущем этап, выполняется операция XOR с R.
- На третьем шаге выполняется циклический сдвиг L влево на разное число бит, зависящее от номера раунда в октете:
- 8 — для 3 и 4 раундов
- 24 — для 7 и 8 раундов
- 16 — для других раундов
- На четвёртом шаге подблоки меняются местам(левый подблок теперь R, правый — L).
- Шаги с 1 по 4 повторяются 8 раз, при этом для каждого повторения меняются S-Блок
- На последнем шаге над подблоками снова осуществляется побитовое XOR с подключами Kn+2 и Kn+3(для L — Kn+3, для R — Kn+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;
Примечания
[править | править код]- ↑ Ralph C. Merkle. Fast Software Encryption Fucntions // Advances in cryptology. — С. 482—483.
Литература
[править | править код]- Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
- Панасенко С. П. Глава 3 // Алгоритмы шифрования. Специальный справочник — СПб.: BHV-СПб, 2009. — С. 288—295. — 576 с. — ISBN 978-5-9775-0319-8
- 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. (недоступная ссылка)