Криптография. Симметричные и асимметричные алгоритмы шифрования.

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

Цель работы — разобраться с алгоритмами шифрования. Для реализации этой цели разработана программа шифрования сообщений, которая объясняет принцип работы используемого в ней алгоритма шифрования.

Исходя из поставленной задачи, программа шифрования должна:

содержать блок, дающий полное представление о работе выбранного алгоритма;
содержать блок шифрования/дешифрования текста, иллюстрирующий работу этого алгоритма.

В качестве технологии реализации поставленной задачи выбрана технология Macromedia Flash. Эта технология более проста для разработчика, нежели Delphi или C++, но при этом она является не менее мощным инструментом разработки приложений, к тому же она позволяет разрабатывать анимацию, управляемую пользователем, с наименьшими затратами времени разработчика.

Теоретическая часть

Симметричные алгоритмы шифрования

Криптография существует со времён Древнего Мира. Тогда использовалась банальная перестановка букв или их замена другими буквами или цифрами. Юлий Цезарь применял подстановку, где буквы сдвигались циклически на три позиции вправо.

Одно из слабых мест этого метода – низкая сопротивляемость частотному анализу. Чтобы снизить вероятность раскрытия сообщения, были разработаны другие методы шифрования. Следующим шагом в эволюции криптографии стало появление шифров с ключами. Теперь зашифрованный текст стал зависеть не только от содержания послания, но и от значения ключа ― определённой последовательности букв или цифр, определяющей способ шифрования/ дешифровки. Примером такого алгоритма шифрования является применение к сообщению операции XOR.

Шифрование/дешифрование операцией XOR

XOR – это операция логического исключающего ИЛИ. Применение операции XOR для двоичных кодов символов сообщения создает двоичные коды символов зашифрованного сообщения. На этом и основан принцип шифрования XOR. Для наглядности приведен программный код на языках программирования C++ и Паскаль — листинги 1 и 2 Приложения. Дешифрование осуществляется повторным выполнением операции XOR над зашифрованным сообщением.

Такой метод шифрования не поддаётся частотному анализу. Но на сегодняшний день этот метод шифрования данных устарел. При современном быстродействии компьютеров разгадать такой шифр не составит труда.

Асимметричные алгоритмы шифрования

Развитие основных типов криптографических протоколов (ключевой обмен, электронно-цифровая подпись (ЭЦП), аутентификация) было бы невозможно без создания открытых ключей и построенных на их основе ассиметричных алгоритмов шифрования.

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

Таким образом, пользователи избавляются от необходимости решать сложную задачу обмена секретными ключами.

Стандарт асимметричного шифрования RSA

Самым распространенным алгоритмом асимметричного шифрования является алгоритм RSA. Он был предложен тремя исследователями — математиками Рональдом Ривестом (R.Rivest), Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977 году. Стойкость RSA базируется на сложности факторизации больших целых чисел. В 1993 году метод RSA был обнародован и принят в качестве стандарта шифрования. RSA можно применять как для шифрования/ дешифрования, так и для генерации/проверки электронно-цифровой подписи.

Генерация ключей

Первым этапом любого асимметричного алгоритма является создание пары ключей — открытого и закрытого и распространение открытого ключа. Пара чисел (d, n) используется для шифрования сообщения и является открытым ключом, а пара чисел (e, n) хранится в строжайшем секрете — закрытый ключ, который дешифрует послания, зашифрованные с помощью открытого ключа.

Шифрование/дешифрование

Далее производится шифрование с помощью этих чисел (d, n). Зашифрованное сообщение можно спокойно передавать по открытому каналу, поскольку операция шифрования, согласно алгоритму RSA, является необратимой математической задачей.

А вот на приемной стороне процесс дешифрования все же возможен благодаря закрытому ключу (e, n).

Электронная цифровая подпись

При ведении деловой переписки подпись ответственного лица является непременным атрибутом документа, преследующим несколько целей:

Гарантирование истинности письма путем сличения подписи с имеющимся образцом;
Гарантирование авторства документа (с юридической точки зрения).

Развитие современных средств безбумажного документооборота немыслимо без развития средств доказательства подлинности и целостности документа — электронно-цифровой подписи (ЭЦП), которая сохранила свойства обычной подписи.

Существует два метода построения ЭЦП, а именно:

Шифрование электронного документа (ЭД) на основе симметричных алгоритмов. Данная схема требует наличие в системе арбитра, пользующегося доверием обеих сторон. Авторизацией документа в данной схеме является сам факт шифрования ЭД секретным кличем и передача его арбитру.
Использование асимметричных алгоритмов шифрования. Фактом подписания документа является его шифрование секретным ключом отправителя.

Развитием второй идеи стала наиболее распространенная схема ЭЦП: шифрование окончательного результата обработки ЭД хеш-функцией при помощи асимметричного алгоритма.

Практическая часть

Программа шифрования состоит из трех логических частей:

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

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

Алгоритм симметричного шифрования

Обучающий компонент

Этот компонент содержит описание операции XOR на конкретном примере: берутся два символа: А и 1, и над ними выполняется операция XOR.

Программа шифрования/дешифрования

Для иллюстрации симметричного алгоритма шифрования написана простая программа, которая из текстового поля, связанного с переменной inText, считывает символы и шифрует введенным пользователем ключом k. Результат выводится в поле outText при нажатии на кнопку «Шифрование».

Чтобы расшифровать полученное зашифрованное сообщение, пользователь должен ввести ключ шифрования в поле k. Зашифрованный текст из поля outText при нажатии на кнопку «Дешифрование» отобразится в поле deshifr ― таким образом получаем исходное сообщение.

Алгоритм асимметричного шифрования

Обучающий компонент

В этом разделе программы по шагам демонстрируется, каким образом происходит процесс шифрования/дешифрования текста. Для наглядности представления процесса, числа p и q выбраны небольшими. Поэтому сгенерированные с их помощью открытый ключ (d, n) и закрытый ключ (e, n) также представлены небольшими числами, что делает процесс вычисления понятным

Программа шифрования/дешифрования

В теоретической части был рассмотрен алгоритм шифрования RSA. Этот алгоритм применен для шифрования текста в следующей последовательности:

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

Зашифрованное сообщение дешифруется закрытым ключом по такому же принципу:

символы сообщения переводятся в ASCII-коды этих символов;
над полученным массивом чисел производятся необходимые вычисления (дешифрация);
полученные числа будут ASCII-кодами символов исходного сообщения.

В представленной форме поле для ввода шифруемого сообщения обращается к связанной переменной inText, поле для зашифрованного сообщения связано с переменной outText.

Для расшифрованного сообщения предназначено поле и связанная с ним переменная deshifr. При нажатии на кнопку «Шифрование» происходит шифрование исходного текста по разработанному алгоритму. Полученный результат ― зашифрованное сообщение (в виде кракозябр) ― отображается в поле outText. Если нужно расшифровать сообщение, пользователю нужно ввести секретный ключ e для дешифрования и нажать на кнопку «Дешифрование».

Для реализации этого подхода к решению задачи шифрования необходимо взять такие параметры p и q, чтобы их произведение было не менее 8500, так как ASCII-коды некоторых специальных символов превышают за 8 000. Возьмем два простых числа, дающих достаточно близкое по значению произведение: p = 103 и q = 83. Тогда N = p*q =8549. Возьмем простое число d = 53. Находим число e = 2525.

Согласно алгоритму шифрования, ASCII-код символа нужно возвести в степень d = 53 и от полученного числа взять остаток от деления его на 8549. Тут возникает сложная вычислительная задача: Flash поддерживает точность вычислений до 15 значащей цифры, а работая, например, с русскими символами, нам приходится возводить в 53 степень значения, близкие к тысяче. Получаем порядка 150 значащих цифр, а для ASCII-кодов, близких к 8000 получаем порядка 200-220 значащих цифр. При дешифровании же нужно возводить ASCII-код в степень 2525, что еще более усложняет задачу (значащих цифр получается порядка 10 000). Проблема выглядит нерешаемой.

Однако, найден простой и оригинальный выход из сложившегося тупика. Вместо того, чтобы тупо возводить число в нужную степень при помощи функции Math.pow(ascii, 2525), организован цикл на 2525 шагов. На каждом шагу цикла производится умножение ASCII-кода на себя, от полученного результата берется остаток от деления на 8549. В этом случае количество значащих цифр в вычислениях не превышает 8 (9 000 х 9 000 = 81 000 000), и точность расчетов не страдает. Программный код этого решения алгоритма шифрования данных приведен в листинге 3 Приложения. Дешифрование имеет аналогичный программный код.

Кстати, непосредственно в кадре написан программный код, который позволяет для произвольно выбранных простых чисел p и q подобрать открытый ключ d и закрытый ключ e. Чем больше значения p и q, тем больше будут значения d и e, тем выше будет надежность шифра. Замечено, что, работая с указанными параметрами, программа начинает «притормаживать», поэтому дальнейший подбор ключей более высоких порядков признан нецелесообразным, хотя разработанный алгоритм вполне может справиться и с ними.

Заключение

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

Литература

Распространенные криптоалгоритмы ― http://www.cryptography.strongdisk.ru
Александр Володин «Кто заверит ЭЦП» ― журнал «Банковские системы» - ноябрь 2002 http://www.bizcom.ru/system/2000-11/04.html
Криптографические алгоритмы с открытым ключом ― http://argosoft.webservis.ru/Base/RSAintro.html
М. Гурвиц «Использование Macromedia FLASH MX» ― М, 2003.
Р. Рейнхард «FLASH MX 2004 Action Script. Библия пользователя» ― М, 2006.

Приложение

Листинг 1

Uses Crt;

Var

i: Byte; {описываем переменные}

Msg: String;

Code: Integer;

Begin

writeln('Enter Message'); {msg – само сообщение}

readln(Msg);

writeln('Enter Key'); {ключ – небольшой длины}

readln(code);

For i:=1 to Length(Msg) Do

Msg[i]:=Chr(Ord(Msg[i]) xor Code); {шифрование }

writeln(' ',Msg);

readkey;

End.

Листинг 2

#include

int main {

char Msg[] = ”Message”; // задаётся сообщение

char Code[] = “8080”; //задается ключ

int i=0; j=0;

printf(“%\n”, Msg);

while (Msg[i] !=’\0’) {

if (j>Length(msg)) j=0; //если j>l длины ключа, тогда j=0;

printf(“%c”,msg[i++] ^= code[j++]);

}

printf(“\n”)’

return 0;

}

Листинг 3

outText = "";

var countS = inText.length;

for (i=0; i<=countS-1; i++) {

InS[i] = inText.slice(i, i+1);

a = ord(InS[i]);

for (k=2; k<=d; k++) {

a *= ord(InS[i]);

a = a%n;

}

InS[i] = a;

outText += chr(InS[i]);

}

В.А. Сухомлинский. Для чего говорят «спасибо»?

Рисуем белые грибы пастелью

Мальчик и колокольчики ландышей

Как нарисовать черёмуху

Барсучья кладовая. Александр Барков