Русская Википедия:Аффинный шифр

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Описание

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

<math>\mbox{E}(x)=(ax+b)\mod{m},</math>

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

<math>\mbox{D}(x)=a^{-1}(x-b)\mod{m},</math>

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

<math>1 = a a^{-1}\mod{m}.</math>

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

<math>\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}</math>

Количество возможных ключей для аффинного шифра можно записать через функцию Эйлера как <math>\varphi(m)m</math>[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», используя упомянутое выше соответствие между буквами и числами, и значения <math>a=3</math>, <math>b=4</math> и <math>m=26</math>, так как в используемом алфавите 26 букв. Только на число <math>a</math> наложены ограничения, так как оно должно быть взаимно простым с 26. Возможные значения <math>a</math>: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25[3]. Значение <math>b</math> может быть любым, только если <math>a</math> не равно единице, так как это сдвиг шифра. Итак, для нашего примера функция шифрования <math> y=E(x)=(3x+4)\pmod{26}</math>. Первый шаг шифрования — запись чисел, соответствующих каждой букве сообщения.

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

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

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

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

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

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

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

Замечание: если каждая <math>y \geqslant b</math>, то функция расшифрования принимает вид <math>\mbox{D}(y)=a^{-1}(y-b)\mbox{ mod }m</math>. (Точно так же, как и в обозреваемом примере, но разберём общий вариант)

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

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

Теперь для каждого <math>y</math> необходимо рассчитать <math>9(y+m-4)</math> и взять остаток от деления этого числа на 26. таблица показывает результат этих вычислений.

шифротекст E J J E K I E J N E S R
<math>y</math> 4 9 9 4 10 8 4 9 13 4 18 17
<math>9(y+26-4)</math> 234 279 279 234 288 270 234 279 315 234 360 351
<math>9(y+26-4)\pmod{26}</math> 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
<math>y</math> 4 9 9 4 10 8 4 9 13 4 18 17
<math>9(y+26-4)</math> 234 279 279 234 288 270 234 279 315 234 360 351
<math>9(y+26-4)\pmod{26}</math> 0 19 19 0 2 10 0 19 3 0 22 13
сообщение A T T A C K A T D A W N


programming language

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

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

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

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

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

Примечания

Шаблон:Примечания