Введение в криптографию
[an error occurred while processing this directive]

...К задачам третьей олимпиады - часть 2


Ответ:

С О В Р Е М Е Н Н А Я -
К Р И П Т О Г Р А Ф И Я
Э Т О - Н А У К А - О -
С Е К Р Е Т Н О С Т И -
Ш И Ф Р О В А Л Ь Н Ы Х
С И С Т Е М - С В Я З И

Докажем, что 20 является периодом рассматриваемой последовательности. Заметим, что у двух натуральных чисел и совпадают цифры единиц тогда и только тогда, когда их разность делится на 10. Таким образом, мы достигнем цели, если докажем, что разность делится на 10 для всех натуральных значений . Исходя из того, что делится на , получаем, что

делится на . Кроме того, делится на для всех 1$" width="43" height="28" >. Вместе с тем,

где каждое из слагаемых делится на 2 (так как содержит произведение ) и делится на 5 (поскольку первое слагаемое есть произведение пяти последовательных чисел, а второе содержит множитель 5). Следовательно, делится на 10. Число

делится на 10, так как каждое из слагаемых делится на 10.

Проверим, что 20 является наименьшим периодом. Выписывая первые 20 значений последовательности , , ...

1 4 7 6 5 3 6 9 0 1 6 3 6 5 6 7 4 9 0

легко убедиться, что она не имеет периода меньшей длины.

Для того, чтобы найти исходное сообщение, найдем сначала цифровое сообщение, полученное из него с помощью таблицы замены. Согласно этой таблице на нечетных местах цифрового образа исходного сообщения могут быть только цифры 0, 1, 2 и 3. Последовательно рассматривая эти значения для каждого нечетного места цифрового сообщения с использованием соответствующей цифры шифрованного сообщения, найдем соответствующие варианты значений цифр шифрующего отрезка. Для этого вычислим остатки от деления разностей цифр шифрованного и варианта цифрового сообщений:

порядковый номер места

1 3 5 7 9 11 13 15 17 19 21 23 25 27

шифрованное сообщение

2 3 8 7 1 4 8 6 6 0 1 3 5 8

вариант 0 для

2 3 8 7 1 4 8 6 6 0 1 3 5 8

вариант 1 для

1 2 7 6 0 3 7 5 5 9 0 2 4 7

вариант 2 для

0 1 6 5 9 2 6 4 4 8 9 1 3 6

вариант 3 для

9 0 5 4 8 1 5 3 3 7 8 0 2 5
<


- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]