Кодирование инф. Курс лекций по темам раздела Кодирование информации, методические рекомендации для подготовки ответа на экзаменационные вопросы, задания для самопроверки
 Скачать 1.18 Mb.
|
|
Основные криптографические алгоритмы. Алгоритм замены. При ответе на данный вопрос необходимо рассказать о криптографическом алгоритме замены и проиллюстрировать способы его построения на конкретных примерах. К основным криптографическим алгоритмам относят алгоритмы замены, перестановки и дробления. Эти три базовых преобразования самостоятельно или в сочетании друг с другом используются в большинстве систем шифрования для создания очень сложных шифровальных алгоритмов. Рассмотрим подробнее алгоритм замены. Пусть требуется зашифровать следующее сообщение (открытый текст): МАМА МЫЛА РАМУ. Один из способов шифрования – простая замена, при которой каждая буква открытого текста заменяется на какую-то букву алфавита (возможно, на ту же самую). Для этого отправитель сообщения должен знать, на какую букву в шифротексте следует заменить каждую букву открытого текста. Часто это делается путем сведения нужных соответствий букв в виде двух алфавитов, например так, как показано ниже в таблице: Открытый алфавит А Л М Р У Ы Шифровальный алфавит А Б В Г Д Е Шифрограмма получается путем замены каждой буквы открытого текста на записанную непосредственно под ней букву шифровального алфавита: 82 ВАВА ВЕБА ГАВД Две алфавитные последовательности, используемые в процессе шифрования, называются, соответственно, открытым и шифровальным компонентом системы. Чтобы получатель шифрограммы мог восстановить открытый текст и прочитать сообщение, ему необходимо иметь копию вышеприведенной таблицы. Дешифровщик повторяет в обратном порядке все действия шифровальщика, раскрывая тем самым содержание сообщения. В вышеприведенном примере использовался алгоритм побуквенной замены. Этот метод называется простой, или моноалфавитной заменой. Ключ к данному шифру состоит из таблицы, содержащей открытый и шифровальный алфавиты, в которой указывается, на какую букву в шифротексте следует заменить букву открытого текста. В такой криптографической системе предполагается, что алгоритм шифрования общеизвестен, тогда как ключ доступен только отправителю и получателю соответствующих сообщений. Для формирования шифровального алфавита можно использовать ключевое слово (ключевую фразу). В этом случае в начале шифровального алфавита записывается начало ключевого слова или первого слова ключевой фразы, потом алфавит формируется с опущением всех тех букв, что уже появились в этом слове (или в первом слове этой фразы), а после этого вписываются остающиеся буквы алфавита в обычном порядке, опять же с опущением всех ранее появившихся букв. Так, если в качестве ключевой мы используем фразу У ЛУКОМОРЬЯ ДУБ ЗЕЛЕНЫЙ, то шифровальный алфавит будет выглядеть следующим образом: У Л К О М Р Ь Я Д Б З Е Н Ы Й А В Г Ё Ж И П С Т Ф Х Ц 83 Ч Ш Щ Ъ Э Ю С помощью ключевого слова (фразы) при шифровании можно перемешать любую алфавитную последовательность. Использование ключевых слов облегчает восстановление открытого и шифровального компонента системы, поскольку при этом необходимо запомнить только соответствующее ключевое слово (фразу). Нет необходимости записывать (или разгадывать) какие бы то ни было таблицы: если помнить ключевое слово, то алфавитную последовательность всегда можно восстановить по памяти. В вышеприведенной шифрограмме между словами сохранены пробелы, однако шифровку можно сделать более защищенной (или, как говорят криптографы, устойчивой, или стойкой ко взлому; шифр считается тем более стойким, чем дольше он не поддается вскрытию) путем удаления межсловных пробелов из окончательного шифротекста. Согласно установившейся практике, шифротекст принято делить на группы из пяти букв каждая. Если убрать пробелы между словами, то нашу шифрограмму можно было бы записать так: ВАВАВ ЕБАГА ВД Вопросы для самопроверки: 1. Поясните понятия «открытый алфавит», «шифровальный алфавит». 2. Приведите пример алгоритма простой замены. 3. Приведите пример шифрования при помощи ключевого слова. 84 Основные криптографические алгоритмы. Алгоритм перестановки. При ответе на данный вопрос необходимо рассказать о криптографическом алгоритме перестановки и проиллюстрировать способы его построения на конкретных примерах. В криптографическом алгоритме перестановки все буквы открытого текста остаются без изменений, но переставляются согласно заранее оговоренному правилу. Здесь также удобно использовать ключ, управляющий процедурой шифрования. Возьмем в качестве ключа для сообщения МАМА МЫЛА РАМУ слово БАЙТ. Пронумеруем буквы ключевого слова в порядке их следования слева направо в русском алфавите: Буквы ключевого слова Б А Й Т Порядковые номера букв в алфавите 2 1 3 4 Далее под полученной числовой последовательностью в строках, равных по длине ключевому слову, запишем открытый текст. Буквы ключевого слова Б А Й Т Порядковые номера букв в алфавите 2 1 3 4 Открытый текст М А М А М Ы Л А Р А М У В процессе шифрования текст будем выписывать уже по 85 отдельным столбцам в порядке, определяемом данной числовой последовательностью АЫАММРМЛМААУ Этот метод перестановки называется перестановкой столбцов, но можно избрать и другие «маршруты» перестановки, например выписывать шифротекст следуя по диагонали (слева направо или справа налево, или же чередуя левое и правое направления) или по спирали и т.п. Кроме того, буквы шифротекста могут записываться в виде различных геометрических фигур или любыми другими способами. Один из них состоит в двойном шифровании путем повторной перестановки столбцов. При этом и в первом, и во втором блоках перестановки может быть использовано одно и то же ключевое слово, хотя лучше использовать разные ключевые слова. Такой шифр, называющийся двойной перестановкой, получил широкое распространение. Вопросы для самопроверки: 1. Объясните алгоритм метода перестановки столбцов. 2. Зашифруйте сообщение У ЛУКОМОРЬЯ ДУБ ЗЕЛЕНЫЙ методом перестановки столбцов с ключевым словом БУКВА. 3. Зашифруйте сообщение У ЛУКОМОРЬЯ ДУБ ЗЕЛЕНЫЙ по следующим маршрутам перестановки: текст вписывается в таблицу размером 5*5 клеток по спирали, начиная с верхнего левого угла по часовой стрелке, а выписывается по столбцам сверху вниз, начиная с последнего столбца. Основные криптографические алгоритмы. Алгоритм дробления. При ответе на данный вопрос необходимо рассказать о 86 криптографическом алгоритме дробления и проиллюстрировать способы его построения на конкретных примерах. В алгоритме дробления каждой букве открытого текста сопоставляется более одного символа шифротекста, после чего символы перемешиваются (переставляются) в определенном порядке. Рассмотрим подробнее алгоритм дробления. Сначала составляется шифровальная таблица размером 6 ∗6 клеток, куда построчно вписывается шифровальный алфавит с ключевой фразой. Пусть ключевая фраза будет У ЛУКОМОРЬЯ ДУБ ЗЕЛЕНЫЙ. Также как и в алгоритме замены запишем в таблицу начало первого слова ключевой фразы, а далее сформируем шифровальный алфавит, исключая уже записанные буквы. После окончания ключевой фразы впишем в таблицу остающиеся буквы алфавита в обычном порядке, но с учетом ранее появившихся букв: 1 2 3 4 5 6 1 У Л К О М Р 2 Ь Я Д Б З Е 3 Н Ы Й А В Г 4 Ё Ж И П С Т 5 Ф Х Ц Ч Ш Щ 6 Ъ Э Ю + - * Получается, что букве У соответствует пара чисел (1, 1), букве Л — пара (1, 2) и т.д. Зашифруем с помощью этого шифровального алфавита фразу МАМА МЫЛА РАМУ. Разобъем полученный открытый текст на группы по шесть символов и 87 выпишем в столбец сответствующую каждому символу пару чисел (координат) из таблицы: М А М А М Ы 1 3 1 3 1 3 5 4 5 4 5 2 Л А Р А М У 1 3 1 3 1 1 2 4 6 4 5 1 Теперь прочитаем пары чисел из каждой шестерки уже построчно. В результате такого преобразования получим для первой шестерки — КККЧЧХ, а для второй — ККУБ+Ф. При таком шифровании координата строки и координата столбца каждой буквы оказываются разъединенными, что характерно именно для раздробляющего шифра. Вопросы для самопроверки: 1. Объясните алгоритм метода дробления. 2. Зашифруйте сообщение У ЛУКОМОРЬЯ ДУБ ЗЕЛЕНЫЙ методом перестановки столбцов с ключевой фразой МАМА МЫЛА РАМУ. 88 Литература 1) Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971. 478 с. 2) Вольфовиц Д. Теоремы кодирования теории информации. М.: Мир, 1967. 248 с. 3) Информатика: Учебник/ под ред. Н.В.Макаровой. М.: Финансы и статистика, 1997. 768 с. 4) Касами Т. и др. Теория кодирования. М.: Мир, 1978. 576с. 5) Кодирование информации: методические указания / сост.: В. Д. Горбоконенко, В. Е. Шикина. – Ульяновск: УлГТУ, 2006. – 56 с. 6) Кузьмин И.В., Кедрус В.А. Основы теории информации и кодирования. Киев: ВИЩА ШКОЛА, 1986. 240 с. 7) Мазур М. Качественная теория информации. М.: Мир, 1974. 239 с. 8) Марков А.А. Введение в теорию кодирования. М.: Наука, 1982. 364 с. 9) Могилев А.В., Пак Н.И., Хеннер Е.К. Информатика: Учеб. пособие для студ. пед. вузов. М.: ИЦ "Академия", 1999. 816 с. 10) Нечаев В.И. Элементы криптографии (Основы теории защиты информации): учебное пособие для университетов и педвузов. /Под.ред. В.А. Садовничего. - М.: Высш. шк., 1999. 256 с. 89 11) Стариченко Б.Е. Теоретические основы информатики. М.: Горячая линия — Телеком, 2003. 312 с. 12) Стратонович Р.Л. Теория информации. М.: Советское радио, 1975. 424 с. 13) Файнстейн А. Основы теории информации. М.: ИЛ, 1960. 233 с. 14) Чисар И., Кернер Я. Теория информации: теоремы кодирования для дискретных систем без памяти. М.: Мир, 1985. 400 с. 15) Шеннон К. Математическая теория связи. В кн.: Работы по теории информации и кибернетике. М.: ИЛ, 1963. С. 243-332. Интернет-источники 1) Теория кодирования [Электронный ресурс] // GOUSPRO — студенческий портал!:сайт. - URL: http://gouspro.ru/?page_id=22 (дата обращения 16.01.2012) 2) Леонов Д. Файлы, которым мы доверяем /Свет в Интернет: интернет-еженедельник, - №33(145)/04.11.03. URL: http://www.lightnet.obninsk.ru/Review/Security/145.shtml (дата обращения 13.12.2011) 3) Бекман И.Н. Компьютеры в информатике: курс лекций [Электронный ресурс] // Лекции. - URL: http://profbeckman.narod.ru/EVM.htm (дата обращения 15.12.2011) 90 Приложение 1. Оригинальный код Бодо. («о» — наличие сигнала, «.» - отсутствие сигнала) Управляющие символы o. ... пробел, перейти к таблице букв .o ... пробел, перейти к таблице цифр oo ... удалить последний знак таблица букв таблица цифр .. o.. A oo o.. K .. o.. 1 o. o.. .. oo. É oo oo. L .. .o. 2 o. .o. 9/ .. .o. E oo .o. M .. ..o 3 o. ..o 7/ .. .oo I oo .oo N .. o.o 4 o. o.o 2/ .. ooo O oo ooo P .. ooo 5 o. ooo ' .. o.o U oo o.o Q .. oo. 1/ o. oo. : .. ..o Y oo ..o R .. .oo 3/ o. .oo ? .o ..o B o. ..o S .o o.. 6 oo o.. ( .o o.o C o. o.o T .o .o. 7 oo .o. ) .o ooo D o. ooo V .o ..o 8 oo ..o - .o .oo F o. .oo W .o o.o 9 oo o.o / .o .o. G o. .o. X .o ooo 0 oo ooo + .o oo. H o. oo. Z .o oo. 4/ oo oo. = .o o.. J o. o.. — .o .oo 5/ oo .oo £ Буква_Частота_Буква_Частота'>Приложение 2. Таблица частотности букв русского языка. Буква Частота Буква Частота пробел 0,175 o 0,090 и 0,062 т 0,053 р 0,040 в 0,038 м 0,026 д 0,025 я 0,018 ы 0,016 б 0,014 г 0,013 х 0,009 ж 0,007 ц 0,004 щ 0,003 Буква Частота Буква Частота е, ë 0,072 а 0,062 н 0,053 с 0,045 л 0,035 к 0,028 п 0,023 у 0,021 з 0,016 ъ, ь 0,014 ч 0,012 й 0,010 ю 0,006 ш 0,006 э 0,003 ф 0,002 |