1. Главная
  2. Информатика
  3. Лабораторная работа №1. Программная реализация простых шифров перестановки и замены

Лабораторная работа №1. Программная реализация простых шифров перестановки и замены

Целью лабораторной работы является приобретение навыков программной реализации простых шифров подстановки и замены.

Требования к содержанию, оформлению и порядку выполнения

Отчет по выполнению лабораторной работы должен содержать: титульный лист, название работы, цель работы и содержательную часть.

В содержательной части отчета по выполнению лабораторной работы для своего варианта требуется привести:

· исходный текст и описание программы шифрования данных;

· результаты шифрования и расшифрования текста;

· выводы по лабораторной работе.

Теоретическая часть

Определение шифров перестановки приведено в разделе 2.3.1. Рассмотрим несколько примеров таких шифров.

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

Шифрование выполнялось следующим образом (см. рис. Л1.1). На стержень цилиндрической формы, который назывался скитала, наматывали спиралью (виток к витку) полоску пергамента и писали на ней вдоль стержня несколько строк текста сообщения (рис. Л1.1). Затем снимали со стержня полоску пергамента с написанным текстом. Буквы на этой полоске оказывались расположенными хаотично.

Лабораторная работа №1. Программная реализация простых шифров перестановки и замены - student2.ru
Рис. Л1.1. Шифр "Скитала".

Такой же результат можно получить, если буквы сообщения писать по кольцу не подряд, а через определенное число позиций до тех пор, пока не будет исчерпан весь текст. Сообщение "НАСТУПАЙТЕ" при размещении его по окружности стержня по три буквы дает шифртекст: "НУТАПЕСА_ТЙ".

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

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

В качестве ключа в шифрующих таблицах используются:

· размер таблицы;

· слово или фраза, задающие перестановку;

· особенности структуры таблицы.

Одним из самых примитивных табличных шифров перестановки является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шифром скитала. Например, сообщение "ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ"записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан на рис. Л1.2.

После заполнения таблицы текстом сообщения по столбцам для формирования шифртекста считывают содержимое таблицы по строкам. Если шифртекст записывать группами по пять букв, получается такое шифрованное сообщение: "ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ".

Лабораторная работа №1. Программная реализация простых шифров перестановки и замены - student2.ru
Рис. Л1.2. Заполнение шифрующей таблицы из 5 строк и 7 столбцов.

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

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

Применим в качестве ключа, например, слово "ПЕЛИКАН", а текст сообщения возьмем из предыдущего примера. На рис. Л1.3 показаны две таблицы, заполненные текстом сообщения и ключевым словом, при этом левая таблица соответствует заполнению до перестановки, а правая таблица – заполнению после перестановки.

До перестановки После перестановки
П Е Л И К А Н   А Е И К Л Н П
 
Т Н П В Е Г Л   Г Н В Е П Л Т
Е А Р А Д О Н   О А А Д Р Н Е
Р Т И Е Ь В О   В Т Е Ь И О Р
М О Б Т М П Ч   П О Т М Б Ч М
И Р Ы С О О Ь   О Р С О Ы Ь И
 
Рис. Л1.3. Шифрующие таблицы, заполненные ключевым словом и текстом сообщения.

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

При считывании содержимого правой таблицы по строкам и записи шифртекста группами по пять букв получим шифрованное сообщение: "ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ".

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

Пример выполнения шифрования методом двойной перестановки показан на рис. Л1.4. Если считывать шифртекст из правой таблицы построчно блоками по четыре буквы, то получится следующее: "ТЮАЕ ООГМ РЛИП ОЬСВ".

Ключом к шифру двойной перестановки служит последовательность номеров столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно).

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы:

· для таблицы 3x3 – 36 вариантов;

· для таблицы 4x4 – 576 вариантов;

· для таблицы 5x5 – 14400 вариантов.


Исходная таблица Перестановка столбцов Перестановка строк

         
П Р И Л   Р Л И П   Т Ю А Е
Е Т А Ю   Т Ю А Е   О О Г М
В О С Ь   О Ь С В   Р Л И П
М О Г О   О О Г М   О Ь С В
  Рис. Л1.4. Пример выполнения шифрования методом двойной перестановки.

Шифры замены определены в разделе 2.3.2. В своей простейшей форме шифр замены может быть задан таблицей подстановки, устанавливающей соответствие между буквами двух алфавитов An и Bn:

Лабораторная работа №1. Программная реализация простых шифров перестановки и замены - student2.ru ,

где Лабораторная работа №1. Программная реализация простых шифров перестановки и замены - student2.ru – i-тая буква алфавита открытого текста, Лабораторная работа №1. Программная реализация простых шифров перестановки и замены - student2.ru – шифрообозначение ai (соответствующая ai буква алфавита шифртекста).

Алфавиты An и Bn не обязательно должны быть различными. В практической криптографии очень часто применяются шифры, в которых алфавиты An и Bn совпадают.

В шифре простой замены каждый символ исходного текста заменяется символами того же алфавита одинаково на всем протяжении текста. Примерами шифров простой замены являются шифр Цезаря и аффинный шифр Цезаря, рассмотренные в разделе 2.3.2. Рассмотрим еще насколько примеров.

Система шифрования Цезаря с ключевым словом. Особенностью этой системы является использование ключевого слова для смещения и изменения порядка символов в алфавите подстановки.

Выберем некоторое число k, 0 < k < 25 , и слово или короткую фразу в качестве ключевого слова. Желательно, чтобы все буквы ключевого слова были различными. Пусть выбраны слово DIPLOMAT в качестве ключевого слова и число k= 5.

Ключевое слово записывается под буквами алфавита, начиная с буквы, числовой код которой совпадает с выбранным числом k:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
D I P L O M A T

Оставшиеся буквы алфавита подстановки записываются после ключевого слова в алфавитном порядке:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
V W X Y Z D I P L O M A T B C E F G H J K N Q R S U

Теперь мы имеем подстановку для каждой буквы произвольного сообщения. Исходное сообщение "SEND MORE MONEY" шифруется как "HZBY TCGZ TCBZS".

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

Шифрующие таблицы Трисемуса. В 1508 г. аббат из Германии Иоганн Трисемус написал печатную работу по криптологии под названием "Полиграфия". В этой книге он впервые систематически описал применение шифрующих таблиц, заполненных алфавитом в случайном порядке. Для получения такого шифра замены обычно использовались таблица для записи букв алфавита и ключевое слово (или фраза). В таблицу сначала вписывалось по строкам ключевое слово, причем повторяющиеся буквы отбрасывались. Затем эта таблица дополнялась не вошедшими в нее буквами алфавита по порядку. Поскольку ключевое слово или фразу легко хранить в памяти, то такой подход упрощал процессы шифрования и расшифрования.

Поясним этот метод шифрования на примере. Для русского алфавита шифрующая таблица может иметь размер 4x8. Выберем в качестве ключа слово БАНДЕРОЛЬ. Шифрующая таблица с таким ключом показана на
рис. Л1.5.

Лабораторная работа №1. Программная реализация простых шифров перестановки и замены - student2.ru
Рис. Л1.5. Шифрующая таблица Трисемуса с ключевым словом "БАНДЕРОЛЬ".

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

Например, при шифровании с помощью этой таблицы сообщения "ВЫЛЕТАЕМПЯТОГО" получаем шифртекст "ПДКЗЫВЗЧШЛЫЙСЙ".

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

Для ручного шифрования можно воспользоваться таблицей, называемой квадратом Вижинера. Пример квадрата Вижинера для русского языка приведен в табл. Л1.1.

Таблица Л1.1

Квадрат Вижинера для русского алфавита

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

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

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

Рассмотрим пример получения шифртекста с помощью квадрата Вижинера. Пусть выбрано ключевое слово "АМБРОЗИЯ". Необходимо зашифровать сообщение "ПРИЛЕТАЮ СЕДЬМОГО". Выпишем исходное сообщение в строку и запишем под ним ключевое слово с повторением. В третью строку будем выписывать буквы шифртекста, определяемые из квадрата Вижинера.

Сообщение ПРИЛЕТАЮ СЕДЬМОГО

Ключ АМБРОЗИЯ АМБРОЗИЯ

Шифртекст ПЪЙЫУЩИЭ ССЕКЬХЛН

Общая постановка задачи

В лабораторной работе требуется:

1. Изучить разделы 2.3.1, 2.3.2 и теоретическую часть к данной лабораторной работе.

2. Разработать программу для шифрования и расшифровывания текста при помощи шифра перестановки или шифра замены. Программа должны обеспечивать:

· задание в командной строке режима работы (шифрование/расшифрование), имени входного файла, имени результирующего файла;

· ввод ключа шифрования/расшифрования с клавиатуры;

· шифрование информации, находящейся в текстовом файле, с записью результата в другой файл.

3. Зашифровать и расшифровать файл, с использованием разработанной программы.

Наши рекомендации

Лабораторная работа №3. Изучение принципов создания блочных шифров на примере алгоритма DES

Лабораторная работа № 6. Реализация политики безопасности в MS Windows

Перестановочные (транспозиционные) шифры. Решетка Кардано и другие примеры шифров перестановки

Перестановки и замены как вид грамматических трансформаций в переводе

Лабораторная работа №3. РЕАЛИЗАЦИЯ ПОИСКА В СИСТЕМАХ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА

Перестановки; 2) замены; 3) добавления; 4) опущения.

Жалобы (на забывание, перестановки, замены, пропуски букв и др.)

Лабораторная работа №1. Реализация алгоритмов сортировки и поиска

Лабораторная работа № 2. Создание простых запросов

ЛАБОРАТОРНАЯ РАБОТА № 2. ЗАПИСЬ И ВЫПОЛНЕНИЕ ПРОСТЫХ ПРОГРАММ