Аффинная система подстановок Цезаря и шифр Цезаря

1. Алгоритм системы подстановок Цезаря + примеры

Пусть есть некий алфавит из N символов, нумерация символов ведётся с нуля (это раздражает, но так уж придумано). Так, для английского алфавита N = 26, номер символа 'a' - 0, 'c' - 2, 'z' - 25.

Имеются некие параметры A, K - целые числа, лежащие в промежутке [0, N-1]. Эти параметры образуют ключ аффинной системы подстановок Цезаря. При этом A и N - взаимно простые числа. Для особо непонятливых: взаимно простые - это числа, которые одновременно делятся только на 1, нельзя найти другого числа, на которое они бы оба делились нацело.

Предположим, некоторый символ из строки открытого текста имеет номер X в заданном алфавите. Тогда он отображается в символ номер (AX + K) mod N.

Приведём пример работы аффинной системы подстановок Цезаря. Пусть A = 3, K = 2, алфавит английский. Тогда слово bug отображается в fku. Например, 'u' идёт под номером 20, (20*3+2) mod 26 = 10, то есть в шифрованном тексте это будет 'k'.

Зачем A и N должны быть взаимно простыми? Если это условие нарушено, будет ситуация, когда разные символы открытого текста отображаются в один и тот же символ шифрованного. Ясно, что расшифрование полученного текста может быть неоднозначным. Допустим, A = 2, K = 3. Тогда результат применения преобразования (2X + 3) mod 26 будет одинаков для символов, которые отстоят в алфавите друг от друга на 13 позиций.

На число K правила аффинной системы подстановок Цезаря не накладывают особых ограничений. Разве что нельзя брать K = 0, если A = 1. В остальных случаях и при K = 0 аффинная система подстановок Цезаря работает нормально, если только A выбрать правильно.

Кстати говоря, так называемый шифр Цезаря, где каждый символ открытого текста сдвигается на фиксированное число позиций, есть частный случай аффинной системы подстановок Цезаря. Подставляем A = 1 и убеждаемся в этом. Очевидно, что шифр Цезаря малонадёжен: если в алфавите N символов, по сути есть N-1 вариантов ключей. Формула шифра Цезаря: вместо символа номер X берём символ (X + K) mod N, где N - количество символов алфавита, K - ключ шифра Цезаря.

2. Взлом системы подстановок Цезаря

Определим, сколько может быть придумано ключей (A, K), если в алфавите N символов. Аффинная система подстановок Цезаря предполагает, что A и N - не имеют общих делителей, ну разве что единицу (то есть взаимно простые), на K никаких ограничений нет. Вот так вот - одним всё можно, другим запреты, впрочем ... разве Цезарь был демократом?

Пусть f(N) - количество таких чисел среди 1,2,...,N-1, которые не имеют с N общих делителей, кроме единички. Тогда выходит, что численцио A можно выбрать f(N) способами, а K - не иначе, как N способами. При этом если A = 1 и K = 0, то (AX + K) mod N = X, то есть мы ничего не шифруем по сути. Итог: можно выдумать N * f(N) - 1 ключей.

Итак, теперь у нас есть формула. Давайте подумаем, N * f(N) - 1 - много или мало? Допустим, закинули в алфавит маленькие буквы, большие, цифры, знаки препинания, ещё какую-нибудь чушь и получили 100 символов. Если число оканчивается на 1, 3, 7, 9, то оно имеет с соткой только один общий делитель - единицу. Так что f(100) = 4 * 10 = 40. Можем поспорить на пиво, что посчитано верно. Считаем дальше 100 * f(100) = 100 * 40 = 4000. Много ли это? Если, допустим, на проверку каждого варианта мы тратим 5 минут, то на все - 20000 минут, то есть по сути 2 недели. Но поскольку мы ещё должны поесть, поспать, попить пивка и т.д., то на самом деле как минимум месяц. Или даже больше. То есть когда-то взломщику пришлось бы сильно помучиться. Это, правда, про худший случай речь шла. В среднем время будет вдвое меньше, но и это не особо радует.

Но сейчас-то только ПОЛНЫЙ LOSER будет перебирать вручную. А для компа 4000 вариантов - да так, мелочи. Так что сейчас аффинная система подстановок Цезаря суть воспоминания о прошлом и 1-2 часа студенческих страданий. А шифр Цезаря - так и того меньше.