Основы теории информации и криптографии - -Учебное пособие (В.В. Лидовский)

11. лекция: основы теории защиты информации

лекции дается понятие криптографии, использование ее на практике, различные методы криптографии, их свойства и методы шифрования. Вводится понятие нераскрываемый шифр. Подробно описываются две системы шифрования: криптосистема без передачи ключей и криптосистема с открытым ключом. Хорошее математическое обоснование систем. Суть электронной подписи. Рассказывается о стандарте шифрования данных DES

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

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

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

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

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

centerline{vbox{offinterlineskiphalign{&strut t#cr
ТЕОРcr
ИЯИНcr
ФОРМcr
АЦИИ.cr}}}

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

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

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

Т	Е	О	Р	И	Я	И	Н	Ф	О	Р	М	А	Ц	И	И
20	6	16	18	10	33	10	15	22	16	18	14	1	24	10	10
К	И	Б	Е	Р	Н	Е	Т	И	К	А	К	И	Б	Е	Р
12	10	2	6	18	15	6	20	10	12	1	12	10	2	6	18
32	16	18	24	28	15	16	2	32	28	19	26	11	26	16	28
Ю	О	Р	Ц	Ъ	Н	О	Б	Ю	Ъ	С	Ш	Й	Ш	О	Ъ

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

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

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

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

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

Предположим абонент решил отправить сообщение ( m<p-1 ) . Для этого он сначала зашифровывает свое сообщение ключом , получая по формуле m_1equiv m^apmod p шифрованное сообщение m_1 , которое отправляется . , получив m_1 , зашифровывает его своим ключом , получая по формуле m_2equiv m_1^bpmod p шифрованное сообщение m_2 , которое отправляется обратно к . шифрует полученное сообщение ключом alpha по формуле m_3equiv m_2^alphapmod p и окончательно отправляет m_3 к . , используя ключ eta , сможет теперь расшифровать исходное сообщение . Действительно, $m_4equiv m_3^etaequiv m^{aalpha beta}equiv mpmod p$ , т.к. aalpha betaequiv1pmod{varphi(p)} , следовательно, aalpha beta=kvarphi(p)+1 для некоторого целого и $m^{kvarphi(p)+1}equiv(m^{varphi(p)})^kmequiv mpmod p$ , т.к. $m^{varphi(p)}equiv1pmod p$ по теореме Эйлера-Ферма.

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

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

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

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

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

Теперь кто-угодно может отправлять конфиденциальные сообщения или . Например, если пользователь книги паролей хочет отправить сообщение для ( должно быть меньшим r_B , или делиться на куски, меньшие r_B ), то он использует ключ из книги паролей для получения шифрованного сообщения m_1 по формуле $m_1equiv m^bpmod{r_B}$ , которое и отправляется . для дешифровки m_1 использует ключ eta в формуле $m_1^etaequiv m^{beta}equiv mpmod{r_B}$ , т.к. $betaequiv1pmod{varphi(r_B)}$ , следовательно, beta=kvarphi(r_B)+1 для некоторого целого и $m^{kvarphi(r_B)+1}equiv(m^{varphi(r_B)})^kmequiv mpmod{r_B}$ , т.к. $m^{varphi(r_B)}equiv1pmod{r_B}$ по теореме Эйлера-Ферма. Доказано1) , что задача нахождения секретного ключа eta по данным из книги паролей имеет ту же сложность, что и задача разложения числа r_B на простые множители.

Пример. Пусть для $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 (из уравнения 7alphaequiv1pmod{132} ). Следовательно, запись в книге паролей для будет иметь вид Acolon 161,7 . Если кто-то захочет отправить секретное сообщение m=3 , то он должен сначала превратить его в шифровку m_1 по формуле $m_1equiv 3^7equiv 94pmod{161}$ . Когда получит m_1=94 он дешифрует его по формуле $mequiv 94^{19} equiv 3pmod{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 - абоненты системы с электронной подписью. Все они независимо друг от друга выбирают и вычисляют ряд чисел точно так же как и в системе с открытым ключом. Пусть -ый абонент ( 1
e ile 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_ialpha_iequiv 1pmod{varphi(r_i)}$ . Записи в книге паролей будут иметь вид:

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

Если m>min(r_1,r_2) , то разбивается на части, каждая из которых меньше меньшего из чисел r_1 и r_2 ;

Если r_1<r_2 , то сообщение сначала шифруется ключом alpha_1 ( $m_1equiv m^{alpha_1}pmod{r_1}$ ), а затем - ключом a_2 ( $m_2equiv m_1^{a_2}pmod{r_2}$ ), если же r_1>r_2 , то сообщение сначала шифруется ключом a_2 ( $m_1equiv m^{a_2}pmod{r_2}$ ), а затем - ключом alpha_1 ( $m_2equiv m_1^{alpha_1}pmod{r_1}$ );

Шифрованное сообщение m_2 отправляется 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_2alpha_2}equiv m_1pmod{r_2}$ и $m_1^{a_1}equiv m^{alpha_1a_1}equiv mpmod{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 . Тdsk к. r_2>r_1 , то сообщение сначала шифруется ключом a_1 , а затем ключом alpha_2 : $m_1equiv 41^5equiv 6pmod{91}$ , $m_2equiv 6^{71}equiv 94pmod{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:

используется только один ключ фиксированной длины 56 бит (в системах с открытым ключом длина ключа должна быть более 300 бит);

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

относительная простота алгоритма обеспечивает высокую скорость работы (как минимум, на порядок выше скорости работы алгоритма для криптосистемы с открытым ключом);

достаточно высокая стойкость алгоритма (стойкость конкретного зашифрованного сообщения зависит от выбора ключа).

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

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

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

| Оглавление|

11. лекция: основы теории защиты информации

Содержание