Полиалфавитны шифры ⇐ ПредыдущаяСтр 2 из 2
Каким бы сложным не был тот или иной алгоритм простой однозначной замены или перестановки все они потенциально обладают существенным недостатком. Зашифрованный текст может быть абсолютно не похож на исходный, но в нем все же остается кое-что от открытого текста. В частности, в тексте сохраняются частоты встречаемости букв и связи между ними. Например, буква «О» в русском языке встречается чаще других. В зашифрованном сообщении, тот символ или буква, которая будет встречаться чаще других, скорее всего, окажется буквой «О». Зная частоты встречаемости отдельных букв и биграмм в открытом тексте можно легко восстановить достаточно длинное зашифрованное сообщение. Еще в XIV веке появились работы, посвященные частотному анализу и шифрам многозначной замены. Шифрами многозначной замены или полиалфавитными называют шифры, в которых один и тот же символ открытого текста в зашифрованном сообщении может быть представлен несколькими разными символами. Простой многоалфавитный шифр. Самым простым вариантом решения задачи многозначной замены символов является использование при шифровании сразу нескольких алфавитов замены. Рассмотрим шифр подстановки, в котором используется два алфавита шифротекста. В процессе шифрования поочередно используются оба алфавита шифрования. Для первой буквы используется первый алфавит, для второй – второй, для третьей снова первый и т.д. В качестве примера с помощью следующей таблицы зашифруем слово «ТРАССА».
В результате шифрования получим текст «ЪЖНЭЫР». Как видно из примера, не смотря на то, что в исходном слове дважды встречались буквы «А» и «С», в зашифрованном слове парных букв не оказалось. Шифр Гронсфельда является многоалфавитной модификацией шифра Цезаря. Если в шифре Цезаря величина сдвига фиксирована, то в шифре Гросфельда она меняется в процессе шифрования. Для этого используется числовой ключ, который циклически записывается под сообщением. В процессе шифрования сдвиг происходит на цифру, указанную под шифруемой буквой. Например, возьмем ключ «34152» и слово «Сообщение».
Шифр пропорциональной замены.Частоты встречаемости символов в открытом тексте различны и хорошо прослеживаются даже в зашифрованном с помощью шифра перестановки или простой замены тексте. В таблице ниже представлены относительные частоты встречаемости символов русского алфавита в обычных текстах.
Как можно заметить, буква «А» встречается в четыре раза чаще буквы «Б», а буква «Ы» в два раза чаще «Ж». Для того, что бы выровнять частоты встречаемости символов в зашифрованном сообщении, те символы, которые в исходном тексте встречаются чаще всего, заменяются не одним, а несколькими символами. Количество замещающих символов выбирается пропорционально частоте встречаемости символов открытого текста. Так, например символы «Ч», «Й», «Х», «Ж», «Ю», «Ш», «Ц», «Щ», «Э» и «Ф» в процессе шифрования можно заменить одним символом. При шифровании букв «О» и «Е» нужно выбирать один из восьми, девяти символов. Выбор замещающего символа из такого множества осуществляется либо случайным образом, либо циклически. При первом появлении буквы берется первый замещающий символ, при втором – второй и т.д. Таблица Тритемия. Задача построения алфавита шифрования для шифра пропорциональной замены все же достаточно сложна. Во-первых, необходимо достаточно точно определить частоты встречаемости букв в открытом тексте. Во-вторых, нужно грамотно составить алфавит шифрования значительно больший по сравнению с исходным алфавитом и при этом обеспечить визуальное единство алфавита. Например, будет неправильно дополнять латинский алфавит символами греческого алфавита. Размер греческого алфавита известен. Если в зашифрованном сообщении будет встречаться только половина символов этого алфавита, то это подтолкнет криптоаналитика на мысль об использовании шифра пропорциональной замены. Еще одной ошибкой будет использовать в качестве первой строки таблицы замены символы только исходного алфавита. Тогда противник будет знать, что те символы, которые не входят в исходный алфавит являются расширяющими. В свою очередь это позволит разбить символы на группы и впоследствии расшифровать сообщение. Интересное решение задачи выравнивания частот символов в зашифрованном сообщении принадлежит Иоганнесу Тритемию. В своей книге «Полиграфия» вышедшей в 1518 году он предложил использовать квадратную таблицу представленную ниже.
В первую строку таблицы записывается обычный алфавит в прямом порядке. Каждая последующая строка таблицы представляет собой тот же алфавит, но сдвинутый относительно алфавита предыдущей строки на одну позицию влево. Первая строка таблицы используется и в качестве алфавита открытого текста и в качестве одного из шифралфавитов. Принцип шифрования достаточно прост: первая буква сообщения шифруется обычным шифром подстановки с помощью первой строки, вторая с помощью второй и т.д. В результате, алфавит шифрования меняется с каждой буквой сообщения. Если в исходном алфавите 24 буквы, то каждая из них может быть представлена в зашифрованном тексте всеми 24 буквами. При этом алфавиты исходного и зашифрованного сообщений совпадают. Шифр Виженера.Минусом шифра Тритемия является отсутствие в системе ключа шифрования как такого. В качестве ключа шифрования может быть использована перестановка символов исходного алфавита в первой строке таблицы Тритемия, но такой ключ сложно менять от сообщения к сообщению. Интересное решение этой проблемы было предложено французским дипломатом Блезом де Виженером. В своей книге «Трактат о шифрах» в 1586 году Виженер предложил использовать в качестве ключа шифрования само сообщение – самоключ. Суть идеи Виженера состояла в том, чтобы менять алфавиты шифрования не последовательно, как в шифре Тритемия, а выбирать их в зависимости от букв сообщения или ранее зашифрованного текста. Сам шифр Виженера фактически представляет собой модификацию шифра Тритемия. В основе шифра лежит таблица Тритемия, сверху и слева от которой записан обычный алфавит. Первая строка таблицы под алфавитом открытого текста может быть представлена как упорядоченным, так и перемешанным алфавитом. Все последующие строки также как и в таблице Тритемя представляют собой предыдущую строку, циклически сдвинутую на одну позицию влево.
Дополнительная строка, записанная сверху таблицы, используется в шифре для сопоставления с символами сообщения, а дополнительный столбец служит для выбора нужного алфавита по символам ключа. Известны два варианта реализации шифра Виженера. В первом варианте в качестве ключа шифрования используется само шифруемое сообщение M = m1, m2,…, mn. Для того чтобы обеспечить однозначность расшифрования в начало ключа (перед сообщением) дописывается одна буква k0 известная как отправителю, так и получателю сообщения K = k0, k1(= m1), k2(= m2),…, kn(=mn). Обе последовательности символов M и K записываются друг под другом. Ниже выписывается зашифрованное сообщение.
Буквы зашифрованного сообщения S = s1, s2,…, sn выбираются из таблицы шифрования по столбцу, соответствующему букве mi сообщения M, и строке, соответствующей символу ki ключа K. Во втором варианте в качестве ключа шифрования используются уже зашифрованные на символы сообщения K = k0, k1(= s1), k2(= s2),…, kn(=sn). В результате каждый следующий символ зависит от предыдущего.
Впоследствии идеи Виженера нашли свое продолжение в работе Гильберта Вернама предложившего в 1917 г. последовательно складывать двоичные значения букв сообщения с двоичными значениями символов достаточно длинного ключа шифрования. Фактически им был предложен шифр гаммирования – совершенный шифр, не поддающийся дешифрованию.
ЗАДАНИЕ НА ЛАБОРАТОРНУЮ РАБОТУ
При выполнении лабораторной работы необходимо программно реализовать алгоритмы шифрования и расшифрования простых шифров. Каждое задание состоит из трех подзадач: сформировать алфавит шифрования и расшифрования; описать алгоритм расшифрования для соответствующего простого шифра; написать программную реализацию шифра на языке высокого уровня Delphi, C++, С# или др. Необходимо предусмотреть загрузку длинных сообщений и ключа (при необходимости) из файла и запись результатов работы программы в файл. Все программы должны работать с русским алфавитом по возможности дополненным пробелом и знаками препинания. В ряде шифров допускается использование только заглавных букв: аффинная перестановка, квадрат Полибия, тюремный шифр, простой многоалфавитный шифр, шифр пропорциональной замены. Варианты задания: 1) Шифр Цезаря с ключом. Величина сдвига задается с клавиатуры; 2) Шифр Атабаш для русского и английского алфавитов; 3) Аффинная перестановка; 4) Шифр подстановки; 5) Квадрат Полибия; 6) Квадрат Полибия со случайным порядком следования символов; 7) Тюремный шифр; 8) Одиночная перестановка по квадрату. Размер вводится с клавиатуры; 9) Шифр вертикальной перестановки по ключевому слову; 10) Шифр двойной перестановки; 11) Магический квадрат; 12) Маршрутный шифр с задаваемым размером матрицы; 13) Простой многоалфавитный шифр из 3, 5, и 10 алфавитов; 14) Шифр Гронсфельда; 15) Шифр пропорциональной замены; 16) Шифр Тритемия; 17) Шифр Виженера с исходным текстом в качестве ключа; 18) Шифр Виженера с зашифрованным сообщением в качестве ключа.
СПИСОК ЛИТЕРАТУРЫ 1) Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черёмушкин А. В. Основы криптографии: Учебное пособие. – М.: Гелиос АРВ, 2005. – 480 С. 2) Сингх С. Книга шифров. Тайная история шифров и их расшифровки. – М.: Астрель, АСТ, 2007. – 448 С. 3) Бабаш А. В., Шанкин Г. П. История криптографии. – М.: Гелиос АРВ, 2002. – 240 С.
Редактор А.А.Литвинова ЛР № от В набор В печать Офсет. Формат 60х84/16. Бумага тип № 3. Объем усл.-п.л., уч.-изд.л. Заказ № . Тираж . Цена _______________________________________________ Издательский центр ДГТУ Адрес университета и полиграфического предприятия: 344010, г.Ростов-на-Дону, пл.Гагарина, 1 ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|