Задачи дня КБ 2009 г.

Задача 1.

Криптограмма

 

12 2 24 5 3 21 6 29 28 2 20 18 20 21 5 10 27 17 2 11 2 16 –

19 2 27 5 8 29 12 31 22 2 16, 19 2 19 5 17 29 8 29 6 29 16:

8 2 19 19 29 10 19 29 14 19 29 29 19 10 2 24 2 11 2 16

10 14 18 21 17 2 20 2 28 29 16 21 29 28 6 29 16.

получена заменой букв на числа (от 1 до 32) так, что разным буквам соответствуют разные числа. Отдельные слова разделены несколькими пробелами, буквы – одним пробелом, знаки препинания сохранены. Буквы «е» и «ё» не различаются. Прочтите четверостишие В. Высоцкого.

 

Решение.

Один из вариантов решения состоит из следующих этапов.

1. 19=н из второй строки («19,2 19,5»).

2. 29=о из третьей строки («29,н,10») и 10=а или 10=и.

3. 14=щ из «но,14,но».

4. 8=д, 2=е, 10=и из «денно и нощно».

Получили текст:

12 е 24 5 3 21 6 о 28 е 20 18 20 21 5 и 27 17 е 11 е 16

н е 27 5 д о 12 31 22 е 16, н е н 5 17 о д о 6 о 16:

д е н н о и н о щ н о о н и е 24 е 11 е 16

и щ 18 21 17 е 20 е 28 о 16 21 о 28 6 о 16.

5. 5=а и 27=з из второй строки.

 

6. 17=в 6=п 16=й – последнее слово второй строки – водопой.

Получили текст:

12 е 24 а 3 21 п о 28 е 20 18 20 21 а и з в е 11 е й

н е з а д о 12 31 22 е й, н е н а в о д о п о й:

д е н н о и н о щ н о о н и е 24 е 11 е й

и щ 18 21 в е 20 е 28 о й 21 о 28 п о й.

7. 21=т 18=у 28=л 20=с из последней строки «ищут веселой толпой».

8. 11=р из «з в е 11 е й» первой строки.

Итак,

12 е 24 а 3 т п о л е с у с т а и з в е р е й

н е з а д о 12 31 22 е й, н е н а в о д о п о й:

д е н н о и н о щ н о о н и е 24 е р е й

и щ у т в е с е л о й т о л п о й.

9. 24=г из «егерей».

10. 12=б 3=ю из «бегают».

11. 31=ы 22=ч из «добычей».

Ответ:

Бегают по лесу стаи зверей

Не за добычей, не на водопой:

Денно и нощно они егерей

Ищут веселой толпой.

 

Задача 2.

При передаче сообщений используется некоторый шифр. Пусть известно, что каждому из трех шифрованных текстов

ЙМЫВОТСЬЛКЪГВЦАЯЯ

УКМАПОЧСРКЩВЗАХ

ШМФЭОГЧСЙЪКФЬВЫЕАКК

соответствовало исходное сообщение МОСКВА. Попробуйте расшифровать три текста

ТПЕОИРВНТМОЛАРГЕИАНВИЛЕДНМТААГТДЬТКУБЧКГЕИШНЕИАЯРЯ

ЛСИЕМГОРТКРОМИТВАВКНОПКРАСЕОГНАЬЕП

РТПАИОМВСВТИЕОБПРОЕННИГЬКЕЕАМТАЛВТДЬСОУМЧШСЕОНШЬИАЯК

при условии, что двум из них соответствует одно и то же сообщение. Сообщениями являются известные крылатые фразы.

 

Решение.

Можно заметить, что последовательность букв МОСКВА входит как подпоследовательность в каждый из шифртекстов первой тройки:

й МывОт СьлКъгВц Аяя

укМапОч Ср Кщ Вз Ах

ш МфэОгчСйъКфьВыеАкк

На основе этого наблюдения можно предположить, что шифрование заключается в следующем. В каждый промежуток между буквами исходного сообщения (начало и конец также считаются промежутками) вставляются одна либо две буквы в соответствии с известным только отправителю и получателю ключом.

Очевидно, что первая буква сообщения должна попасть на 2-е или 3-е место шифрованного текста. Сравнивая буквы, стоящие на указанных местах в подлежащих расшифрованию криптограммах, делаем вывод, что одно и то же исходное сообщение соответствует первому и третьему шифртексту и что первая буква этого сообщения – П.

Рассуждая далее аналогичным образом, заключаем, что второй буквой повторяющегося сообщения является О (сопоставили ОИ из 1-й криптограммы и ИО из 3-й) и так далее. В итоге получим, что первой итретьей криптограмме соответствует исходное сообщение

ПОВТОРЕНИЕМАТЬУЧЕНИЯ

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

СЕ, СМ, ИМ, ИГ

СЕГ, сео, СМО, СМР, ИМО, ИМР, ИГР, игт

сегр, сегт, СМОТ, СМОК, смрк, смрр, ИМОТ, ИМОК,

имрк, имрр, игрк, игрр

СМОТР, СМОТО, СМОКО, смокм, ИМОТР, ИМОТО, ИМОКО, имокм

СМОТРМ, СМОТРИ,

смотои, смотот, смокои, смокот, имотрм, имотри,

имотои, имотот, имокои, имокот

СМОТРИВ, СМОТРИА

СМОТРИВВ, СМОТРИВК, СМОТРИАК, СМОТРИАН и так далее.

В итоге получим исходное сообщение СМОТРИВКОРЕНЬ.

 

Задача 3.

Знаменитый математик Леонард Эйлер в 1759 г. нашел замкнутый маршрут обхода всех клеток шахматной доски ходом коня ровно по одному разу. Прочтите текст, вписанный в клетки шахматной доски по такому маршруту (см. рис.). Начало текста в a4.

66.png

Решение.

Алгоритм обхода показан на рисунке:

77.png

Ответ:

Кавалергардов век недолог

И потому так сладок он.

Труба трубит, откинут полог. . .

Задача 4

 

Задача:

Для зашифрования фразы был взят кубик Рубика с нанесенными на гранях русскими буквами. Развертка кубика показана на рис. 1. Затем грани последовательно повернули по часовой стрелке на 90° определенное число раз: грань 1 – шесть раз; грань 2 – три раза; грань 3 – один раз; грань 4 – четыре; грань 5 – два и, наконец, грань 6 – пять раз. Затем каждая буква фразы отыскивалась на грани кубика и заменялась буквой этой же грани, следующей за ней по часовой стрелке (например, на рис. 1 буква A переходит в букву Б, буква П в С). Буквы, находящиеся в центре грани, не заменяются. В результате получилась строка:

ОЕХДМАПРМКПДОПИМ

Прочтите исходное сообщение88.png.

 

Решение:

 

Заметим, четырёхкратный поворот грани ничего не изменяет, а трёхкратный поворот по часовой стрелке эквивалентен одному повороту против часовой стрелки. Таким образом, чтобы узнать, как были расположены буквы при шифровании, необходимо повернуть грань 1 – два раза; грань 2 – один раз (против часовой стрелки); грань 3 – один раз; грань 4 – не поворачивать; грань 5 – два и, наконец, грань 6 – один раз. После этого, исходя из расположения букв на полученном кубике, можно найти исходное сообщение, заменяя буквы шифртекста на буквы, стоящие в клетках против часовой стрелки. Отметим, что нет необходимости узнавать, куда перешли все написанные на кубе буквы. Достаточно узнать расположение букв шифртекста после описанных преобразований. После этого следует выделить клетку, следующую против часовой стрелки за клеткой с рассматриваемой буквой шифртекста. Затем необходимо осуществить обратное преобразование, и в выделенной клетке на исходном кубе окажется соответствующая буква открытого текста.

Ответ: Джероламо Кардан

 


Задача 5

Шифр Bifid, имеющий простое правило зашифрования, использует в качестве ключа квадратную таблицу, в которую в некотором порядке записаны буквы английского алфавита (буквы I и J отождествлены). Результатом зашифрования фразы SIXTY EIGHT MILES на приведенном ключе является «фраза» RYXXT OFTXT LKSWS. Зашифруйте на том же ключе фразу ENTER OTHER LEVEL.

C

O

D

E

A

B

F

G

H

I

K

L

M

N

P

Q

R

S

T

U

V

W

X

Y

Z

Решение:

Ключом шифра служит систематически перемешанный алфавит, записанный в квадратную таблицу. Такие алфавиты широко использовались в криптографии. Первые буквы алфавита составляли легко запоминаемое ключевое слово (в условии данной задачи это слово CODE), остальные же буквы следовали в их естественном порядке. Такое мнемоническое правило позволяло быстро восстановить ключ и произвести зашифрование или расшифрование.

1

2

3

4

5

1

C

O

D

E

A

2

B

F

G

H

I

3

K

L

M

N

P

4

Q

R

S

T

U

5

V

W

X

Y

Z

Правило зашифрования шифра Bifid состоит в следующем. Строки и столбцы квадратной таблицы пронумеруем числами от 1 до 5, как показано на рисунке. Теперь каждая буква алфавита имеет свой номер, состоящий из пары чисел (i, j), где i - номер строки, а j - номер столбца. Например, буква S имеет номер (4, 3). Выпишем буквы открытого текста в строку, разделяя пробелом каждую пятерку букв, а под ней - номера соответствующих букв. Фраза, взятая из условия задачи, запишется в виде

S

I

X

T

Y

E

I

G

H

T

M

I

L

E

S

4

2

5

4

5

1

2

2

2

4

3

2

3

1

4

3

5

3

4

4

4

5

3

4

4

3

5

2

4

3

Затем заменим номера букв. Для этого выпишем две строчки из пяти цифр под каждой пятеркой в одну строку из десяти цифр. Например, для второй пятерки получается строка 1222445344. В получившейся строке каждая последовательная пара цифр и будет новыми номерами букв пятерки, которые выпишем под соответствующими буквами. Так, для букв второй пятерки получаем новые номера:

E

I

G

H

T

1

2

4

5

4

2

2

4

3

4

O

F

T

X

T

Наконец, заменяем буквы открытого текста буквами, номера которых в квадратной таблице указаны теперь под соответствующими буквами. В результате этой замены получаем шифрованный текст. Например, пятерка EIGHT будет зашифрована в пятерку OFTXT.

Зашифруем на том же ключе фразу ENTER OTHER LEVEL, заполнив следующую таблицу:

E

N

T

E

R

O

T

H

E

R

L

E

V

E

L

1

3

4

1

4

1

4

2

1

4

3

1

5

1

3

4

4

4

4

2

2

4

4

4

2

2

4

1

4

2

1

4

4

4

4

1

2

4

4

4

3

5

3

4

4

3

1

4

4

2

4

1

2

4

2

1

1

2

1

2

D

Q

T

T

R

E

B

R

T

T

K

V

L

Q

R

Глоссарий.

 

1. Шифр подстановки – шифр, который каждый символ открытого текста заменяет на некоторый другой.

· Шифр простой замены (одноалфавитный шифр) span class="apple-style-span">— шифр, при котором каждый символ открытого текста заменяется на некоторый, фиксированный при данном ключе символ того же алфавита (пример — шифр Цезаря).

· Многоалфавитный шифр подстановки состоит из нескольких шифров простой замены (шифр Виженера, одноразовый блокнот, шифр Гронсфельда, машина Enigma).

Для вскрытия подобных шифров используется частотный криптоанализ.

2. Шифр Хилла – шифр подстановки, который позволял на практике оперировать более чем с тремя символами за раз. В шифре выбирается числовое кодирование всех символов некоторого алфавита. Ключом является квадратная матрица из тех же самых чисел некоторого размера n, обратимая над кольцом вычетов ZN (N - размер алфавита). В шифруемом тексте символы заменяются их числовыми эквивалентами , и записываются построчно в матрицу из n строчек. Криптограмма получается умножением матрицы-ключа на матрицу сообщения. Обратное преобразование осуществляется с помощью обратной к ключу матрицы.

3. Шифр Виженера текст шифруется ключевым словом, длинна которого является периодом шифра. Шифрование происходит по формуле ei = mi + ki(mod 26) , где ei - i-й символ криптограммы, mi - i-й символ шифруемого текста, ki - i mod D символ ключа.

4. Одноразовый блокнот (Шифр Вернама) - единственный известный абсолютно секретный шифр. Он основан на том, что сообщение кодируется побитовым xor с одноразовым ключом, длина которого не меньше длины передаваемого сообщения.

Ek(x1)= x1+k (mod 2). Dk(x1)= (x1+k+k) mod 2 = x1.

Шифр назван в честь телеграфиста Гильберта Вернама, который сконструировал телеграфный аппарат, автоматически кодирующий сообщения таким методом (ключ подавался на отдельной ленте).

5. Шифр перестановки /b>подразумевает разбиение исходного текста на блоки по n символов и использование для каждого такого блока некоторой перестановки E. Ключом такого шифра является используемая при шифровании матрица P или вектор t, указывающий правило перестановки. Таким образом, общее число возможных ключей определяется длиной блока n и равно n!.

6. Латинский квадрат — таблица n × n, заполненная n различными символами таким образом, чтобы в каждой строке и в каждом столбце встречались все n символов (каждый по одному разу).