Алгоритм перестановки

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

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

ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ.

получится такой шифротекст:

ИЛЕТО ХЫМКА ККАТТ ЕДУБЪ ТСУП

В последней группе (пятерке) не хватает одной буквы. Значит, прежде чем шифровать исходное выражение, следует его дополнить незначащей буквой, например «О» до числа, кратного пяти:

ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.

Тогда шифрограмма, несмотря на столь незначительные изменения, будет выглядеть по-другому:

ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП

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

Во время Гражданской войны в США в ходу был такой шифр: исходную фразу писали в несколько строк. Например, по пятнадцать букв в каждой (с заполнением последней строки незначащими буквами).

П У С Т Ь Б У Д Е Т Т А К К А

К М Ы Х О Т Е Л И К Л М Н О П

После этого вертикальные столбцы по порядку писали в строку с разбивкой на пятерки букв:

ПКУМС ЫТХЬО БТУЕД ЛЕИТК ТЛАМК НКОАП

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

Шифры сложной замены

Шифр Гронсфельда состоит в модификации шифра Цезаря числовым ключом. Для этого под буквами сообщения записывают цифры числового ключа. Если ключ короче сообщения, то его запись циклически повторяют. Зашифрованное сообщение получают примерно также, как в шифре Цезаря, но используют не одно жестко заданное смещение, а фрагменты ключа.

Пусть в качестве ключа используется группа из трех цифр – 314, тогда сообщение

С О В Е Р Ш Е Н Н О С Е К Р Е Т Н О

3 1 4 3 1 4 3 1 4 3 1 4 3 1 4 3 1 4

Ф П Ё С Ь З О С С А Х З Л Ф З У С С

В шифрах многоалфавитной замены для шифрования каждого символа исходного сообщения применяется свой шифр простой замены (свой алфавит).

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

ПРИЕЗЖАЮ_ШЕСТОГО

АГАВААГАВААГАВАА

ПОИГЗЖЮЮЮШЕПТНГО

Такая операция соответствует сложению кодов ASCII символов сообщения и ключа по модулю 256.

2. Выполните задание. Результаты запишите в тетрадь.

1. Зашифруйте фразу «ГРУЗИТЕ АПЕЛЬСИНЫ БОЧКАМИ ТЧК БРАТЬЯ КАРАМАЗОВЫ ТЧК» методом Виженера с помощью ключа ВЕНТИЛЬ.

2. Дан шифр-текст: СВПООЗЛУЙЬСТЬ_ЕДПСОКОКАЙЗО. Известно, что шифрование производилось по столбцам.

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

Контрольные вопросы:

1. В чем заключается система шифрования Цезаря?

2. Как используется схема Виженера?

3. Объясните сущность алгоритма перестановки.

4. В чем особенность шифра Гронсфельда?

5. Как производится расшифровка текста?

Практическая работа 15. Комплексная работа по кодированию информации

Цель работы: контроль навыков кодирования информации разного типа.

Краткое теоретическое обоснование: см.практические работы 11-15.

Оборудование: дидактические материалы – контрольно-оценочные средства по дисциплине «Основы теории информации»

Последовательность выполнения:

· Выполните ТЗ№2. Тест № 4 "Кодирование и декодирование информации". В тесте необходимо выбрать только один ответ из предложенных вариантов. Выполнять тест лучше самостоятельно, без применения конспектов, учебников и прочей вспомогательной литературы.

· Выполните ПЗ№2. Задачи 11-19.

Лабораторная работа 2. Изучение приемов сжатия информации с помощью программных средств

Цель работы: Изучение приемов сжатия информации с помощью программных средств.

Краткое теоретическое обоснование:

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

Оборудование: персональный компьютер, ОС, программы-архиваторы, дидактические материалы – контрольно-оценочные средства по дисциплине «Основы теории информации».

Последовательность выполнения:

1. На диске D: в папке STUDENT создайте именной каталог. Скопируйте в этот каталог несколько файлов с расширениями.docx (документ MS Word 2007),.txt (Текстовый файл, содержащий текстовые данные, как правило, организованные в виде строк. Текстовым файлам противопоставляются двоичные файлы, в которых содержатся данные, не рассчитанные на интерпретацию в качестве текста (например, файлы, хранящие закодированные звук или изображение),.jpg (изображение JPEG),.bmp (изображение BMP). В папке может находиться несколько файлов одного типа. Суммарный объём файлов каждого типа не должен быть меньше одного мегабайта.

2. Поместите файлы в архивы (отдельный для файлов каждого вида) 7z и Zip с нормальным и наивысшим уровнями сжатия (всего получится 16 архивов). Имя архива должно содержать тип сжимаемого файла, степень сжатия и номер по списку студентов группы.

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

4. Проведите проверку целостности одного из архивов.

5. Создайте защищённый паролем самораспаковывающийся 7z архив для файлов.txt с нормальным уровнем сжатия. Объясните разницу в объёмах файлов самораспаковывающегося и соответствующего не самораспаковывающегося архивов.

6. Создайте подпапку в именной папке и распакуйте туда содержимое самораспаковывающегося архива, а также любой из файлов, содержащийся в архиве с файлами *.bmp.

7. Создайте многотомный архив с размером тома, равным 300Кб, содержащий созданную в предыдущем задании подпапку именной папки.

8. Выполните отчет о проделанной работе.

Отчет должен включать:

· титульный лист;

· содержание (оглавление);

· цель работы;

· протокол выполнения задания — краткое описание последовательности команд (функций), позволяющих выполнить соответствующее задание;

· результаты проведённого анализа и их интерпретацию;

· выводы;

· список использованной литературы.

В отчёте должна присутствовать таблица со сравнением степеней сжатия, интерпретация результатов, снимки экранов различных стадий выполнения заданий, выводы по заданиям.

Контрольные вопросы:

1. Какие факторы влияют на степень избыточности данных?

2. Какие программные средства называются архиваторами?

3. Понятие процесса архивации, разархивации файлов.

4. Дайте определение понятиям: сжатие информации, архивный файл, коэффициент сжатия.

5. Основные характеристики процессов сжатия.

6. Какая зависимость существует между коэффициентом сжатия и эффективностью метода сжатия?

7. Преимущества и недостатки обратимых и необратимых методов сжатия.

8. Форматы архивных файлов. Приведите примеры форматов обратимых и необратимых методов сжатия.

9. В чем состоит основная идея алгоритмов RLE, LZW, Хаффмана.