МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОУ ВПО ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ИНСТИТУТ МАТЕМАТИКИ И КОМПЬЮТЕРНЫХ НАУК
КАФЕДРА ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ
КУРСОВАЯ РАБОТА
Шифрования и расшифровка по алгоритму RC6
Выполнил студент 358 группы
Забокрицкий О.В.
Научный руководитель
старший преподаватель
Нестерова О. А.
«__»______2009 _____________
Тюмень, 2009
Содержание
1. Введение…….………………………………………..…..2
2. Теоретическая часть……………………………………..5
· Общие характеристики RC6 алгоритма.………….6
· Окружения с ограничениями пространства……...6
· Аппаратная реализация…………………………….6
· Свойства ключа……………………………………..7
· Шифрование и расшифровка……………………....7
· Другие возможности настройки…………………...8
· Принцип работы…………………………………….9
3. Практическая часть……………………………………..11
4. Заключение……………………………………………...13
5. Список литературы……………………………………..14
6. Приложение А. Тексты программ……………………..15
7. Приложение В. Экранные формы……………………..19
Введение.
Криптография (перевод с греч. “тайнопись”) издавна использовалась при обмене самой разнообразной информацией. Самые ранние упоминания об использовании криптографии: Египет – 1900 г. до н.э., Месопотамия – 1500 г. до н.э., при написании Библии – 500 г. до н.э.
Одним из наиболее известных в древней истории деятелей, постоянно пользовавшийся тайнописью, был Юлий Цезарь. Он придумал шифр, носящий название шифр Цезаря (Caesar cipher).
Тайнописью пользовались на протяжении средних веков в Европе, на Ближнем Востоке и в Северной Америке.
Во время гражданской войны в США тайнопись использовалась и северянами и южанами. С тех пор она использовалась в каждой значительной войне.
Во время Второй мировой войны польские и британские шифровальщики раскрыли секрет немецкой шифровальной машины Энигма. В результате было уничтожено множество немецких подводных лодок, потоплен линкор Бисмарк, и вооруженные силы Германии понесли тяжелые потери в ряде операций.
Значение криптографии сегодня на самых различных уровнях обмена информации трудно переоценить. В своей курсовой работе я постараюсь описать один из алгоритмов шифрования, дать его математическую основу, а так же реализовать его в среде программирования.
При написании курсовой работы поставлены следующие цели:
1) Изучить RC6 - алгоритм шифрования.
2) Реализовать программу шифрования и расшифровки по алгоритму RC6.
Задачи, которые необходимо было решить:
1) Подобрать среду разработки программы.
2) Определить эффективность работы алгоритма.
Теоретическая часть.
Алгоритм RC6 является продолжением криптоалгоритма RC5, разработанного Рональдом Ривестом (англ. Ron Rivest) – очень известной личностью в мире криптографии. RC5 был незначительно изменен для того, чтобы соответствовать требованиям AES по длине ключа и размеру блока. При этом алгоритм стал еще быстрее, а его ядро, унаследованное от RC5, имеет солидный запас исследований.
Алгоритм был одним из пяти финалистов конкурса AES, был также представлен NESSIE и CRYPTREC. Является собственническим (проприетарным) алгоритмом, и запатентован RSA Security.
Так как 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 является запатентованным алгоритмом шифрования.
Общие характеристики.
RC6 не имеет известных атак безопасности. RC6 использует зависящие от данных ротации в качестве нелинейных компонентов. Его резерв безопасности является адекватным. Аналитики высоко оценивают простоту RC6, которая может способствовать анализу его безопасности. Предшественником RC6 является RC5, который также стал предметом тщательного анализа.
Окружения с ограничениями пространства.
RC6 имеет небольшие требования к ROM, что является преимуществом в окружениях с ограничениями пространства. У RC6 при расшифровке отсутствует возможность вычисления подключа на лету, что создает повышенные требования к RAM. Это не вполне соответствует реализации в устройстве с существенными ограничениями на RAM, если требуется расшифровка.
Аппаратные реализации.
RC6 может быть эффективно реализован на любом языке объектно-ориентированного программирования.
Первая группа (I) обладает самой высокой скоростью выполнения, далее следуют вторая (II) и третья (III) группы.
|
|
||||||||||
| 32 бита(С)
|
32 бита (Java)
|
64 бита (С и ассемблер)
|
8 бит (С и ассемблер)
|
32 бита смарт-карты (ARM)
|
Цифровые сигнальные процессоры
|
|||||
| MARS
|
II |
II |
II |
II |
II |
II |
||||
| RC6
|
I |
I |
II |
II |
I |
II |
||||
| Rijndael
|
II |
II |
I |
I |
I |
I |
||||
| Serpent
|
III |
III |
III |
III |
III |
III |
||||
| Twofish
|
II |
III |
I |
II |
III |
I |
||||
|
|
||||||||||
| 32 бита(С)
|
32 бита (Java)
|
64 бита (С и ассемблер)
|
8 бит (С и ассемблер)
|
Цифровые сигнальные процессоры
|
||||||
| MARS
|
II |
II |
III |
II |
II |
|||||
| RC6
|
II |
II |
II |
III |
II |
|||||
| Rijndael
|
I |
I |
I |
I |
I |
|||||
| Serpent
|
III |
II |
II |
III |
I |
|||||
| Twofish
|
III |
III |
III |
II |
III |
|||||
| Таблица 3. Полная оценка выполнения
|
||
| Шифрование/ расшифровка
|
Установление ключа
|
|
| MARS
|
II |
II |
| RC6
|
I |
II |
| Rijndael
|
I |
I |
| Serpent
|
III |
II |
| Twofish
|
II |
III |
Шифрование vs. Рас шифрование.
Шифрование и расшифровка в RC6 имеют аналогичные функции. Таким образом, эффективность RC6 при шифровании и расшифровке существенно не отличается.
Свойства ключа.
RC6 поддерживает возможность вычисления подключей на лету только для шифрования, используя порядка 100 байтов для промежуточных значений. Подключи расшифровки должны быть вычислены заранее.
Другие возможности настройки.
Размеры блока, ключа и число раундов параметризуемы. RC6 поддерживает размер ключа намного больше 256 бит.
Принцип работы.
Алгоритм является сетью Фейcтеля с 4 ветвями смешанного типа : в нем два четных блока используются для одновременного изменения содержимого двух нечетных блоков. Затем производится обычный для сети Фейстеля сдвиг на одно машинное слово, что меняет четные и нечетные блоки местами. Сам алгоритм предельно прост и изображен на рисунке 1. Разработчики рекомендуют при шифровании использовать 20 раундов сети, хотя в принципе их количество не регламентируется. При 20 повторах операции шифрования алгоритм имеет самую высокую скорость среди 5 финалистов AES.
Рис.1.
Преобразование T(x) очень просто : T(X)=(X*(X+1)) mod 2N
. Оно используется в качестве нелинейного преобразования с хорошими показателями перемешивания битового значения входной величины.
| Биективные математические функции |
||
|
|
Сложение |
X'=X+V |
|
|
Исключающее ИЛИ |
X'=X XOR V |
| Битовые сдвиги |
||
|
|
Циклический сдвиг влево |
X'=X ROL V |
|
|
Циклический
сдвиг вправо
|
X'=X ROR V |
Шифрование для RC6-w/r/b (w – длина слова в битах, r – ненулевое количество итерационных циклов шифрования, b – длина ключа в байтах) описывается следующим образом:
Вход:
Исходный текст, записанный в 4-х w-битовых регистрах A,B,C,D
Число циклов шифрования r
Ключевая таблица S[0.. 2r + 3] w-битовых слов.
Выход:
Шифрованный текст в регистрах A,B,C,D
Процедура:
B = B + S[0];
D = D + S[1];
for i=1 to r do
{
t = (B * (2 * B + 1)) << log2
w
u = (D * (2 * D + 1)) << log2
w
A = (A xor t) << u + s[2*i]
C =(C xor U)<< t) + s[2*i+1]
(A,B,C,D) = (B,C,D,A)
}
A = A + S[2*r +2]
C = C + S[2*r +3]
Исходный файл разбивается на порции по 128 бит. Эти порции, в свою очередь, состоят из четырех блоков (которые как раз и используются в четырех ветвях сети Фейcтеля). Первая порция считывается, и к четным блокам прибавляются по модулю 2N
первые два 32-битовых слова ключа. Далее, блоки считываются последовательно в цикле из файла. На каждой итерации производится сдвиг на машинное слово, что меняет четные и нечетные блоки местами. В цикле над четными блоками производится операция преобразования T(X)=(X*(2*X+1)) mod 2N
и циклический сдиг влево на log2
32 = 5 бит. Далее, над преобразованными блоками и исходными нечетными блоками производится операция XOR и циклический сдвиг влево на количество бит, хранимое после преобразования в четных блоках. Заключительная операция в цикле - сложение по модулю 2N
с (2*i)-м и (2*i+1)-м 32-битовыми словами ключа. Далее, как было сказано выше, четные и нечетные блоки меняются местами и начинается новая итерация цикла. После окончания цикла к нечетным блокам прибавляются по модулю 2N
последние два 32-битовых слова ключа.
Расшифровка описывается следующим образом:
Вход:
Шифрованный текст, записанный в 4-х w-битовых регистрах A,B,C,D
Число циклов шифрования r
Ключевая таблица S[0.. 2r + 3] w-битовых слов.
Выход:
Исходный текст в регистрах A,B,C,D
Процедура:
C = C - S[2*r +3]
A = A - S[2*r +2]
for i=r downto 1 do
{
(A,B,C,D) = (D,A,B,C)
u =(D * (2 * D + 1))<< log2
w
t = (B * (2 * B + 1))<< log2
w
C = (C - S[2*i+1]<< t) xor u
A = (A - S[2*i]) <<u) xor t
}
D = D - S[1]
B = B - S[0]
Алгоритм вычисления ключей для RC6-w/r/b выглядит следующим образом:
Пользователь задает ключ длиной b байтов. Достаточное число ненулевых байтов дописывается в конец, чтобы получилось целое число слов. Затем эти байты записываются, начиная с младшего в массив из слов, т.е. первый байт ключа записывается в L[0], и т.д., а L[c-1] при необходимости дополняется со стороны старших разрядов нулевыми байтами. В результате работы алгоритм генерации ключей будет вычислено 2r + 4 слов, которые будут записаны в массиве S[0.. 2r + 3].
Константы P32
= b7e15163 и Q32
= 9e3779b9 – это константы, получаемые из двоичного представления е – 2, где е – основание натурального логарифма, и ф – 1, где ф – золотое сечение соответственно.
Алгоритм вычисления ключей для RC6:
Вход:
Определенный пользователем b-байтовый ключ, предварительно загруженный в массив L[0..c-1].
Число раундов шифрования r.
Выход:
Ключевая таблица S[0.. 2r + 3] w-битовых слов.
Процедура:
S[0] := P32
for i := 1 to 2*r+3 do
S[k] := S[k-1] +Q32
v = 3 * max{c,2*r + 4}
A = B = i = j
for i := 1 to v do
{
A = S[i] = (S[i] + A + B) << 3
B = L[j] = (L[j] + A + B) <<(AA + BB)
i = (i+1) mod (2*r+4);
j = (j+1) mod c;
}
После того, как пользователь задает исходный ключ, который записывается в исходный массив L, начинает формироваться ключевая таблица S. Первый элемент S = b7e15163. Далее, в цикле для всех 2*r+3 элементов таблицы S ее элементы задаются следующим образом: каждый следующий элемент равен предыдущему плюс константа 9e3779b9. Далее, определяется, что больше, число ненулевых элементов массива L или 2*r+4. Это значение, помноженное на 3, используется далее в качестве предела итераций для цикла. В новом цикле снова преобразуются элементы таблицы S. Каждый элемент S[i] равен сумме самого себя, предыдущего элемента S[i-1] и предыдущего элемента L[i-1]. К этому значению применяется циклический сдвиг влево на 3 бит. Аналогичным образом в этом же цикле рассчитывается i-й элемент массива L, за исключение того, что сдвиг влево производится на число бит, равное сумме L[i] и S[i]. Каждые следующие индексы массивов i и j равны самим себе, взятым с увеличением на 1 по модулю (2*r+4) или с соответственно.
Практическая часть
В результате работы над курсовой была разработана программа шифрования/расшифровки по алгоритму RC6 со следующими параметрами: длина слова в битах (w) = 32, количество циклов шифрования (r) = 20, размер ключа в байтах (b) = 1..255. Программа написана на языке программирования Object Pascal в среде Borland Delphi 6.0. Текст программы приведен в приложении А.
Для проведения расшифровки, зашифрованного по данному алгоритму файла, необходимо выполнить следующие действия: в блоке выбора выполняемого действия выбрать операцию «Расшифровка файла». В качестве ключа необходимо ввести слово «пароль». В качестве исходного файла можно выбрать файл input1.txt (при этом его содержимое загрузится в многострочный редактор). В поле «Конечный файл» вводится имя выходного файла. Введем имя «output1.txt». При нажатии на кнопку «Расшифровать» содержимое расшифрованного файла загружается в многострочный редактор (рис. 2).
рис. 2.
В результате тестирования был также рассмотрен вариант использования ключа, который отличается от верного на 1 символ. В результате сравнения результатов расшифровки было установлено, что степень перемешивания бит при кодировании очень высока, т.к. всего лишь один неверный символ в ключе привел к полному отличию расшифрованного файла от исходного (рис. 3).
рис. 3.
Также был рассмотрен вариант шифрования при частичной замене содержимого исходного файла с использованием того же пароля: в результате замены нескольких символов в начале исходного файла было установлено, что зашифрованные файлы резко отличаются друг от друга. Это также является подтверждением высокой степени перемешивания бит в результате работы алгоритма шифрования. В ходе анализа результатов работы программы было установлено, что все необходимые функции выполняются.
Заключение
В данной курсовой работе была спроектирована и реализована система шифрования/расшифровки по алгоритму RC6. Была разработана программа, которая выполняет как функцию шифрования, так и расшифровки.
Созданная программа была протестирована. Результаты тестирования показали ее правильную и устойчивую работу. Полученные результаты работы программы были проанализированы и позволяют сделать вывод о том, что поставленная задача была успешна решена.
Реализация системы проводилась с использованием инструментальных средств Borland Delphi 7.0. При написании программы основное внимание было уделено удобству работы пользователя и построению дружественного интерфейса.
Список литературы:
1. «Практическая криптография: алгоритмы и их программирование». Авторы: А. В. Агpановcкий, Р. А. Хади .
2. «RC6 and the AES». Автор: M.J.B. Robshaw
3. Материалы с официальной страницы НИСТ США http://www.nist.gov/aes
Приложение
А
Тексты
программы
unit uCoding;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, ComCtrls;
type
TForm1 = class(TForm)
GroupBox1: TGroupBox;
RadioButton1: TRadioButton;
RadioButton2: TRadioButton;
Label1: TLabel;
edKey: TEdit;
Label2: TLabel;
OpenDialog1: TOpenDialog;
Label3: TLabel;
edFirstFile: TEdit;
edSecondFile: TEdit;
btFirstFile: TButton;
Label4: TLabel;
Label5: TLabel;
Memo1: TMemo;
Memo2: TMemo;
btGo: TButton;
procedure btFirstFileClick(Sender: TObject);
procedure RadioButton1Click(Sender: TObject);
procedure btGoClick(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
const r = 20;
var Buf: array [1..4] of Integer;
S: array [0..2*r+3] of Integer;
{$R *.dfm}
procedure TForm1.btFirstFileClick(Sender: TObject);
begin
OpenDialog1.InitialDir := GetCurrentDir;
if OpenDialog1.Execute then
Memo1.Lines.LoadFromFile(OpenDialog1.FileName);
edFirstFile.Text := OpenDialog1.FileName;
end;
procedure TForm1.RadioButton1Click(Sender: TObject);
begin
if RadioButton1.Checked then btGo.Caption := 'Шифровать'
else btGo.Caption := 'расшифровать';
end;
function LRot32(X: Integer; c: Integer): Integer; assembler;
asm
mov ecx,&c
mov eax,&X
rol eax,cl
mov &Result,eax
end;
function RRot32(X: Integer; c: Integer): Integer; assembler;
asm
mov ecx,&c
mov eax,&X
ror eax,cl
mov &Result,eax
end;
//Генерация ключа:
procedure MakeKey;
var Key: ShortString;
L: array [0..63] of Integer;
Len, c, k, v, i, j: byte;
A, B: Integer;
begin
Key := Form1.edKey.Text;
Len := Length(Key);
FillChar(L, Sizeof(L), 0);
Move(Key, L, Len+1);
c := Len div 4;
if Len mod 4 <> 0 then Inc(c);
S[0] := $B7E15163;
for i:=1 to 2*r+3 do
S[i] := S[i-1] + $9E3779B9;
i := 0; j := 0;
A := 0; B := 0;
if c>2*r+4 then v := 3*c else v := 3*(2*r+4);
for k:=1 to v do begin
A := LRot32((S[i]+A+B), 3);
S[i] := A;
B := LRot32((L[j]+A+B), (A+B));
L[j] := B;
i := (i+1) mod (2*r+4);
j := (j+1) mod c;
end; {for k}
end;
procedure EnCript;
var Temp, A, B, C, D, t, v: Integer;
i: Byte;
begin
A := Buf[1];
B := Buf[2];
C := Buf[3];
D := Buf[4];
B := B + S[0];
D := D + S[1];
for i:=1 to r do begin
t := LRot32(B*(2*B+1), 5);
v := LRot32(D*(2*D+1), 5);
A := LRot32(A xor t, v)+S[2*i];
C := LRot32(C xor v, t)+S[2*i+1];
Temp := A;
A := B;
B := C;
C := D;
D := Temp;
end;
A := A + S[2*r+2];
C := C + S[2*r+3];
Buf[1] := A;
Buf[2] := B;
Buf[3] := C;
Buf[4] := D;
end;
procedure DeCript;
var Temp, A, B, C, D, t, v: Integer;
i: Byte;
begin
A := Buf[1];
B := Buf[2];
C := Buf[3];
D := Buf[4];
A := A - S[2*r+2];
C := C - S[2*r+3];
for i:=r downto 1 do begin
Temp := D;
D := C;
C := B;
B := A;
A := Temp;
t := LRot32(B*(2*B+1), 5);
v := LRot32(D*(2*D+1), 5);
A := RRot32(A-S[2*i], v) xor t;
C := RRot32(C-S[2*i+1], t) xor v;
end;
B := B - S[0];
D := D - S[1];
Buf[1] := A;
Buf[2] := B;
Buf[3] := C;
Buf[4] := D;
end;
procedure TForm1.btGoClick(Sender: TObject);
var f1, f2: file;
NumRead, NumWritten, i: Integer;
begin
MakeKey; //Генерация ключа
AssignFile(f1, edFirstFile.Text);
AssignFile(f2, edSecondFile.Text);
Reset(f1, 1);
Rewrite(f2, 1);
repeat
FillChar(Buf, Sizeof(Buf), 0);
BlockRead(f1, Buf, SizeOf(Buf), NumRead);
if RadioButton1.Checked then EnCript else Decript;
if not((RadioButton2.Checked) and (NumRead<SizeOf(Buf))) then
BlockWrite(f2, Buf, SizeOf(Buf), NumWritten);
until (NumRead = 0) Or (SizeOf(Buf) <> NumRead);
CloseFile(f1);
CloseFile(f2);
Memo2.Lines.LoadFromFile(edSecondFile.Text);
end;
end.
Приложение В
Экранные формы
Рисунок 4 - Основное окно программы