Аффинный шифр - Affine cipher

Аффинный шифр - это разновидность моноалфавитный замещающий шифр, где каждой букве в алфавите сопоставляется ее числовой эквивалент, зашифровывается с помощью простой математической функции и преобразуется обратно в букву. Используемая формула означает, что каждая буква шифруется до одной другой буквы и обратно, что означает, что шифр по сути является стандартным шифром подстановки с правилом, определяющим, какая буква к какой идет. Таким образом, у него есть слабые места всех подстановочных шифров. Каждая буква зашифрована с функцией $(топор + б) мод 26$ , куда $б$ - величина сдвига.

Описание

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

{ Displaystyle { mbox {E}} (х) = (топор + b) { bmod {m}},}

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

{ displaystyle { mbox {D}} (х) = a ^ {- 1} (x-b) { bmod {m}},}

куда $а -1$ это модульный мультипликативный обратный из $а$ по модулю $м$ . Т.е. он удовлетворяет уравнению

{ displaystyle 1 = aa ^ {- 1} { bmod {m}}.}

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

{ displaystyle { begin {align} { mbox {D}} ({ mbox {E}} (x)) & = a ^ {- 1} ({ mbox {E}} (x) -b) { bmod {m}} & = a ^ {- 1} (((ax + b) { bmod {m}}) - b) { bmod {m}} & = a ^ {- 1} (ax + bb) { bmod {m}} & = a ^ {- 1} ax { bmod {m}} & = x { bmod {m}}. End {выравнивается} }}

Недостатки

Поскольку аффинный шифр по-прежнему является моноалфавитным шифром подстановки, он наследует слабые стороны этого класса шифров. В Шифр цезаря это аффинный шифр с $а = 1$ поскольку функция шифрования просто сводится к линейному сдвигу. В Шифр атбаш использует $а = -1$ .

Учитывая конкретный случай шифрования сообщений на английском языке (т.е. $м = 26$ ), всего существует 286 нетривиальных аффинных шифров, не считая 26 тривиальных шифров Цезаря. Это число связано с тем, что есть 12 чисел, которые совмещать с 26, что меньше 26 (это возможные значения $а$ ). Каждое значение $а$ может иметь 26 различных дополнительных сдвигов ( $б$ ценить); следовательно, существует 12 × 26 или 312 возможных ключей. Это отсутствие разнообразия делает систему крайне небезопасной, если рассматривать ее в свете Принцип Керкхоффа.

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

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

Примеры

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

А	B	C	D	E	F	грамм	ЧАС	я	J	K	L	M	N	О	п	Q	р	S	Т	U	V	W	Икс	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

Шифрование

В этом примере шифрования^[1] открытый текст, который нужно зашифровать, называется «AFFINE CIPHER», используя указанную выше таблицу для числовых значений каждой буквы, принимая $а$ быть 5, $б$ быть 8, и $м$ равным 26, поскольку в используемом алфавите 26 символов. Только ценность $а$ имеет ограничение, так как он должен быть взаимно прост с 26. Возможные значения, которые $а$ может быть 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25. Значение для $б$ может быть произвольным, пока $а$ не равно 1, так как это сдвиг шифра. Таким образом, функция шифрования для этого примера будет $у = E (Икс) = (5 Икс + 8) мод 26$ . Первый шаг в шифровании сообщения - записать числовые значения каждой буквы.

простой текст	А	F	F	я	N	E	C	я	п	ЧАС	E	р
$Икс$	0	5	5	8	13	4	2	8	15	7	4	17

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

простой текст	А	F	F	я	N	E	C	я	п	ЧАС	E	р
$Икс$	0	5	5	8	13	4	2	8	15	7	4	17
$(5 Икс + 8)$	8	33	33	48	73	28	18	48	83	43	28	93
$(5 Икс + 8) мод 26$	8	7	7	22	21	2	18	22	5	17	2	15

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

простой текст	А	F	F	я	N	E	C	я	п	ЧАС	E	р
$Икс$	0	5	5	8	13	4	2	8	15	7	4	17
$(5 Икс + 8)$	8	33	33	48	73	28	18	48	83	43	28	93
$(5 Икс + 8) мод 26$	8	7	7	22	21	2	18	22	5	17	2	15
зашифрованный текст	я	ЧАС	ЧАС	W	V	C	S	W	F	р	C	п

Расшифровка

В этом примере расшифровки зашифрованный текст, который будет расшифрован, является зашифрованным текстом из примера шифрования. Соответствующая функция дешифрования $D (у) = 21(у - 8) мод 26$ , куда $а -1$ рассчитывается как 21, а $б$ равно 8. Для начала напишите числовые эквиваленты каждой буквы в зашифрованном тексте, как показано в таблице ниже.

зашифрованный текст	я	ЧАС	ЧАС	W	V	C	S	W	F	р	C	п
$у$	8	7	7	22	21	2	18	22	5	17	2	15

Теперь следующий шаг - вычислить $21(у - 8)$ , а затем возьмите остаток от деления результата на 26. В следующей таблице показаны результаты обоих вычислений.

зашифрованный текст	я	ЧАС	ЧАС	W	V	C	S	W	F	р	C	п
$у$	8	7	7	22	21	2	18	22	5	17	2	15
$21(у - 8)$	0	−21	−21	294	273	−126	210	294	−63	189	−126	147
$21(у - 8) мод 26$	0	5	5	8	13	4	2	8	15	7	4	17

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

зашифрованный текст	я	ЧАС	ЧАС	W	V	C	S	W	F	р	C	п
$у$	8	7	7	22	21	2	18	22	5	17	2	15
$21(у - 8)$	0	−21	−21	294	273	−126	210	294	−63	189	−126	147
$21(у - 8) мод 26$	0	5	5	8	13	4	2	8	15	7	4	17
простой текст	А	F	F	я	N	E	C	я	п	ЧАС	E	р

Закодирован весь алфавит

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

письмо в открытом виде	А	B	C	D	E	F	грамм	ЧАС	я	J	K	L	M	N	О	п	Q	р	S	Т	U	V	W	Икс	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
$(5 Икс + 8) мод 26$	8	13	18	23	2	7	12	17	22	1	6	11	16	21	0	5	10	15	20	25	4	9	14	19	24	3
письмо с зашифрованным текстом	я	N	S	Икс	C	ЧАС	M	р	W	B	грамм	L	Q	V	А	F	K	п	U	Z	E	J	О	Т	Y	D

Примеры программирования

Следующее Python code может использоваться для шифрования текста аффинным шифром:

# Печатает таблицу транспонирования для аффинного шифра.# a должно быть взаимно просто с m = 26.def аффинный(а: int, б: int) -> Никто:    за я в классифицировать(26):        Распечатать(chr(я+ord('А')) + ": " + chr(((а*я+б)%26)+ord('А')))# Пример вызовааффинный(5, 8)