Краткие теоретические сведения. Последовательность выполнения
Последовательность выполнения
1. Ознакомиться с базовыми методами шифрования (перестановка, подстановка)
2. Составить программы для зашифрования/расшифрования текстовых файлов (файлов в формате ASCII) методами:
· Перестановки;
· Цезаря;
· Одноразового блокнота;
· Виженара с использование датчика случайных чисел;
· Виженара с использование пароля;
3. Отладить и выполнить составленные программы (в программах рекомендуется предусмотреть обход управляющих символов с кодами 00h..1Fh).
Краткие теоретические сведения
Большинство языков программирования предоставляют специалисту готовые средства для работы со строками переменной длины. Традиционно младший байт внутреннего представления такой строки содержит ее текущую длину, далее следуют символы строки от первого до последнего. Максимальная длина строки в таком представлении равна 255 символам.
Текстовый файл является последовательностью строк из символов с кодами 20h..FFh, длиной от 0 до 255 каждая, разделенную управляющими символами 0Dh/0Ah (CR/LF – возврат каретки/перевод строки). Символы с кодами 00h..1Fh, включая CR/LF, считаются управляющими и используются в текстах для специальных целей.
Криптографические преобразования строк сводятся к перестановкам (перемещениям), заменам (подстановкам) символов в строке или комбинациям обоих методов.
При перестановках криптопреобразованиям подвергаются блоки текста фиксированной длины (последний блок может быть меньшей длины). В лабораторной работе рекомендуемая длина таких блоков 5…10 символов.
Для криптопреобразования по методу перестановок должна быть создана таблица перестановок CryptTab, длина которой совпадает с длиной блоков, на которые разбивается исходный текст. Значение CryptTab [i] указывает положение i-го элемента из исходного блока текста в строке переставляемых элементов (зашифрованном блоке). Зашифрование и расшифрирование отличаются направлением перебора символов строки.
Например, исходный блок текста
шифр
Пронумеруем буквы исходного блока: ш – 1; и – 2; ф – 3; р – 4.
Создадим таблицу перестановок из четырех (по количеству букв в блоке) элементов:
CryptTab[1]=2;
CryptTab[2]=4;
CryptTab[3]=1;
CryptTab[4]=3;
Переставим буквы исходного блока в соответствии с этой таблицей: первую букву (ш) поставим на второе место в зашифрованном блоке, вторую букву (и) – на четвертое место и так далее. В результате получим:
фшри
Для расшифровки используем ту же таблицу: на первое место в расшифрованном блоке ставим вторую букву из зашифрованного блока (ш), на второе место – четвертую букву (и) и т.д. В результате восстанавливаем исходный блок.
Таблица перестановок (играющая роль ключа шифра) может создаваться случайным образом при каждом вызове программы.
Программа должна выводит четыре текстовые строки (каждую своим цветом): исходную (желтый), таблицу перестановок (зеленый), шифровку исходной (циан) и результат ее расшифровки (белый).
Поскольку при перестановках коды символов не меняются, то для шифрования текстовых файлов в большинстве случаев их можно использовать без всяких ограничений.
Криптозащиту с помощью замен рассмотрим на примере шифра Гая Юлия Цезаря, описываемого преобразованиями, соответственно прямым (расшифрование):
X = Y + (N – Shift) (mod N) (1)
и обратным (зашифрование):
Y = X + Shift (mod N), (2)
где X и Y — позиция (код) исходного и зашифрованного символа в N-символьном алфавите соответственно; <Shift> — сдвиг 1,2...N-1, не зависящий от номера позиции символа в строке.
Очевидно, что взятие по (mod N) необходимо, чтобы в результате преобразований не выйти за границы значений кодовой таблицы. Заметим, что всегда
Y = Y + N (mod N)
Однако следует учесть, что такие преобразования для кодовой таблицы ASCII с N=256 затрагивает управляющие символы (символы с кодами 00…1Fh). Это вызывает ряд затруднений. Во-первых, ориентированные на традиционное представление строк языки программирования высокого уровня, такие как Бейсик, Паскаль, Си содержат автоматические средства ввода-вывода для вставки (при записи) и удаления (при чтении) пар символов CR/LF, разделяющих строки текстового файла. Так, для языка Паскаль такими средствами являются операторы Readln, Writeln. Чтобы использовать традиционные средства ввода-вывода для работы с зашифрованным текстовым файлом, необходимо сохранить его строковую структуру. Иначе говоря, криптографические преобразования не должны мешать работе механизма блокирования/разблокирования строк. Последнее условие выполняется, если шифрующие механизмы не порождают символов CR/LF, разрезающих строку на части при ее записи на диск или выводе на экран. Конечно, подобное ограничение снижает криптостойкость шифрованных текстов, но другого выбора нет.
Во-вторых, в результате прямого преобразования Цезаря для некоторого символа (и некоторого ключа, т.е. сдвига <Shift>) в шифрограмме может быть получен символ 1Ah (конец файла). Если этот символ будет записан на диск, то при чтении зашифрованного файла с диска операция чтения будет остановлена на этом символе и все последующие символы прочитаны не будут.
Чтобы исключить манипуляции с управляющими символами при криптографических преобразованиях можно использовать следующий прием. При зашифровании положение в алфавите исходного символа C с кодом Ord (C) из диапазона 20h..FFh считать равным:
X = Ord (C) – 32.
Этот код и использовать в (2) при шифровании. Число символов в таком алфавите (N) равно 224, а управляющие коды отсутствуют (символы CR/LF будут формироваться автоматически при записи в файл очередной строки с помощью оператора Writeln, либо вообще не подвергаться шифрованию при использовании оператора Write).
При расшифровании после получения Y по формуле (1) код символа корректируется:
Ord(С) = Y + 32.
Для фиксированного значения сдвига <Shift> программа шифрования/расшифрирования использует фиксированную таблицу соответствия между символами исходного и зашифрованного сообщений, ключ шифра представляет собой значение сдвига. Такой шифр получил название "одноалфавитный шифр подстановки". В общем случае для N-символьного алфавита таких таблиц, т. е. способов расшифровки, всего может быть N. Причем каждая таблица имеет простое устройство, и все они могут быть проверены даже вручную.
Усиление криптостойкости шифра Цезаря достигается в том случае, если считать сдвиги зависящими от положения шифруемого символа в строке. Тогда каждому положению символа соответствует своя шифровальная таблица. Число различных таблиц по-прежнему равно N, однако, для расшифрования уже необходимо знать порядок следования таблиц, что, собственно, и есть ключом шифра. Последнее и обусловливает повышение надежности шифра. Такой шифр получил название одноразовый блокнот и теоретически считается абсолютно стойким (при условии, что для каждого исходного текста выбирается свой ключ). Легко видеть, что длина ключа, при этом, равна длине исходного текста (ключ в подобных преобразования часто называют гаммой).
В шифре Виженара текст разбивается на блоки по К символов каждый (последний блок текста может быть меньше К) и в каждом таком блоке последовательно применяются К таблиц шифрования.
При разработке программ шифрования для заполнения таблицы сдвигов возможно использование датчика псевдослучайных чисел (такие датчики, как правило, встроены в среду разработки – Turbo Pascal? Turbo C и т.д. Исследования показывают, что начальное состояние такого датчика определяется 4-байтовым числом (для большинства программ, работающих в реальном режиме), что в результате дает всего 4 294 967 296 различных способов шифрования. Однако это число можно увеличить, используя для создания гаммы шифра два или более подобных датчиков и комбинируя порождаемые ими случайные последовательности.
Вместо применения подобных генераторов можно использовать пароль. Достаточно длинный и не смысловой пароль способен создать уже значительные трудности при попытке взлома, если только злоумышленник не раздобудет фрагмент исходного текста, по которому легко восстановить весь пароль и расшифровать текст.
Содержание отчета
1. Краткое описание методов шифрования.
2. Исходные тексты программы.
3. Результаты работы программ:
исходная строка;
гамма или ключ (пароль) шифрования
зашифрованная строка
расшифрованная строка.