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 бит)^[1]. RC6 очень похож на RC5 по своей структуре и также довольно прост в реализации.

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

Детали 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$

Процедура расширения ключа для 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 на языке C#

В данной реализации используется размер слова W = 32 бита, что соответствует размеру блока в 128 бит. Число раундов R = 16. Ключ K определяется пользователем самостоятельно.

using System;
using System.IO;
using System.Collections.Generic;
 
namespace RC6
{
    class RC6
    {
        // Константы для операций свига
        public const int W = 32;
        public const int R = 16;
 
        // Переменные для работы с файлами
        public Byte[] fileData;
        public uint fileLength;
 
        // Список расшифрованных / рашифрованных данных
        public List<Byte> resultData = new List<Byte>();
 
        // Крипто-ключ
        public UInt32[] key = new UInt32[2 * R + 4];
 
        // Функция записи данных в файл
        public void WriteByteArrayToFile(Byte[] buffer, string fileName)
        {
            try
            {
                FileStream fs = new FileStream(fileName, FileMode.Create, FileAccess.ReadWrite);
                BinaryWriter bw = new BinaryWriter(fs);
 
                for (int i = 0; i < fileLength; i++)
                    bw.Write(buffer[i]);
 
                bw.Close();
                fs.Close();
            }
            catch (Exception ex)
            {
                // Опущено для реализации под различными типами проектов
            }
        }
 
        // Функция чтения данных из файла
        public Byte[] ReadByteArrayFromFile(string fileName)
        {   
            Byte[] buffer = null;
 
            try
            {
                FileStream fs = new FileStream(fileName, FileMode.Open, FileAccess.Read);
                BinaryReader br = new BinaryReader(fs);
 
                long numBytes = new FileInfo(fileName).Length;
                buffer = br.ReadBytes((int)numBytes);
 
                br.Close();
                fs.Close();
            }
            catch (Exception ex)
            {
                // Опущено для реализации под различными типами проектов
            }
 
            return buffer;
        }
 
        // Функция сдвига вправо
        public UInt32 RightShift(UInt32 z_value, int z_shift)
        {
            return ((z_value >> z_shift) | (z_value << (W - z_shift)));
        }
 
        // Функция сдвига влево
        public UInt32 LeftShift(UInt32 z_value, int z_shift)
        {
            return ((z_value << z_shift) | (z_value >> (W - z_shift)));
        }
 
        // Функция определения числа сдвигов
        public int OffsetAmount(int dwVar)
        {
            int nLgw = (int)(Math.Log((double)W) / Math.Log(2.0));
 
            dwVar = dwVar << (W - nLgw);
            dwVar = dwVar >> (W - nLgw);
 
            return dwVar;
        }
 
        // Функция генерации ключа
        public void KeyGen(UInt32 dwKey)
        {
            UInt32 P32 = 0xB7E15163;
            UInt32 Q32 = 0x9E3779B9;
            UInt32 i, A, B;
            UInt32 dwByteOne, dwByteTwo, dwByteThree, dwByteFour;
 
            dwByteOne = dwKey >> 24;
            dwByteTwo = dwKey >> 8;
            dwByteTwo = dwByteTwo & 0x0010;
            dwByteThree = dwKey << 8;
            dwByteThree = dwByteThree & 0x0100;
            dwByteFour = dwKey << 24;
 
            dwKey = dwByteOne | dwByteTwo | dwByteThree | dwByteFour;
 
            key[0] = P32;
 
            for (i = 1; i < 2 * R + 4; i++)
                key[i] = key[i - 1] + Q32;
 
            i = A = B = 0;
 
            int v = 3 * Math.Max(1, 2 * R + 4);
 
            for (int s = 1; s <= v; s++)
            {
                A = key[i] = LeftShift(key[i] + A + B, OffsetAmount(3));
                B = dwKey = LeftShift(dwKey + A + B, OffsetAmount((int)(A + B)));
 
                i = (i + 1) % (2 * R + 4);
            }
        }
 
        // Функция преобразования массива UInt32 к списку байт
        public void ConvertFromUInt32ToByteArray(UInt32[] array)
        {
            List<byte> results = new List<byte>();
 
            foreach (UInt32 value in array)
            {
                byte[] converted = BitConverter.GetBytes(value);
                results.AddRange(converted);
            }
 
            // Формирование списка зашифрованных / расшифрванных байт данных
            resultData.AddRange(results);
        }
 
        // Функия преобразования массива байт в массив UInt32 (подогнана под текущую задачу)
        public UInt32[] ConvertFromByteArrayToUIn32(byte[] array, int position)
        {
            List<UInt32> results = new List<UInt32>();
            // Размер блока конвертируемых данных. Читаем по 16 байт.
            int length = position + 16;                 
 
            for (int i = position; i < length; i += 4)
            {
                byte[] temp = new byte[4];
 
                for (int j = 0; j < 4; ++j)
                {
                    if (i + j < array.Length)
                        temp[j] = array[i + j];
                    else
                        temp[j] = 0x00;         // заполняем недостающие блоки в случае достижения
                                                // конца файла
                }
 
                results.Add(BitConverter.ToUInt32(temp, 0));
            }
 
            return results.ToArray();
        }
 
        // Функция расшифровки файла
        public void DecodeFile()
        {
            UInt32[] pdwTemp;
 
            for (int i = 0; i < fileLength; i += 16)
            {
                pdwTemp = ConvertFromByteArrayToUIn32(fileData, i);
 
                pdwTemp[1] = (pdwTemp[1] + key[0]);
                pdwTemp[3] = (pdwTemp[3] + key[1]);
 
                for (int j = 1; j <= R; j++)
                {
                    UInt32 t = LeftShift((pdwTemp[1] * (2 * pdwTemp[1] + 1)),
                                        OffsetAmount((int)(Math.Log((double)W) / Math.Log(2.0))));
                    UInt32 u = LeftShift((pdwTemp[3] * (2 * pdwTemp[3] + 1)),
                                        OffsetAmount((int)(Math.Log((double)W) / Math.Log(2.0))));
 
                    pdwTemp[0] = (LeftShift(pdwTemp[0] ^ t, OffsetAmount((int)u)) + key[2 * j]);
                    pdwTemp[2] = (LeftShift(pdwTemp[2] ^ u, OffsetAmount((int)t)) + key[2 * j + 1]);
 
                    UInt32 temp = pdwTemp[0];
                    pdwTemp[0] = pdwTemp[1];
                    pdwTemp[1] = pdwTemp[2];
                    pdwTemp[2] = pdwTemp[3];
                    pdwTemp[3] = temp;
                }
 
                pdwTemp[0] = (pdwTemp[0] + key[2 * R + 2]);
                pdwTemp[2] = (pdwTemp[2] + key[2 * R + 3]);
 
                // Конвертируем в выходной массив расшифрованных данных
                ConvertFromUInt32ToByteArray(pdwTemp);
            }
 
            pdwTemp = null;
        }
 
        // Функция шифрования файла
        public void EncodeFile()
        {
            UInt32[] pdwTemp;
 
            for (int i = 0; i < fileLength; i += 16)
            {
                pdwTemp = ConvertFromByteArrayToUIn32(fileData, i);
 
                pdwTemp[0] = (pdwTemp[0] - key[2 * R + 2]);
                pdwTemp[2] = (pdwTemp[2] - key[2 * R + 3]);
 
                for (int j = R; j >= 1; j--)
                {
                    UInt32 temp = pdwTemp[3];
                    pdwTemp[3] = pdwTemp[2];
                    pdwTemp[2] = pdwTemp[1];
                    pdwTemp[1] = pdwTemp[0];
                    pdwTemp[0] = temp;
 
                    UInt32 t = LeftShift((pdwTemp[1] * (2 * pdwTemp[1] + 1)),
                                        OffsetAmount((int)(Math.Log((double)W) / Math.Log(2.0))));
                    UInt32 u = LeftShift((pdwTemp[3] * (2 * pdwTemp[3] + 1)),
                                        OffsetAmount((int)(Math.Log((double)W) / Math.Log(2.0))));
 
                    pdwTemp[0] = (RightShift((pdwTemp[0] - key[2 * j]), OffsetAmount((int)u))) ^ t;
                    pdwTemp[2] = (RightShift((pdwTemp[2] - key[2 * j + 1]), OffsetAmount((int)t))) ^ u;
                }
 
                pdwTemp[1] = (pdwTemp[1] - key[0]);
                pdwTemp[3] = (pdwTemp[3] - key[1]);
 
                // Конвертируем в выходной массив зашифрованных данных
                ConvertFromUInt32ToByteArray(pdwTemp);
            }
 
            pdwTemp = null;
        }
    }
}

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

Вариант алгоритма 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})$ операций. Дон Копперсмит заметил, что за счет значительной памяти и предварительного вычисления можно организовать атаку «meet-in-the-middle», чтобы восстановить расширенный ключевой массив 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.

Примечания

1. ↑ Исходные тексты RC6-32/20/64 с ключом 512 бит на языке C
2. ↑ Сравнение алгоритмов RC6 и AES

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

• SCAN’s entry on RC6
• RSA Security’s RC6 page
• Спецификация алгоритма RC6