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

Аффинный шифр - это тип моноалфавитного шифра подстановки , где каждая буква в алфавите сопоставляется с ее числовым эквивалентом, зашифровывается с помощью простой математической функции и преобразуется обратно в букву. Используемая формула означает, что каждая буква шифруется до одной буквы и обратно, что означает, что шифр по сути является стандартным шифром подстановки с правилом, определяющим, какая буква к какой идет. Таким образом, у него есть слабые места всех подстановочных шифров. Каждая буква зашифрована функцией ( 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}(x-b){\bmod {m}},}$

где ^-1 является модульным мультипликативным обратным из более по модулю т . Т.е. он удовлетворяет уравнению

${\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+b-b){\bmod {m}}\\&=a^{-1}ax{\bmod {m}}\\&=x{\bmod {m}}.\end{aligned}}}$

Слабые стороны [ править ]

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

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

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

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

Примеры [ править ]

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

Шифрование [ править ]

В этом примере шифрования ^[1] открытый текст, который должен быть зашифрован, представляет собой «AFFINE CIPHER» с использованием упомянутой выше таблицы для числовых значений каждой буквы, принимая 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 (х ) = (5 х + 8) по модулю 26 . Первый шаг в шифровании сообщения - записать числовые значения каждой буквы.

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

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

Расшифровка [ править ]

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

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

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

Закодирован весь алфавит [ править ]

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

Примеры программирования [ править ]

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

# Печатает таблицу транспонирования для аффинного шифра. # a должно быть взаимно просто с m = 26. def  affine ( a :  int ,  b :  int )  ->  None :  для  i  в  диапазоне ( 26 ):  print ( chr ( i + ord ( 'A' ))  +  ":"  +  chr ((( a * i + b ) % 26 ) + ord ( 'А' )))# Пример вызова affine ( 5 ,  8 )

См. Также [ править ]

• Аффинные функции
• Код atbash
• Шифр цезаря
• ROT13
• Темы в криптографии

Ссылки [ править ]