Аффинный шифр
Аффинный шифр — это частный случай более общего моноалфавитного шифра подстановки. К шифрам подстановки относятся также шифр Цезаря, ROT13 и Атбаш. Поскольку аффинный шифр легко дешифровать, он обладает слабыми криптографическими свойствами[1].
Описание
В аффинном шифре каждой букве алфавита размера [math]\displaystyle{ m }[/math] ставится в соответствие число из диапазона [math]\displaystyle{ 0 .. m-1 }[/math]. Затем при помощи модульной арифметики для каждого числа, соответствующего букве исходного алфавита, вычисляется новое число, которое заменит старое в шифротексте. Функция шифрования[2] для каждой буквы
- [math]\displaystyle{ \mbox{E}(x)=(ax+b)\mod{m}, }[/math]
где модуль [math]\displaystyle{ m }[/math] — размер алфавита, а пара [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] — ключ шифра. Значение [math]\displaystyle{ a }[/math] должно быть выбрано таким, что [math]\displaystyle{ a }[/math] и [math]\displaystyle{ m }[/math] — взаимно простые числа. Функция расшифрования[2]
- [math]\displaystyle{ \mbox{D}(x)=a^{-1}(x-b)\mod{m}, }[/math]
где [math]\displaystyle{ a^{-1} }[/math] — обратное к [math]\displaystyle{ a }[/math] число по модулю [math]\displaystyle{ m }[/math]. То есть оно удовлетворяет уравнению[2]
- [math]\displaystyle{ 1 = a a^{-1}\mod{m}. }[/math]
Обратное к [math]\displaystyle{ a }[/math] число существует только в том случае, когда [math]\displaystyle{ a }[/math] и [math]\displaystyle{ m }[/math] — взаимно простые. Значит, при отсутствии ограничений на выбор числа [math]\displaystyle{ a }[/math] расшифрование может оказаться невозможным. Покажем, что функция расшифрования является обратной к функции шифрования
- [math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ a=3 }[/math], [math]\displaystyle{ b=4 }[/math] и [math]\displaystyle{ m=26 }[/math], так как в используемом алфавите 26 букв. Только на число [math]\displaystyle{ a }[/math] наложены ограничения, так как оно должно быть взаимно простым с 26. Возможные значения [math]\displaystyle{ a }[/math]: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25[3]. Значение [math]\displaystyle{ b }[/math] может быть любым, только если [math]\displaystyle{ a }[/math] не равно единице, так как это сдвиг шифра. Итак, для нашего примера функция шифрования [math]\displaystyle{ y=E(x)=(3x+4)\pmod{26} }[/math]. Первый шаг шифрования — запись чисел, соответствующих каждой букве сообщения.
сообщение | A | T | T | А | C | K | A | T | D | A | W | N |
[math]\displaystyle{ x }[/math] | 0 | 19 | 19 | 0 | 2 | 10 | 0 | 19 | 3 | 0 | 22 | 13 |
Теперь, для каждого значения [math]\displaystyle{ x }[/math] найдем значение [math]\displaystyle{ (3x+4) }[/math]. После нахождения значения [math]\displaystyle{ (3x+4) }[/math] для каждого символа возьмем остаток от деления [math]\displaystyle{ (3x+4) }[/math] на 26. Следующая таблица показывает первые четыре шага процесса шифрования.
сообщение | A | T | T | А | C | K | A | T | D | A | W | N |
[math]\displaystyle{ x }[/math] | 0 | 19 | 19 | 0 | 2 | 10 | 0 | 19 | 3 | 0 | 22 | 13 |
[math]\displaystyle{ 3x+4 }[/math] | 4 | 61 | 61 | 4 | 10 | 34 | 4 | 61 | 13 | 4 | 70 | 43 |
[math]\displaystyle{ (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]\displaystyle{ x }[/math] | 0 | 19 | 19 | 0 | 2 | 10 | 0 | 19 | 3 | 0 | 22 | 13 |
[math]\displaystyle{ 3x+4 }[/math] | 4 | 61 | 61 | 4 | 10 | 34 | 4 | 61 | 13 | 4 | 70 | 43 |
[math]\displaystyle{ (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]\displaystyle{ \mbox{D}(y)=a^{-1}(y+m-b)\mbox{ mod }m }[/math], где [math]\displaystyle{ a^{-1}=9 }[/math], [math]\displaystyle{ b=4 }[/math] и [math]\displaystyle{ m=26 }[/math].
Замечание: если каждая [math]\displaystyle{ y \geqslant b }[/math], то функция расшифрования принимает вид [math]\displaystyle{ \mbox{D}(y)=a^{-1}(y-b)\mbox{ mod }m }[/math]. (Точно так же, как и в обозреваемом примере, но разберём общий вариант)
Для начала запишем численные значения для каждой буквы шифротекста, как показано в таблице ниже.
шифротекст | E | J | J | E | K | I | E | J | N | E | S | R |
[math]\displaystyle{ y }[/math] | 4 | 9 | 9 | 4 | 10 | 8 | 4 | 9 | 13 | 4 | 18 | 17 |
Теперь для каждого [math]\displaystyle{ y }[/math] необходимо рассчитать [math]\displaystyle{ 9(y+m-4) }[/math] и взять остаток от деления этого числа на 26. таблица показывает результат этих вычислений.
шифротекст | E | J | J | E | K | I | E | J | N | E | S | R |
[math]\displaystyle{ y }[/math] | 4 | 9 | 9 | 4 | 10 | 8 | 4 | 9 | 13 | 4 | 18 | 17 |
[math]\displaystyle{ 9(y+26-4) }[/math] | 234 | 279 | 279 | 234 | 288 | 270 | 234 | 279 | 315 | 234 | 360 | 351 |
[math]\displaystyle{ 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]\displaystyle{ y }[/math] | 4 | 9 | 9 | 4 | 10 | 8 | 4 | 9 | 13 | 4 | 18 | 17 |
[math]\displaystyle{ 9(y+26-4) }[/math] | 234 | 279 | 279 | 234 | 288 | 270 | 234 | 279 | 315 | 234 | 360 | 351 |
[math]\displaystyle{ 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]\displaystyle{ a=1 }[/math], что сводит функцию шифрования к простому линейному сдвигу[1].
В случае шифрования сообщений на русском языке (т.е. [math]\displaystyle{ m=33 }[/math]) существует 297 нетривиальных аффинных шифров, не учитывая 33 тривиальных шифра Цезаря. Это число легко посчитать, зная, что существует всего 20 чисел взаимно простых с 33 и меньших 33 (а это и есть возможные значения [math]\displaystyle{ a }[/math]). Каждому значению [math]\displaystyle{ a }[/math] могут соответствовать 33 разных дополнительных сдвига (значение [math]\displaystyle{ b }[/math]); то есть всего существует 20*33 или 660 возможных ключей. Аналогично, для сообщений на английском языке (т.е. [math]\displaystyle{ m=26 }[/math]) всего существует 12*26 или 312 возможных ключей[3]. Такое ограниченное количество ключей приводит к тому, что система крайне не криптостойка с точки зрения принципа Керкгоффса.
Основная уязвимость шифра заключается в том, что криптоаналитик может выяснить (путём частотного анализа[4], полного перебора[1], угадывания или каким-либо другим способом) соответствие между двумя любыми буквами исходного текста и шифротекста. Тогда ключ может быть найден путём решения системы уравнений[4]. Кроме того, так мы знаем, что [math]\displaystyle{ a }[/math] и [math]\displaystyle{ m }[/math] — взаимно простые, это позволяет уменьшить количество проверяемых ключей для полного перебора.
Преобразование, подобное аффинному шифру, используется в линейном конгруэнтном методе[5] (разновидности генератора псевдослучайных чисел). Этот метод не является криптостойким по той же причине, что и аффинный шифр.
Примечания
- ↑ 1,0 1,1 1,2 1,3 S. R. Nagpaul, Surender Kumar Jain. Topics in applied abstract algebra. — AMS. — P. 137-138.
- ↑ 2,0 2,1 2,2 Johannes Buchmann. Introduction to cryptography. — Springer. — P. 95.
- ↑ 3,0 3,1 David Salomon. Coding for data and computer communications. — Springer. — P. 204.
- ↑ 4,0 4,1 Josef Pieprzyk, Thomas Hardjono, Jennifer Seberry. Fundamentals of computer security. — Springer, 2003. — P. 72-74. — 677 p.
- ↑ Алгоритмы: введение в разработку и анализ. — Издательский дом Вильямс. — С. 130-131.