Потоковый шифр Rivest Cipher 4. Особенности алгоритма

Атака Кляйна

     В 2005 году Андреас Кляйн представил анализ шифра RC4, в котором он указал на сильную коррелированность ключа  и ключевого потока RC4. Кляйн проанализировал атаки на первом раунде (подобные атаке ФМШ), на втором раунде и возможные их улучшения. Он также предложил некоторые изменения алгоритма для усиления стойкости шифра. В частности, он утверждает, что если поменять направление цикла на обратное в алгоритме ключевого расписания, то можно сделать шифр более стойким к атакам типа ФМШ.

Комбинаторная проблема

     В 2001 году Ади Шамир и Ицхак Мантин первыми поставили комбинаторную  проблему, связанную с количеством  всевозможных входных и выходных данных шифра RC4. Если из всевозможных 256 элементов внутреннего состояния шифра известно x элементов из состояния (x ≤ 256), то, если предположить, что остальные элементы нулевые, максимальное количество элементов, которые могут быть получены детерминированным алгоритмом за следующие 256 раундов также равно x. В 2004 году это предположение было доказано Сорадюти Полом (Souradyuti Paul) и Бартом Прэнилом (Bart Preneel).

Программная реализация

     Работа  многих поточных шифров основана на линейных регистрах сдвига с обратной связью (LFSR). Это позволяет достичь высокой эффективности реализаций шифра в виде ИС. Но затрудняет программную реализацию таких шифров. Поскольку шифр RC4 не использует LFSR и основан на байтовых операциях, его удобно реализовывать программно. Типичная реализация выполняет от 8 до 16 машинных команд на каждый байт текста, поэтому программная реализация шифра должна работать очень быстро.

     Пример  реализации RC4 на языке C:

unsigned char S[256];

unsigned int i, j;

 

/* ключевое расписание */

void rc4_init(unsigned char *key, unsigned int key_length) {

    for (i = 0; i < 256; i++)

        S[i] = i;

 

    for (i = j = 0; i < 256; i++) {

        unsigned char temp;

        j = (j + key[i % key_length] + S[i]) & 255;

        temp = S[i];

        S[i] = S[j];

        S[j] = temp;

    }

 

    i = j = 0;

}

 

/* Вывод одного псевдослучайного байта */

unsigned char rc4_output() {

    unsigned char temp;

 

    i = (i + 1) & 255;

    j = (j + S[i]) & 255;

 

    temp = S[j];

    S[j] = S[i];

    S[i] = temp;

 

    return S[(temp + S[j]) & 255];

}

Блок-схема  программы

 

 
 

 
 

Модули  и функции программы

Начальная установка вызова формы

fastcall TForm1::TForm1(TComponent* Owner)

        : TForm(Owner)

Функция открытого текста

     Загрузка  текста из файла (формат txt):

void OpenText()

Функция шифрования

     Выполнение  всех процедур, связанных с шифрованием  и создание файла с шифротекстом:

void __fastcall TForm1::aEncryptExecute(TObject *Sender)

void __fastcall TForm1::ProcessFile(const AnsiString& pFrom, const AnsiString& pTo)

void __fastcall RC4_InitKey(unsigned char* Key, int KeyLength)

Функция расшифрования

     Выполнение  всех процедур, связанных с расшифрованием и создание файла с расшифрованным текстом:

void __fastcall TForm1::aDecryptExecute(TObject *Sender)

void __fastcall TForm1::ProcessFile(const AnsiString& pFrom, const AnsiString& pTo)

void __fastcall RC4_InitKey(unsigned char* Key, int KeyLength)

Функция выхода из программы

void __fastcall TForm1::aExitExecute(TObject *Sender)

Функция отображения алгоритма

void __fastcall TForm1::aHelpExecute(TObject *Sender)

Инструкция  пользователя

Главное окно программы

Рис. 2. Общий вид программы

 
 
 
 
 

Файл

      Содержит:

     Зашифровать – выбор файла, который необходимо зашифровать. При нажатии открывается интерфейс, позволяющий выбрать файл в проводнике.

Рис. 3. Выбор текстового файла для шифрования

Рис. 4. Шифруемый текст

 
 
 

     Расшифровать – выбор файла, который необходимо расшифровать. При нажатии открывается интерфейс, позволяющий выбрать файл в проводнике.

Рис. 5. Выбор текстового файла для расшифрования

Рис. 6. Зашифрованный текст

     Выход – выход из программы.

 
 
 
 
 
 
 
 

Помощь

     Содержит:

     Алгоритм – отображает теоретическую информацию об алгоритме, реализуемом в работе.

Рис. 7. Описание работы алгоритма

Поле  “Ключ”

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

Окно  процесса шифрования

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

Рис. 9. Отображение процесса шифрования

Последовательность  действий

     Выбрать входной и выходный файлы, ввести ключ, нажать «Зашифровать/Расшифровать». Т.к. алгоритм симметричный, то процессы шифрования и расшифрования аналогичны.

Заключение

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

Алгоритм RC4 — это поточный шифр с переменной длиной ключа, разработанный в 1987 году Рональдом Райвистом для компании RSA Data Security. Как и его «компаньон», блочный шифр RC2, RC4 представляет собой шифр с переменной длиной ключа, пригодный для быстрого магистрального шифрования. Он очень компактен в терминах размера кода и особенно удобен для процессоров с побайтно-ориентированной обработкой. RC4 может шифровать со скоростью около 10 Мбайт/с на процессоре с тактовой частотой 330 Мгц и, подобно RC2, имеет особый статус, значительно упрощающий получение разрешения на экспорт (схема позволяет безболезненно редуцировать длину ключа). В течение семи лет этот алгоритм был фирменным секретом, и подробности о его конструкции предоставлялись только после подписания договора о неразглашении.

В настоящее  время алгоритм RC4 реализован в десятках коммерческих криптопродуктов, включая Lotus Notes, Apple Computer’s AOCE, Oracle Secure SQL; он также является частью спецификации стандарта сотовой связи CDPD.

Компания RSA Data Security объявила, что шифр обладает иммунитетом к методам линейного и дифференциального криптоанализа и до сих пор у него не обнаружены короткие циклы. Обычно цитируется заключение закрытой работы криптографа RSA Labs Мэтта Робшоу: «Не имеется известных слабых ключей, и, хотя нет доказательства для нижней границы периодов последовательностей RC4, проведенный теоретический анализ показывает, что период в подавляющем большинстве случаев превышает 10100. Тщательный и всеобъемлющий анализ стойкости RC4 не выявил никаких оснований подвергать сомнению стойкость, обеспечиваемую генератором RC4».

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

Исходные  тексты и информацию об RC4 можно найти  во многих криптографических библиотеках, например в исходных текстах SSLeay, Crypto++ и Ssh.

Американское  правительство обычно разрешает к экспорту шифры RC4 с 40-битными ключами. Такие короткие ключи могут быть легко взломаны правительствами, преступниками и даже дилетантами.

Интересно, что экспортный вариант SSL (Secure Socket Layer корпорации Netscape), где используется шифр RC4-40, был недавно вскрыт по крайней мере двумя независимыми группами. Процесс вскрытия занял порядка восьми дней; в большинстве крупных университетов (или компаний) такой объем вычислительных мощностей доступен любому студенту старших курсов по специальности computer science.

Список  литературы

1. Б. Шнайер «Прикладная криптография. 2-е издание. Протоколы, алгоритмы и исходные тексты на языке С». Издано: 2002, "Триумф", 816 стр.
2. Кузнецов М.В. C++. Мастер-класс в задачах и примерах (+ CD-ROM). Спб.: БХВ-Петербург, 2007.
3. Э.А. Ишкова С++ начала программирования / Изд. 3-е М.: ООО «Бином-Пресс», 2007. – 368 стр.
4. Коблиц Н. Курс теории чисел и криптографии. - М.: ТВП, 2001.
5. Электронный ресурс RC4 – Википедия // http://ru.wikipedia.org/wiki/RC4
6. Электронный ресурс RSA Laboratories // http://www.rsa.com/rsalabs/node.asp?id=2009
7. Электронный ресурс http://dic.academic.ru/
8. Электронный ресурс http://www.des-crypto.ru/cryptography/rc4/
9. Электронный ресурс http://www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html
10. Ермолаев Е. Без проводов и без защиты // Спецвыпуск: Хакер, номер 059 / стр. 18-24. (Журнал).

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 

Листинг программы

//---------------------------------------------------------------------------

 

#include <vcl.h>

#pragma hdrstop

 

#include "MainUnit.h"

#include "RC4Unit.h"

#include "AboutUnit.h"

#include "Unit2.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

        : TForm(Owner)

{

}

 

//---------------------------------------------------------------------------

void __fastcall TForm1::ProcessFile(const AnsiString& pFrom, const AnsiString& pTo)

{

  // Если  ключевая фраза будет пустой, алгоритм вылетит

  if (Edit1->Text == "")

  {

    Edit1->Text = "DefaultPassPhrase";

  }

 

  // Передаем  ключевую фразу на генератор  матрицы

  Memo1->Lines->Add("Инициализация  матрицы..");

  RC4_InitKey(Edit1->Text.c_str(), Edit1->Text.Length());

  Memo1->Lines->Add("Выполнено 256 перестановок");

 

  Memo1->Lines->Add("Открытие  файлов..");

  // Открываем первый файл на чтение

  HANDLE in = CreateFile(pFrom.c_str(), GENERIC_READ, 0, NULL,

                        OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL);

  if (in == INVALID_HANDLE_VALUE)

  {

    Memo1->Lines->Add("..ошибка!");

    Application->MessageBox(("Не удалось открыть входной файл: "+pFrom).c_str(), "  Ошибка",