Криптографический алгоритм RC4

1. Криптографический алгоритм RC4
1. История алгоритма

Один из широко распространенных алгоритмов потокового шифрования – RC4 – был разработан в 1987г. Рональдом Линном Ривестом, известным  американским специалистом в области  криптографии, который также является соавтором алгоритма RSA, автором хэш-функции MD5 и целого ряда других активно используемых в криптографии хэш-функций и шифров. В течение нескольких лет алгоритм считался коммерческой тайной компании RSA Security, пока не был анонимно опубликован в 1994г. Начиная с этого времени, он нашел широкое применение в целом ряде криптографических приложений, включая такие известные, как SSL и TLS – для шифрования данных, передаваемых по сетям ЭВМ, не предусматривающим защиты пользовательских данных, WPA и WEP – для защиты беспроводных соединений.

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

Алгоритм RC4 строится, как и любой потоковый шифр на основе параметризованного ключом генератора псевдослучайных битов с равномерным распределением. Длина ключа может составлять от 40 до 256 бит.

Поскольку данный алгоритм известен, он более не является коммерческой тайной. Однако, название «RC4» является торговой маркой компании RSA. Поэтому иногда шифр называют «ARCFOUR» или «ARC4» (имея в виду Alleged RC4 — предполагаемый RC4, поскольку RSA официально не опубликовала алгоритм), чтобы избежать возможных претензий со стороны владельца торговой марки.

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

В США длина  ключа для использования внутри страны рекомендуется равной 128 битов, но соглашение, заключённое между Software Publishers Association (SPA) и правительством США даёт RC4 специальный статус, который означает, что разрешено экспортировать шифры длиной ключа до 40 бит. 56-битные ключи разрешено использовать заграничным отделениям американских компаний.

 

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

 

Генератор ключевого  потока RC4

 

Ядро алгоритма  состоит из функции генерации  ключевого потока. Эта функция  генерирует последовательность битов (ki), которая затем объединяется с открытым текстом (mi) посредством суммирования по модулю два. Так получается шифрограмма (ci):

 

 

Расшифровка заключается  в регенерации этого ключевого  потока (ki) и сложении его и шифрограммы (ci) по модулю два. В силу свойств суммирования по модулю два на выходе мы получим исходный незашифрованный текст(mi):

 

 

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

RC4 — фактически класс  алгоритмов, определяемых размером  его блока. Этот параметр n является  размером слова для алгоритма.  Обычно, n = 8, но в целях анализа  можно уменьшить его. Однако  для повышения безопасности необходимо  увеличить эту величину. Внутреннее состояние RC4 представляется в виде массива слов размером 2n и двух счетчиков, каждый размером в одно слово. Массив известен как S-бокс oн всегда содержит перестановку 2n возможных значений слова. Два счетчика обозначены через i и j.

 

1.3. Алгоритм инициализации RC4

 

Алгоритм инициализации RC4 также называется алгоритмом ключевого  расписания (англ. Key-Scheduling Algorithm or KSA). Этот алгоритм использует ключ, сохраненный  в Key, и имеющий длину L байт. Инициализация  начинается с заполнения массива S, далее этот массив перемешивается путем перестановок определяемых ключом. Так как только одно действие выполняется над S, то должно выполняться утверждение, что S всегда содержит все значения кодового слова.

Генератор ключевого  потока RC4 переставляет значения, хранящиеся в S, и каждый раз выбирает различное значение из S в качестве результата. В одном цикле RC4 определяется одно n-битное слово K из ключевого потока, которое в последующем суммируется с исходным текстом для получения зашифрованного текста. Эта часть алгоритма называется генератором псевдослучайной последовательности (англ. Pseudo-Random Generation Algorithm or PRGA).

 

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

 

В отличие от современных шифров (таких, как в eSTREAM), RC4 не использует отдельной оказии (англ. nonce) наряду с ключом. Это значит, что если один ключ должен использоваться в течение долгого времени для шифрования нескольких потоков, сама криптосистема, использующая RC4, должна комбинировать оказию и долгосрочный ключ для получения потокового ключа для RC4. Один из возможных выходов — генерировать новый ключ для RC4 с помощью хэш-функции от долгосрочного ключа и оказии. Однако, многие приложения, использующие RC4, просто конкатенируют ключ и оказию. Из-за этого и слабого расписания ключей, используемого в RC4, приложение может стать уязвимым.

 

 

2. Стандарт цифровой подписи DSS

 

2.1. О стандарте цифровой подписи DSS.

 

DSS (Digital Signature Standard) — американский стандарт, описывающий Digital Signature Algorithm (DSA), который может быть использован для генерации цифровой подписи. Цифровая подпись служит для установления изменений данных и для установления подлинности подписавшейся стороны. Получатель подписанных данных может использовать цифровую подпись для доказательства третьей стороне факта, что подпись действительно сделана отправляющей стороной.

Когда сообщение  получено, получатель может пожелать проверить не изменили ли сообщение во время передачи. Получатель также может захотеть проверить подлинность подписавшейся стороны. DSA дает возможность сделать это.

 

2.2. Математическая проблема лежащая в основе алгоритма DSS

 

DSA используемый в составе стандарта DSS для выработки электронной цифровой подписи. Основан на математической проблеме дискретного логарифмирования в конечном поле. Пусть, например, нам даны элементы а и b из конечного поля F, причем известно, что а=b^х при некотором натуральном х. Задача дискретного логарифмирования состоит в том, чтобы определить это х. Можно, разумеется, просто перебирать последовательно все натуральные числа, проверяя, выполнено ли указанное равенство, но это будет экспоненциальный алгоритм. Пока наилучший из разработанных математиками алгоритмов дискретного логарифмирования является субэкспоненциальным.

 

2.3. Использование DSA

 

DSA используется  одной стороной для генерации  подписи данных, а другой для  проверки подлинности подписчика. Подпись генерируется при помощи закрытого ключа. Любая сторона может проверить подлинность цифровой подписи при помощи открытого ключа. Открытый ключ посылается вместе с подписанными данными. Открытый и закрытый ключи не совпадают.

Хэш-функция  используется при генерации подписи для получения сжатой версии данных. Полученные данные обрабатываются при помощи DSA для получения цифровой подписи. Для проверки подписи используется та же хэш-функция. Хэш функция описана в SHS (Secure Hash Standard).

 

 

 

 

Использование SHA вместе с DSA

 

 

 

 

2.4. Параметры DSA

 

 DSA использует следующие параметры:

1. p – простое  число p, где 2^L-1 < p < 2^L, 512 =< L =< 1024 и L кратно 64

2. q – простой  делитель p-1, причем 2¹⁵⁹ < q < 2¹⁶⁰

3. g = h^(p-1)/q mod p, где h любое целое число 1 < h < p - 1 такое, что h^(p-1)/q mod p > 1

4. x – случайное  или псевдослучайное целое число,  где 0 < x < q

5. y = g^x mod p

6. k – случайное  или псевдослучайное целое число,  где 0 < k < q.

 

Целые p, q и g могут быть открытыми и могут быть общими для группы людей. x и y являются закрытым и открытым ключами, соответственно. Параметры x и k используются только для генерации подписи и должны держаться в секрете. Параметр k разный для каждой подписи.

 

2.5. Генерация подписи

 

Подписью сообщения M является пара чисел r и s, где

r = (g^k mod p) mod q

s = (k⁻¹(SHA(M) + xr)) mod q.

SHA(M) — 160-битная бинарная строка.

Если r = 0 или s = 0, должно быть сгенерировано новое k и вычислена новая подпись. Если подпись вычислялась правильно, вероятность того, что r = 0 или s = 0 очень мала.

Подпись вместе с сообщением пересылается получателю.

 

2.6. Проверка подписи

 

Числа p, q, g и  открытый ключ находятся в открытом доступе.

Пусть M', r' и s' полученные версии M, r и s, соответственно, и пусть y — открытый ключ. При проверке подписи сначала нужно посмотреть, выполняются ли следующие неравенства:

0 < r' < q

0 < s' < q.

 

Если хотя бы одно неравенство не выполнено, подпись  должна быть отвергнута. Если условия  неравенств выполнены, производятся следующие вычисления:

w = (s')⁻¹ mod q

u1 = ((SHA(M')w) mod q

u2 = ((r')w) mod q

v = (((g)^ul (y)^u2) mod p) mod q.

 

Если v = r', то подлинность  подписи подтверждена.

Если v ≠ r', то сообщение  могло быть изменено, сообщение могло  быть неправильно подписано или сообщение могло быть подписано мошенником. В этом случае полученные данные следует рассматривать как поврежденные.