prosvirin_kir 21 дек 2020 в 14:50

RC6. От простого к сложному

7 мин

12K

Криптография*Алгоритмы*

Из песочницы

В этой статье вы узнаете

Кто этот ваш блочный шифр.
Каких принципов придерживались создатели алгоритма.
Как выглядит процесс подготовки ключа.
Алгоритм работы.
И причем тут вообще RC5?

Введение в RC6.

Алгоритм RC6 (Rivest’s Cipher 6) - симметричный блочный шифр, использующий в качестве своей основы сеть Фестеля, разработанный Рональдом Ривестом в 1998 году.

Для начала разберемся с терминологией:

Что значит симметричный?

Есть два типа ~~людей~~ шифров:

Симметричные (то, что нам нужно)
Ассиметричные (как-нибудь в другой раз, бро)

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

Алгоритмы симметричного шифрования:
AES (Advanced Encryption Standard)
3DES (Triple Data Encryption Algorithm )
RC4, RC5, RC6 (Rivest cipher)

В ассиметричном шифровании используется два ключа: открытый и закрытый. Из названий ясно, что открытый ключ может свободно передаваться по каналам связи, а вот закрытый ключ нужно хранить в тайне.

Алгоритмы ассиметричного шифрования:
RSA (Rivest-Shamir-Adleman)
DSA (Digital Signature Algorithm), DSS (Digital Signature Standard)
Diffie-Hellman

Что значит блочный?

Блочное шифрование это один из видов симметричного шифрования. Называется он так, потому что работает с блоками: группами бит, фиксированной длины.

Чтобы стало яснее, рассмотрим один из методов построения блочных шифров: сеть Фестеля.

Какая, какая сеть?

Фестеля. Это конструкция из ячеек. На вход каждой ячейки поступают данные и ключ. А на выходе каждой из них изменённые данные и изменённый ключ.

Чтобы зашифровать информацию ее разбивают на блоки фиксированной длины. Как правило, длина входного блока является степенью двойки.

Алгоритм шифрования:

Каждый из блоков делится на два подблока одинакового размера — левый и правый.
Правый подблок скармливается функции .
После чего умножается по модулю 2 (операция xor) с левым блоком .
Полученный результат в следующем раунде будет играть роль правого подблока.
А правый подблок (без изменений) выступит в роли левого подблока.

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

Далее операции повторяются столько раз, сколько задано раундов.

Замечание. Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи следуют в обратном порядке.

Выглядит это примерно так:

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

Теперь, когда мы разобрались с основными понятиями, попробуем копнуть немного глубже.

RC6 параметризированный алгоритм. Это значит, что его работа зависит от некоторых начальных параметров, которые устанавливаются перед началом его работы. Попробуем понять на примере параметра :

Все основные вычисления, которыми оперирует алгоритм, имеют w~- битные машинные слова в качестве входа и выхода. Как мы уже выяснили, RC6 блочный шифр. Причем входной и выходной блоки имеют 4 регистра A, B, C, D каждый размером по w~- бит. Обычно w=32 . Тогда размер блока будет $4\times 32=128$ бит.

Таким образом является одним из параметров алгоритма, который мы можем задавать. Выпишем их все:

размер слова в битах. Каждое слово содержит слов в байтах. Блоки открытого текста и шифротекста имеют длину побит (т.к. 4 регистра).
количество раундов. Так же размер расширенного массива ключейбудет иметьслово (об этом далее). Допустимые значения $0\leq r\leq 255$ .
количество бит в секретном ключе .
секретный ключ размеров байт: .

Чтобы было ясно, о каком алгоритме идем речь принято писать RC6/w/r/b .

Схема подготовки ключа

Алгоритм подготовки ключа состоит из трех простых этапов и использует две магические константы:

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

Для конкретного мы определяем две величины:

$P_w \leftarrow Odd((e-2)2^w)\\Q_w \leftarrow Odd((\phi-1)2^w)$

где e=2.71828... (экспонента), $\phi=1.61803...$ (золотое сечение). $Odd(\cdot)~-$ операция округления до ближайшего нечетного целого.

Например, если взять w = 32 , то значения получатся такие:

$P32 = 10110111111000010101010101011 = b7e15163\\ Q32 = 10011110001101110110110111001 = 9e3779b9$

Теперь рассмотрим основные этапы. Их три:

1 этап. Конвертация секретного ключа

На этом этапе нужно скопировать секретный ключ из массива K[0...b-1] в массив L[0...c-1] , который состоит из c=b/u слов, где u=w/8- количество байт в слове. Если не кратен w / 8 , то дополняется нулевыми битами до ближайшего большего кратного:

# здесь x<<<y - операции циклического сдвига 

c = [max(b, 1) / u]
for b - 1 downto 0 do
	L[i/u] = (L[i/u]<<<8) + K[i]

2 этап. Инициализация массива ключей

Массив ключей так же называют расширенной таблицей ключей. Она заполняется с помощью тех самых магических констант, которые мы определили ранее:

S[0] = P_w

for i = 1 to 2r + 3 do
	S[i] = S[i - 1] + Q_w

3 этап. Перемешивание

Этот шаг состоит в том, чтобы перемешать секретный ключ, который нам дал пользователь:

# Вход: Пользовательский ключ длинной b байт, скопированный в массив
#			 	L[0,...,c-1]
#				Количество раундов r

# Выход: w-битный массив ключей S[0,...,2r+3]
  
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. Но мы не будем спешить и для того, чтобы было проще понять принцип его работы, рассмотрим предыдущию версию RC5. А также рассмотрим шаги развития этого алгоритма, которые привели Рональда Ривеста к конечному варианту шифра RC6:

Немного про RC5

RC5 блочный шифр, разработанный Рональдом Ривестом в 1994 году. Одно из отличий от RC6 это то, что он имеет два регистра на входе и на выходе вместо четырех. Второе отсутствие операции умножения в процессе вычислений.

Рональд Ривест писал, что при создании этого шифра он придерживался нескольких правил:

RC5 должен быть блочным шифром. Т.е. открытый и зашифрованный текст представляют собой битовые последовательности (блоки) и секретный ключ должен использоваться как в процессе шифрования, так и в процессе расшифровки.
RC5 должен использовать только примитивные операции, реализованные на большинстве процессоров.
RC5 должен быть адаптирован к процессорам с разной длиной машинного слова. Например, когда станут доступны 64-битные процессоры, RC5 сможет на них работать.
RC5 должен быть быстрым. Т.е. основными вычислительными операциями должны быть операторы, которые одновременно работают с целыми словами.
RC5 должен иметь переменное количество раундов. Чтобы пользователь мог выбирать между более высокой скоростью вычислений и более высокой безопасностью.
RC5 должен иметь ключ переменной длины. Чтобы пользователь мог выбрать подходящий для него уровень безопасности.
RC5 должен быть простым в реализации и иметь невысокие требования к памяти.
Последнее, но немаловажное RC5 должен обеспечивать высокую безопасность при выборе подходящих значений параметров.

Процесс подготовки ключа у RC5 точно такой же, как и у RC6. А вот сам алгоритм шифрования и расшифровки проще. Cхема шифрования RC5:

А псевдокод буквально состоит из пяти строчек:

A = A + S[0]
B = B + S[1]
for i = 1 to r do 
  A = ((A xor B)<<<B) + S[2i]
  B = ((B xor A)<<<A) + S[2i + 1]

Здесь стоит отметить, что за один раунд в RC5 одновременно обновляются обе переменные.

Путь от RC5 к RC6

Возьмем от RC5 все самое лучшее:

Простоту
Безопасность
Хорошую эффективность

Рассмотрим основные шаги, которые привели Рональда Ривеста к конечному варианту RC6.

Начнем с базового полу-раундового(переменные обновляются поочередно) алгоритма RC5:

for i = 1 to r do 
{
  A = ((A xor B)<<<B) + S[2i]
  (A, B) = (B, A)
}

Запустим параллельно две копии RC5. Первую на регистрах A и B, а другую на C и D:

for i = 1 to r do 
{
  A = ((A xor B)<<<B) + S[2i]
  C = ((C xor D)<<<D) + S[2i + 1]
  (A, B) = (B, A)
  (C, D) = (D, C)
}

Вместо того, чтобы менять местами A на B и C на D, поменяем регистры (A, B, C, D) = (B, C, D, A). В этом случае вычисления на блоке AB перемешиваются с вычислениями на блоке CD:

for i = 1 to r do 
{
  A = ((A xor B)<<<B) + S[2i]
  C = ((C xor D)<<<D) + S[2i + 1]
  (A, B, C, D) = (B, A, D, C)
}

Далее еще раз смешаем AB и CD переставив циклические сдвиги:

for i = 1 to r do 
{
  A = ((A xor B)<<<D) + S[2i]
  C = ((C xor D)<<<B) + S[2i + 1]
  (A, B, C, D) = (B, A, D, C)
}

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

Частный случай такого преобразования функция f (x) = x (2x + 1) (mod~2^w) , за которой следует сдвиг влево на пять битовых позиций:

for i = 1 to r do
{
	t = (B * (2B + 1))<<<5
  u = (D * (2D + 1))<<<5
  A = ((A xor t)<<<u) + S[2i]
  C = ((C xor u)<<<t) + S[2i + 1]
  (A, B, C, D) = (B, C, D, A)
}

И на десерт сделаем так, чтобы операции, используемые на начальном шаге первого раунда и заключительном шаге последнего раунда отличались от преобразований всех остальных раундов(такая операция, называются pre- и post-whitening):

B = B + S[0]
D = D + S[1]
for i = 1 to r do
{
	t = (B * (2B + 1))<<<5
  u = (D * (2D + 1))<<<5
  A = ((A xor t)<<<u) + S[2i]
  C = ((C xor u)<<<t) + S[2i + 1]
  (A, B, C, D) = (B, C, D, A)
}
A = A + S[2r + 2]
C = C + S[2r + 3]

Теперь после того, как мы тут все замиксовали, посмотрим еще раз на то, что имеем:

Шифрование

Еще раз напомним, что RC6 работает с четырьмя w~- битными регистрами A, B, C, D. Они содержат исходный входной открытый текст, а также выходной шифротекст. Причем первый байт открытого текста или шифротекста помещается в младший байт A, а последний байт в самый старший байт D. Ниже приведен псевдокод:

# Вход: Открытый текст в 4-х w-битных регистрах A, B, C, D
#				Количество раундов 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 xor t)<<<u) + S[2i]
  C = ((C xor 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) = (B, C, D, A) означает параллельное присвоения значений.

Схема одного раунда в алгоритме RC6 выглядит так:

Дешифрование

Для полноты картины еще немного псевдокода по дешифровке:

# Вход: Зашифрованный текст в 4-х w-битных регистрах 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) xor u
  A = ((A - S[2i])>>>u) xor t
}
D = D - S[1]
B = B - S[0]

Что по атакам?

Для варианта алгоритма RC6-128/20/b никаких атак не выявлено. Атаки ~~слева~~ были обнаружены только для варианта алгоритма с числом раундов r<20

Полагается, что лучший вариант атаки на RС6 полный перебор b~- байтового ключа шифрования. Для него потребуется $min(2^{8b}, 2^{1408})$ операций. Однако, было замечено, что за счет значительной памяти и предварительного вычисления можно организовать атаку встреча посередине, которая потребует $min(2^{8b}, 2^{702})$ операций. Что тоже очень много.

Для таких типов атак, как дифференциальный и линейный криптоанализ, приведем следующую таблицу:

Здесь приведены наиболее выгодные цифры для данных атак. Цифры в прямоугольнике обозначают, что требования к данным для успешной атаки превышают $2 ^ {128}$ от общего числа возможных открытых текстов.

Таким образом, приходим к выводу, что RC6 с 20 раундами защищен от дифференциальных и линейных криптоаналитических атак.

Выводы

RC6 - это безопасный, компактный и простой блочный шифр. Он предлагает пользователю хорошую производительность и в тоже время полностью параметризуется: размер ключа шифрования, число раундов и размер машинного слова. Учитывая все это, шифр является достаточно универсальным.

Так же существуют улучшения алгоритма RC6, такие как RC6_en, но о нем как-нибудь в другой раз.

Основные источники

R.L. Rivest (1994) The RC5 Encryption Algorithm
R.L. Rivest, M.J.B. Robshaw, R.Sidney, and Y.L. Yin. (1998) The RC6 Block Cipher
S. Contini, R.L. Rivest, M.J.B. Robshaw and Y.L. Yin. (1998) The Security of the RC6

Теги:

Хабы: