Афинная подстановка биграмм

Люди, кто разбирается, попробуйте помочь, пожалуйста!
Афинная подстановка биграмм являет собой такое криптографическое превращение. Открыт текст (ВТ) х1, х2 . разбивается на биграммы, которые непересекающиеся (x1,x2)(x3,x4). Пусть m - количество букв в алфавите. Занумеруем буквы алфавита числами от 0 к m-1. Тогда каждой биграмме ( хи,xi+1 ) можно единственным чином сопоставить число Xi в границях от 0 к m2-1:
(хи,xi+1)=Xi=xi m+ xi+1.
Например, биграмме (в, бы)=(2,1) отвечает число 2*31 + 1 = 63, если m=31.
Биграммы шифруются независимо по такому правилу. Пусть Xi =(хи,xi+1) - биграмма ВТ, а Yi=(yi,yi+1) - соответствующая биграмма шифрованного текста (ШТ). Тогда
Yi=axi + b (mod m2)
где 0 < а Ј m2-1 -число, взаимно простое из m, 0 Ј b Ј m2-1 - произвольное число в указанных границях. Таким образом, ключ шифра афинной подстановки состоит из пары чисел но и b. Афинная подстановка при атаке, которая базируется только на знании ШТ, раскрывается с помощью частотного анализа. А именно, обозначим через X* биграмму, которая чаще всего встречается в языке, X**- следующую за ней относительно частоты и так далее, Y*,y**.- биграммы ШТ, которые расположены в порядке спадения частот. Если допустить, что биграмма X* шифруется как Y*, а X** - как Y**, то для неизвестных параметров ключа а, b можно составить систему уравнений:
Y*=ax* + b (mod m2)
Y**=ax** + b (mod m2) (1)
откуда
Y* - Y** =a(X* - X**) (mod m2) (2)
- уравнение для определения параметра а.
Если X* - X** взаимно простое из m2, то уравнение (2) имеет единственное решение
а = (X* - X**)-1(Y* - Y**) mod (m2). (3)
Если НСД(X* - X**,m2)=d, то при Y* - Y**, что не делится на d, уравнение (2) не имеет решения, а при Y* - Y**, что делится на d, имеет d решений:
a1, a1+m2/d, a1 +2m2/d,., a1+(d-1)m2/d, где a1 - решение уравнения
(Y*-y**)/d = a1 (X*-x**)/d (mod m2/d).
Если а найдено, то из (1) b = Y* - ax* (mod m2).
Дешифрация при известных но и b выполняется за формулой
Xi = a-1(Yi - b) (mod m2) (4)
Предположение о том, что Х* и Х** шифруются соответственно в У* и У**, может оказаться ошибочным. Тогда нужно подставить в (1) другие пары Х и В из числа наиболее вероятных в языке и самых частых в ШТ, например, Х*«у**, Х**«у* и так далее до тех пор, пока при дешифрации не выйдет содержательный текст.
Замечание. Для того, чтобы пользоваться формулами (3),(4) нужно уметь находить обратный элемент а-1 (mоd т), который существует только при а взаимно простому из т. Это делается с помощью алгоритма Евклида. Пусть 0<а<т взаимно простое из т. Тогда существуют такие целые числа к, s, что ka+sm = 1, то есть ка = 1 (mod m).таким чином, к = a-1 (mod m).
Пример. Найти 152-1 (mоd 1089). Применим алгоритм Евклида для нахождения НСД (152, 1089):
1089 = 7 * 152 + 25;
152 = 6 * 25 + 2;
25 = 12 * 2 + 1;
НСД (152, 1089) = 1.
Используя эту последовательность ривностей в зворотнему порядке, представляем 1 в виде к 152 + s 1089 :
1 = 25 - 12 * 2 = 25 - 12( 152 - 6 * 25) = -12 * 152 + 73 * 25 = -12 * 152 + 73 ( 1089 - 7 * 152) = - 523 * 152 + 73 * 1089.
Заметим, что -523 = 566 (mod 1089), таким образом,
152-1 = 566 (mod 1089).
Порядок и рекомендации относительно выполнения работы:
предоставляется текст, который является результатом шифровки с помощью афинной подстановки биграмм ВТ, написанного русским языком без пробилив, знаков пунктуации и больших букв. Буква е замещена буквой е, а ъ - буквой ь. Таким образом, алфавит ВТ состоит из 31 буквы, что занумерованные в алфавитном порядке : а = 0, бы = 1 ., я = 30. Следовательно, модуль в уравнениях (1) - (4) т2 = 961. Для дешифрувания ШТ нужно определить биграммы ШТ, которые встречаются чаще всего, и, подбирая пары с наиболее частыми биграммами русского языка, найти параметры а и b, как указано выше. Пятью самыми частыми биграммами русского языка (в порядке спадения частот) является:
ст, но, то, на, ен.
Порядок выполнения работы таков:
1) Выполнить программу вычисления частот биграмм, найти 5 самых частых биграмм Шт.
2) Написать программу определения а-1 (mоd т) для (а, т) = 1, т = 961.
3) Выбрать две пары биграмм Х«у из пяти самых частых в языке и в Шт. Составить для них систему уравнений (1).
4) Решить систему уравнений (1). При этом, если уравнение (2) не имеет решений, сразу переходить к следующим парам биграмм. Если решение (2) единственное, то проверить, будет ли он взаимно простым с модулем 961, не взаимно простые из 961 развязки отбрасывать и переходить к следующим парам биграмм. Если решение (2) не единственное, то найти все развязки, что взаимно простые с 961.
5) Для найденного решения (решений) системы (1) дешифровать ШТ, используя формулу (4).
6) Повторять действия 3 - 5, пока дешифрованный текст не будет содержательным.