Архив задач олимпиады по математике и криптографии
Циклический сдвиг, 8-11 класс.
Целое число s ∈ {0,…,30} может быть преобразовано следующим образом. Пусть, например, s = 9. Представим его в двоичной системе счисления пятизначным числом: s = 9 = 010012. Теперь выберем какое-нибудь целое число c ≥ 0 и сдвинем получившуюся строку 01001 циклически на c позиций влево. Например, при c = 1 получится строка 10010, представляющая собой двоичную запись числа 18. Значит, сдвигом на одну позицию из числа 9 получается число 18; будем это записывать так: 9 ⋘ 1 = 18. (Если 01001 сдвинуть влево на две позиции, то получится 00101, то есть 9 ⋘ 2 = 5.) Итак, s ⋘ c – это число, получившееся сдвигом числа s на c позиций влево. Для зашифрования осмысленного слова выбирается секретный ключ – набор из 64 чисел k1,…,k32 ∈ {0,…,30} и c1, … , c32 ∈ {0,1,2,3}. Затем с каждой буквой слова (по отдельности) проделывается следующее. Букву заменяют числом a по таблице и последовательно вычисляют a1 = (a + k1 ) ⋘ c1, a2 = (a1 + k2) ⋘ c2, … , a32 = (a31 + k32 ) ⋘ c32. Исходную букву затем заменяют на букву, соответствующую числу a32. (Если в процессе вычислений получается число, превышающее 30, то оно заменяется остатком от деления на 31. Так, сумму 20 + 17 следует заменить на 6.)
В результате зашифрования получился набор букв ЯГКЫНИ. Найдите исходное слово, если известно, что при зашифровании на этом ключе буква Ъ переходит в букву Ь, а буква П – в Е.
Покажем, что (s ⋘ c) = r31(s ∙ 2c ). Обозначим это равенство через ✱. Заметим, что ✱ достаточно доказать для c = 1. Пусть s = (s4s3s2s1s0)2. Если s4 = 0, то равенство ✱ очевидно. Если s4 = 1, то s = 16 + 23s3 + 22s2 + 2s1 + s0. Тогда r31(s ∙ 2) = 24s3 + 23s2 + 22s1 + 2s0 + 1 = (s ⋘ c), и равенство ✱ доказано. Следовательно,
То есть, на одном шаге шифрования - линейное преобразование числа a происходит по вышеуказанному правилу. Так как композиция линейных преобразований есть линейное преобразование, то a32 = (ax + k), где x и k – неизвестные. Воспользуемся тем, что на этом ключе буква Ъ переходит в букву Ь, а буква П – в Е:
27 = (25x + k), 5 = (14x + k) (mod 31).
Вычитая из первого равенства второе, получим: 22 = 11x. Отсюда x = 2. Тогда 27 = (25 ∙ 2 + k) (mod 31) и, следовательно, k = 8. Окончательно получили: a32 = (2a + 8). Тогда a = 2(-1)(a32 - 8) = 16a32 + 27 (можно было сразу решать уравнение a = (a32x + k)). Последовательно подставляя буквы шифрованного текста ЯГКЫНИ, получим исходное слово МОСКВА.