§4. Математические основы криптографии.

4.1. Криптографические примитивы.

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

4.1.1. Подстановки

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

Таблица 2 - Таблица простой замены

Символы шифруемого текста

А

Б

В

Г

Д

Е

Ж

З

И

Й

К

Л

М

Н

О

П

Заменяющие символы

С

П

Х

Л

Р

З

Э

М

А

Ы

Я

Д

Ю

Т

Г

Ж

Символы шифруемого текста

Р

С

Т

У

Ф

Х

Ц

Ч

Ш

Щ

Ь

Ы

Ъ

Э

Ю

Я

Заменяющие символы

Н

Й

О

Ц

Б

Ф

У

К

Ч

Ш

Щ

Ь

И

Ъ

Е

В

Используя эту таблицу зашифруем слово криптография. Получим: янажоглнсбав.

Такой шифр имеет низкую стойкость. Зашифрованный текст имеет те же статистические характеристики, что и исходный. Поэтому проведя статистический анализ повторяемости отдельных символом так, как это сделал Шерлок Холмс в романе Конана Дойля «Тайна пляшущих человечков», можно восстановить таблицу подстановок. Поэтому простую замену в настоящее время используют редко и лишь в тех случаях, когда шифруемый текст короток.

4.1.2. Перестановки

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

Пример перестановки. Зашифровать текст «встреча состоится в 16-20» с помощью перестановки

N	1	2	3	4	5	6	7	8
P(N)	4	7	8	1	6	5	2	3

(первый символ переходит на 4-ю позицию, второй – на седьмую и т.д.).

Длина текста равна 24. Разобьем текст на блоки по восемь символов и переставим каждый блок по- отдельности. Получим:

№	1	2	3	4	5	6	7	8	1	2	3	4	5	6	7	8	1	2	3	4	5	6	7	8
M	в	с	т	р	е	ч	а		с	о	с	т	о	и	т	с	я		в	1	6	-	2	0
Enc(M)	р	а		в	ч	е	с	т	т	т	с	с	и	о	о	с	1	2	0	я	-	6		в

Получился текст «ра вчестттссиоос120я-6 и».

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

в	с	т	р	е
ч	а		с	о
с	т	о	и	т
с	я		в
8	-	2	0

Читаем по столбцам «вчасс8сатя-т о 2рсив0еот »

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

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

В методе DES используется расширенная перестановка следующего вида

32	1	2	3	4	5	4	5	6	7	8	9
8	9	10	11	12	13	12	13	14	15	16	17
16	17	18	19	20	21	20	21	22	23	24	25
24	25	26	27	28	29	28	29	30	31	32	1

В этом методе шифруемый текст разбивается на блоки по 64 бита, и каждый блок подвергается серии перестановок. Сначало выделяется первая половина блока из 32 битов – некоторый вектор X(x₁, x₂, ..., x₃₂). Он подается на вход этой перестановки, и после преобразования будет получен вектор E(X) длины 48 бит. При этом 1-й бит вектора E(X) будет равен x₃₂, второй – x₁, третий – x₂ и т.д. согласно таблице расширенной перестановки.