Здавалка
Главная | Обратная связь

Полиалфавитны шифры



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

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

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

 

Исходн. алф. АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦШЩЫЬЪЭЮЯ
Алфавит шифр. 1 НЗЦМИЯТЮХРЩФШЭЧКАГЫЪЖЛЕСПВОУБЬДЁ
Алфавит шифр. 2 РОАЩУЮБЛШКГЕНВДЫФЖЭЪЙХЦЬТИМЁЗЯЧС

 

В результате шифрования получим текст «ЪЖНЭЫР». Как видно из примера, не смотря на то, что в исходном слове дважды встречались буквы «А» и «С», в зашифрованном слове парных букв не оказалось.

Шифр Гронсфельда является многоалфавитной модификацией шифра Цезаря. Если в шифре Цезаря величина сдвига фиксирована, то в шифре Гросфельда она меняется в процессе шифрования. Для этого используется числовой ключ, который циклически записывается под сообщением. В процессе шифрования сдвиг происходит на цифру, указанную под шифруемой буквой. Например, возьмем ключ «34152» и слово «Сообщение».

 

Открытый текст С О О Б Щ Е Н И Е
Ключ
Зашифрованный текст О К Н Ъ Ц В Й З А

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

 

Буква Частота Буква Частота Буква Частота Буква Частота
Пробел 0,145 Р 0,041 Я 0,019 Х 0,009
О 0,095 В 0,039 Ы 0,016 Ж 0,008
Е 0,074 Л 0,036 З 0,015 Ю 0,007
А 0,064 К 0,029 Ъ, Ь 0,015 Ш 0,006
И 0,064 М 0,026 Б 0,015 Ц 0,004
Т 0,056 Д 0,026 Г 0,014 Щ 0,003
Н 0,055 П 0,024 Ч 0,013 Э 0,003
С 0,046 У 0,021 Й 0,010 Ф 0,002

 

Как можно заметить, буква «А» встречается в четыре раза чаще буквы «Б», а буква «Ы» в два раза чаще «Ж». Для того, что бы выровнять частоты встречаемости символов в зашифрованном сообщении, те символы, которые в исходном тексте встречаются чаще всего, заменяются не одним, а несколькими символами. Количество замещающих символов выбирается пропорционально частоте встречаемости символов открытого текста. Так, например символы «Ч», «Й», «Х», «Ж», «Ю», «Ш», «Ц», «Щ», «Э» и «Ф» в процессе шифрования можно заменить одним символом. При шифровании букв «О» и «Е» нужно выбирать один из восьми, девяти символов. Выбор замещающего символа из такого множества осуществляется либо случайным образом, либо циклически. При первом появлении буквы берется первый замещающий символ, при втором – второй и т.д.

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

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

 

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

 

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

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

Шифр Виженера.Минусом шифра Тритемия является отсутствие в системе ключа шифрования как такого. В качестве ключа шифрования может быть использована перестановка символов исходного алфавита в первой строке таблицы Тритемия, но такой ключ сложно менять от сообщения к сообщению. Интересное решение этой проблемы было предложено французским дипломатом Блезом де Виженером. В своей книге «Трактат о шифрах» в 1586 году Виженер предложил использовать в качестве ключа шифрования само сообщение – самоключ.

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

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

 

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

 

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

В первом варианте в качестве ключа шифрования используется само шифруемое сообщение M = m1, m2,…, mn. Для того чтобы обеспечить однозначность расшифрования в начало ключа (перед сообщением) дописывается одна буква k0 известная как отправителю, так и получателю сообщения K = k0, k1(= m1), k2(= m2),…, kn(=mn). Обе последовательности символов M и K записываются друг под другом. Ниже выписывается зашифрованное сообщение.

 

Сообщение m1 m2mn
Ключ k0 m1 mn-1
Зашифрованное сообщение s1 s2sn

Буквы зашифрованного сообщения S = s1, s2,…, sn выбираются из таблицы шифрования по столбцу, соответствующему букве mi сообщения M, и строке, соответствующей символу ki ключа K.

Во втором варианте в качестве ключа шифрования используются уже зашифрованные на символы сообщения K = k0, k1(= s1), k2(= s2),…, kn(=sn). В результате каждый следующий символ зависит от предыдущего.

 

Сообщение m1 m2mn
Ключ k0 s1 sn-1
Зашифрованное сообщение s1 s2sn

 

Впоследствии идеи Виженера нашли свое продолжение в работе Гильберта Вернама предложившего в 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 Все права принадлежат авторам размещенных материалов.