Новиков Ф.А. Дискретная математика для программистов (860615), страница 45
Текст из файла (страница 45)
В результате вскрыть этот шифр оказывается невозможно, если не существует эффективныхалгоритмов разложения на множители (что очень вероятно, хотя и не доказано строго).6.5.6. Цифровая подписьШифр с открытым ключом позволяет выполнять и многие другие полезныеоперации, помимо шифрования и посылки сообщений в одну сторону. Преждевсего, для организации многосторонней секретной связи каждому из участниковдостаточно сгенерировать свою пару ключей (открытый и закрытый), а затемсообщить всем партнёрам свой открытый ключ.Заметим, что операции зашифровки и расшифровки по существу одинаковы,и различаются только показателем степени, а потому коммутируют:М - ( M e ) d mod п = Med mod п - Mde mod n = ( M d ) e mod n = M.Это обстоятельство позволяет применять различные приёмы, известные как цифровая (или электронная) подпись.Рассмотрим следующую схему взаимодействия корреспондентов X и Y.
Отправитель X кодирует сообщение S своим закрытым ключом (С : = Sd mod п)и посылает получателю Y пару (S,C), то есть подписанное сообщение. Получатель Y, получив такое сообщение, кодирует подпись сообщения открытымключом отправителя X, то есть вычисляет S' : = Се mod п. Если оказывается, чтоS = S', то это означает, что (нешифровапиое!) сообщение S действительно былоотправлено корреспондентом X. Если же S Ф S', то сообщение было искаженопри передаче или фальсифицировано.238Глава 6. Кодирование 238ОТСТУПЛЕНИЕВ подобного рода схемах возможны различные проблемы, которые носят уже не математический, а социальный характер. Например, допустим, что злоумышленник Z имееттехническую возможность контролировать всю входящую корреспонденцию получателяY незаметно для последнего.
Тогда, перехватив сообщение отправителя X, в которомсообщался открытый ключ е, злоумышленник Z может подменить открытый ключ отправителя X своим собственным открытым ключом. После этого злоумышленник сможетфальсифицировать все сообщения отправителя X, подписывая их своей цифровой подписью, и, таким образом, действовать от имени отправителя X. Другими словами, цифроваяподпись удостоверяет, что сообщение S пришло из того же источника, из которого былполучен открытый ключ е, но не более того.Можно подписывать и шифрованные сообщения. Для этого отправитель X сначала кодирует своим закрытым ключом сообщение S, получая цифровую подписьС, а затем кодирует полученную пару (S, С) открытым ключом получателя Y.Получив такое сообщение, получатель Y сначала расшифровывает сообщениесвоим закрытым ключом, а потом убеждается в подлинности полученного сообщения, сравнив его с результатом применения открытого ключа отправителя Xк подписи С.ЗАМЕЧАНИЕК сожалению, даже эти меры не смогут защитить от злоумышленника Z, сумевшегоподменить открытый ключ отправителя X.
Конечно, в этом случае злоумышленник несможет дешифровать исходное сообщение, но он сможет подменить исходное сообщениефальсифицированным, а получатель пе сможет обнаружить подмену сообщения.КомментарииВопросы, затронутые в этой главе, очень существенны для практических информационных технологий, которые невозможны без кодирования, сжатия данныхи шифрования. Разумеется, здесь описаны простейшие варианты, в реальных современных программах применяются более изощрённые методы. Общие вопросыкодирования достаточно подробно описаны в [10] и [11]. Алгоритмы связанныес оптимальным и помехоустойчивым кодированием заимствованы (в переработанном виде) из [10].
По вопросам сжатия данных помимо специальной литературы см. [9]. Шифрованию посвящено множество специальных монографий.Лаконичное изложение основных идей можно найти в [17].Упражнения6.1. Является ли схема алфавитного кодирования(а —• 0, Ь —+ 10, с —> O i l , d —• 1011, епрефиксной? Разделимой?1111).239Упражнения6.2. Построить оптимальное префиксное алфавитное кодирование для алфавита{а, 6, с, d} со следующим распределением вероятностей появления букв:ра = 1/2, Рь = 1/4, pc=pd= 1/8.6.3. Показать, что для несимметричных ошибок функцияd6(0',P")=f2minmaxfmin\E&ЦЗ', (3"%min\ES(0"', 0")\является расстоянием.6.4.
Проследить работу алгоритма сжатия Лемпела-Зива на примере следующего исходного текста: abaabaaab.6.5. Пусть в системе программирования имеется процедура Randomize, котораяполучает целочисленный параметр и инициализирует датчик псевдослучайных чисел, и функция без параметров Rnd, которая выдает следующее псевдослучайное число в интервале [0,1]. Составить алгоритмы шифровки ирасшифровки с закрытым ключом.Глава 7ГрафыЭта глава открывает заключительную часть книги, целиком посвященную графам и алгоритмам на них. Среди дисциплин и методов дискретной математикитеория графов и особенно алгоритмы па графах находят наиболее широкое применение в программировании.
Как показано в разделе 7.5, между понятием графаи понятием бинарного отношения, рассмотренным в главе 1, имеется глубокаясвязь — можно сказать, что это равпообъёмпые понятия. Возникает естественный вопрос, почему же тогда графам оказывается столь заметное предпочтениепри изучении дискретной математики и программирования? Дело в том, что теория графов предоставляет очень удобный язык для описания программных (даи многих других) моделей. Этот тезис можно пояснить следующей аналогией.Понятие отношения также можно полностью выразить через понятие множества(см. замечание в подразделе 1.4.1 и далее). Однако независимое определениепонятия отношения удобнее — введение специальных терминов и обозначенийупрощает изложение теории и делает её более понятной.
То же относится и ктеории графов. Стройная система специальных терминов и обозначений теорииграфов позволяет просто и доступно описывать сложные и тонкие вещи. Особенно важна возможность наглядной графической интерпретации понятия графа(см. 7.1.4). Само название «граф» подразумевает наличие графической интерпретации. Картинки часто позволяют сразу «усмотреть» суть дела па интуитивномуровне, дополняя и украшая утомительные текстовые доказательства и сложныеформулы. Эта глава практически полностью посвящена описанию языка теорииграфов.7.1. Определения графовКак это пи удивительно, но для понятия «граф» пет общепризнанного единогоопределения.
Разные авторы, особенно применительно к разным приложениям, называют словом «граф» очень похожие, но все-таки различные объекты.Здесь используется терминология [28], которая была выбрана из соображениймаксимального упрощения определений и доказательств.7.1.1. История теории графовТеория графов многократно переоткрывалась разными авторами при решенииразличных прикладных задач.2417.1. Определения графов1. Задача о Кёнигсбергских мостах.
На рис. 7.1 представлен схематический планцентральной части города Кёнигсберг (ныне Калининград), включающий дваберега реки Перголя, два острова на ней и семь соединяющих их мостов. Задача состоит в том, чтобы обойти все четыре участка суши, пройдя по каждомумосту один раз, и вернуться в исходную точку. В 1736 году Эйлером 1 былопоказано, что решения этой задачи не существует. Точнее говоря, Эйлер получил необходимое и достаточное условие существования решеиия для всехзадач типа задачи о Кёнигсбергских мостах (см.
10.2.1).Т СJ ~ TРис. 7 . 1 . Иллюстрация к задаче о Кёнигсбергских мостах2. Задача о трёх домах и трёх колодцах. Имеется три дома и три колодца, какимто образом расположенные на плоскости. Требуется провести от каждого домак каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 7.2).Эта задача также не имеет решеиия.
В 1930 году Куратовским1 было доказанонамного более сильное утверждение, а именно достаточность условия существования решения для всех задач типа задачи о трёх домах и трёх колодцах(необходимость этого условия была известна и ранее, см. 10.8.2).Рис. 7 . 2 . Иллюстрация к задаче о трёх домах и трёх колодцах3.
Задача о четырёх красках. Разделение плоскости на неперекрывающиеся области называется картой. Области на карте называются соседними, если ониимеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области пе были закрашены одним цветом(рис. 7.3). С конца XIX века известна гипотеза, что для этого достаточно четырёх красок. В 1976 году Аппель и Хейкен опубликовали решение задачи11Леонард Эйлер (1707-1783).Казимир Куратовский (1896-1979).242Глава 7. Графыо четырёх красках, которое базировалось на переборе вариантов с помощьюкомпьютера.1ОТСТУПЛЕНИЕРешение задачи о четырёх красках Аппелем и Хейкеном «программным путем» явилосьпрецедентом, породившим бурную дискуссию, которая отнюдь не закончена.
Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около2000) типов потенциальных контрпримеров к теореме о четырёх красках и показать, чтони один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно — объём перебора выходит далеко за рамки человеческих возможностей.Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки...
Методыформального доказательства правильности программ не применимы к программам такойсложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и вданном случае вообще невозможно. Таким образом, остаётся уповать на программистскуюквалификацию авторов и верить, что они всё сделали правильно.7.1.2. Основное определениеГрафом G(V,E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества Е двухэлементных подмножеств множества V (Е — множество рёбер),G{V,E) =f (V\E),Уф0,EC2VkVeeE(|e| = 2 ) .ЗАМЕЧАНИЕЛегко видеть, что любое множество Е двухэлементных подмножеств множества V определяет симметричное бинарное отношение на множестве V.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
