Дискретная математика (998286), страница 34
Текст из файла (страница 34)
ТЕОРЕМА Шифрование с открытым ключом корректно, то есть в предыдущих обозначениях Р; = Яь Доказательство Легко видеть, что Р; = (Я;)ьв шос1 и. Покажем, что ЧМ < и М" = М шод п. Действительно, числа д и е взаимно обратны по модулю (р — 1)(д — 1), то есть ед = 1+ й(р — 1)(д — 1) при некотором к. Если М ф О (шод р), то по малой теореме Ферма имеем: ,, щч-ы М"'аз М(М~к '1) = — М.1Щ' '> гв М (пюд р). Если М аа О (шод р), то сравнение Мев еа М (гпод р), очевидно, выполняется. Таким образом, УО<М<пМ"'квМ (пюдр).
Совершенно аналогично имеем ЧО<М< М"=— М ( дд), Глава б. Кодирование и по следствию к китайской теореме об остатках ЧМ < и М'" ш М (щог1 и). Поскольку Яг < и и Р; < и, заключаем, что т'( Р; = Яо Пример Генерация ключей: 1. р:=3, д:=11; 2. и: = )л) = 3 * 11 = 33; 3. (р — 1) (д — 1) = 2 * 10 = 20, е: = 7; 4, 8:=7 г щос1 20 = 3, (7*3 шог) 20 = 1), Пусть, Я,: = 3, Яз . = 1, Яз .
.= 2 (Я„Яз, Яз-< и = 33). Тогда код определяется сле- дующим образом. 1. Сг . = 3" тог1 33 = 2187 щоб 33 = 9; 2. Сэ.=1т щод 33 = 1 щод 33 =1; 3. Сз.=2" мог) 33= 128 щог( 33 = 29. При расшифровке имеем: 1. Рг..=йз шог( ЗЗ = 729 шог1 33 = 3; 2.
Рз',=1э тог1 33= 1 мог)33=1; 3. Рз . = 29э аког( 33 = 24389 щоб 33 = 2. ОТСТУПЛЕНИЕ Шифры с открытым ключом сравнительно просты в реализации, очень практичны (поскольку нет необходимости пересылать по каналам связи закрытый ключ н можно безопасно хранить его в одном месте) и в то же время обладают высочайшей криптостойкостью. Кажется, что дешифровать сообщение несложно; достаточно разложить открыто опубликованное число и на множители, восстановив числа р и Гь и далее можно легко вычислить секретный ключ 4.
Однако дело заключается в следующем. В настоящее время известны эффективные алгоритмы определения простоты чисел, которые позволяют за несколько минут подобрать пару очень больших простых чисел (по 100 и больше цифр в десятичной записи). В то же время неизвестны эффективные алгоритмы разложения очень больших чисел на множители. Разложение на множители числа в 200 и больше цифр потребовало бы сотен лет работы самого лучшего суперкомпьютера. При практическом применении шифров с открытым ключом используют действительно большие простые числа (не менее 100 цифр в десятичной записи, а обычно значительно больше).
В результате вскрыть этот шифр оказывается невозможно, если не существует эффективных алгоритмов разложения на множители (что очень вероятно, хотя и не доказано строго). 187 6.5. Шифрование 6.6.6. Цифровая подпись Шифр с открытым ключом позволяет выполнять и многие другие полезные операции, помимо шифрования и посылки сообщений в одну сторону. Прежде всего, для организации многосторонней секретной связи каждому из участников достаточно сгенерировать свою пару ключей (открытый и закрытый), а затем сообщить всем партнерам свой открытый ключ.
Заметим, что операции зашифровки и расшифровки по существу одинаковы, и различаются только показателем степени, а потому коммутируют: М = (М')з пюс1 и = Мьа пюй и = М"' гносео и = (М')~ шогг и = М. Это обстоятельство позволяет применять различные приемы, известные как цифровал (или электроянал) подпись. Рассмотрим следующую схему взаимодействия корреспондентов Х и У.
Отправитель Х кодирует сообщение Я своим закрытым ключом (С: = М" щи и) и посылает получателю У пару (Я,С), то есть подписанное сообщение. Получатель У, получив такое сообщение, кодирует подпись сообщения открытым ключом Х, то есть вычисляет Я': = С' шог( и. Если оказывается, что Я = Я', то это означает, что (нешифрованное!)' сообщение Я действительно было отправлено корреспондентом Х. Если же Я ф Я', то сообщение было искажено при передаче или фальсифицировано. ОТСТУПЛ Е НИ Е В подобного рода схемах возможны различные проблемы, которые носят уже не математический, а социальный характер.
Например, допустим, что злоумышленник Я имеет техническую возможность контролировать всю входящую корреспонденцию У незаметно для последнего. Тогда, перехватив сообщение Х, в котором сообщался открытый ключ е, злоумышленник Я может подменить открытый ключ Х своим собственным открытым ключом. После этого злоумышленник сможет фальсифицировать все сообщения Х подписывая их своей цифровой подписью, и, таким образом, действовать от имени Х. Другими словами, цифровая подпись удостоверяет, что сообщение Я пришло из того же источника, из которого был получен открытый клгоч е, но не более того.
Можно подписывать и шифрованные сообщения. Для этого отправитель Х сначала кодирует своим закрытым ключом сообщение Я, получая цифровую подпись С, а затем кодирует полученную пару (Я, С) открытым ключом получателя У. Получив такое сообщение, У сначала расшифровывает его своим закрытым ключом, а потом убеждается в подлинности полученного сообщения, сравнив его с результатом применения открытого ключа Х к подписи С. ЗАМЕЧАНИЕ К сожалению, лаже эти меры нс смогут защитить от злоумышленника Я, сумевшего полменить открытый ключ Х.
Конечно, в-этом случае я не сможет дешифровать исходное сообщение, но он сможет подменить исходное сообщение фальсифицированным. Глава 6. Кодирование 1ВВ Комментарии Вопросы, затронутые в этой главе, очень существенны для практических инфориационных технологий, которые невозможны без кодирования, сжатия данных б шифрования.
Разумеется, в реальных современных программах применяются Ьолее изощренные, по сравнению с описанными здесь простейшими вариантаии, методы. Общие вопросы кодирования достатоино подробно описаны в [17] и [25]. По вопросам сжатия данных, помимо сцецнальной литературы, см. 116]. Шифрованию посвящено множество специальных монографий. Лаконичное изаожение основных идей можно найти в [16]. Алгоритм 5.1 общеизвестен. Прочие алгоритмы этой главы заимствованы (в переработанном виде) из [17].
Упражнения 6.1. Является ли схема алфавитного кодирования (а -+ О,Ь -+ 10,с -+ 011,Н -+ 1011,е -б 1111) префиксной? разделимой? 6.2. Построить оптимальное префиксное алфавитное кодирование для алфавита (а,Ь,с,б() со следующим распределением вероятностей появления букв; р = 1/2, рь = 1/4, р = 1/В рб = 1/8.
6.3. Показать, что для несимметричных ошибок функция об((3 (3 ) 2 пйп шах шш [Е~((3'„(3'а)[, ппп, [а. ((3"',(3а)[, (д'"ее 1 ч,(еб(В' д"' Ц ™ (ебйк» В"Л1 является расстоянием. 6А. Проследить работу алгоритма сжатия Лемпела — Зива на примере следующего исходного текста: аЬааЬаааЬ. 6.5. Пусть в системе программирования имеется процедура йапдош(хе, которая получает целочисленный параметр и инициализирует датчик псевдослучайных чисел, н функция без параметров Япб, которая выдает следующее псевдослучайное число в интервале [О, Ц, Составить алгоритмы шифровки и расшифровки с закрытым ключом.
ГЛАВА 7 Графы Эта глава открывает вторую часть книги, целиком посвященную графам и алгоритмам на них. Среди дисциплин и методов дискретной математики теория графов и особенно алгоритмы на графах находят наиболее широкое применение в программировании. Как показано в разделе 7.5, между понятием графа и понятием отношения, рассмотренным в главе 1, имеется глубокая связь — в сущности зто равнообъемные понятия. Возникает естественный вопрос, почему же тогда графам оказывается столь явное предпочтение? Дело в том, что теория графов предоставляет очень удобный язык для описания программных (да и многих других) моделей. Этот тезис можно пояснить следующей аналогией.
Понятие отношения также можно полностью выразить через понятие множества (см. замечание в подразделе 1,5.1 и далее). Однако независимое определение понятия отношения удобнее — введение специальных терминов и обозначений упрощает изложение теории и делает ее более понятной. То же относится и к теории графов. Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные и тонкие вещи. Особенно важно наличие наглядной графической интерпретации понятия графа (подраздел 7.1.4).
Само название «граф» подразумевает наличие графической интерпретации. Картинки позволяют сразу «усмотреть» суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы. Эта глава практически полностью посвящена описанию языка теории графов. 7.1. Определения графов Как зто ни удивительно, но для понятия «граф» нет общепризнанного единого определения. Разные авторы, особенно применительно к разным приложениям, называют «графом» очень похожие, но все-таки различные объекты. Здесь используется терминология [23), которая была выбрана из соображений максимального упрощения определений и доказательств. Глава 7.
Графи 190 7.1.1. История теории графов Теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач. 1. Задача о Кенигсбергских мостах. Обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку (рнс. 7.1). Эта задача была решена Эйлером' в 1736 году Рис. 7.1. Иллюстрация к задаче с Кенигсбергских мостах 2. Задача о трех домах и трех колодцах. Имеется трн дома и три колодца.
Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 7.2). Эта задача была решена Куратовскимз в 1930 году. Рис. 7.2. Иллюстрация к задаче о трех домах и трех колодцах 3. Задача о четырех красках. Любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом (рис.
7.3). тдеонарл Эйлер (1707-1783) аиуратовский (1896-1979) 7Л. Определеиил графов Рис. 7.3. Иллюстрация к задаче о четырех красках 7.1.2. Основное определение Графом С(1; Е) называется совокупность двух множеств — непустого множества 'тг (множества вершин) и множества Е неупорядоченных пар различных элементов множества тг (Š— множество ребер). С(Ъ;Е)=(У;Е), Ъ'фе, Ес)гхЪ", Е=Е т. Число вершин графа С обозначим р, а число ребер — д р:=р(С):=Р~, т=я(С):='1Е). 7Л.З. Смежность Пусть е,, ез — вершины, е = (ет,ез) — соединяющее их ребро. Тогда вершина ет и ребро е иниидвнтнны, вершина ез и ребро е также инцидентны.
Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. Множество вершин, смежных с вершиной е, называется множвсглвом смежттостяи вершины е и обозначается Г+(е): Г"(е):=(ин'тг((и,е) ЕЕ), Г(е):=Г'(е):=Г+(е)0(е), и н Г(е) с=Ф е н Г(и). ЗАМЕЧАНИЕ Если ие оговорено противное, то подразумевается Г+ и обозначается просто Г. Если А с 'т' — множество вершин, то Г(А) — множество всех вершин, смежных с вершинами из А Г(А): = (и Н 'т' ~ 3е с А и с Г(е)) = Ц Г(е). .сх 192 ГлаВа 7. Графы 7.1.4. Диаграммы Обычно граф изображают диаграммой: вершины — точками (или кружками), ребра — линиями.
Пример На рис. 7.4 приведен пример диаграммы графа, имеющего четыре вершины и пять ребер. В этом графе вершины е, и ез, их и ез из и е«, с«и оы ег и е« смежны, а вершины ог и оз не смежны. Смежные ребра: ег и ез, ег и ез, ез и е«, е« и еы ег и ез, ег и ез, ез и ею е« и ез. Несмежные ребра: е, и ез, ег не«. Рис. 7.4. Диаграмма графа 7.1.5. Другие определения Часто рассматриваются следующие родственные графам обьекты. 1. Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (илн орграфои).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
