ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ
Для обеспечения дополнительной скрытности можно повторно зашифровать сообщение, которое уже прошло шифрование. Такой метод шифрования называется двойной перестановкой. В случае двойной перестановки столбцов и строк таблицы перестановки определяются отдельно для столбцов и отдельно для строк. Сначала в таблицу записывается текст сообщения, а потом поочередно переставляются столбцы, а затем строки. При расшифровании порядок перестановок должен быть обратным.
Пример выполнения шифрования методом двойной перестановки показан в таблицах, приведенных ниже. Если считывать шифртекст из правой таблицы построчно блоками по четыре буквы, то получится следующее: ТЮАЕ ООГМ РЛИП ОЬСВ
Ключом к шифру двойной перестановки служит последовательность номеров столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно).
|
1
|
2
|
3
|
4
|
3
|
Р
|
Л
|
И
|
П
|
1
|
Т
|
Ю
|
А
|
Е
|
4
|
О
|
Ь
|
С
|
В
|
2
|
О
|
О
|
Г
|
М
|
|
1
|
2
|
3
|
4
|
1
|
Т
|
Ю
|
А
|
Е
|
2
|
О
|
О
|
Г
|
М
|
3
|
Р
|
Л
|
И
|
П
|
4
|
О
|
Ь
|
С
|
В
|
|
4
|
1
|
3
|
2
|
3
|
П
|
Р
|
И
|
Л
|
1
|
Е
|
Т
|
А
|
Ю
|
4
|
В
|
О
|
С
|
Ь
|
2
|
М
|
О
|
Г
|
О
|
Исходная таблица Перестановка столбцов Перестановка строк
Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы:
для таблицы 3х3 36 вариантов;
для таблицы 4х4 576 вариантов;
для таблицы 5х5 14400 вариантов.
Однако двойная перестановка не отличается высокой стойкостью и сравнительно просто «взламывается» при любом размере таблицы шифрования.
Применение магических квадратов
В средние века для шифрования перестановкой применялись и магические квадраты.
Магическими квадратами называют квадратные таблицы с вписанными в их клетки последовательными натуральными числами, начиная от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число.
Шифруемый текст вписывали в магические квадраты в соответствии с нумерацией их клеток. Если затем выписать содержимое такой таблицы по строкам, то получится шифртекст, сформированный благодаря перестановке букв исходного сообщения. В те времена считалось, что созданные с помощью магических квадратов шифртексты охраняет не только ключ, но и магическая сила.
Пример магического квадрата и его заполнения сообщением
ПРИЛЕТАЮ ВОСЬМОГО
16
|
3
|
2
|
13
|
5
|
10
|
11
|
8
|
9
|
6
|
7
|
12
|
4
|
15
|
14
|
1
|
О
|
И
|
Р
|
М
|
Е
|
О
|
С
|
Ю
|
В
|
Т
|
А
|
Ь
|
Л
|
Г
|
О
|
П
|
Шифртекст, получаемый при считывании содержимого правой таблицы по строкам, имеет вполне загадочный вид: ОИРМ ЕОСЮ ВТАЬ ЛГОП
Число магических квадратов быстро возрастает с увеличением размера квадрата. Существует только один магический квадрат размером 3х3 (если не учитывать его повороты). Количество магических квадратов 4х4 составляет уже 880, а количество магических квадратов 5х5 - около 250000. Магические квадраты средних и больших размеров могли служить хорошей базой для обеспечения нужд шифрования того времени, поскольку практически нереально выполнить вручную перебор всех вариантов для такого шифра.
Шифры простой замены
При шифровании заменой (подстановкой) символы шифруемого текста заменяются символами того же или другого алфавита с заранее установленным правилом замены. В шифре простой замены каждый символ исходного текста заменяется символами того же алфавита одинаково на всем протяжении текста. Часто шифры простой замены называют шифрами одноалфавитной подстановки.
Полибианский квадрат
Одним из первых шифров простой замены считается так называемый полибианский квадрат. За два века до нашей эры греческий писатель и историк Полибий изобрел для целей шифрования квадратную таблицу размером 5х5, заполненную 24-мя буквами греческого алфавита и пробелом в случайном порядке:
λ
|
ε
|
υ
|
ω
|
γ
|
ρ
|
ζ
|
δ
|
σ
|
ο
|
μ
|
η
|
β
|
ξ
|
τ
|
ψ
|
π
|
θ
|
α
|
κ
|
χ
|
ν
|
|
φ
|
ι
|
При шифровании в этом полибианском квадрате находили очередную букву открытого текста и записывали в шифртекст букву, расположенную ниже ее в том же столбце. Если буква текста оказывалась в нижней строке таблицы, то для шифртекста брали самую верхнюю букву из того же столбца. Например, для слова τ α υ ρ ο σ
получается шифртекст : κ φ δ μ τ ξ
Концепция полибианского квадрата оказалась плодотворной и нашла применение в криптосистемах последующего времени.
Рассмотрим, как практически выполняется шифрование заменой с помощью компьютера. Самый простой и эффективный способ сделать текст нечитаемым - спрятать его, смешав с последовательностью случайных чисел. Такую последовательность задают с помощью ключа, а смесь получают с помощью операции XOR3. Почему именно случайная последовательность? Можно исходить из того, что криптоаналитик попытается снизить неопределенность чтения шифровки, зная статистические свойства нашей последовательности. Если он знает наше намерение использовать последовательность, где 1 встречается с вероятностью р, а 0 с вероятностью 1-р, то он также с вероятностью р будет предполагать наличие 1. Вероятность его успеха будет равна:
р*р+(1-р)*(1-р).
Эта функция достигает минимума при р=0.5, что получается при случайном равновероятном выборе 0 и 1. Далее, если биты в случайной последовательности будут равновероятно принимать значения 0 и 1, то биты в шифровке будут также обладать этим свойством. Действительно, пусть вероятность нулевого бита в тексте равна р, а единичного- 1-р. Нулевой бит в шифровке появляется, когда соответствующие биты последовательности и текста оба равны либо 0, либо 1. Значит, вероятность появления нулевого бита в шифре равна:
0.5*р+0.5*(1-р)=0.5.
Более того, если биты в случайной последовательности статистически независимы друг от друга, то и в шифровке они становятся такими же, т.е. текст превращается в шум.
Система шифрования Цезаря
Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, который использовал этот шифр при переписке с Цицероном (около 50 г. до н.э.).
При шифровании исходного текста каждая буква заменялась на другую букву того же алфавита по следующему правилу. Заменяющая буква определялась путем смещения по алфавиту от исходной буквы на К букв. При достижении конца алфавита выполнялся циклический переход к его началу. Цезарь использовал шифр замены при смещении К = 3. Такой шифр замены можно задать таблицей подстановок, содержащей соответствующие пары букв открытого текста и шифртекста. Совокупность возможных подстановок для К=3 показана в
Одноалфавитные подстановки (К = 3, m = 26)
А -> D
D
|
J -> M
M
|
S -> V
v
|
В -> E
Е
|
К -> N
N
|
T -> W
|
С -> F
F
|
L -> O
0
|
U -> X
X
|
D -> G
G
|
М -> P
Р
|
V -> Y
Y
|
Е -> H
Н
|
N -> Q
|
W -> Z
Z
|
F -> I
1
|
O -> R
R
|
X -> A
A
|
G -> J
|
P -> S
S
|
Y -> B
В
|
Н -> K
К
|
Q -> T
Т
|
Z -> C
С
|
I -> L
L
|
R -> U
U
|
|
Например, послание Цезаря VENI VIDI VICI (в переводе на русский означает «Пришел, Увидел, Победил»), направленное его другу Аминтию после победы над понтийским царем Фарнаком, сыном Митридата, выглядело бы в зашифрованном виде так: YHQL YLGL YLFL
Шифрующие таблицы Трисемуса
В 1508 г. аббат из Германии Иоганн Трисемус написал печатную работу по криптологии под названием «Полиграфия». В этой книге он впервые систематически описал применение шифрующих таблиц, заполненных алфавитом в случайном порядке. Для получения такого шифра замены обычно использовались таблица для записи букв алфавита и ключевое слово (или фраза). В таблицу сначала вписывалось по строкам ключевое слово, причем повторяющиеся буквы отбрасывались. Затем эта таблица дополнялась не вошедшими в нее буквами алфавита по порядку. Поскольку ключевое слово или фразу легко хранить в памяти, то такой подход упрощал процессы шифрования и расшифрования.
Поясним этот метод шифрования на примере. Для русского алфавита шифрующая таблица может иметь размер 4х8. Выберем в качестве ключа слово БАНДЕРОЛЬ. Шифрующая таблица с таким ключом показана ниже.
Б
|
А
|
Н
|
Д
|
Е
|
Р
|
О
|
Л
|
Ь
|
В
|
Г
|
Ж
|
3
|
И
|
Й
|
К
|
М
|
П
|
С
|
Т
|
У
|
Ф
|
Х
|
Ц
|
Ч
|
Ш
|
Щ
|
Ы
|
Ъ
|
Э
|
Ю
|
Я
|
Как и в случае полибианского квадрата, при шифровании находят в этой таблице очередную букву открытого текста и записывают в шифртекст букву, расположенную ниже ее в том же столбце. Если буква текста оказывается в нижней строке таблицы, тогда для шифртекста берут самую верхнюю букву из того же столбца.
Например, при шифровании с помощью этой таблицы сообщения ВЫЛЕТАЕМ ПЯТОГО получаем шифртекст ПДКЗЫВЗЧШЛЫЙСЙ
Такие табличные шифры называются монограммными, так как шифрование выполняется по одной букве. Трисемус первым заметил, что шифрующие таблицы позволяют шифровать сразу по две буквы. Такие шифры называются биграммными.
Биграммный шифр Плейфейра
Шифр Плейфейра, изобретенный в 1854 г., является наиболее известным биграммным шифром замены. Он применялся Великобританией во время первой мировой войны. Основой шифра Плейфейра является шифрующая таблица со случайно расположенными буквами алфавита исходных сообщений.
Для удобства запоминания шифрующей таблицы отправителем и получателем сообщений можно использовать ключевое слово (или фразу) при заполнении начальных строк таблицы. В целом структура шифрующей таблицы системы Плейфейра полностью аналогична структуре шифрующей таблицы Трисемуса. Поэтому для пояснения процедур шифрования и расшифрования в системе Плейфейра воспользуемся шифрующей таблицей Трисемуса из предыдущего раздела.
Процедура шифрования включает следующие шаги.
1. Открытый текст исходного сообщения разбивается на пары букв (биграммы). Текст должен иметь четное количество букв и в нем не должно быть биграмм, содержащих две одинаковые буквы. Если эти требования не выполнены, то текст модифицируется даже из-за незначительных орфографических ошибок.
2. Последовательность биграмм открытого текста преобразуется с помощью шифрующей таблицы в последовательность биграмм шифртекста по следующим правилам:
2.1. Если обе буквы биграммы открытого текста не попадают на одну строку или столбец (как, например, буквы А и Й в табл. Трисемуса), тогда находят буквы в углах прямоугольника, определяемого данной парой букв. В нашем примере это – буквы АЙОВ. Пара букв АЙ отображается в пару ОВ. Последовательность букв в биграмме шифртекста должна быть зеркально расположенной по отношению к последовательности букв в биграмме открытого текста.
2.2. Если обе буквы биграммы открытого текста принадлежат одному столбцу таблицы, то буквами шифртекста считаются буквы, которые лежат под ними. (Например, биграмма НС дает биграмму шифртекста ГЩ.) Если при этом буква открытого текста находится в нижней строке, то для шифртекста берется соответствующая буква из верхней строки того же столбца. (Например, биграмма ВШ дает биграмму шифртекста ПА.)
2.3. Если обе буквы биграммы открытого текста принадлежат одной строке таблицы, то буквами шифртекста считаются буквы, которые лежат справа от них. (Например, биграмма НО дает биграмму шифртекста ДЛ.) сли при этом буква открытого текста находится в крайнем правом столбце, то для шифра берут соответствующую букву из левого столбца в той же строке. (Например, биграмма ФЦ дает биграмму шифртекста ХМ.)
Зашифруем текст
|
