Курсы повышения квалификации

Математические основы информатики

А.Г. Гейн

Учебный план

№_ГАЗЕТЫ

Лекция

17/2007

Лекция 1.Что такое “математические основы информатики”. Почему информатику нередко считают близкой род-
ственницей математики? Верно ли это? Возможна ли информатика без математики? Какая математика нужна для освоения
информатики? Может ли школьная математика дать основу для информатики?

Информация и ее кодирование. Математика кодов. Коды, исправляющие ошибки. Экономное кодирование.

18/2007

Лекция 2. Математические модели формальных исполнителей. Что такое формальная обработка информации? Конеч-
ные автоматы. Что первично: язык или исполнитель? Грамматика языка. Распознаваемые языки. Универсальные исполни-
тели (машина Тьюринга, машина Поста).

19/2007

Лекция 3.Алгоритм и его свойства. Алгоритмическая неразрешимость. Вычислимость. Сложность.
Контрольная работа № 1.

20/2007

Лекция 4. Графы. Графы и орграфы. В каких задачах они возникают? Различные свойства графов (эйлеровость, гамильто-
новость, планарность, двудольность). Сети. Потоки в сетях. Представление графов. Основные алгоритмы на графах.

21/2007

Лекция 5. Логические модели в информатике. Алгебра высказываний. Булевы функции. Нормальные формы. Полные
классы булевых функций. Релейно-контактные схемы. Вентили. Математические модели процессора и памяти компьютера. Предикаты и отношения. Реляционная алгебра. Теоретические основы реляционных СУБД. Языки логического программирования и их математическое основание.
Контрольная работа № 2.

22/2007

Лекция 6. Компьютерная теория чисел и вычислительная геометрия. Зачем нужна теория чисел в компьютерных
науках? Гонка за простыми числами. Как разложить число на множители? Чем отличается теоретическая геометрия от
вычислительной? Почему гладко на бумаге, но коряво на компьютере? Основные правила и алгоритмы вычислительной
геометрии.
23/2007 Лекция 7. Защита информации. Защита символьной информации. Что нужно защищать? Электронная подпись. Системы
верификации. Криптосистемы с открытым ключом. Защита графической информации. Математика электронных водяных знаков.
24/2007 Лекция 8. Основы методики преподавания математических основ информатики.
Итоговая работа

Лекция 8. Защита информации

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

§ 26. Математика и криптография

Пусть имеется сообщение S, записанное в некотором алфавите А. Оно преобразуется в другое сообщение Т. Вообще говоря, это другое сообщение может быть исполнено в другом алфавите. Например, пляшущими человечками, как у Конан Дойла. Но каждому ясно, что это, скорее, психологическое воздействие, нежели реальная преграда для дешифрования — ведь нет никакой разницы, как изображены символы алфавита, если нам все равно неизвестно, каким символам исходного алфавита они соответствуют. Конечно, может так случиться, что алфавит сообщения Т содержит больше символов, нежели алфавит А. Ну так надо просто расширить алфавит А, выписав все символы, которые встречаются в сообщении Т1.

Фактически мы уже высказали основную идею криптографии — науки о способах шифрования сообщений с целью ее защиты от незаконных пользователей. Она состоит в том, что фиксируется некоторое преобразование f алфавита А, и в каждом сообщении над алфавитом А каждая входящая в него буква b заменяется на f(b)2. Конечно, функции бывают разными. На роль f нам годится лишь такая, для которой существует алгоритм, позволяющий вычислить ее значение. Такую функцию называют вычислимой3. Поэтому нередко вместо функции шифрования говорят об алгоритме шифрования. Важно, конечно, чтобы функция f была обратимой, т.е. по значению f(b) однозначно восстанавливалось само b.

Самый простой вариант функции f реализуется в так называемом “шифре замены”. В этом случае функция f осуществляет взаимно-однозначное отображение алфавита А на себя. К примеру, в шифре Цезаря каждая буква заменяется на букву, расположенную в алфавите на 3 символа правее (после последней буквы алфавита снова идет первая, за ней вторая и т.д.).
В русском варианте фраза “А я иду, шагаю по Москве” превратится в “Г в лжц, ыгёгб тс Псфнез”. Получив такую фразу, вы, может быть, и не сразу догадаетесь, о чем идет речь, но для опытного криптоаналитика расшифровать ее труда не составит. И дело даже не в том, что перебрать все возможные варианты обратной
для f функции и выбрать тот из них, который дает осмысленную фразу, для современного компьютера не столь уж тяжелая задача (таких вариантов менее 33!). Просто любой естественный язык имеет определенные статистические закономерности, которые позволяют резко уменьшить количество перебираемых вариантов. Простейшая из таких закономерностей состоит в том, что в русском языке не так уж много слов, состоящих из одной буквы4. Если иметь достаточно длинный текст, то наиболее часто встречающийся в нем символ просто будет совпадать с буквой, обладающей наибольшей частотой в текстах на данном языке (например, в русском языке такой буквой является “е”). Значит, сразу становится ясно, какой буквой надо заменять этот символ. Так постепенно можно выявить ключ шифрования и по нему построить дешифрующий ключ5.

Есть две идеи, как сделать так, чтобы жизнь криптоаналитикам медом не казалась. Первая состоит в том, что функция f может зависеть от одного или нескольких параметров. Такие параметры называют ключом шифрования. К примеру, текст можно разрезать на порции одной длины и для каждой порции применить свой алгоритм замены. Для уже упоминавшейся фразы “А я иду, шагаю по Москве” ее нарезка на порции длины 4 (пробел учитывается как символ, но для простоты нами не шифруется) и шифрование каждой нечетной порции сдвигом на 2, а нечетной — сдвигом на 4 приведет к тексту “В б мзч, ъведв ср Крумдж”. Теперь расшифровка букв “В” и “б” в начале текста не очень-то помогает расшифровать слово “ъведв”. И статистические закономерности появления сочетаний букв в этом тексте уже совсем не те, что в исходном.

В рассмотренном примере три параметра шифрования: числа 4, 2, 4, определяющие исполнение алгоритма. Они и составляют ключ, который должен быть сообщен получателю сообщения, чтобы тот мог поручить компьютеру мгновенно дешифровать текст. Строго говоря, простой алгоритм замены тоже обладает ключом — число 3. Но, как мы уже обсуждали, такой ключ можно и не знать для того, чтобы успешно дешифровать текст сообщения.

Предельным случаем является смена шифрующего алгоритма на каждом символе передаваемого сообщения. Если шифрующим алгоритмом по-прежнему остается алгоритм замены, то в качестве ключа выступает последовательность натуральных чисел. Заметим, что каждое число не превосходит числа символов в алфавите, поэтому ключ снова можно записать символами данного алфавита. Это не принципиально с точки зрения математической сути, но облегчает запоминание ключа — фразу “Весна идёт” запомнить легче, чем последовательность чисел 3, 6, 19, 15, 1, 0, 10, 5, 7, 20 (здесь мы пробелу поставили в соответствие число 0). Наша избитая фраза “А я иду, шагаю по Москве” шифруется тогда как “Г е ьтф, шйзлс тф Аэтклй”. Поскольку в ключе всего лишь 10 символов, то после кодирования первых 10 букв сообщения мы используем ключ с его начала. Конечно, взломать такой шифр уже намного сложнее, но если массив сообщений, зашифрованных одним и тем же ключом, достаточно велик, то и в нем обнаруживаются статистические закономерности. Из этого примера видно, что ключ должен быть достаточно длинным, оптимально, чтобы его длина совпадала с длиной сообщения и в нем самом не наблюдалось бы каких-либо статистических закономерностей. Это утверждение, аргументированное нами, можно сказать, “на пальцах”, является одной из базовых математических теорем криптографии. Она была доказана К.Шенноном в 1945 г. и опубликована в докладе “Математическая теория криптографии”, рассекреченном лишь в 60-е годы прошлого века. Вот ее формулировка:

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

Алгоритм шифрования при этом может быть совсем простым — например, побитовое сложение исходного сообщения с ключом (операция XOR). Дешифрование в этом случае осуществляется также побитовым сложением шифрованного сообщения с тем же ключом. Такая реализация абсолютно стойкого шифра предложена Вериамом и носит его имя.

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

Впрочем, математику — математическое, а информатику — информатическое. Мы уже неоднократно повторяли мысль, что как задачу сформулируешь (т.е. построишь модель), такой ответ и получишь. Если в качестве существенного фактора выдвигается абсолютная стойкость шифра, то и ответ получится соответствующий. А всегда ли нужна такая стойкость? Ведь нередко информация, которая еще вчера была секретной, сегодня публикуется в средствах массовой информации. Например, намерение компании продать свои акции или купить акции другой компании остается секретом только до момента совершения этой сделки, однако указания о ней, даваемые компанией своим биржевым агентам, не должны стать известными конкурентам ранее определенного срока. Таким образом, задача не в том, чтобы противник вообще никогда не смог расшифровать сообщение, а в том, чтобы он не успел это сделать за определенное время. А это совсем другая постановка задачи, и потому решение у нее совсем другое.

Однако, прежде чем обсуждать такую “исправленную” задачу, мы обсудим вторую идею построения шифрующей функции f. Она состоит в том, чтобы эта функция зависела от шифруемого текста. Вот пример. Запишем сообщение “А я иду, шагаю по Москве” в несколько строк по 4 символа в каждой строке (для наглядности мы разместили его на клетчатой бумаге):

А теперь запишем его, читая символы по столбцам. Получится “Аи аос дшю кяуа Мв ,гпое”. Приведенный нами способ шифрования называется шифром “Сцитала” и был использован спартанским полководцем Лисандром6.

Другой разновидностью являются так называемые “решеточные шифры”. Для этого создается шаблон в виде квадратной сетки с вырезанными клетками (пример шаблона размером 6 х 6 приведен на рис. 2, вырезанные клетки закрашены). Квадрат накладывается на лист бумаги, в клетки вписываются буквы, затем квадрат поворачивают на 90°, снова в клетки вписывают буквы, еще раз поворачивают на 90°, снова в клетки вписывают буквы, еще раз поворачивают на 90° и снова в клетки вписывают буквы. После этого получается сплошной текст. Недостатком является то, что количество символов в шифруемом сообщении должно быть квадратом четного числа. Впрочем, можно в конце сообщения всегда добавить сколько-то неинформативных символов. Саму решетку тоже можно хранить не как геометрический объект, а описанием координат вырезанных клеток. На рис. 3 показан результат шифрования фразы “А я иду, шагаю по Москве” шаблоном, изображенным на рис. 2; в качестве дополнительного неинформативного символа выбрана буква “р”.

Получившийся текст можно снова выписать в строку, получится “МАшрорарсг акяр рв юе рдрррупро, рр”.

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

Вот если бы ключ можно было сделать не секретным…

Вопросы и задания

1. В тексте параграфа сказано, что в шифре Цезаря, которым зашифрована фраза “А я иду, шагаю по Москве”, для дешифрования потребуется перебрать намного меньше вариантов, чем 33!. Оцените, насколько меньше. Ответ выразите в процентах от числа 33!.

2. а) Составьте алгоритм шифрования шифром Цезаря с запрашиваемым ключом n.

б) Для алгоритма, составленного вами в пункте а), составьте алгоритм дешифрования.

3. а) Составьте алгоритм шифрования с ключевой фразой (по типу “Весна идёт”) с запрашиваемой у пользователя фразой.

б) Для алгоритма, составленного вами в пункте а), составьте алгоритм дешифрования.

4. Составьте алгоритм шифрования шифром “Сцитала” с запрашиваемым ключом n.

б) Для алгоритма, составленного вами в пункте а), составьте алгоритм дешифрования.

5. Дешифруйте сообщение

“рДивуиядг,о , асн вмдооии ядй! ад сн”,

зашифрованное решеткой, представленной на рис. 2.

6. а) К фрагменту сказки А.С. Пушкина был применен шифр простой замены, т.е. каждая буква исходного текста заменена так, что разным буквам соответствуют разные буквы, а одинаковым — одинаковые. Пробелы и знаки препинания сохранены. Получился следующий текст.

Дче аепеиь рвуа д птлтаы:

У дзиза хлрчатюа лтаы,

Р чазяа д глтотб цтия

Аирвцтаь аир хзгтаыия,

Дче китчтдцы мзлзвые,

Делрктны увтлые,

Дче итдны, ктк нт пзвхзи,

Ч нрмр вявькт Сеинзмзи.

Попытайтесь дешифровать текст

б) Выполните такое же задание, как в а), для следующего шифрованного сообщения.

Бтсвбр ел ибвн анжмс,

Гвлъ ел бтсвбрн тсбмс

Т залсбгалрыим цнвкрлим,

Т снвнилим ъл тлълим.

77. На сайте Википедии есть статья про шифрмашину “Энигма”

http://ru.wikipedia.org/wiki/%D0%AD%D0%BD%D0%B8%D0%B3%D0%BC%D0%B0.

Вот фрагмент этой статьи.

“Как и другие роторные машины, “Энигма” состояла из комбинации механических и электрических систем. Механическая часть включала в себя клавиатуру, набор вращающихся дисков (роторов), которые были расположены вдоль вала и прилегали к нему, и ступенчатого механизма, двигающего один или более роторов при каждом нажатии клавиши. Конкретный механизм работы мог быть разным, но общий принцип был таков: при каждом нажатии клавиши самый правый ротор сдвигается на одну позицию, а при определенных условиях сдвигаются и другие роторы. Движение роторов приводит к различным криптографическим преобразованиям при каждом следующем нажатии клавиши на клавиатуре.

Механические части двигались, образуя меняющийся электрический контур, то есть фактически шифрование букв осуществлялось электрически. При нажатии клавиш контур замыкался, ток проходил через различные компоненты и в итоге включал одну из множества лампочек, отображавшую выводимую букву. Например, при шифровке сообщения, начинающегося с ASF..., оператор вначале нажимал кнопку A, и загоралась лампочка D, то есть D становилась первой буквой криптограммы. Оператор продолжал шифрование S таким же образом, и так далее.

Для объяснения принципа работы “Энигмы” приведен рисунок. Он упрощен, — на самом деле механизм состоял из 26 лампочек, клавиш, разъемов и электрических схем внутри роторов. Ток шел из батареи (1) через переключатель (2) в коммутационную панель (3). Коммутационная панель позволяла перекоммутировать соединения между клавиатурой (2) и неподвижным входным колесом (4). Далее ток проходил через разъем (3), в данном примере неиспользуемый, входное колесо (4) и схему соединений трех роторов (5) и входил в рефлектор (6). Рефлектор возвращал ток обратно, через роторы и входное колесо, но уже по другому пути, далее через разъем 'S', соединенный с разъемом 'D', через другой переключатель (9), и зажигалась лампочка.

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

Для приведенной на рисунке упрощенной версии “Энигмы” найдите результат шифрования текста DDFFSDAAS, если известно, что правый ротор (5) сдвигался на один шаг при каждом нажатии клавиши, а остальные роторы — на один шаг после полного оборота соседнего справа ротора. При этом контакты на роторах расположены так, что при сдвиге ротора на один шаг нижний по схеме контакт переходит наверх, а остальные сдвигаются на шаг вниз.

§ 27. Криптография с открытым ключом

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

Долгое время считалось, что знание шифрующего ключа позволяет легко строить дешифрующий ключ. Например, в шифре Вериама они просто совпадают. Поэтому ключи шифровки и дешифровки составляли главную тайну в таком способе защиты информации. Однако в 1976 г. в работе двух американских математиков У.Диффи и М.Э. Хеллмана было обосновано, что между ключом шифрования и ключом дешифрования нет прямой связи. Можно ключ шифрования сообщить всем желающим, но тем не менее ключ дешифровки по нему построить не удастся (за разумное время). Это математическое открытие привело к так называемому шифрованию с открытым ключом.

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

Обозначим буквой А алгоритм шифрования. Результат его применения к тексту Т обозначим А(Т). Аналогично через Д обозначим алгоритм дешифрования, а результат его применения к Т обозначим Д(Т). Тогда, очевидно, выполняются следующие правила:

Д(А(Т)) = Т и А(Д(Т)) = Т.

Алгоритм А и все его параметры (ключи) сообщается всем (например, публикуется в газете). Если теперь кто-то хочет отправить секретное сообщение владельцу А и Д, то он просто шифрует его А. Цель защиты сообщения от посторонних глаз достигнута.

Но владелец А и Д наверняка хочет быть уверенным, что он получил сообщение от верного ему человека, а ведь зашифровать сообщение с помощью А мог любой. Тогда можно поступить так. Отправитель сообщения изготовляет собственную пару ключей, обозначим соответствующие версии алгоритмов А0 и Д0. Как обычно, А0 сообщается всем. Затем отправитель проделывает с текстом следующую манипуляцию: А(Д0(Т)). Получатель к полученному сообщению сначала применяет только ему известный Д и получает Д0(Т), а затем общедоступный А0. Теперь у него на руках сообщение Т и полная уверенность, что это прислал тот, кто нужно, — ведь никто другой не мог зашифровать этот текст ключом Д0. Как мы видим, в данном случае решена задача защиты не только от утечки, но и от возможности подделать информацию.

Говоря об алгоритмах А и Д, мы определили их различие туманной фразой, что, хотя они взаимно обратны, по одному из них нельзя построить другой за разумное время. Что означает эта фраза?

В конце лекции 2 мы обсуждали возможность сравнения эффективности алгоритмов, например, через реализацию их с помощью машины Тьюринга. Важной характеристикой алгоритма выступает количество действий, которое потребуется машине Тьюринга, чтобы выполнить данный алгоритм над заданным объемом данных, скажем, лентой, на которой имеется сообщение длины n. Ясно, что с ростом n будет расти и число исполняемых действий, а значит, и время, необходимое для получения результата. Говорят, что алгоритм полиномиален степени k, если существует такая константа С, что количество действий, выполняемых данным алгоритмом для обработки данных объема n, не превосходит Cnk. При этом k, естественно, выбирается наименьшим из всех возможных. Так вот, шифрующая функция f выбирается так, чтобы алгоритм для ее вычисления был полиномиальным, а алгоритм вычисления обратной функции уже полиномиальным не был ни для какого k. Такую функцию в криптографии называют односторонней.

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

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

1) при любом значении K существует полиномиальный алгоритм вычисления функции f;

2) при неизвестном значении K не существует полиномиального алгоритма вычисления функции, обратной к f;

3) при известном значении K существует полиномиальный алгоритм вычисления функции, обратной к f.

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

Вот пример построения функции с секретом.

1. Выберем два различных простых числа p и q.

2. Положим n = pq.

3. Выберем число d, взаимно простое с числом (p – 1)(q – 1).

4. Найдем такое s, чтобы sd mod (p – 1)(q – 1) = 1. Такое s нетрудно найти, пользуясь алгоритмом Евклида.

Алгоритм шифрования состоит из двух шагов.

1. Исходное сообщение кодируется последовательностью натуральных чисел ai, каждое из которых взаимно просто с n (например, каждая буква алфавита заменяется ее порядковым номером с указанным исключением).

2. Каждое ai заменяется на bi по правилу

bi = (ai)s mod n.

Последовательность bi и является шифрованным сообщением.

Как видно, для шифрования нужно знать только числа n и s. Их можно сообщить всем, они являются открытым ключом шифрования.

Секретом здесь является число d. Чтобы расшифровать сообщение, вычислим xi = (bi)d mod n. Ясно, что xi = (ai)sd mod n. Однако еще Л.Эйлер установил, что для n = pq, где p и q — различные простые числа, при любом целом с, взаимно простом с n, имеет место равенство c(p – 1)(q – 1) = 1 (mod n). Тем самым,
(ai)sd mod n = (ai) (p – 1)(q – 1)m + 1 mod n = (ai) (p – 1)(q – 1)m ai mod n = 1 · ai mod n. Следовательно, xi = ai, т.е. текст расшифрован.

Предположим, что d, p и q неизвестны. Как тогда построить по n и s алгоритм дешифрования?

Сначала надо разложить n на два простых множителя. Простые числа p и q выбираются обычно довольно большими, так что получение их, исходя из известного n, уже довольно трудоемкая задача. Далее, по найденным вычисляется число (p – 1)(q – 1), после чего с помощью алгоритма Евклида по значению s однозначно находится значение d.

Изложенная нами схема была предложена в 1978 г. Р.Риверстом, А.Шамиром и Л.Адлеманом и получила название RSA-схемы — по первым буквам английского написания фамилий этих изобретателей. Для иллюстрации своего метода авторы зашифровали таким способом некоторую английскую фразу, в которой буквы латинского алфавита были закодированы двузначными числами десятичной системы (пробел00, а01, b02 и т.д.). Были сообщены числа n и s. Более того, было объявлено, что число n является произведением двух простых чисел, одно из которых содержит 64 цифры, а другое — 65. Правда, s было невелико, всего лишь 9007. Тому, кто первый дешифрует сообщение, была обещана награда в 100$.

Расшифровано сообщение было лишь 17 лет спустя. После 220-дневной теоретической подготовки в работе приняло участие около 600 человек и около 1600 компьютеров, объединенных с помощью сети Интернет.

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

“В банк “Народный кредит”. Прошу перечислить с моего счета № 37845612 на счет № 21384562 в банке “Северное сияние” 15 000 (пятнадцать тысяч) рублей. Клиент: Петров Иван Сидорович. Код: 3XAZ43ав47UTГорRPOP12”.

Как вы видите, текст полностью открыт. И получивший его работник банка должен быть уверен, что в этот текст не внесено изменений ни в перечисляемую сумму, ни в номера счетов, ни в какие другие реквизиты. Для проверки этого как раз и служит код в конце сообщения, который, кстати, тоже передается совершенно открыто. А в чем же секрет? Секретным является алгоритм получения кода. Отправитель поступает так. Он шифрует текст своего поручения алгоритмом, который предоставлен банком. Разумеется, шифрование производится автоматически, и клиент этот алгоритм, как правило, не знает; более того, для каждого клиента алгоритм может быть своим и меняться в зависимости, например, от даты, когда проводится шифрование. Получившееся закодированное сообщение он и приписывает в конце к своему поручению после слова “Код”. Работник банка применяет тот же алгоритм к полученному сообщению и сравнивает получившийся у него код с присланным ему поручителем. Если они совпали, то можно быть уверенным, что никаких изменений в тексте поручения не производилось и, значит, поручение можно выполнять. Как видите, совсем не всегда требуется знать алгоритм дешифрования — достаточно иметь секретный алгоритм шифрования. Описанный способ борьбы с преднамеренным искажением информации будем называть методом одностороннего шифрования.

Вопросы и задания

1. Постройте RSA-систему, взяв в качестве p и q числа 37 и 41.

2. Составьте алгоритм шифрования фраз русского языка на основе RSA-системы, построенной вами при выполнении задания 1.

3. Предложите какой-либо алгоритм для проверки отсутствия искажений в переданном сообщении на основе приписываемого кода. Проверьте эффективность предложенного вами алгоритма на каких-либо сообщениях.

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

Хотя в преамбуле данной лекции с широтой души сказано “пусть видят и слышат”, на самом деле значительные усилия всегда прилагались к тому, чтобы скрыть сам факт существования информации и/или ее передачи. Наука о передаче информации, при которой сохраняется в тайне сам факт такой передачи, называется стеганографией.

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

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

Пусть, к примеру, имеется следующая последовательность двоичных чисел, отображающих в цифровом коде какой-то звуковой образ в формате МР3:

11011010 10011011 11100010 11011011 11011010 10011011 11100010 11011011

Мы хотим “спрятать” в этой последовательности, скажем, русскую букву “С”. В кодовой таблице
СР-1251 эта буква имеет номер 209, а ее двоичный код равен 11010001. А теперь в каждом байте исходной 8-байтовой последовательности последний бит заменяем, если нужно, на соответствующий бит кода буквы “С”. Получаем:

11011011 10011011 11100010 11011011 11011010 10011010 11100010 11011011

Реально такую подмену не услышать.

В следующие восемь байтов встраивается следующая буква сообщения, например, “О”. И так далее.

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

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

Так что компьютерные средства защиты информации активно развиваются в самых разнообразных направлениях.

Вместо эпилога. Некоторые аспекты методики преподавания математических основ информатики

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

Ответ на вопрос “почему?” на первый взгляд кажется довольно очевидным — в школьном курсе математики не изучаются те современные разделы этой великолепной науки, которые позволяют понять весьма тонкие механизмы компьютерных технологий. И этот ответ правильный. Но неполный.

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

Чему должен научиться школьник, изучающий курс “Математические основы информатики”? Во-первых, у него должно быть четкое понимание, что за всеми умными штучками стоят конкретные алгоритмы. Во-вторых, он должен знать, каковы эти основные алгоритмы. В-третьих, знать, как устроены структуры данных для этих алгоритмов. В-четвертых, знать, каковы ограничения на представление данных в компьютере, и понимать, как эти ограничения сказываются на результатах и самой возможности применения предлагаемых алгоритмов.

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

Таким образом, главная цель курса “Математические основы информатики” — это перестройка мышления учащихся на конструктивный стиль. Поэтому у школьников, специализирующихся в такой углубленной информатике, вовсе не обязательны высокие успехи в математике и, наоборот, высокие успехи в математике вовсе не гарантия успешности в информатике. Надо иметь это в виду как при отборе учащихся в классы с углубленной подготовкой по информатике, так и в процессе обучения в таком классе.

А теперь несколько слов о собственно методике. Напомним, что методическое обеспечение изучения любой темы предусматривает несколько концентров: создание мотивации, выделение содержательного ядра и его освоение, расширение ядра и установление связей с другими разделами курса, а также другими дисциплинами, контроль усвоения. Мы остановимся только на двух моментах — мотивационное введение и расширение ядра.

Мотивационное введение

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

1) апелляция к жизненному опыту учащихся;

2) ссылка на то, что приобретенное сегодня знание понадобится при изучении какого-то последующего материала, важность овладения которым сомнения не вызывает;

3) создание проблемной ситуации;

4) использование занимательного сюжета;

5) ролевой подход;

6) деловая игра8.

Вот, к примеру, сюжетный вариант создания мотивации при изучении темы “Конечные автоматы”, которую мы обсуждали в § 39. Учащимся предлагается следующее задание.

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

“Замогилье”

Дом с привидениями

Дорогой друг!

Некоторое время назад я купил старый дом, но обнаружил, что он посещается двумя странными звуками: Пением и Смехом. В результате он мало подходит для жилья. Однако я не отчаиваюсь, ибо я установил путем практической проверки, что их поведение подчиняется определенным законам, непонятным, но непререкаемым, и что я могу воздействовать на них, играя на Органе или сжигая Ладан.

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

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

Что касается Смеха, то если в предыдущую минуту горел Ладан, Смех будет звучать или молчать в зависимости от того, звучало или молчало Пение (так что Смех копирует Пение минутой позже). Если, однако, Ладан не горел, Смех будет делать противоположное тому, что делало Пение.

В ту минуту, когда я пишу Вам это, Смех и Пение оба звучат. Прошу Вас сообщить мне, какие действия с Ладаном и Органом должен я совершить, чтобы установить и поддерживать тишину в доме?

Обсуждая текст письма, учащиеся приходят к выводу, что имеют дело с некоторым управляемым формальным исполнителем, имеющим 4 состояния:

Смех и Пение звучат;

Смех молчит, Пение звучит;

Смех звучит, Пение молчит;

Смех и Пение молчат.

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

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

Расширение ядра и установление связей с другими разделами курса

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

Дана фигура, составленная из нескольких одинаковых правильных шестиугольников. В каждом шестиугольнике нарисовано несколько стрелок. Требуется, начав с нижнего шестиугольника (он отмечен внешней “входной” стрелкой), закончить свой путь в верхнем (он отмечен внешней “выходной” стрелкой), перемещаясь из одного шестиугольника в другой по следующему правилу: из каждого шестиугольника можно сделать прыжок в одном из двух направлений, куда указывают стрелки, находящиеся в этом шестиугольнике, причем на столько шестиугольников, сколько стрелок указывают на это направление.

Выполните это задание для фигур, изображенных на рис. 1 а)–в) на с. 10–11, посетив при этом наименьшее число шестиугольников.

ПРИМЕР:

На левом рисунке приведенного примера изображена исходная ситуация, на правом — искомый путь. При этом пришлось побывать лишь в четырех шестиугольниках (считая начальный и конечный шестиугольники).

Рис. 1

Нарисовать граф всевозможных вариантов перемещения практически невозможно. Тем не менее здесь эффективно работает “волновой алгоритм”, который обсуждался нами в § 12: начав с нижнего шестиугольника, надо последовательно в каждом шестиугольнике написать количество шагов, за которое этот шестиугольник достигается.

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

* * *

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

Еще раз желаем всем успехов.


1 Мы все время говорим про одно сообщение, хотя на практике имеется, конечно, некоторый массив сообщений. Впрочем, их можно соединить в одно “большое” сообщение.

2 Иногда применяется и другая схема, когда функция f отображает не алфавит в алфавит, а одно сообщение целиком в другое. Например, фраза “Над всей Испанией безоблачное небо” шифровала приказ к началу франкистского мятежа. Нередко отсутствие точки в конце сообщения агента (или, наоборот, ее наличие) шифрует сообщение о его работе под контролем противника. Однако эта схема не технологична — ведь о таком шифровании можно договориться лишь для конечного числа сообщений, а передавать заранее неоговоренную информацию невозможно.

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

4 Опытный криптограф, разумеется, добавит к основному алфавиту символ “пробел” и его тоже зашифрует. Впрочем, опытный криптограф не будет вообще пользоваться шифром простой замены.

5 Подробное объяснение недостатков шифра простой замены содержится в рассказе Э.По “Золотой жук” и в уже упоминавшемся произведении А. Конан Дойла “Пляшущие человечки”.

6 Свое название он получил от способа реализации. Брался жезл цилиндрической формы — сцитала, на него наматывалась лента, и вдоль жезла строка за строкой писалось сообщение. Затем лента разматывалась, и на ней оказывался зашифрованный текст.

7 Это задание взято нами с интернет-олимпиады по криптографии, информатике и математике “Верченко-100”. Заинтересовавшиеся читатели могут выйти на сайт этих олимпиад, где найдут немало интересных материалов.

8 Проблемам мотивации в курсе информатики была посвящена специальная лекция в рамках курса “Методика преподавания современного курса информатики” — Педагогический университет “Первое сентября”, 2004.

9 Текст “письма” взят из книги У.Р. Эшби, одного из основоположников теории конечных автоматов.