Архив задач олимпиады по математике и криптографии

Плохое шифрование, 8-11 класс.

Для зашифрования осмысленного слова его буквы заменили числами x1, x2, … ,xn по таблице. 

Затем выбирали четные натуральные числа p и q и для каждого числа xi из соотношений xi = yi + pzi, zi = yi + qxi нашли целые числа yi и zi. Потом по формулам ci = r32(zi ), i = 1, … , n получили числа c1, … ,cn (где r32(a) – остаток от деления числа a на 32), которые вновь заменили буквами согласно таблице. В результате получили вот что: ЖЯЮЦКР. Найдите исходное слово, если известно, что оно начинается на букву В.

  • Решение

    • Решение

    Рассмотрим произвольную букву открытого и шифрованного текстов. Для соответствующих им (по таблице) чисел x и c выполняются равенства x = y + pz и z = y + qx, при некотором y, p и q. При этом по условию c = r32 (z). Используя свойство сравнений по модулю целого числа, получим: x - c = pc - qx (mod 32) или x(1+q)=c(1+p)(mod 32). 
     Для дальнейшего решения будем пользоваться следующим свойством: если наибольший общий делитель чисел a и n равен 1, то сравнение x = y (mod n) равносильно ax = ay (mod n). Используя условие задачи для первой буквы открытого и шифрованного текста, получим равенство 2(1 + q) = 6(1 + p) (mod 32). 
    Заметим, что сравнение 6t = 2 (mod 32) имеет 2 решения по модулю 32: t = 11(mod 32), t = 27 (mod 32). Тогда получим, что 11∙(1 + q) = (1 + p) (mod 32) или 27∙(1 + q) = (1 + p) (mod 32) для каждого t. Таким образом, x = 11c (mod 32) или x = 27c (mod 32) соответственно. Остается воспользоваться полученными соотношениями для остальных букв. Осмысленное слово получается только при втором варианте. А значит, исходное слово ВЕКТОР.
  • Ответ

    • Ответ

    ВЕКТОР.