RC6

RC6
Сеть Фейстеля алгоритма RC6
Создатель	Рональд Райвест, М. Робшоу, Р. Сидни (RSA Laboratories)
Создан	1998 г.
Опубликован	1998 г.
Размер ключа	128, 192 или 256 бит (от 0 до 2040 бит)
Размер блока	128 бит (для 32-разрядных платформ)
Число раундов	20 (по умолчанию)
Тип	Сеть Фейстеля

RC6 — симметричный блочный криптографический алгоритм, производный от алгоритма RC5. Был создан Роном Ривестом, Мэттом Робшау и Рэем Сиднеем для удовлетворения требований конкурса Advanced Encryption Standard (AES). Алгоритм был одним из пяти финалистов конкурса, был также представлен NESSIE и CRYPTREC. Является собственническим (проприетарным) алгоритмом, и запатентован RSA Security.

Вариант шифра RC6, заявленный на конкурс AES, поддерживает блоки длиной 128 бит и ключи длиной 128, 192 и 256 бит, но сам алгоритм, как и RC5, может быть сконфигурирован для поддержки более широкого диапазона длин как блоков, так и ключей (от 0 до 2040 бит). RC6 очень похож на RC5 по своей структуре и также довольно прост в реализации.

Является финалистом AES, однако одна из примитивных операций — операция умножения, медленно выполняемая на некотором оборудовании и затрудняет реализацию шифра на ряде аппаратных платформ и, что оказалось сюрпризом для авторов, на системах с архитектурой Intel IA-64 также реализована довольно плохо. В данном случае алгоритм теряет одно из своих ключевых преимуществ — высокую скорость выполнения, что стало причиной для критики и одной из преград для избрания в качестве нового стандарта. Однако, на системах с процессором Pentium II, Pentium Pro, Pentium III, PowerPC и ARM алгоритм RC6 опережает победителя — Rijndael.

Детали RC6

Так же, как и RC5, RC6 — полностью параметризированная семья алгоритмов шифрования. Для спецификации алгоритма с конкретными параметрами, принято обозначение RC6-w/r/b, где

• w — длина машинного слова в битах.
• r — число раундов.
• b — длина ключа в битах. Возможные значения 0..255 бит.

Для того чтобы соответствовать требованиям AES, блочный шифр должен обращаться с 128-битовыми блоками. Так как RC5 — исключительно быстрый блочный шифр, расширение его, чтобы работать с 128-битовыми блоками привело бы к использованию двух 64-битовых рабочих регистров. Но архитектура и языки программирования ещё не поддерживают 64-битные операции, поэтому пришлось изменить проект так, чтобы использовать четыре 32-битных регистров вместо двух 64-битных.

Расширение ключа

Генерация констант:

Так же, как и в RC5, в RC6 генерируются две псевдослучайные величины, используя две математические константы:экспонента (e) и золотое сечение (f).

$Q_{w}\leftarrow Odd((f-1)*2^{w})$

$P_{w}\leftarrow Odd((e-2)*2^{w})$,

где $Odd()$ — это округление до ближайшего нечетного целого. При w = 32 бита (в шестнадцатеричном виде):

$Q_{32}=9E3779B9$

$P_{32}=B7E15163$

В десятичном виде:

$P_{32}=3084996963$

$Q_{32}=2654435769$

Процедура расширения ключа для RC6-w/r/b:

Таблица ключей для шифра RC6 также идентична таблице шифра RC5. Отличие состоит в том, что большее количество слов из массива L получено из предоставленного пользователем ключа для использования в течение шифрования и расшифровки.

Вход:

• b-байтный ключ, заданный пользователем, предварительно преобразованный в массив из $c$ слов $L[0,...,c-1]$.
• r — количество раундов.

Выход:

• w-битная таблица ключей $S[0,...,2r+3]$.

>>>, <<< - циклические сдвиги вправо и влево соответственно.

	S[0]=Pw
	for i=1 to 2r+3 do
    		S[i]=S[i-1]+Qw

	A=B=i=j=0

	v=3*max{c,2r+4}
	for s=1 to v do
    	{
        	A=S[i]=(S[i]+A+B)<<<3
        	B=L[j]=(L[j]+A+B)<<<(A+B)
        	i=(i+1) mod (2r+4)
        	j=(j+1) mod c
    	}

Шифрование и расшифрование

RC6 работает с четырьмя w-битными регистрами A, B, C и D, которые содержат входной исходный текст и выходной шифрованный текст в конце шифрования.

Шифрование/Расшифрование с помощью RC6-w/r/b

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

Вход:

• r количество раундов
• w-разрядные ключи для каждого раунда S[0, … , 2r + 3]

Выход:

• шифрованный текст сохраняется в A, B, C и D

	B = B + S[0]
	D = D + S[1]
	for i = 1 to r do
	{
		t = (B(2B + 1)) <<< lg w
		u = (D(2D + 1)) <<< lg w
		A = ((A ⊕ t) <<< u) + S[2i]
		C = ((C ⊕ u) <<< t) + S[2i + 1] 
                (A, B, C, D)  =  (B, C, D, A)

	}
	A = A + S[2r + 2]
	C = C + S[2r + 3]

Процедура расшифровки:

Вход:

• шифрованный текст, сохранённый в A, B, C и D
• r количество раундов
• w-разрядные ключи для каждого раунда S[0, … , 2r + 3]

Выход:

• исходный текст сохраняется в A, B, C и D

	C = C - S[2r + 3]
	A = A - S[2r + 2]

	for i = r downto 1 do
	{
	   (A, B, C, D) = (D, A, B, C)
	    u = (D(2D + 1)) <<< lg w
	    t = (B(2B + 1)) <<< lg w
	    C = ((C - S[2i + 1]) >>> t) ⊕ u
	    A = ((A - S[2i]) >>> u) ⊕ t
	}
	D = D - S[1]
	B = B - S[0]

Безопасность

Вариант алгоритма RC6, который был заявлен на AES, как уже было сказано, поддерживает блоки длиной 128 бит и ключи длиной 128, 192 и 256 бит, а также содержит 20 раундов. То есть RC6-128/20/b, где b=128,192 или 256 бит. В отношении такого алгоритма никаких атак не было обнаружено. Были обнаружены атаки только против упрощенных версий алгоритма, то есть алгоритма с уменьшенным количеством раундов.

Полагается, что лучший вариант нападения на RС6, доступный для криптоаналитика, является полным перебором b-байтового ключа шифрования (или расширенный ключевой массив S [0,…,43], когда предоставленный пользователем ключ шифрования особенно длинный). Для полного перебора требуется $min(2^{8b},2^{1408})$ операций. Дон Копперсмит заметил, что за счет значительной памяти и предварительного вычисления можно организовать атаку встреча посередине, чтобы восстановить расширенный ключевой массив S [0,…,43]. Это потребовало бы $2^{704}$ вычислений и таким образом требуемое количество операций равнялось $min(2^{8b},2^{704})$.

Более продвинутые атаки, такие как дифференциальный и линейный криптоанализ, выполнимые на версиях шифра с маленьким количеством раундов, сложно выполнимы для нападение на полный шифр RC6 с 20 раундами. Сложность состоит в том, что трудно найти хорошие повторяющиеся особенности или линейные приближения, с которыми могла бы быть осуществлена атака.

Интересная проблема — установить соответствующие цели для безопасности против этих более продвинутых атак. Чтобы преуспеть, эти атаки типично требуют большого количества данных, и получение $2^{a}$ блоков известных или выбранных пар зашифрованного\открытого текста — задача отличная от попытки возвратить один ключ из $2^{a}$ возможных. Стоит заметить, что с шифром, работающим со скоростью один терабит в секунду (то есть, шифруя данные со скоростью $10^{12}$ бит/сек), время, требуемое для 50 компьютеров, работающих параллельно, чтобы зашифровать $2^{64}$ блоков данных, составляет более года; зашифровать $2^{80}$ блоков данных — больше чем 98 000 лет; и зашифровать $2^{128}$ блоков данных составляет больше чем $10^{19}$ лет.

Хотя требования к данным для $2^{64}$ блоков для успешной атаки могли бы быть рассмотрены как достаточные в практических сроках, разработчики стремились обеспечивать намного больший уровень безопасности.

Исследования RC5 не проявили слабостей в установке ключа. Это привело к использованию того же процесса установки ключа и в RC6. Процесс преобразования ключа, предоставляемого пользователем, к таблице ключей, кажется, хорошо смоделирован псевдослучайным процессом. Таким образом, в то время как нет доказательства, что никакие два ключа не приводят к одной и той же таблице ключей, это, кажется, очень маловероятно. Это можно оценить как вероятность того, что существуют два 256-битовых ключа, приводящие к одной и той же таблице 44, 32-разрядных ключей, есть приблизительно $2^{2*256-44*32}=2^{-896}=10^{-270}$.

Мы можем суммировать наши требования на безопасности RC6 следующим образом:

— Лучшей атакой на RC6 является полный перебор для обеспеченного пользователем ключа шифрования.

— Требования к данным, чтобы организовать более сложные атаки на RC6, такие как дифференциальный и линейный криптоанализ, превышают доступные данные.

Важным критерием резерва безопасности является максимальное число раундов, при котором возможна атака. Это возможно для 12-, 14- и 15- раундовых вариантов RC6.

Шифр	Количество раундов (b)	Тип атаки	Текст	Байты памяти	Операции
RC6-128/20/b	12	Статистические различия	$2^{94}$	$2^{42}$	$2^{119}$
	14	Статистические различия	$2^{118}$	$2^{112}$	$2^{122}$
	15 (256)	Статистические различия	$2^{119}$	$2^{138}$	$2^{215}$

В четвёртом столбце «Текст» находится информация о количестве блоков незашифрованного и соответствующих им блокам зашифрованного текста данным ключом. В пятом столбце «Байты памяти» записано максимальное количество байтов памяти, которые нужны в произвольной точке осуществления атаки. В шестом столбце «Операции» указано ожидаемое число операций, которые нужно произвести для осуществления атаки.

Оценка аппаратных средств

Для большинства приложений внедрение RC6 в программное обеспечение — вероятно, лучший выбор. Примитивные операции RC6 (сложение, вычитание, умножение, исключающее или, смещение) очень хорошо поддерживаются современными микропроцессорами и поэтому при разработке этих процессоров выгодно это учитывать.

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

С 20 раундами на блок время шифрования приблизительно равно 100 наносекунд для каждого блока, обеспечивая предполагаемую скорость передачи данных приблизительно 1.3 Гбит/сек.

Выполнение

Как следует из описания алгоритма, RС6 — очень компактен. Действительно, реализация алгоритма RC6 на Ассемблере для микропроцессора Intel Pentium Pro может быть осуществлена в менее чем 256 байтах кода для каждой из задач:

1. установки ключа,
2. блока шифрования,
3. блока дешифрования.

В отличие от многих других алгоритмов шифрования RC6 не использует справочные таблицы во время шифрования. Это означает, код RC6 и данные могут помещаться в современной кэш памяти и тем самым экономить место в памяти.

Учитывая, что RC6 полностью параметризуется, и что он может быть эффективно и компактно осуществлен, шифр кажется особенно универсальным.

Гибкость и направления развития

Как мы уже заметили, RC6 предоставляет пользователю большую гибкость относительно размера ключа шифрования, числа раундов и размера слова основного вычислительного модуля.

В то время как RC6, представленный для рассмотрения на AES, базируется на использования 32-разрядных слов (размер блока 128 бит), будущая потребность рынка нуждается в расширении RC6 для других размеров блока. Наибольшую важность представляют размеры блока в 256 бит, которые использовали бы размер слова 64 бит и производительность, предлагаемую следующим поколением системной архитектуры. Также отметим, что структура RC6 позволяет эксплуатировать определенную степень параллелизма в подпрограммах расшифровки и шифровании. Например, вычисление t и u в каждом раунде может быть вычислено параллельно, как и обновления A и C. Поскольку процессоры развиваются в направлении увеличения количества внутреннего параллелизма (например, с перемещением к суперскалярной архитектуре), реализации RC6 должны продемонстрировать большую производительность.

Лицензирование

Так как RC6 не был выбран в качестве AES, то нет гарантий, что его использование является свободным. С января 2007 веб-страница официального сайта RSA Laboratories, разработчика RC6, содержит следующее:

«We emphasize that if RC6 is selected for the AES, RSA Security will not require any licensing or royalty payments for products using the algorithm» («Мы подчеркиваем, что если RC6 будет выбран в качестве AES, то RSA Security не будет требовать каких либо лицензионных или авторских отчислений за продукты, использующие алгоритм»).

Выделенное слово «если» означает, что RSA Security Inc. теперь может требовать лицензионные и авторские платежи за любой продукт, который использует алгоритм RC6. RC6 является запатентованным алгоритмом шифрования (U.S. Patent 5 724 428 и U.S. Patent 5 835 600).

Источники

• R.L. Rivest, M.J.B. Robshaw, R.Sidney, and Y.L. Yin. The RC6 Block Cipher. v1.1, August 1998.
• J. Beuchat FPGA Implementations of the RC6 Block Cipher.

Внешние ссылки

• SCAN’s entry on RC6 Архивировано 28 января 2012 года.
• RSA Security’s RC6 page
• Спецификация алгоритма RC6 (недоступная ссылка)