Khufu

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

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

Историческая справка

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

Так в конце 1990-х годов группа криптографов из компании Xerox разработала шифр Khufu, названный в честь египетского фараона Хеопса. На добровольной основе алгоритм был передан Агентству национальной безопасности ещё до публикации и патентования. Беспокоясь о безопасности, АНБ попросило Xerox не публиковать данный алгоритм. Разумеется, данное требование было соблюдено со стороны Xerox. Однако, один из редакторов отослал копию алгоритма Джону Гилмору, который выложил алгоритм в открытый доступ, что было против воли Меркела. В дальнейшем, алгоритм был представлен в 1990 году на конференции CRYPTO.

Алгоритм

Введение

Ральфу Мерклу удалось создать алгоритм шифрования, опирающийся на два основных постулата (описанные в спецификации алгоритмов):

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

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

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

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

Описание алгоритма

Алгоритм Khufu - блочный алгоритм, в основе которого лежит сеть Фейстеля.

Основные параметры алгоритма

1. Размер блока шифрования равен 64 бит.
2. Размер ключа шифрования должен лежать в пределах от 64 бит до 512 бит. При этом размер ключа обязательно должен быть кратен 64.
3. Алгоритм состоит из N раундов преобразований, где N - любое число кратное 8.

Этапы шифрования

1. На первом этапе (аналогично алгоритму DES) 64-битный блок данных делится на два блока по 32 бита (в дальнейшем, будем называть их L и R соответственно).
2. На втором этапе над каждым из подблоков осуществляется побитовое XOR с подключами K₁ и K₂ соотвественно (для левого подблока - K₁, для правого - K₂). Процедуру вычисления подключей можно посмотреть здесь.
3. На третьем этапе младший байт (последние 8 бит) левого подблока проходить через таблицу замен, на основе которое получается 4-байтное (32-битное) значение. При чём, в каждом октете операций (октет, в данном случае, называем набор из восьми раундов шифрования) используется новая таблица замен. Алгоритм построения таблицы описан здесь.
4. На четвёртом этапе значение, полученное на предыдущем этапе складывается побитово (XOR) с правым подблоком текста.
5. На пятом этапе выполняется циклический сдвиг влево на различное число бит левого подблока, алгоритм которого зависит от номера раунда в октете:
   • 8 - если номер равен 3 или 4
   • 24 - если номер равен 7 или 8
   • 16 - во всех остальных случаях
6. На шестом этапе левый и правый подблоки меняются местами
7. На седьмом этапе выполняется сложение, аналогичное второму этапу, но с другими ключами K₃ и K₄ соответственно

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

Основная идея алгоритма Khufu заключается именно в зависимости подключей и таблицы замен (фактически S-блоков) от раундового ключа, что делает программную реализацию более эффективной. Вместо того чтобы вычислять 6 блоков замен, как в алгоритме DES, алгоритм Khufu использует только одну замену последних 8-бит левого подблока на 32 бита. Рассмотрим алгоритм построения таблиц и подключей. Он строится в несколько этапов.

Этапы построения таблиц замен

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

Построение таблицы

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

Фрагмент инициализируемой таблицы

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

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

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

байт	4 байта
00	FA	A1	22	41
01	71	88	B3	15
FF	44	11	C4	E1

• После данных итераций происходит формирование таблицы замен. Фрагмент данной таблицы указан выше.

Устойчивость и использование

Из представленного выше описания алгоритма видно, что основное достоинство алгоритма Khufu - это зависимость таблиц замен и подключей от раунда шифрования, а, следовательно, и ключа шифрования. Это существенно увеличивает стойкость алгоритма против дифференциального криптоанализа. Отсюда следует основная спецификация данного алгоритма: алгоритм Khufu должен использоваться там, где необходимо скоростное шифрование больших объёмов данных с редкой сменой ключа. При достаточно частой смене ключа данный алгоритм неэффективен, поскольку вычисление таблиц замен и подключей довольно дорогая и длительная процедура, что делает алгоритм неэффективным с точки зрения времени выполнения.

Атаки на шифр

Наилучшая атака на шифр Khufu произведёна Гилбертом и Шово. Атака произведена на 16-раундовый Khufu. Для того чтобы полностью вскрыть скрытую информацию потребовалось 2³¹ выбранных открытых текстов. Но этот результат не удалось расширить на большее количество раундов.

Грубая сила

Шифр устойчив к атаке методом грубой силы. 512-битовый ключ обеспечивает сложность вскрытия 2⁵¹² что делает шифр устойчив к данному методу.

См. также

• A Million Random Digits with 100,000 Normal Deviates

Литература

• Шнайер, Брюс. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms, and Source Code in C. — Триумф, 2002. — 816 с. — 3000 экз. — ISBN 5-89392-055-4.
• Панасенко С. П. Алгоритмы шифрования. Специальный справочник.. — СПб.: БХВ-Петербург, 2009. — 576 с. — ISBN 978-5-9775-0319-8.
• Жданов О.Н., Золоторёв В.В. Методы и средства криптографической защиты информации: Учебное пособие.. — Красноярск: БХВ-Петербург, 2007. — 217 с.
• Knudsen, Lars. Fast software encryption.. — Bergen, Norway, 1999. — ISBN 3-540-66226-X.

Отрывок, характеризующий Khufu

– Все пропало? – повторил он. – Ежели бы я был не я, а красивейший, умнейший и лучший человек в мире, и был бы свободен, я бы сию минуту на коленях просил руки и любви вашей.
Наташа в первый раз после многих дней заплакала слезами благодарности и умиления и взглянув на Пьера вышла из комнаты.
Пьер тоже вслед за нею почти выбежал в переднюю, удерживая слезы умиления и счастья, давившие его горло, не попадая в рукава надел шубу и сел в сани.
– Теперь куда прикажете? – спросил кучер.
«Куда? спросил себя Пьер. Куда же можно ехать теперь? Неужели в клуб или гости?» Все люди казались так жалки, так бедны в сравнении с тем чувством умиления и любви, которое он испытывал; в сравнении с тем размягченным, благодарным взглядом, которым она последний раз из за слез взглянула на него.
– Домой, – сказал Пьер, несмотря на десять градусов мороза распахивая медвежью шубу на своей широкой, радостно дышавшей груди.
Было морозно и ясно. Над грязными, полутемными улицами, над черными крышами стояло темное, звездное небо. Пьер, только глядя на небо, не чувствовал оскорбительной низости всего земного в сравнении с высотою, на которой находилась его душа. При въезде на Арбатскую площадь, огромное пространство звездного темного неба открылось глазам Пьера. Почти в середине этого неба над Пречистенским бульваром, окруженная, обсыпанная со всех сторон звездами, но отличаясь от всех близостью к земле, белым светом, и длинным, поднятым кверху хвостом, стояла огромная яркая комета 1812 го года, та самая комета, которая предвещала, как говорили, всякие ужасы и конец света. Но в Пьере светлая звезда эта с длинным лучистым хвостом не возбуждала никакого страшного чувства. Напротив Пьер радостно, мокрыми от слез глазами, смотрел на эту светлую звезду, которая, как будто, с невыразимой быстротой пролетев неизмеримые пространства по параболической линии, вдруг, как вонзившаяся стрела в землю, влепилась тут в одно избранное ею место, на черном небе, и остановилась, энергично подняв кверху хвост, светясь и играя своим белым светом между бесчисленными другими, мерцающими звездами. Пьеру казалось, что эта звезда вполне отвечала тому, что было в его расцветшей к новой жизни, размягченной и ободренной душе.


С конца 1811 го года началось усиленное вооружение и сосредоточение сил Западной Европы, и в 1812 году силы эти – миллионы людей (считая тех, которые перевозили и кормили армию) двинулись с Запада на Восток, к границам России, к которым точно так же с 1811 го года стягивались силы России. 12 июня силы Западной Европы перешли границы России, и началась война, то есть совершилось противное человеческому разуму и всей человеческой природе событие. Миллионы людей совершали друг, против друга такое бесчисленное количество злодеяний, обманов, измен, воровства, подделок и выпуска фальшивых ассигнаций, грабежей, поджогов и убийств, которого в целые века не соберет летопись всех судов мира и на которые, в этот период времени, люди, совершавшие их, не смотрели как на преступления.
Что произвело это необычайное событие? Какие были причины его? Историки с наивной уверенностью говорят, что причинами этого события были обида, нанесенная герцогу Ольденбургскому, несоблюдение континентальной системы, властолюбие Наполеона, твердость Александра, ошибки дипломатов и т. п.
Следовательно, стоило только Меттерниху, Румянцеву или Талейрану, между выходом и раутом, хорошенько постараться и написать поискуснее бумажку или Наполеону написать к Александру: Monsieur mon frere, je consens a rendre le duche au duc d'Oldenbourg, [Государь брат мой, я соглашаюсь возвратить герцогство Ольденбургскому герцогу.] – и войны бы не было.
Понятно, что таким представлялось дело современникам. Понятно, что Наполеону казалось, что причиной войны были интриги Англии (как он и говорил это на острове Св. Елены); понятно, что членам английской палаты казалось, что причиной войны было властолюбие Наполеона; что принцу Ольденбургскому казалось, что причиной войны было совершенное против него насилие; что купцам казалось, что причиной войны была континентальная система, разорявшая Европу, что старым солдатам и генералам казалось, что главной причиной была необходимость употребить их в дело; легитимистам того времени то, что необходимо было восстановить les bons principes [хорошие принципы], а дипломатам того времени то, что все произошло оттого, что союз России с Австрией в 1809 году не был достаточно искусно скрыт от Наполеона и что неловко был написан memorandum за № 178. Понятно, что эти и еще бесчисленное, бесконечное количество причин, количество которых зависит от бесчисленного различия точек зрения, представлялось современникам; но для нас – потомков, созерцающих во всем его объеме громадность совершившегося события и вникающих в его простой и страшный смысл, причины эти представляются недостаточными. Для нас непонятно, чтобы миллионы людей христиан убивали и мучили друг друга, потому что Наполеон был властолюбив, Александр тверд, политика Англии хитра и герцог Ольденбургский обижен. Нельзя понять, какую связь имеют эти обстоятельства с самым фактом убийства и насилия; почему вследствие того, что герцог обижен, тысячи людей с другого края Европы убивали и разоряли людей Смоленской и Московской губерний и были убиваемы ими.
Для нас, потомков, – не историков, не увлеченных процессом изыскания и потому с незатемненным здравым смыслом созерцающих событие, причины его представляются в неисчислимом количестве. Чем больше мы углубляемся в изыскание причин, тем больше нам их открывается, и всякая отдельно взятая причина или целый ряд причин представляются нам одинаково справедливыми сами по себе, и одинаково ложными по своей ничтожности в сравнении с громадностью события, и одинаково ложными по недействительности своей (без участия всех других совпавших причин) произвести совершившееся событие. Такой же причиной, как отказ Наполеона отвести свои войска за Вислу и отдать назад герцогство Ольденбургское, представляется нам и желание или нежелание первого французского капрала поступить на вторичную службу: ибо, ежели бы он не захотел идти на службу и не захотел бы другой, и третий, и тысячный капрал и солдат, настолько менее людей было бы в войске Наполеона, и войны не могло бы быть.
Ежели бы Наполеон не оскорбился требованием отступить за Вислу и не велел наступать войскам, не было бы войны; но ежели бы все сержанты не пожелали поступить на вторичную службу, тоже войны не могло бы быть. Тоже не могло бы быть войны, ежели бы не было интриг Англии, и не было бы принца Ольденбургского и чувства оскорбления в Александре, и не было бы самодержавной власти в России, и не было бы французской революции и последовавших диктаторства и империи, и всего того, что произвело французскую революцию, и так далее. Без одной из этих причин ничего не могло бы быть. Стало быть, причины эти все – миллиарды причин – совпали для того, чтобы произвести то, что было. И, следовательно, ничто не было исключительной причиной события, а событие должно было совершиться только потому, что оно должно было совершиться. Должны были миллионы людей, отрекшись от своих человеческих чувств и своего разума, идти на Восток с Запада и убивать себе подобных, точно так же, как несколько веков тому назад с Востока на Запад шли толпы людей, убивая себе подобных.
Действия Наполеона и Александра, от слова которых зависело, казалось, чтобы событие совершилось или не совершилось, – были так же мало произвольны, как и действие каждого солдата, шедшего в поход по жребию или по набору. Это не могло быть иначе потому, что для того, чтобы воля Наполеона и Александра (тех людей, от которых, казалось, зависело событие) была исполнена, необходимо было совпадение бесчисленных обстоятельств, без одного из которых событие не могло бы совершиться. Необходимо было, чтобы миллионы людей, в руках которых была действительная сила, солдаты, которые стреляли, везли провиант и пушки, надо было, чтобы они согласились исполнить эту волю единичных и слабых людей и были приведены к этому бесчисленным количеством сложных, разнообразных причин.
Фатализм в истории неизбежен для объяснения неразумных явлений (то есть тех, разумность которых мы не понимаем). Чем более мы стараемся разумно объяснить эти явления в истории, тем они становятся для нас неразумнее и непонятнее.
Каждый человек живет для себя, пользуется свободой для достижения своих личных целей и чувствует всем существом своим, что он может сейчас сделать или не сделать такое то действие; но как скоро он сделает его, так действие это, совершенное в известный момент времени, становится невозвратимым и делается достоянием истории, в которой оно имеет не свободное, а предопределенное значение.
Есть две стороны жизни в каждом человеке: жизнь личная, которая тем более свободна, чем отвлеченнее ее интересы, и жизнь стихийная, роевая, где человек неизбежно исполняет предписанные ему законы.
Человек сознательно живет для себя, но служит бессознательным орудием для достижения исторических, общечеловеческих целей. Совершенный поступок невозвратим, и действие его, совпадая во времени с миллионами действий других людей, получает историческое значение. Чем выше стоит человек на общественной лестнице, чем с большими людьми он связан, тем больше власти он имеет на других людей, тем очевиднее предопределенность и неизбежность каждого его поступка.