Аффинный шифр

Аффинный шифр — это частный случай более общего моноалфавитного шифра подстановки. К шифрам подстановки относятся также шифр Цезаря, ROT13 и Атбаш. Поскольку аффинный шифр легко дешифровать, он обладает слабыми криптографическими свойствами^[1].

Описание

В аффинном шифре каждой букве алфавита размера $m$ ставится в соответствие число из диапазона $0 .. m-1$. Затем при помощи модульной арифметики для каждого числа, соответствующего букве исходного алфавита, вычисляется новое число, которое заменит старое в шифротексте. Функция шифрования^[2] для каждой буквы

$\mbox{E}(x)=(ax+b)\mod{m},$

где модуль $m$ — размер алфавита, а пара $a$ и $b$ — ключ шифра. Значение $a$ должно быть выбрано таким, что $a$ и $m$ — взаимно простые числа. Функция расшифрования^[2]

$\mbox{D}(x)=a^{-1}(x-b)\mod{m},$

где $a^{-1}$ — обратное к $a$ число по модулю $m$. То есть оно удовлетворяет уравнению^[2]

$1 = a a^{-1}\mod{m}.$

Обратное к $a$ число существует только в том случае, когда $a$ и $m$ — взаимно простые. Значит, при отсутствии ограничений на выбор числа $a$ расшифрование может оказаться невозможным. Покажем, что функция расшифрования является обратной к функции шифрования

$\begin{matrix}\mbox{D}(\mbox{E}(x)) &= &a^{-1}(\mbox{E}(x)-b)\mod{m}\\ &= &a^{-1}(((ax+b)\mod{m})-b)\mod{m} \\ &= &a^{-1}(ax+b-b)\mod{m} \\ &= &a^{-1}ax \mod{m}\\ & = &x\mod{m}. \end{matrix}$

Количество возможных ключей для аффинного шифра можно записать через функцию Эйлера как $\varphi(m)m$^[1].

Примеры шифрования и расшифрования

В следующих примерах используются латинские буквы от A до 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	Z
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Шифрование

В этом примере необходимо зашифровать сообщение "ATTACK AT DAWN", используя упомянутое выше соответствие между буквами и числами, и значения $a=3$, $b=4$ и $m=26$, так как в используемом алфавите 26 букв. Только на число $a$ наложены ограничения, так как оно должно быть взаимно простым с 26. Возможные значения $a$: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25^[3]. Значение $b$ может быть любым, только если $a$ не равно единице, так как это сдвиг шифра. Итак, для нашего примера функция шифрования $y=E(x)=(3x+4)\pmod{26}$. Первый шаг шифрования — запись чисел, соответствующих каждой букве сообщения.

сообщение	A	T	T	А	C	K	A	T	D	A	W	N
$x$	0	19	19	0	2	10	0	19	3	0	22	13

Теперь, для каждого значения $x$ найдем значение $(3x+4)$. После нахождения значения $(3x+4)$ для каждого символа возьмем остаток от деления $(3x+4)$ на 26. Следующая таблица показывает первые четыре шага процесса шифрования.

сообщение	A	T	T	А	C	K	A	T	D	A	W	N
$x$	0	19	19	0	2	10	0	19	3	0	22	13
$3x+4$	4	61	61	4	10	34	4	61	13	4	70	43
$(3x+4)\pmod{26}$	4	9	9	4	10	8	4	9	13	4	18	17

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

сообщение	A	T	T	А	C	K	A	T	D	A	W	N
$x$	0	19	19	0	2	10	0	19	3	0	22	13
$3x+4$	4	61	61	4	10	34	4	61	13	4	70	43
$(3x+4)\pmod{26}$	4	9	9	4	10	8	4	9	13	4	18	17
шифротекст	E	J	J	E	K	I	E	J	N	E	S	R

Расшифрование

Для расшифрования возьмем шифротекст из примера с шифрованием. Функция расшифрования будет $\mbox{D}(y)=a^{-1}(y-b)\mbox{ mod }m$, где $a^{-1}=9$, $b=4$ и $m=26$. Для начала запишем численные значения для каждой буквы шифротекста, как показано в таблице ниже.

шифротекст	E	J	J	E	K	I	E	J	N	E	S	R
$y$	4	9	9	4	10	8	4	9	13	4	18	17

Теперь рассчитаем для каждого $y$ необходимо рассчитать $9(y-4)$ и взять остаток от деления этого числа на 26. Следующая таблица показывает результат этих вычислений.

шифротекст	E	J	J	E	K	I	E	J	N	E	S	R
$y$	4	9	9	4	10	8	4	9	13	4	18	17
$9(y-4)$	0	45	45	0	54	36	0	45	81	0	126	117
$9(y-4)\pmod{26}$	0	19	19	0	2	10	0	19	3	0	22	13

Последний шаг операции расшифрования для шифротескста — поставить в соответствие числам буквы. Сообщение после расшифрования будет "ATTACKATDAWN". Таблица ниже показывает выполнение последнего шага.

шифротекст	E	J	J	E	K	I	E	J	N	E	S	R
$y$	4	9	9	4	10	8	4	9	13	4	18	17
$9(y-4)$	0	45	45	0	54	36	0	45	81	0	126	117
$9(y-4)\pmod{26}$	0	19	19	0	2	10	0	19	3	0	22	13
сообщение	A	T	T	А	C	K	A	T	D	A	W	N

Шифрование всего алфавита

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

буква сообщения	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
$x$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
$(3x+4)\pmod{26}$	4	7	10	13	16	19	22	25	2	5	8	11	14	17	20	23	0	3	6	9	12	15	18	21	24	1
буква шифротекста	E	H	K	N	Q	T	W	Z	C	F	I	L	O	R	U	X	A	D	G	J	M	P	S	V	Y	B

Криптоанализ

Так как аффинный шифр является по сути моноалфавитным шифром замены, то он обладает всеми уязвимостями этого класса шифров. Шифр Цезаря — это аффинный шифр с $a=1$, что сводит функцию шифрования к простому линейному сдвигу^[1].

В случае шифрования сообщений на русском языке (т.е. $m=33$) существует 627 нетривиальных аффинных шифров, не учитывая 33 тривиальных шифра Цезаря. Это число легко посчитать, зная, что существует всего 20 чисел взаимно простых с 33 и меньших 33 (а это и есть возможные значения $a$). Каждому значению $a$ могут соответствовать 33 разных дополнительных сдвига (значение $b$); то есть всего существует 20*33 или 660 возможных ключей. Аналогично, для сообщений на английском языке (т.е. $m=26$) всего существует 12*26 или 312 возможных ключей^[3]. Такое ограниченное количество ключей приводит к тому, что система крайне не криптостойка с точки зрения принципа Керкгоффса.

Основная уязвимость шифра заключается в том, что криптоаналитик может выяснить (путем частотного анализа^[4], полного перебора^[1], угадывания или каким-либо другим способом) соответствие между двумя любыми буквами исходного текста и шифротекста. Тогда ключ может быть найдет путем решения системы уравнений^[4]. Кроме того, так мы знаем, что $a$ и $m$ — взаимно простые, это позволяет уменьшить количество проверяемых ключей для полного перебора.

Преобразование, подобное аффинному шифру, используется в линейном конгруэнтном методе^[5] (разновидности генератора псевдослучайных чисел). Этот метод не является криптостойким по той же причине, что и аффинный шифр.

Примечания

1. ↑ ^{1 2 3 4} S. R. Nagpaul, Surender Kumar Jain Topics in applied abstract algebra. — AMS. — P. 137-138.
2. ↑ ^{1 2 3} Johannes Buchmann Introduction to cryptography. — Springer. — P. 95.
3. ↑ ^{1 2} David Salomon Coding for data and computer communications. — Springer. — P. 204.
4. ↑ ^{1 2} Josef Pieprzyk, Thomas Hardjono, Jennifer Seberry Fundamentals of computer security. — Springer, 2003. — P. 72-74. — 677 p.
5. ↑ Алгоритмы: введение в разработку и анализ. — Издательский дом Вильямс. — С. 130-131.