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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Аффинный шифр — это частный случай более общего моноалфавитного шифра подстановки. К шифрам подстановки относятся также шифр Цезаря, 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.