Основы криптографии

Данный урок предназначен для учеников старшей школы для более глубокого изучения предмета «Информатика и ИКТ»

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

Для обеспечения информационной безопасности изобретено много разных методов и средств защиты информации.

Можно выделить три основные возможности сохранения информации:

— Создать недоступный для других канал связи между абонентами.

— В общедоступном канале связи скрыть сам факт передачи информации. Разработкой методов скрытия передачи информации занимается наука стеганография.

— В общедоступном канале связи передавать преобразованную (зашифрованную) информацию, которую может восстановить только получатель.

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

Исходное, незашифрованное сообщение называется открытым текстом (plain text). Зашифрованное сообщение называется шифртекстом (ciphertext). Процесс преобразования открытого текста в шифртекст называется зашифрованием (enciphering), а обратный процесс — расшифрованием (deciphering). Зашифрование и расшифрование выполняются в соответствии с криптографическим алгоритмом (cryptographic algorithm). Обычно криптографический алгоритм содержит сменный элемент — криптографический ключ (cryptographic key), позволяющий выбрать одно конкретное преобразование из множества преобразований, реализуемых данным алгоритмом.

Существует два основных типа криптографических алгоритмов:

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

Свойства:

простота и быстрота построения и реализации
высокое быстродействие

2) асимметричные, использующие для зашифрования и расшифрования два разных ключа.

Свойства:

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

Разумеется, асимметричное шифрование имеет более высокую степень защищенности.

Рассмотрим примеры классических симметричных криптосистем.
В качестве первого примера рассмотрим классическую криптосистему на основе шифра Цезаря, который использовался знаменитым римским императором Юлием Цезарем. Шифр Цезаря строится по следующему алгоритму: каждая буква слова заменяется четвертой (в порядке следования) буквой алфавита. Алгоритм шифрования букв английского языка согласно шифру Цезаря можно представить в следующей таблице:

Как видно, любую закодированную фразу достаточно легко расшифровать, даже если длинна замены буквы неизвестна.

Применим к русскому алфавиту по аналогичному алгоритму.

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

a	b	c	d	e	f	g	h	i	j	k	l	m
0	1	2	3	4	5	6	7	8	9	10	11	12

n	o	p	q	r	s	t	u	v	w	x	y	z
13	14	15	16	17	18	19	20	21	22	23	24	25

2) в качестве ключа рассмотреть любую последовательность букв английского языка;
3) заменить ключ последовательностью цифр согласно пункту 1;
4) заменить открытый текст последовательностью цифр согласно пункту 1 (пробелы при замене не учитывать);
5) записать под последовательностью цифр открытого текста последовательность цифр ключа, при этом последовательность цифр ключа записать необходимое число раз;
6) сложить попарно эти две последовательности, при этом если сумма равна или больше 26, то вычесть 26;
7) заменить полученные цифры буквами английского языка согласно пункту 1.

Например, зашифруем открытый текст meetmeatcentralpark с помощью шифра Виженера с помощью ключа cipher. Тогда согласно алгоритму (пункты 4. и 5.) ключ cipher заменяется последовательностью цифр (2,8,15,7,4,17), а открытый текст meetmeatcentralparkзаменяется последовательностью цифр (12,4,4,19,12,4,0,19,2,4,13,19,17,0,11,15,0,17,10). Тогда согласно алгоритму (пункт 6.) получим следующую таблицу:

12	4	4	19	12	4	0	19	2	4	13	19	17	0	11	15	0	17	10
2	8	15	7	4	17	2	8	15	7	4	17	2	8	15	7	4	17	2

Сложив попарно эти две последовательности с возможной заменой (согласно пункту 6. алгоритма), получим последовательность (14,12,19,0,16,21,2,1,17,11,17,12,19,8,0,22,4,8,12). Следовательно, согласно пункту 7. алгоритма в качестве шифра исходного открытого текста получим последовательность omtaqvcbrlrmtiaweim.

Шифр Виженера можно применить и к русскому алфавиту. Мы с вами увидели, что шифр Виженера более трудный для построения (по сравнению с шифром Цезаря), но он и более трудный для взлома. Шифр Виженера был невзламываемым до середины 19 века, но в 1863 году прусский офицер Касисский нашёл простой теоретико-числовой метод поиска длины ключа.

Помимо рассмотренных нами простых примеров, существует еще очень много разнообразных симметричных шифров. Некоторые, например: AES, ГОСТ 28147-89 используются и сегодня.

Ассиметричных шифров также достаточно много. Наиболее известный и распространенный: RSA (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.

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

RSA-ключи генерируются следующим образом:

Выбираются два различных случайных простых числа $p$ и $q$ заданного размера (например, 1024 бита каждое).
Вычисляется их произведение $n=p\cdot q$ , которое называется модулем.
Вычисляется значение функции Эйлера от числа $n$ :

$\varphi (n)=(p-1)\cdot (q-1).$
Выбирается целое число ), взаимно простое со значением функции . Обычно в качестве берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые числа Ферма 17, 257 или 65537.
- Число $e$ называется открытой экспонентой.
- Время, необходимое для шифрования с использованием быстрого возведения в степень, пропорционально числу единичных бит в $e$ .
- Слишком малые значения $e$ , например 3, потенциально могут ослабить безопасность схемы RSA.
Вычисляется число , мультипликативно обратное к числу по модулю , то есть число, удовлетворяющее сравнению:

$d\cdot e\equiv 1{\pmod {\varphi (n)}}.$
- Число $d$ называется секретной экспонентой. Обычно, оно вычисляется при помощи расширенного алгоритма Евклида.
Пара $\left\{e,n\right\}$ публикуется в качестве открытого ключа RSA (англ. RSA public key).
Пара $\left\{d,n\right\}$ играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.