В этой статье вы узнаете
-
Кто этот ваш блочный шифр.
-
Каких принципов придерживались создатели алгоритма.
-
Как выглядит процесс подготовки ключа.
-
Алгоритм работы.
-
И причем тут вообще 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) с левым блоком .
-
Полученный результат в следующем раунде будет играть роль правого подблока.
-
А правый подблок(без изменений) выступит в роли левого подблока.
Раундом в батле криптографии называют один из последовательных шагов(циклов) обработки данных в алгоритме блочного шифрования. ключ на - ом раунде (рассмотрим позже).
Далее операции повторяются столько раз, сколько задано раундов.
Замечание. Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи следуют в обратном порядке.
Выглядит это примерно так:
Параметры алгоритма
Теперь, когда мы разобрались с основными понятиями, попробуем копнуть немного глубже.
RC6 параметризированный алгоритм. Это значит, что его работа зависит от некоторых начальных параметров, которые устанавливаются перед началом его работы. Попробуем понять на примере параметра :
Все основные вычисления, которыми оперирует алгоритм, имеют битные машинные слова в качестве входа и выхода. Как мы уже выяснили, RC6 блочный шифр. Причем входной и выходной блок имеют 4 регистра A, B, C, D каждый размером по бит. Обычно . Тогда размер блока будет бит.
Таким образом является одним из параметров алгоритма, который мы можем задавать. Выпишем их все:
Чтобы было ясно, о каком алгоритме идем речь принято писать .
Схема подготовки ключа
Алгоритм подготовки ключа состоит из трех простых этапов и использует две магические константы:
Генерация констант
Для конкретного мы определяем две величины:
где (экспонента), (золотое сечение). операция округления до ближайшего нечетного целого.
Например, если взять , то значения получатся такие:
Теперь рассмотрим основные этапы. Их три:
1 этап. Конвертация секретного ключа
На этом этапе нужно скопировать секретный ключ из массивав массив , который состоит из слов, где количество байт в слове. Если не кратен , то дополняется нулевыми битами до ближайшего большего кратного:
# здесь 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, как указано выше, будем использовать измененные версии этих регистров. Проще говоря, мы хотим сделать так, чтобы величина циклического сдвига зависела от битов входного слова.
Частный случай такого преобразования функция , за которой следует сдвиг влево на пять битовых позиций:
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 работает с четырьмя битными регистрами 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С6 полный перебор байтового ключа. шифрования. Для него потребуется операций. Однако, было замечено, что за счет значительной памяти и предварительного вычисления можно организовать атаку встреча посередине, которая потребует операций. Что тоже очень много.
Для таких типов атак, как дифференциальный и линейный криптоанализ приведем следующую таблицу:
Здесь приведены наиболее выгодные цифры для данных атак. Цифры в прямоугольнике обозначает, что требования к данным для успешной атаки превышают от общего числа возможных открытых текстов.
Таким образом, приходим к выводу, что 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
Комментариев нет:
Отправить комментарий