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

Простая замена с использованием остатков

Для зашифрования слова каждая его буква заменяется на двухзначное число согласно таблице. Затем выбираются секретные ключи K1,K2 – натуральные числа от 1 до 9. С их помощью каждое двузначное число преобразуется так. Пусть A – первая цифра двузначного числа, B – его вторая цифра. Двухзначное число (A,B) преобразуется в число (A1,B1) по формулам A1=B,B1=r10 (A+K1∙B). Здесь r10 (x) – остаток от деления числа x на 10. Затем число (A1,B1) преобразуется в число (A2,B2) по аналогичным формулам, но только вместо ключа K1 используется ключ K2. Далее каждое исходное двузначное число (A,B) было заменено числом (A2,B2 ). В результате получилось вот что: 49 97 32 20 52 77 20 37 85 72. Восстановите исходное слово.

  • Решение

    • Решение

    Если решать задачу перебором, то придется проверить 81 пару ключей (K1,K2 ). Чтобы перебор уменьшить, воспользуемся тем, что цифра A может принимать только значения 0, 1, 2, 3. Для этого выразим A (а заодно и B) через A2,B2,K1,K2. По условию
    {A1=B
    {B1=A+K1∙B)

    {A2=B1
    {B2=A1+K2∙B1. (1)

    (Здесь и далее условимся для краткости вместо r10 (x)=y писать просто x=y, то есть равными для нас будут числа, дающие одинаковый остаток при делении на 10; например, 8=-2.) Отсюда

    A=A2∙(1+K1 K2 )-K1∙ B2, (2)
    B=B2-K2 ∙A 2 (3)
    Поскольку A∈{0,1,2,3}, цифры каждого из чисел 49 97 32 20 52 77 20 37 85 72 удовлетворяют (согласно (2)) одному из следующих четырех равенств:
    [0=A2∙(1+K1 K2 )-K1∙ B2,
    [3=A2∙(1+K1 K2 )-K1∙ B2. (4)
    Подставим в эти равенства цифры числа 20 из шифртекста:
    A2=2,B2=0 ⇒7(1+K1 K2 )∈{0,2} ⇒ 1+K1 K2∈{0,1,5,6}.
    Подставив в соотношения (4) цифры числа 77: 7(1+K1 K2-K1 )∈{0,1,2,3} ⇒
    1+K1 K2-K1∈{0,3,6,9}. (5)
    Аналогично для 52:
    5(1+K1 K2 )-2K1∈{0,1,2,3}. (6)
    Теперь для каждого значения суммы 1+K1 K2, указанного в пункте а), найдем с помощью (5) соответствующее значение K1, а потом для пары 1+K1 K2 и K1 проверим справедливость (6).
    1+K1 K2=0. Из (5) ⇒K1∈{0,1,4,7}. Значения 0 и 4 не годятся, так как произведение K1 K2 сейчас нечетно. Значение 7 не удовлетворяет (6). В итоге нашли одну возможную пару ключей (K1,K2 )=(1,9)∈{(1,9),(7,3),(6,8)}.
    1+K1 K2=1. Из (5) ⇒K1∈{1,2,5,8}. Значения 1 и 5 очевидно не годятся (не выполнится равенство 1+K1 K2=1). Возможные пары ключей (K1,K2 )∈{(2,5),(8,5)}. Пара (8,5) не удовлетворяет (6).
    1+K1 K2=5. Из (5) ⇒K1∈{2,5,6,9}. Значение 5 очевидно не годится (не выполнится равенство 1+K1 K2=5). Возможные пары ключей (K1,K2 )∈{(2,2),(2,7),(9,6),(6,4),(6,9)}. Условию (6) удовлетворяют только пары (2,2) и (2,7).
    1+K1 K2=6. Из (5) ⇒K1∈{0,3,6,7}. Значение 0 и 6 очевидно не годятся (не выполнится равенство 1+K1 K2=6). Оставшиеся возможные пары ключей (K1,K2 )∈{(3,5),(7,5)} обе не удовлетворяют (6).
    Таким образом предстоит рассмотреть следующие три пары ключей (K1,K2 ): (1,9), (2,5), (2,2) и (2,7). Для них по формулам (2), (3) восстановим исходный текст. Осмысленное слово ХОЛЕСТЕРИН получится для пары (2,7).
  • Ответ

    • Ответ

    ХОЛЕСТЕРИН.