Материал: Раздел 1. Криптографические одноключевые системы
Раздел 1. Криптографические системы с симметричным
ключом
Элементы классической криптографии
Древние криптографические системы
Познакомимся с некоторыми старыми криптосистемами (даются в современной интерпретации)[10].
Система Цезаря.
Путь требуется передать текстовое сообщение, написанное на английском языке (содержит 26 букв, пробелы игнорируются): WE GO TO CITY. Все буквы от A до Z нумеруются цифрами от 0 до 25 и в сообщении производится замена, например со сдвигом на три:
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 E F G H I J K L M N O P Q R S T U V W X Y Z A B C
В этом случае исходный текст будет зашифрован как ZHJRWRFLWB.
Ключевое пространство системы Цезаря состоит из 26 чисел от 0 до 25 и определяет сдвиг всех букв алфавита при заменах. Ek и Dk легко вычисляются одно из другого, так как Dk = E26-k. Множество замен {Ek}образует коммутативную группу сдвигов, причем Ek-1 = Dk
Обобщением шифра Цезаря может служить шифр замены. Поскольку число перестановок 26 букв равно 26!, то пространство ключей такого шифра равно 26!.т.е. достаточно велико. Однако, полное множество перестановок n элементов образует группу, то есть по Ek просто и однозначно находится Dk
Криптосистема Хилла
Криптосистема основана на свойствах линейной алгебры. Все буквы английского алфавита кодируются цифрами, как и в предыдущем случае: A - 0, B- 1,...,Z - 26. Матрица для шифрования M имеет размер d x d. Все операции выполняются по модулю 26. Все сообщение разбивается на блоки длины d. Для работы криптосистемы необходимо, чтобы матрица M имела бы обратную.
Например, M
=
M-1=
Исходное сообщение HELP определяется двумя векторами
P1
=
=
;
P2
=
=
;
Из уравнений MP1=C1
=
;
MP2
= C2
=
,что
соответствует шифрованному сообщению
HIAT.
Криптосистема Ришелье. Эта система относится к группе методов называемых «информация среди мусора». Для шифрования сообщений используется лист картона с прорезями, например
X |
X |
X |
X |
X |
X |
X |
|
X |
X |
X |
X |
X |
X |
X |
X |
X |
X |
|
X |
X |
X |
X |
X |
X |
|
X |
X |
X |
X |
X |
X |
X |
X |
|
|
X |
X |
X |
X |
|
X |
X |
X |
X |
|
|
X |
|
X |
X |
|
X |
X |
X |
X |
X |
X |
X |
|
X |
X |
X |
X |
X |
X |
X |
X |
|
|
Картон с прорезями накладывается на лист бумаги и в прорези вписывается сообщение. Затем картон снимается и в остальные клеточки вписывается «мусор», который полностью затеняет ранее написанный текст. Так для примера можно написать сообщение:
I |
|
L |
O |
V |
E |
|
Y |
O |
U |
I |
|
H |
A |
V |
E |
|
Y |
O |
U |
D |
E |
E |
P |
|
U |
N |
D |
E |
R |
M |
Y |
|
S |
K |
I |
N |
|
M |
Y |
L |
O |
V |
E |
|
L |
A |
S |
T |
S |
F |
O |
R |
E |
V |
E |
R |
|
I |
N |
H |
Y |
P |
E |
R |
S |
P |
A |
C |
E |
Оно выглядит совершенно невинно. Но если наложить картон с прорезями, получим зловещее сообщение: YOU KILL AT ONCE.
Одноалфавитными системами называются системы подстановок, в которых буквы заменяются одинаково на протяжении всего текста. Существуют многоалфавитные подстановки. Простейшим примером многоалфавитной подстановки может служить следующая. Исходное сообщение поделено на блоки по три буквы в каждом. При шифровании первая буква каждого блока становится третьей, а вторая и третья становятся соответственно первой и второй. Так, сообщение LETUSGOTOFRANCE станет ETLSGUTOORAFCEN. Система легко обобщается. Пусть длина блока равна d, тогда число вариантов блоковой замены равно d!
В некоторых случаях в одноалфавитных системах криптотекст использует алфавит отличный от алфавита исходного текста. Например, шифр замены букв может иметь такой вид:
A:
B: C: J’ K’ L’ S T U
D: E: F: M’ N’ O’ V W X
G: H: I: P’ Q’ R’ Y Z
Т
огда
исходное сообщение WE
TALK
ABOUT
IT
MANY
TIMES
будет выг-лядеть так:
Если исходное сообщение достаточно длинно и написано на любом естественном языке, то для его расшифровки можно использовать статистические данные о вероятности появления букв в произвольных сообщениях. Если же алфавиты исходного сообщения и криптотекста совпадают и нет никакой дополнительной информации о частоте появления букв в текстах (например, используется редкий язык), то расшифровка усложняется, так как потребует N! вариантов перебора подстановок, где N – число букв используемого алфавита..
Считается, что одной из самых древних криптосистем является система Полибия. Рассмотрим квадрат замен (доска Полибия):
A B C D E
A A B C D E
B F G H I K
C L M N O P
D Q R S T U
E V W X Y Z
Каждая буква a представляется в криптотексте парой букв, соответствующих ее координатам. Так, например, сообщение HALLOW будет представлено как BCAACACACDEB. В нашей классификации система Полибия есть одноалфавитная система замен. Буква J исключена для того, чтобы получить квадрат. Алфавит шифротекста уже алфавита исходного текста.
Аффинная криптосистема определяется двумя целыми числами a и b, причем
0 £ a,b £ 25, (a,26) = 1. Буква a заменяется на aa+ b mod 26. Для a = 3 и b = 5 получаем следующие замены букв:
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
F I L O R U X A D G J M P S V Y B E H K N Q T W Z C
Условие взаимной простоты a и 26 обеспечивает взаимную однозначность отображения.
Подсчитаем, сколько разных ключей имеется в приведенной аффинной системе. Число a может принимать следующие значения: 1,3,5,7,9,11,15,17,19,21,23,25. Не зависимо от значения a число b принимает 26 значений (от 0 до 25). Случай a = 1, b= 0 следует исключить. Тогда общее число ключей равно 311. В таком простейшем случае криптоаналитику не потребуется много времени для подбора ключа.
Система Цезаря с ключевым словом является одноалфавитной системой замены и определяется некоторым числом a и ключевым словом (фразой) с возможным повторением букв. Пусть система задана числом a = 8 и фразой: HOW MANY ELKS. Как и ранее выписываются подряд все буквы латинского алфавита и под буквой стоящей на 8 месте без пробелов пишется ключевая фраза. Оставшиеся буквы первой строки в алфавитном порядке дописываются далее с циклическим переносом:
0 8 25
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
P Q R T U V X Z H 0 W M A N Y E L K S B C D F G I J
Простейшая защита против атак криптоаналитика, основанных на подсчете частот появления различных букв в текстах, используется в криптосистеме омофонов (HOMOPHONES), которая также является одноалфавитной. Буквы исходного сообщения имеют несколько замен, причем число замен каждой буквы пропорционально вероятности ее появления в тексте сообщения.
1.1.2.Многоалфавитные системы
Система Плайфейра (PLAYFAIR), названа в честь барона Плайфейра. Буквы английского алфавита, среди которых отсутствует J, упорядочиваются в виде квадрата 5 x 5, например
S Y D W Z
R I P U L
H C A X F
T N O G E
B R M Q V
Квадрат используется для зашифрования и расшифрования по следующим правилам:
Исходный текст делится на блоки по 2 буквы в каждом. Текст имеет четную длину и в нем не должно быть блоков, содержащих 2 одинаковые буквы. Если эти требования не выполнены, текст модифицируется (даже в ущерб правилам грамматики). Например, AL LM EN; KI SS ME; WH ER EA RE YO U. Первый текст допустим, второй содержит в блоке 2 одинаковые буквы, третий имеет нечетную длину.
Если пара букв блока не попадает в одну строку или столбец, то эта пара шифруется парой букв прямоугольника. Если же пара букв попадает в одну строку или столбец, то она шифруется буквами со сдвигом вправо (в строке) или вниз (в столбце). Так, AL шифруется FP; LM - PV; EN - TO.
Зашифруем криптотекст CR YP TO EN IG MA - HI DI NG TO UN DO
EN IG MA - шифровальная машина на которой была основана криптосистема, используемая немцами во время ВО.
При циклическом смещении строк и столбцов квадрата Плейфейра получаем эквивалентный квадрат. Известны модификации квадрата Плейфейра: прямоугольники размером 4 x 4, 3 x 9 и с иным способом замены.
Система Плейфейра с ключевым словом строится следующим образом: выбирается ключевое слово без повтора букв и записывается в первых строках квадрата, а затем выписываются оставшиеся буквы в алфавитном порядке. Так, для ключевой фразы: HOW MANY ELKS получаем квадрат для шифрования:
H O W M A
N Y E L K