Основы теории защиты информации

Криптография (тайнопись) - это раздел математики, в котором изучаются и разрабатываются системы изменения письма с целью сделать его непонятным для непосвященных лиц. Известно, что еще в V веке до нашей эры тайнопись использовалась в Греции. В современном мире, где все больше и больше услуг предоставляется через использование информационных технологий, проблема защиты информации методами криптографии имеет первостепенное значение. Сегодня большая часть обмена информацией проходит по компьютерным сетям и часто (в бизнесе, военным и прочее) нужно обеспечивать конфиденциальность такого обмена. Теоретические основы классической криптографии впервые были изложены Клодом Шенноном в конце 1940-х годов.

Простейшая система шифрования - это замена каждого знака письма на другой знак по выбранному правилу. Юлий Цезарь, например, заменял в своих секретных письмах первую букву алфавита на четвертую, вторую - на пятую, последнюю - на третью и т.п., т.е. A на D, B на E, Z на C и т.п. Октавиан Август заменял каждую непоследнюю букву алфавита на следующую, а последнюю на первую. Подобные шифры, называемые простой заменой или подстановкой, описаны в рассказах "Пляшущие человечки" А. К. Дойла, "Золотой жук" Э. По и других.

Шифры простой замены легко поддаются расшифровке, при знании исходного языка сообщения, т.к. каждый письменный язык характеризуется частотой встречаемости своих знаков. Например, в английском языке чаще всего встречается буква E, а в русском - О. Таким образом, в шифрованном подстановкой сообщении на русском языке самому частому знаку будет с большой вероятностью соответствовать буква О. Вероятность будет расти с ростом длины сообщения.

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

В шифрах- перестановках знаки сообщения специальным образом переставляются между собой, например, записывая сообщение в строки заданной длины и беря затем последовательность слов в столбцах в качестве шифра. Сообщение "ТЕОРИЯИНФОРМАЦИИ", используя строки длины 4, будет в шифрованном таким методом виде выглядеть как "ТИФАЕЯОЦОИРИРНМИ", потому что при шифровании использовался следующий прямоугольник:

$$\centerline{\vbox{\offinterlineskip\halign{\strut\tt#\cr ТЕОР\cr ИЯИН\cr ФОРМ\cr АЦИИ.\cr}}}$$

Шифры-перестановки в общем случае практически не поддаются дешифровке. Для их дешифровки необходимо знать дополнительную информацию. Крупный недостаток подобных шифров в том, что если удастся каким-то образом расшифровать хотя бы одно сообщение, то в дальнейшем можно расшифровать и любое другое. Модификацией шифров-перестановок являются шифры-перестановки со словом-ключом, которое определяет порядок взятия слов-столбцов. Например, если для рассмотренного шифра взять ключ "РЫБА", то шифрованное сообщение будет выглядеть как "РНМИОИРИТИФАЕЯОЦ".

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

Наиболее простой способ использования ключа хорошего шифра следующий: под символами сообщения записывается раз за разом ключ, затем номера соответствующих знаков сообщения и ключа складываются. Если полученная сумма больше общего числа знаков, то от нее отнимается это общее число знаков. Полученные числа будут номерами символов кода. С ростом длины ключа трудоемкость дешифровки подобного шифра стремительно растет. Например, рассмотренное ранее сообщение с ключом "КИБЕРНЕТИКА" в шифрованном виде будет выглядеть как "ЮОРЦЪНОБЮЪСШЙШОЪ". Процесс шифровки описывается схемой:

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

В информационных сетях использование традиционных систем шифрования с ключом затрудненно необходимостью иметь специальный особо защищенный способ для передачи ключа. В 1976 году У. Диффи (Diffie W.) и М. Хеллман (Hellman M.) - инженеры-электрики из Станфордского университета, а также студент Калифорнийского университета Р. Меркль (Merkle R.), предложили новый принцип построения криптосистем, не требующий передачи ключа принимающему сообщение и сохранения в тайне метода шифрования. В дальнейшем, в качестве примеров, рассмотрим три системы, основанные на идеях Диффи и Хеллмана: без передачи ключей, с открытым ключом и электронную подпись - все они в свою очередь основаны на математическом фундаменте теории чисел.

Упражнение 47 Зашифровать сообщение "КИБЕРНЕТИКА" ключом "ДИСК".

Криптосистема без передачи ключей

Пусть абоненты $$A, B, C, \ldots$$ условились организовать между собой секретную переписку. Для этой цели они выбирают достаточно большое простое число $$p$$ такое, что $$p-1$$ хорошо разлагается на не очень большие простые множители. Затем каждый из абонентов независимо один от другого выбирает себе некоторое натуральное число, взаимно простое с $$p-1$$. Пусть число абонента $$A$$ - $$a$$, абонента $$B$$ - $$b$$ и т.д. Числа $$a, b, \ldots$$ составляют первые секретные ключи соответствующих абонентов. Вторые секретные ключи ( $$\alpha$$ для $$A$$, $$\beta$$ для $$B$$ и т.д.) находятся из уравнений: для $$A$$ из $$a\alpha\equiv1\pmod{\varphi(p)}$$, $$0<\alpha<p-1$$ ; для $$B$$ - из $$b\beta\equiv1\pmod{\varphi(p)}$$, $$0<\beta<p-1$$ и т.д. Пересылаемые сообщения, коды-числа, должны быть меньше $$p-1$$. В случае, когда сообщение больше или равно $$p-1$$, оно разбивается на части таким образом, чтобы каждая часть была числом, меньшим $$p-1$$.

Предположим абонент $$A$$ решил отправить сообщение $$m$$ ( $$m<p-1$$ ) $$B$$. Для этого он сначала зашифровывает свое сообщение ключом $$a$$, получая по формуле $$m_1\equiv m^a\pmod p$$ шифрованное сообщение $$m_1$$, которое отправляется $$B$$. $$B$$, получив $$m_1$$, зашифровывает его своим ключом $$b$$, получая по формуле $$m_2\equiv m_1^b\pmod p$$ шифрованное сообщение $$m_2$$, которое отправляется обратно к $$A$$. $$A$$ шифрует полученное сообщение ключом $$\alpha$$ по формуле $$m_3\equiv m_2^\alpha\pmod p$$ и окончательно отправляет $$m_3$$ к $$B$$. $$B$$, используя ключ $$\beta$$, сможет теперь расшифровать исходное сообщение $$m$$. Действительно, $$m_4\equiv m_3^\beta\equiv m^{a\alpha b\beta}\equiv m\pmod p$$, т.к. $$a\alpha b\beta\equiv1\pmod{\varphi(p)}$$, следовательно, $$a\alpha b\beta=k\varphi(p)+1$$ для некоторого целого $$k$$ и $$m^{k\varphi(p)+1}\equiv(m^{\varphi(p)})^km\equiv m\pmod p$$, т.к. $$m^{\varphi(p)}\equiv1\pmod p$$ по теореме Эйлера-Ферма.

Пример. Абоненты $$A$$ и $$B$$ вместе выбрали $$p=23$$ ( $$\varphi(23)=22$$ ), $$A$$ выбрал $$a=5$$, а $$B$$ - $$b=7$$. Затем из уравнения $$5\alpha\equiv1\pmod{\varphi(23)}$$ $$A$$ находит $$\alpha=9$$, а $$B$$ из подобного уравнения находит $$\beta=19$$. При передаче сообщения $$m=17$$ от $$A$$ к $$B$$ сначала $$A$$ отправляет к $$B$$ $$m_1\equiv 17^5\equiv 21\pmod{23}$$, из $$m_1=21$$ $$B$$ вычисляет $$m_2\equiv 21^7\equiv 10\pmod{23}$$ и отправляет его обратно $$A$$, из $$m_2=10$$ $$A$$ вычисляет для $$B$$ $$m_3\equiv 10^9\equiv 20\pmod{23}$$, наконец, $$B$$ может прочитать посланное ему сообщение $$20^{19}\equiv 17\pmod{23}$$.

Упражнение 48 Между абонентами $$A$$ и $$B$$ установлен секретный канал связи без передачи ключей при заданных $$p=167$$ и их первых ключах 15 и 21. Описать процесс передачи сообщений 22 (от $$A$$ к $$B$$ ) и 17 (от $$B$$ к $$A$$ ).

Криптосистема с открытым ключом

Первую и наиболее известную систему с открытым ключом разработали в 1978 году американцы Р. Ривест (Rivest R.), Э. Шамир (Shamir A.) и Л. Адлеман (Adleman L.). По их именам эта система получила название RSA.

Пусть абоненты $$A$$ и $$B$$ решили организовать для себя возможность секретной переписки. Для этого каждый из них независимо выбирает два больших простых числа ( $$p_{A_1}$$, $$p_{A_2}$$ и $$p_{B_1}$$, $$p_{B_2}$$ ), находит их произведение ( $$r_A$$ и $$r_B$$ ), функцию Эйлера от этого произведения ( $$\varphi(r_A)$$ и $$\varphi(r_B)$$ ) и случайное число ( $$a$$ и $$b$$ ), меньшее вычисленного значения функции Эйлера и взаимно простое с ним. Кроме того, $$A$$ из уравнения $$a\alpha\equiv1\pmod{\varphi(r_A)}$$ находит $$\alpha$$ ( $$0<\alpha<\varphi(r_A)$$ ), а $$B$$ из уравнения $$b\beta\equiv1\pmod{\varphi(r_B)}$$ находит $$\beta$$ ( $$0<\beta<\varphi(r_B)$$ ). Затем $$A$$ и $$B$$ печатают доступную всем книгу паролей вида:

Теперь кто-угодно может отправлять конфиденциальные сообщения $$A$$ или $$B$$. Например, если пользователь книги паролей хочет отправить сообщение $$m$$ для $$B$$ ( $$m$$ должно быть меньшим $$r_B$$, или делиться на куски, меньшие $$r_B$$ ), то он использует ключ $$b$$ из книги паролей для получения шифрованного сообщения $$m_1$$ по формуле $$m_1\equiv m^b\pmod{r_B}$$, которое и отправляется $$B$$. $$B$$ для дешифровки $$m_1$$ использует ключ $$\beta$$ в формуле $$m_1^\beta\equiv m^{b\beta}\equiv m\pmod{r_B}$$, т.к. $$b\beta\equiv1\pmod{\varphi(r_B)}$$, следовательно, $$b\beta=k\varphi(r_B)+1$$ для некоторого целого $$k$$ и $$m^{k\varphi(r_B)+1}\equiv(m^{\varphi(r_B)})^km\equiv m\pmod{r_B}$$, т.к. $$m^{\varphi(r_B)}\equiv1\pmod{r_B}$$ по теореме Эйлера-Ферма. Доказано12, что задача нахождения секретного ключа $$\beta$$ по данным из книги паролей имеет ту же сложность, что и задача разложения числа $$r_B$$ на простые множители.

Пример. Пусть для $$A$$ $$p_{A_1}=7$$ и $$p_{A_2}=23$$, тогда $$r_A=p_{A_1}p_{A_2}=161$$, $$\varphi(161)=6*22=132$$, $$a=7$$, $$\alpha=19$$ (из уравнения $$7\alpha\equiv1\pmod{132}$$ ). Следовательно, запись в книге паролей для $$A$$ будет иметь вид $$A\colon\ 161,7$$. Если кто-то захочет отправить $$A$$ секретное сообщение $$m=3$$, то он должен сначала превратить его в шифровку $$m_1$$ по формуле $$m_1\equiv 3^7\equiv 94\pmod{161}$$. Когда $$A$$ получит $$m_1=94$$ он дешифрует его по формуле $$m\equiv 94^{19} \equiv 3\pmod{161}$$.

Упражнение 49 Нужно послать секретные сообщения 25 и 2 для JB и 14 для CIA, используя следующие записи открытой книги паролей криптосистемы RSA:

JB: 77,7;
CIA: 667,15.

Упражнение 50 Пользователь системы RSA выбрал $$p_1=11$$ и $$p_2=47$$. Какие из чисел 12, 33, 125, 513 он может выбрать для открытого ключа? Вычислить для них закрытый ключ.

Упражнение 51 Пользователь системы RSA, выбравший $$p_1=17$$, $$p_2=11$$ и $$a=61$$, получил шифрованное сообщение $$m_1=3$$. Дешифровать $$m_1$$.

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

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

Пусть $$W_1, W_2, \ldots, W_n$$ - абоненты системы с электронной подписью. Все они независимо друг от друга выбирают и вычисляют ряд чисел точно так же как и в системе с открытым ключом. Пусть $$i$$ -ый абонент ( $$1\ne i\le n$$ ) выбирает два больших простых числа $$p_{i1}$$ и $$p_{i2}$$, затем вычисляет их произведение - $$r_i=p_{i1}p_{i2}$$ и функцию Эйлера от него - $$\varphi(r_i)$$, затем выбирает первый ключ $$a_i$$ из условий $$0<a_i<\varphi(r_i)$$, $$\hbox{НОД}(a_i, \varphi(r_i))=1$$ и, наконец, вычисляет второй ключ $$\alpha_i$$ из уравнения $$a_i\alpha_i\equiv 1\pmod{\varphi(r_i)}$$. Записи в книге паролей будут иметь вид:

Если абонент $$W_1$$ решает отправить секретное письмо $$m$$ $$W_2$$, то ему следует проделать следующую последовательность операций:

$$W_2$$ для дешифровки сообщения $$m_2$$ должен знать, кто его отправил, поэтому к $$m_2$$ должна быть добавлена электронная подпись, указывающая на $$W_1$$. Если $$r_1<r_2$$, то для расшифровки $$m_2$$ сначала применяется ключ $$\alpha_2$$, а затем - $$a_1$$, если же $$r_1>r_2$$, то для расшифровки $$m_2$$ сначала применяется ключ $$a_1$$, а затем - $$\alpha_2$$. Рассмотрим случай $$r_1<r_2$$: $$m_2^{\alpha_2}\equiv m_1^{a_2\alpha_2}\equiv m_1\pmod{r_2}$$ и $$m_1^{a_1}\equiv m^{\alpha_1a_1}\equiv m\pmod{r_1}$$ по теореме Эйлера-Ферма.

Пример. Пусть $$W_1$$ выбрал и вычислил следующие числа $$p_{11}=7, p_{12}=13, r_1=p_{11}p_{12}=91, \varphi(91)=72, a_1=5, \alpha_1=29$$, а $$W_2$$ - следующие $$p_{21}=11, p_{22}=23, r_2=253, \varphi(253)=220, a_2=31, \alpha_2=71$$. После занесения записей о $$W_1$$ и $$W_2$$ в открытую книгу паролей, $$W_2$$ решает послать сообщение $$m=41$$ для $$W_1$$. Т. к. $$r_2>r_1$$, то сообщение сначала шифруется ключом $$a_1$$, а затем ключом $$\alpha_2$$: $$m_1\equiv 41^5\equiv 6\pmod{91}$$, $$m_2\equiv 6^{71}\equiv 94\pmod{253}$$. Сообщение $$m_2$$ отправляется $$W_1$$. Получив $$m_2=94$$, $$W_1$$, зная, что оно пришло от $$W_2$$, дешифрует его сначала ключом $$a_2$$, а затем ключом $$\alpha_1$$: $$94^{31}\pmod{253}\equiv 6$$, $$6^{29}\pmod{91}\equiv 41$$.

Если подписать сообщение открытым образом, например, именем отправителя, то такая "подпись" будет ничем не защищена от подделки. Защита электронной подписи обычно реализуется с использованием таких же методов, что в криптосистеме с открытым ключом.

Электронная подпись генерируется отправителем по передаваемому сообщению и секретному ключу. Получатель сообщения может проверить его аутентичность по прилагаемой к нему электронной подписи и открытому ключу отправителя.

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

Стандарт шифрования данных

В 1977 году в США был предложен стандарт для шифрования данных - DES (Data Encryption Standard), разработанный в IBM. В 1980 он был одобрен ведущей мировой организацией по стандартам - ANSI. В настоящее время алгоритм DES широко используется для защиты коммерческой информации.

DES - это классическая криптосистема с открытым способом шифровки и дешифровки, секретность которой обеспечивается исключительно ключом. Основные достоинства DES:

Главный недостаток DES связан с его классической организацией, т.е. с необходимостью обеспечивать сверхнадежный канал для передачи ключей.

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

Примером программы, реализующей алгоритм DES, является программа DISKREET из пакета Norton Utilities.