Шифр замены

Helgus ~ µастер ~ Kласс: Это незавершённая статья по ивентологии и её применениям

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

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

Исторический пример

Шифр Цезаря

Историческим примером шифра замены является шифр Цезаря (I век до н.э.). Он заключался в следующем: каждая буква алфавита заменялась другой буквой, из этого алфавита, идущей за данной через некоторый интервал. Возьмем интервал равный 3 [1].

Алфавит

А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ю Э Я

алфавит со сдвигом

Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я А Б В

Таким образом буква А будет заменяться буквой Г, Б – Д, В – Е, и т.д. Зашифруем слово «РИМ»:

Р $\rightarrow$ У

И $\rightarrow$ Л

М $\rightarrow$ П

Получили: РИМ $\rightarrow$ УЛП

Запишем при помощи формул М := РИМ;

Слово «ЗАМЕНА»

З $\rightarrow$ К;

А $\rightarrow$ Г;

М $\rightarrow$ П;

Е $\rightarrow$ И;

Н $\rightarrow$ Р;

А $\rightarrow$ Г;

М := ЗАМЕНА

E(M) = КГПИРГ

Шифр Виженера

Квадрат Виженера выглядит следующим образом:

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

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 A

C 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

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

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 D

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Z 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

Система Виженера подобна системе Цезаря, в которой ключ меняется от шага к шагу. Квадрат используется как для шифрования так и для дешифрования. Осуществляется это следующим образом. Из полной таблицы выбирается первая строка и те строки, первые буквы которых соответствуют буквам ключа. Первой размещается первая строка, а под нею — строки, соответствующие буквам ключа в порядке следования этих букв в ключе шифрования. Так, для сообщения SECRET и ключа CRYPTO находим пересечения S-строки и C-столбца: получаем букву T. Закодированное сообщение будет иметь вид: TNECLF. Для расшифрования находит в C – строке лежит буква T? Получаем S.

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

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

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

Одноалфавитные замены

Рассмотри другой шифр. Представим ситуацию, что американская разведка перехватила сообщение адресованное японскому флотскому офицеру, перед атакой на Перл-Харброр [2].

19	17	17	19	14
20	23	18	19	08
12	16	19	08	03
21	08	25	18	14
18	06	03	18	08
15	18	22	18	11

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

Тогда, мы всего возможных вариантов замены букв можно посчитать по формуле

$A_n^k$ = $={\frac {n!}{(n-k)!}}$

В сообщение 16 букв, n =16, а во всем алфавите 26, k = 26. Получаем размещение без повторения 16 из 26, т.е.

$A_{26}^{16}={\frac {26!}{(10)!}}$

И это равно

$A_{26}^{16}=11113631534573680000$

Чаще всего встречается число 18. Заменим 18 на букву E – самую распространенную букву.

19	17	17	19	14
20	23	E	19	08
12	16	19	08	03
21	08	25	E	14
18	06	03	E	08
15	E	22	E	11

Тогда остается

$A_{26}^{15}=1010331395066880000$ вариантов.

Рассмотрим первую пятерку цифр: 19 17 17 19 14. По нашему предположению, что каждое число буквы, можно сделать вывод, что или 19 – гласная, а 17 – согласная, или наоборот, т.к. в слове не может быть 4 гласных (согласных) подряд. Поскольку 19 встречается чаще (четыре раза), она скорее может оказаться гласной, чем 17 (которая встречается только дважды). После Е самая частая гласная — А. Пусть 17 — А.

A	17	17	A	14
20	23	E	A	08
12	16	A	08	03
21	08	25	E	14
18	06	03	E	08
15	E	22	E	11

Так, как нам известно, что сообщение адресовано японскому флотскому офицеру, то можно предположить, что первое слово Attack – атака. В таком случае 17 — Т, 14 — С и 20 — К.

A	T	T	A	C
K	23	E	A	08
12	16	A	08	03
21	08	25	E	C
18	06	03	E	08
15	E	22	E	11

Также, нам, сейчас, известно, что атака была на Перл-Харбор (Pearl Harbor) 7 декабря, и в сообщение встречается только одна пара EA – тогда пусть 23 – P, 08 – R, 12 – L.

A	T	T	A	C
K	P	E	A	R
L	16	A	R	03
21	R	25	E	C
E	06	03	E	R
15	E	22	E	11

И уже не трудно догадаться, что 16 – H, 03 – B, 21 – O, 25 – D, 06 – M, 15 – S, 22 – V, 11 – N.

Таким образом, получаем сообщение

A	T	T	A	C
K	P	E	A	R
L	H	A	R	B
O	R	D	E	C
E	M	B	E	R
S	E	V	E	N

Открытый текст: ATTACK PEARL HARBOR DECEMBER SEVEN

Многоалфавитные замены

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

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

Первую проблему можно легко решить, если для каждой буквы исходного алфавита строится некоторое множество символов $M_\alpha$ так, что множества $M_\alpha$ и $M_{\beta }$ попарно не пересекаются при $\alpha <>\beta$, то есть любые два различные множества не содержат одинаковых элементов. Множество $M_\alpha$ называется множеством шифрообозначений для буквы $\alpha$. При зашифровании каждая буква $\alpha$ открытого сообщения, начиная с первой, заменяется любым символом из множества $M_\alpha$.

Многоалфавитная замена

a	b	c	…	z
$M_a$	$M_b$	$M_c$	…	$M_z$

является ключом шифра замены [3].

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

А	Б	В	Г	Д	Е	Ж	З	И	Й	К	М	Н	О	П	Р
21	37	14	22	01	24	62	73	46	23	12	08	27	53	35	04
40	26	63	47	31	83	88	30	02	91	72	32	77	68	60	44
10	03	71	82	15	70	11	55	90	69	38	61	54	09	84	45

С	Т	У	Ф	Х	Ц	Ч	Ш	Щ		Ы	Ь	Э	Ю	Я
20	13	59	25	75	43	19	29	06	65	74	48	36	28	16
52	39	07	49	33	85	58	80	50	34	17	56	78	64	41
89	67	93	76	18	51	87	66	81	92	42	79	86	05	57

то сообщение «я знаком с шифрами замены» может быть зашифровано, например, любым из следующих трех способов:

16	55	54	10	69	09	61	89	29	90	49	44	10	08	02	73	21	32	83	54	74
41	55	77	10	23	68	08	20	66	90	76	44	21	61	90	55	51	61	83	84	42
57	30	27	10	91	68	32	20	80	02	49	45	40	32	46	55	40	08	83	27	42

Такой вид кодирования, называется шифрование методом ```многоалфавитной``` подстановки.

Литература

1. Бабаш А.В., Шанкин Г.П. Криптография: аспекты защиты. М.: Солон – Р, 2002.

2. Стивенсон Нил. Криптономикон (Stephenson N. Cryptonomicon. N. Y.: Avon, 1999)

3. Ященко В.В., ред. Введение в криптографию. М: МЦНМО, 2000

См.также

• Криптография
• Шифр Цезаря

---

Nomaan 08:31, 11 августа 2008 (UTC)