Лабораторная работа № 2

 

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

 

Цель работы

 

Ознакомиться с различными шифрами простой замены (шифрами подстановки) и методами их дешифрования.

 

 

Теоретические сведения

 

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

 

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

 

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

 

λ	ε	υ	ω	γ
r	ς	δ	σ	ο
m	η	β	ξ	τ
Ψ	π	θ	α	ζ
c	ν		φ	ι

 

Рисунок 2.2.1 - Полибианский квадрат из 24 букв греческого алфавита

 

 

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

 

τ δ φ μ π

 

получается шифротекст

ζ ξ ω ψ ν.

 

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

 

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

 

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

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

 

Таблица 2.2.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 → P	V → Y
E → H	N → Q	W → Z
F → I	O → R	X → A
G → J	P → S	Y → B
H → K	Q → T	Z → C
I → L	R → U

Например, послание Цезаря

 

 

VENI VIDI VICI

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

 

 

YHQL YLGL YLFL.

 

 

Достоинством системы шифрования Цезаря является простота шифрования и расшифрования.

Недостатки данной системы следующие:

 

· подстановки, выполняемые в соответствии с системой Цезаря не маскируют частот появления различных букв исходного открытого текста;

· сохраняется алфавитный порядок в последовательности заменяющих букв. При изменении К изменяются только начальные позиции такой последовательности;

· число возможных ключей К мало;

· шифр Цезаря легко вскрывается на основе анализа частот появления букв в шифротексте.

 

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

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

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

 

В системе шифрования Цезаря использовались только ад­дитивные свойства множества целых Z_m. Однако символы мно­жества Z_m можно также умножать по модулю m. Применяя одно­временно операции сложения и умножения по модулю m над эле­ментами множества Z_m, можно получить систему подстановок, которую называют аффинной системой подстановок Цезаря.

 

E_a,b(t) = at + b (mod m),

 

где a,b - целые числа, 0 < a,b < m, НОД (a,m) = 1.

 

Следует заметить, что преобразование E_ab(t) является взаимно однозначным отображением на множестве Z_m только в том случае, если наибольший общий делитель чисел а и m,  (НОД (а, m)), равен единице, т.е. а и m должны быть взаимно простыми числами.

Например, пусть m = 26, а = 3, b = 5. Тогда, очевидно, НОД (3,26) = 1, и мы получаем следующее соответствие между числовыми кодами букв:

 

Таблица 2.2.2 – Соответствия между числовыми кодами букв

 

t	0	1	2	3	4	5	6	7	8	9	10	11	12
3 t + 5	5	8	11	14	17	20	23	0	3	6	9	12	15

 

t	13	14	15	16	17	18	19	20	21	22	23	24	25
3 t + 5	18	21	24	1	4	7	10	13	16	19	22	25	2

 

 

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

 

Таблица 2.2.3 – Соотвествие для букв открытого текста и шифротекста

 

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

Q

P

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

 

Исходное сообщение   NIGHT преобразуется

в шифротекст SDXAK

Достоинством аффинной системы является удобное управление ключами - ключи шифрования и расшифрования представляются в компактной форме в виде пары чисел (а, b).

Недостатки аффинной системы аналогичны недостаткам системы шифрования Цезаря.

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