Зашифруйте сообщения

[Hi4ko]

Задание №7, олимпиада "Ломоносов" по информатике, очный тур. Я сам не участвовал, т.к. не захотел поехать в Москву.

Задача 7. В результате оперативных мероприятий контрразведчиками
были перехвачены части шифровок, переданных агентом 007. Установлено,
что незашифрованное сообщение состоит из четного количества десятичных
цифр. Для некоторых незашифрованных сообщений известны соответствую-
щие им шифрованные сообщения. Они приведены в таблице.

Незашифрованное сообщение Зашифрованное сообщение
146077 73442104634623446106
292651 61062346231621542344
639208 23462314311621043354
418035 21143344730433443114
200871 71442304714461546144

Зашифруйте сообщения
703109 394775

Ответы:
703109 23466114210671566104
394775 31542316614421142346

Меня интересует, как такое решается. Все мои идеи были неправильными

[e2e4]

Задача из разряда "продолжите последовательность". В мусор ее.

[wallflower]

e2e4
Не, тут интересней. Степени свободы меньше.

Hi4ko
Видно, что зашифрованное сообщение состоит из последовательных четвёрок.

146077  73 44  21 04  63 46  23 44  61 06
292651  61 06  23 46  23 16  21 54  23 44
639208  23 46  23 14  31 16  21 04  33 54
418035  21 14  33 44  73 04  33 44  31 14
200871  71 44  23 04  71 44  61 54  61 44
703109  23 46  61 14  21 06  71 56  61 04
394775  31 54  23 16  61 44  21 14  23 46

Причём, не все цифры допускаются:

1 цифра: 2, 3, 6, 7
2 цифра: 1, 3
3 цифра: 0, 1, 4, 5
4 цифра: 4, 6.

Имеется 64 варианта четверок, то есть, возможно, каждая из них просто кодирует 6 бит. Далее, поскольку по условию входное число имеет чётную длину, то, вероятно, кодируется парами (блочный шифр). Плюс некоторая избыточность, для усложнения.

(Оффтоп)

Ещё смотрим: 292651 и 200871 начинаются на одну цифру, а последняя пара шифра -- 44. 394775 и 292651 имеют одинаковую вторую цифру, а предпоследняя пара у них -- 23. Вроде бы и 200871 с 703109 подходят, но -- предпоследнюю пару 61 имеет также 146077. Поэтому может совпало просто.

Может всё проще, а меня унесло. В любом случае задачка весьма интересна.

[Shadow]

Шифр 6-значного числа представляет 20-ти значное, очевидно восьмичное число. По 3 бита - 60 битов на 6 цифр. Запишем шифры в двоичном виде:

111011100100010001000100110011100110010011100100110001000110
110001000110010011100110010011001110010001101100010011100100
010011100110010011001100011001001110010001000100011011101100
010001001100011011100100111011000100011011100100011001001100
111001100100010011000100111001100100110001101100110001100100

Видно что любой второй бит - лишний, они все одинаковые и чередуются. Уберем их, останутся 30 бита для 6 цифр. Так как цифры по условие идут парами, положим по 10 битов на пару

14 60 77    1111000000   0010110100   1100100001
29 26 51    1000010011   0100101100   0110001100
63 92 08    0011010010   1001001100   0000011110
41 80 35    0000100111   0011100001   1100010010
20 08 71    1101000010   0011010010   0110100100

08 Присуствует 2 раза (3-е и 5-ое число) и шифруется 0011010010. Что означает, что числа шифруются в обратном порядке. Т.е первое число надо записать как 770641 и т.д
В любой декаде ровно по 4 единиц и 6 нулей. Если посмотреть на них через разряд (1,3,5,7,9 и 2,4,6,8,10), увидим, что в этих пятерок ровно по 2 единиц и 3 нулей и это хорошо, потому что $C_5^2=10$ - как раз число цифр в 10-ичной системе. Разделим их

77 06 41  11000 11000   01100 00110   10100 10001
15 62 92  10001 00101   00110 10010   01010 10010
80 29 36  01001 01100   10010 01010   00011 00110
53 08 14  00101 00011   01100 01001   10001 10100
17 80 02  10001 11000   01001 01100   01100 10010

Тут уже все ясно, можно написать как шифруется каждая цифра:

0   01100
1   10001
2   10010
3   00011
4   10100
5   00101
6   00110
7   11000
8   01001
9   01010

[wallflower]

Shadow

[Hi4ko]

Shadow в сообщении #550276 писал(а):

Шифр 6-значного числа представляет 20-ти значное, очевидно восьмичное число. По 3 бита - 60 битов на 6 цифр. Запишем шифры в двоичном виде:

111011100100010001000100110011100110010011100100110001000110
110001000110010011100110010011001110010001101100010011100100
010011100110010011001100011001001110010001000100011011101100
010001001100011011100100111011000100011011100100011001001100
111001100100010011000100111001100100110001101100110001100100

Видно что любой второй бит - лишний, они все одинаковые и чередуются. Уберем их, останутся 30 бита для 6 цифр. Так как цифры по условие идут парами, положим по 10 битов на пару

14 60 77    1111000000   0010110100   1100100001
29 26 51    1000010011   0100101100   0110001100
63 92 08    0011010010   1001001100   0000011110
41 80 35    0000100111   0011100001   1100010010
20 08 71    1101000010   0011010010   0110100100

08 Присуствует 2 раза (3-е и 5-ое число) и шифруется 0011010010. Что означает, что числа шифруются в обратном порядке. Т.е первое число надо записать как 770641 и т.д
В любой декаде ровно по 4 единиц и 6 нулей. Если посмотреть на них через разряд (1,3,5,7,9 и 2,4,6,8,10), увидим, что в этих пятерок ровно по 2 единиц и 3 нулей и это хорошо, потому что $C_5^2=10$ - как раз число цифр в 10-ичной системе. Разделим их

77 06 41  11000 11000   01100 00110   10100 10001
15 62 92  10001 00101   00110 10010   01010 10010
80 29 36  01001 01100   10010 01010   00011 00110
53 08 14  00101 00011   01100 01001   10001 10100
17 80 02  10001 11000   01001 01100   01100 10010

Тут уже все ясно, можно написать как шифруется каждая цифра:

0   01100
1   10001
2   10010
3   00011
4   10100
5   00101
6   00110
7   11000
8   01001
9   01010

Это гениально )