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


Аффинный шифр — это частный случай более общего моноалфавитного шифра подстановки. К шифрам подстановки относятся также шифр Цезаря, ROT13 и Атбаш. Поскольку аффинный шифр легко дешифровать, он обладает слабыми криптографическими свойствами.

Описание

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

E ( x ) = ( a x + b ) mod m , {displaystyle {mbox{E}}(x)=(ax+b)mod {m},}

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

D ( x ) = a − 1 ( x − b ) mod m , {displaystyle {mbox{D}}(x)=a^{-1}(x-b)mod {m},}

где a − 1 {displaystyle a^{-1}} — обратное к a {displaystyle a} число по модулю m {displaystyle m} . То есть оно удовлетворяет уравнению

1 = a a − 1 mod m . {displaystyle 1=aa^{-1}mod {m}.}

Обратное к a {displaystyle a} число существует только в том случае, когда a {displaystyle a} и m {displaystyle m} — взаимно простые. Значит, при отсутствии ограничений на выбор числа a {displaystyle a} расшифрование может оказаться невозможным. Покажем, что функция расшифрования является обратной к функции шифрования

D ( E ( x ) ) = a − 1 ( E ( x ) − b ) mod m = a − 1 ( ( ( a x + b ) mod m ) − b ) mod m = a − 1 ( a x + b − b ) mod m = a − 1 a x mod m = x mod m . {displaystyle {egin{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}axmod {m}&=&xmod {m}.end{matrix}}}

Количество возможных ключей для аффинного шифра можно записать через функцию Эйлера как φ ( m ) m {displaystyle varphi (m)m} .

Примеры шифрования и расшифрования

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

Шифрование

В этом примере необходимо зашифровать сообщение "ATTACK AT DAWN", используя упомянутое выше соответствие между буквами и числами, и значения a = 3 {displaystyle a=3} , b = 4 {displaystyle b=4} и m = 26 {displaystyle m=26} , так как в используемом алфавите 26 букв. Только на число a {displaystyle a} наложены ограничения, так как оно должно быть взаимно простым с 26. Возможные значения a {displaystyle a} : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25. Значение b {displaystyle b} может быть любым, только если a {displaystyle a} не равно единице, так как это сдвиг шифра. Итак, для нашего примера функция шифрования y = E ( x ) = ( 3 x + 4 ) ( mod 26 ) {displaystyle y=E(x)=(3x+4){pmod {26}}} . Первый шаг шифрования — запись чисел, соответствующих каждой букве сообщения.

Теперь, для каждого значения x {displaystyle x} найдем значение ( 3 x + 4 ) {displaystyle (3x+4)} . После нахождения значения ( 3 x + 4 ) {displaystyle (3x+4)} для каждого символа возьмем остаток от деления ( 3 x + 4 ) {displaystyle (3x+4)} на 26. Следующая таблица показывает первые четыре шага процесса шифрования.

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

Расшифрование

Для расшифрования возьмем шифротекст из примера с шифрованием. Функция расшифрования будет D ( y ) = a − 1 ( y + m − b )  mod  m {displaystyle {mbox{D}}(y)=a^{-1}(y+m-b){mbox{ mod }}m} , где a − 1 = 9 {displaystyle a^{-1}=9} , b = 4 {displaystyle b=4} и m = 26 {displaystyle m=26} .

Замечание: если каждая y ⩾ b {displaystyle ygeqslant b} , то функция расшифрования принимает вид D ( y ) = a − 1 ( y − b )  mod  m {displaystyle {mbox{D}}(y)=a^{-1}(y-b){mbox{ mod }}m} . (Точно так же, как и в обозреваемом примере, но разберём общий вариант)

Для начала запишем численные значения для каждой буквы шифротекста, как показано в таблице ниже.

Теперь для каждого y {displaystyle y} необходимо рассчитать 9 ( y + m − 4 ) {displaystyle 9(y+m-4)} и взять остаток от деления этого числа на 26. Следующая таблица показывает результат этих вычислений.

Последний шаг операции расшифрования для шифротекста — поставить в соответствие числам буквы. Сообщение после расшифрования будет "ATTACKATDAWN". Таблица ниже показывает выполнение последнего шага.


programming language

Криптоанализ

Так как аффинный шифр является по сути моноалфавитным шифром замены, то он обладает всеми уязвимостями этого класса шифров. Шифр Цезаря — это аффинный шифр с a = 1 {displaystyle a=1} , что сводит функцию шифрования к простому линейному сдвигу.

В случае шифрования сообщений на русском языке (т.е. m = 33 {displaystyle m=33} ) существует 297 нетривиальных аффинных шифров, не учитывая 33 тривиальных шифра Цезаря. Это число легко посчитать, зная, что существует всего 20 чисел взаимно простых с 33 и меньших 33 (а это и есть возможные значения a {displaystyle a} ). Каждому значению a {displaystyle a} могут соответствовать 33 разных дополнительных сдвига (значение b {displaystyle b} ); то есть всего существует 20*33 или 660 возможных ключей. Аналогично, для сообщений на английском языке (т.е. m = 26 {displaystyle m=26} ) всего существует 12*26 или 312 возможных ключей. Такое ограниченное количество ключей приводит к тому, что система крайне не криптостойка с точки зрения принципа Керкгоффса.

Основная уязвимость шифра заключается в том, что криптоаналитик может выяснить (путём частотного анализа, полного перебора, угадывания или каким-либо другим способом) соответствие между двумя любыми буквами исходного текста и шифротекста. Тогда ключ может быть найден путём решения системы уравнений. Кроме того, так мы знаем, что a {displaystyle a} и m {displaystyle m} — взаимно простые, это позволяет уменьшить количество проверяемых ключей для полного перебора.

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



Имя:*
E-Mail:
Комментарий: