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

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

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

${\displaystyle E(x)=(ax+b){\bmod {m}}}$

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

${\displaystyle D(x)=a^{-1}(xb){\bmod {m}}}$

где a ⁻¹ — модульное мультипликативное обратное число a по модулю m . То есть, оно удовлетворяет уравнению

${\displaystyle 1=aa^{-1}{\bmod {m}}}$

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

${\displaystyle {\begin{aligned}D(E(x))&=a^{-1}(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{aligned}}}$

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

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

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

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

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

В этом примере шифрования ^[1] открытый текст, который должен быть зашифрован, — это «АФФИННЫЙ ШИФР» с использованием таблицы, упомянутой выше, для числовых значений каждой буквы, принимая a равным 5, b равным 8 и m равным 26, поскольку в используемом алфавите 26 символов. Только значение a имеет ограничение, поскольку оно должно быть взаимно простым с 26. Возможные значения, которые может иметь a , — 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25. Значение b может быть произвольным, пока a не равно 1, поскольку это сдвиг шифра. Таким образом, функция шифрования для этого примера будет y = E ( x ) = (5 x + 8) mod 26 . Первым шагом в шифровании сообщения является запись числовых значений каждой буквы.

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

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

В этом примере расшифровки зашифрованный текст, который будет расшифрован, является зашифрованным текстом из примера шифрования. Соответствующая функция расшифровки — D ( y ) = 21( y − b) mod 26 , где a ⁻¹ вычисляется как 21, а b равно 8. Для начала запишите числовые эквиваленты каждой буквы в зашифрованном тексте, как показано в таблице ниже.

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

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

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

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

# Печатает таблицу транспозиции для аффинного шифра. def  affine ( a :  int ,  b :  int ,  s :  str ):  import  string D  =  dict ( enumerate ( string.ascii_lowercase , start = 0 ) ) E = { v : kfork , vinD.items ( ) } size = len ( string.ascii_lowercase ) ret = " " print ( size ) forcins : N = E [ c ] val = a * N + b val = val % size print ( f " { c } ( { N } ) - > { D [ val ] } ( { val } ) " ) ret + = D [ val ] return ret​​​​​                                         аффинный ( 7 ,  3 ,  'foobar' )

• Аффинные функции
• Код Атбаша
• шифр Цезаря
• РОТ13
• Темы криптографии