Система шифрования Цезаря

Методы шифрования

Оглавление

ОПИСАНИЕ МЕТОДОВ ШИФРОВАНИЯ.. 1

1. Шифр перестановки «Скитала». 1

2. Шифрующие таблицы.. 2

3. Магические квадраты.. 4

4. ШИФРЫ ПРОСТОЙ ЗАМЕНЫ... 4

4.1.Полибианский квадрат.. 4

4.2. Система шифрования Цезаря. 5

4.3. Аффинная система подстановок Цезаря. 5

4.4. Система Цезаря с ключевым словом.. 6

4.5. Шифрующие таблицы Трисемуса. 7

4.6. Биграммный шифр Плейфейра. 8

4.7. Система омофонов. 9

5. ШИФРЫ СЛОЖНОЙ ЗАМЕНЫ... 9

5.1. Шифр Гронсфельда. 10

5.2. Система шифрования Вижинера. 10

5.3. Шифр "двойной квадрат" Уитстона. 12

6. Роторные машины.. 13

7. ШИФРОВАНИЕ МЕТОДОМ ГАММИРОВАНИЯ.. 15

8. Методы генерации псевдослучайных последовательностей чисел. 16

ОПИСАНИЕ МЕТОДОВ ШИФРОВАНИЯ

Шифр перестановки «Скитала»

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

Шифрование выполнялось следующим образом. На стержень цилиндрической формы, который назывался скитала, наматывали спиралью (виток к витку) полоску пергамента и писали на ней вдоль стержня несколько строк текста сообщения. Затем снимали со стержня полоску пергамента с написанным текстом. Буквы на этой полоске оказывались расположенными хаотично. Такой же результат можно получить, если буквы сообщения писать по кольцу не подряд, а через определенное число позиций до тех пор, пока не будет исчерпан весь текст.

	Н	А	С	Т
	У	П	А	Й
	Т	Е

Рис.1.

Сообщение НАСТУПАЙТЕ при размещении его по окруж­ности стержня по три буквы дает шифртекст НУТАПЕСА_ТЙ

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

Шифрующие таблицы

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

В качестве ключа в шифрующих таблицах используются'

• размер таблицы;

• слово или фраза, задающие перестановку,

• особенности структуры таблицы.

Одним из самых примитивных табличных шифров пере­становки является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шиф­ром скитала Например, сообщение

ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ

записывается в таблицу поочередно по столбцам.

Результат за­полнения таблицы из 5 строк и 7 столбцов показан на рис. 2.

Т	Н	П	В	Е	Г	Л
Е	А	Р	А	д	О	Н
Р	Т	И	Е	Ь	В	О
М	О	Б	Т	М	П	Ч
И	Р	Ы	С	О	О	Ь

Рис 2. Заполнение таблицы из 5 строк и 7 столбцов

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

ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ

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

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

Применим в качестве ключа, например, слово ПЕЛИКАН, а текст сообщения возьмем из предыдущего примера. На рис. 3 показаны две таблицы, заполненные текстом сообщения и ключе­вым словом, при этом левая таблица соответствует заполнению до перестановки, а правая таблица- заполнению после пере­становки.

Ключ

П

Е

Л

И

К

А

Н

А

Е

И

К

Л

Н

П

Т

Н

П

В

Е

Г

Л

Г

Н

В

Е

П

Л

Т

Е

А

Р

А

Д

О

Н

А

А

Д

Р

Н

Е

Р

Т

И

Е

Ь

В

О

В

Т

Е

Ь

И

О

Р

М

О

Б

Т

М

П

Ч

П

Т

М

Б

Ч

М

И

Р

Ы

С

О

О

Ь

О

Р

С

О

Ы

Ь

И

До перестановки После перестановки

Рис 3. Таблицы, заполненные ключевым словом и текстом сообщения

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

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

ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ

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

Пример выполнения шифрования методом двойной пере­становки показан на рис. 4.

Если считывать шифртекст из пра­вой таблицы построчно блоками по четыре буквы, то получится следующее:

ТЮАЕ ООГМ РЛИП ОЬСВ

Ключом к шифру двойной перестановки служит последова­тельность номеров столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно).

П

Р

И

Л

Р

Л

И

П

Т

Ю

А

Е

Е

Т

А

Ю

Т

Ю

А

Е

О

О

Г

М

В

О

С

Ь

О

Ь

С

В

Р

Л

И

П

М

О

Г

О

О

О

Г

М

О

Ь

С

В

Исходная таблица Перестановка столбцов Перестановка строк

Рис. 4. Пример выполнения шифрования методом двойной перестановки

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы:

• для таблицы 3х3 36 вариантов;

• для таблицы 4х4 576 вариантов;

• для таблицы 5х5 14400 вариантов.

Однако двойная перестановка не отличается высокой стой­костью и сравнительно просто "взламывается" при любом размере таблицы шифрования.

Магические квадраты

В средние века для шифрования перестановкой применя­лись и магические квадраты.

Магическими квадратами называют квадратные таблицы с вписанными в их клетки последовательными натуральными чис­лами, начиная от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число.

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

Пример магического квадрата и его заполнения сооб­щением ПРИЛЕТАЮ ВОСЬМОГО - на рис. 5.

					О	И	Р	М
					Е	О	С	Ю
					В	Т	А	Ь
					Л	Г	О	П

Рис 5. Пример магического квадрата 4х4 и его заполнения сообщением ПРИЛЕТАЮ ВОСЬМОГО

Шифртекст, получаемый при считывании содержимого правой таблицы по строкам, имеет вполне загадочный вид: ОИРМ ЕОСЮ ВТАЪ ЛГОП

Число магических квадратов быстро возрастает с увеличе­нием размера квадрата. Существует только один магический квад­рат размером 3х3 (если не учитывать его повороты). Количество магических квадратов 4х4 составляет уже 880, а количество маги­ческих квадратов 5х5 - около 250000.

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

ШИФРЫ ПРОСТОЙ ЗАМЕНЫ

При шифровании заменой (подстановкой) символы шиф­руемого текста заменяются символами того же или другого алфа­вита с заранее установленным правилом замены. В шифре про­стой замены каждый символ исходного текста заменяется симво­лами того же алфавита одинаково на всем протяжении текста. Часто шифры простой замены называют шифрами одноалфавит­ной подстановки.

Полибианский квадрат

Одним из первых шифров простой замены считается так называемый "полибианский квадрат". За два века до нашей эры греческий писатель и историк Полибий изобрел для целей шифрования квадратную таблицу размером 5x5, заполненную буквами греческого алфавита в случайном порядке. (Рис.6.)

l	e	u	w	g
r	z	d	s	o
m	h	b	x	t
y	p	q	a	k
c	n		j	i

Рис.6. Полибианский квадрат, заполненный случайным образом 24 буквами греческого алфавита и пробелом.

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

Концепция полибианского квадрата оказалась плодотворной и нашла применение в криптосистемах последующего времени.

Система шифрования Цезаря

Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). Свое название этот шифр получил по имени римского императора Гая Юлия Цезаря, кото­рый использовал этот шифр при переписке с Цицероном (около 50 г. до н.э.).

При шифровании исходного текста каждая буква заменя­лась на другую букву того же алфавита по следующему правилу. Заменяющая буква определялась путем смещения по алфавиту от исходной буквы на К букв. При достижении конца алфавита выполнялся циклический переход к его началу. Цезарь использо­вал шифр замены при смещении К = 3. Такой шифр замены мож­но задать таблицей подстановок, содержащей соответствующие пары букв открытого текста и шифр текста. Совокупность возмож­ных подстановок для К=3 показана в табл. 1.

Таблица 1

Одно-алфавитные подстановки (К = 3, m = 26)

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

Например, послание Цезаря: VENI VIDI VICI

(в переводе на русский означает "Пришел, Увидел, Победил"), на­правленное его другу Аминтию после победы над понтийским ца­рем Фарнаком, сыном Митридата, выглядело бы в зашифрован­ном виде так: YHQL YLGL YLFL