Меню Главная Случайная статья Настройки Аффинный шифр Материал из https://ru.wikipedia.org Аффинный шифр — это частный случай более общего моноалфавитного шифра подстановки. К шифрам подстановки относятся также шифр Цезаря, ROT13 и Атбаш. Поскольку аффинный шифр легко дешифровать, он обладает слабыми криптографическими свойствами[1]. Содержание 1 Описание 2 Примеры шифрования и расшифрования 2.1 Шифрование 2.2 Расшифрование 3 Криптоанализ 4 Примечания Описание В аффинном шифре каждой букве алфавита размера ${\displaystyle m}$ ставится в соответствие число из диапазона ${\displaystyle 0..m-1}$. Затем при помощи модульной арифметики для каждого числа, соответствующего букве исходного алфавита, вычисляется новое число, которое заменит старое в шифротексте. Функция шифрования[2] для каждой буквы ${\displaystyle {\mbox{E}}(x)=(ax+b)\mod {m},}$ где модуль ${\displaystyle m}$ — размер алфавита, а пара ${\displaystyle a}$ и ${\displaystyle b}$ — ключ шифра. Значение ${\displaystyle a}$ должно быть выбрано таким, что ${\displaystyle a}$ и ${\displaystyle m}$ — взаимно простые числа. Функция расшифрования[2] ${\displaystyle {\mbox{D}}(x)=a^{-1}(x-b)\mod {m},}$ где ${\displaystyle a^{-1}}$ — обратное к ${\displaystyle a}$ число по модулю ${\displaystyle m}$. То есть оно удовлетворяет уравнению[2] ${\displaystyle 1=aa^{-1}\mod {m}.}$ Обратное к ${\displaystyle a}$ число существует только в том случае, когда ${\displaystyle a}$ и ${\displaystyle m}$ — взаимно простые. Значит, при отсутствии ограничений на выбор числа ${\displaystyle a}$ расшифрование может оказаться невозможным. Покажем, что функция расшифрования является обратной к функции шифрования ${\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}}}$ Количество возможных ключей для аффинного шифра можно записать через функцию Эйлера как ${\displaystyle \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», используя упомянутое выше соответствие между буквами и числами, и значения ${\displaystyle a=3}$, ${\displaystyle b=4}$ и ${\displaystyle m=26}$, так как в используемом алфавите 26 букв. Только на число ${\displaystyle a}$ наложены ограничения, так как оно должно быть взаимно простым с 26. Возможные значения ${\displaystyle a}$: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25[3]. Значение ${\displaystyle b}$ может быть любым, только если ${\displaystyle a}$ не равно единице, так как это сдвиг шифра. Итак, для нашего примера функция шифрования ${\displaystyle y=E(x)=(3x+4){\pmod {26}}}$. Первый шаг шифрования — запись чисел, соответствующих каждой букве сообщения. сообщение A T T А C K A T D A W N ${\displaystyle x}$ 0 19 19 0 2 10 0 19 3 0 22 13 Теперь, для каждого значения ${\displaystyle x}$ найдем значение ${\displaystyle (3x+4)}$. После нахождения значения ${\displaystyle (3x+4)}$ для каждого символа возьмем остаток от деления ${\displaystyle (3x+4)}$ на 26. Следующая таблица показывает первые четыре шага процесса шифрования. сообщение A T T А C K A T D A W N ${\displaystyle x}$ 0 19 19 0 2 10 0 19 3 0 22 13 ${\displaystyle 3x+4}$ 4 61 61 4 10 34 4 61 13 4 70 43 ${\displaystyle (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 ${\displaystyle x}$ 0 19 19 0 2 10 0 19 3 0 22 13 ${\displaystyle 3x+4}$ 4 61 61 4 10 34 4 61 13 4 70 43 ${\displaystyle (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 Расшифрование Для расшифрования возьмем шифротекст из примера с шифрованием. Функция расшифрования будет ${\displaystyle {\mbox{D}}(y)=a^{-1}(y+m-b){\mbox{ mod }}m}$, где ${\displaystyle a^{-1}=9}$, ${\displaystyle b=4}$ и ${\displaystyle m=26}$. Замечание: если каждая ${\displaystyle y\geqslant b}$, то функция расшифрования принимает вид ${\displaystyle {\mbox{D}}(y)=a^{-1}(y-b){\mbox{ mod }}m}$. (Точно так же, как и в обозреваемом примере, но разберём общий вариант) Для начала запишем численные значения для каждой буквы шифротекста, как показано в таблице ниже. шифротекст E J J E K I E J N E S R ${\displaystyle y}$ 4 9 9 4 10 8 4 9 13 4 18 17 Теперь для каждого ${\displaystyle y}$ необходимо рассчитать ${\displaystyle 9(y+m-4)}$ и взять остаток от деления этого числа на 26. таблица показывает результат этих вычислений. шифротекст E J J E K I E J N E S R ${\displaystyle y}$ 4 9 9 4 10 8 4 9 13 4 18 17 ${\displaystyle 9(y+26-4)}$ 234 279 279 234 288 270 234 279 315 234 360 351 ${\displaystyle 9(y+26-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 ${\displaystyle y}$ 4 9 9 4 10 8 4 9 13 4 18 17 ${\displaystyle 9(y+26-4)}$ 234 279 279 234 288 270 234 279 315 234 360 351 ${\displaystyle 9(y+26-4){\pmod {26}}}$ 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 Криптоанализ Так как аффинный шифр является по сути моноалфавитным шифром замены, то он обладает всеми уязвимостями этого класса шифров. Шифр Цезаря — это аффинный шифр с ${\displaystyle a=1}$, что сводит функцию шифрования к простому линейному сдвигу[1]. В случае шифрования сообщений на русском языке (т.е. ${\displaystyle m=33}$) существует 297 нетривиальных аффинных шифров, не учитывая 33 тривиальных шифра Цезаря. Это число легко посчитать, зная, что существует всего 20 чисел взаимно простых с 33 и меньших 33 (а это и есть возможные значения ${\displaystyle a}$). Каждому значению ${\displaystyle a}$ могут соответствовать 33 разных дополнительных сдвига (значение ${\displaystyle b}$); то есть всего существует 20*33 или 660 возможных ключей. Аналогично, для сообщений на английском языке (т.е. ${\displaystyle m=26}$) всего существует 12*26 или 312 возможных ключей[3]. Такое ограниченное количество ключей приводит к тому, что система крайне не криптостойка с точки зрения принципа Керкгоффса. Основная уязвимость шифра заключается в том, что криптоаналитик может выяснить (путём частотного анализа[4], полного перебора[1], угадывания или каким-либо другим способом) соответствие между двумя любыми буквами исходного текста и шифротекста. Тогда ключ может быть найден путём решения системы уравнений[4]. Кроме того, так мы знаем, что ${\displaystyle a}$ и ${\displaystyle m}$ — взаимно простые, это позволяет уменьшить количество проверяемых ключей для полного перебора. Преобразование, подобное аффинному шифру, используется в линейном конгруэнтном методе[5] (разновидности генератора псевдослучайных чисел). Этот метод не является криптостойким по той же причине, что и аффинный шифр. Примечания 1 2 3 4 S. R. Nagpaul, Surender Kumar Jain. Topics in applied abstract algebra. — AMS. — P. 137-138. 1 2 3 1 2 1 2