Образовательный материал

Федеральное агентство по образованию
Сибирский государственный аэрокосмический университет
имени академика М. Ф. Решетнева







криптография

Сборник задач краевых олимпиад 2007–2008 гг.
с решениями и комментариями





















Красноярск 2009




УДК 004.056
ББК 32.973
К00

Рецензенты:
доктор физико-математических наук, профессор М. Н. Носков (Сибирский федеральный университет);
кандидат технических наук, доцент В. Н. Тяпкин
(Сибирский государственный аэрокосмический университет
имени академика М. Ф. Решетнева)






К00 Криптография : сб. задач краевых олимпиад 2007–2008 гг. с решениями и комментариями / О. Н. Жданов, В. В. Золотарев, А. М. Попов, В. Х. Ханов и др. ; под общ. ред. О. Н. Жданова. – Сиб. гос. аэрокосмич. ун-т. – Красноярск, 2009. – 64 с.

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

УДК 004.056
ББК 32.973





© Сибирский государственный аэрокосмический
университет имени академика М. Ф. Решетнева, 2009

Оглавление


Предисловие
1. Первая краевая олимпиада по криптографии для школьников (Красноярск, 2007)
2. Вторая краевая олимпиада по криптографии для школьников (Красноярск, 2008)
3. Обзор некоторых основных понятий криптографии
Библиографический список





























Предисловие

Криптография – наука о методах преобразования информации с целью ее защиты от несанкционированного доступа. Развитием этих методов занимались лучшие умы человечества и, прежде всего, математики. Несколько тысячелетий криптография развивалась как искусство, было больше случайных находок, нежели результатов глубоких исследований. В середине двадцатого столетия появились фундаментальные работы К. Шеннона по теории информации, работы других ученых. И криптография стала в гораздо большей степени опираться на научные методы.
Связи между математикой и криптографией давние и глубокие. Современная криптография использует тонкие методы абстрактной алгебры, теории чисел, теории вероятностей.
В настоящее время во многих вузах читаются курсы криптографической защиты информации. Для школьников появились факультативные курсы, в которых в доступной форме излагаются основные понятия и иллюстрируются методы криптографии.
С 1991 г. Институт криптографии, связи и информатики Академии ФСБ России проводит ежегодные олимпиады по криптографии и математике для школьников. Эти олимпиады вызывают достаточно большой интерес у старшеклассников. В 2007 г. по инициативе ряда преподавателей Сибирского государственного аэрокосмического университета состоялась первая олимпиада по криптографии для школьников Красноярского края. Олимпиада эта несколько отличается от обычных, традиционных олимпиад по математике. Школьники, принявшие участие в олимпиаде, увидели другую часть математики, отличную от той, которая входит в обязательную школьную программу. Проявленный старшеклассниками интерес убедил организаторов первой олимпиады в полезности этого начинания. И олимпиада Красноярского края по криптографии стала традиционной.
В данном сборнике представлены условия задач прошедших олимпиад (2007 и 2008 гг.) с решениями и комментариями, приведены ссылки на использованную литературу. Составители заданий олимпиад пользовались богатым опытом коллег, добавив и свои находки. Сборник может быть полезен при подготовке к олимпиадам по математике и к олимпиадам по криптографии, ставшими в крае уже традиционными.
Важно заметить: для решения задач никаких специальных знаний не требуется. Вместе с тем, в плане психологическом, знакомство с некоторыми понятиями криптографии будет полезным, да и расширение кругозора не помешает, поэтому вдумчивый читатель найдет здесь обзор основных понятий криптографии.
Составители сборника надеются, что данное издание поможет школьникам старших классов в формировании правильного представления о задачах, решаемых специалистами по защите информации и о методах их работы. Заинтересовавшимся мы можем посоветовать продолжить изучение этого круга вопросов по литературе, приведенной в библиографическом списке.
В подготовке заданий первой олимпиады принимали участие преподаватели СибГАУ О. Н. Жданов, М. Н. Жукова, В. В. Золотарев, А. М. Попов, В. Х. Ханов.
В подготовке заданий второй олимпиады.приняли участие О. Н. Жданов, А. М. Кукарцев, А. Б. Меркулов, А. М. Попов, В. Х. Ханов, Т. А .Чалкин.
Обзор основных понятий криптографии составили О. Н. Жданов, И. А. Куденкова, И. А. Лубкин, Т. А. Чалкин.



















1. Первая краевая олимпиада
по криптографии для школьников
(Красноярск, 2007)

В 2007 г. олимпиада по криптографии проводилась в один тур для учащихся 11-х классов. Были составлены два варианта заданий. Задачи 1.1, 1.3, 1.5, 1.7, 1.9 – первый вариант; однотипные им 1.2, 1.4, 1.6, 1.8, 1.10 – второй вариант. В зависимости от сложности задач, их решение оценивалось разным количеством баллов.

Условия задач

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

Текст 1
11 25 28 33 35 42 47 53 69 72 83 11 19 22 17 31 47 39 45 17 11 57
83 91 19 11 59 62 53 45 11 51 11 65 25 25 28 11 83 91 51
45 11 19 25 33 62 35 69 72 83 19 25 65 51 83 91 11

Текст 2
97
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Перед вами два зашифрованных текста. Открытые тексты состоят только из русских букв. Шифрование заключалось в замене каждой буквы открытого текста двузначным числом. Разным буквам соответствуют разные числа, различия между строчной и прописной буквами не делалось, знаки препинания опущены.
Про какой из двух текстов сразу можно сказать, что он зашифрован с ошибками?

Текст 1
11 95 28 25 29 18 31 42 51 11 18 37 62 95 76 18 53 31
45 69 11 73 25 18 42 11 81 91 28 13 15 57 84 11 33 46 25
67 11 48 58 88 93 18 25 11 31 25 29 18 91 57 45 53 62
37 18 29 67 73 67 11 25 18 11 29 31 62 31 37

Текст 2
25 93 18 31 48 33 15 84 17 37 45 42 29 11 53 51 73 57 69 62 11
15 17 18 76 81 88 91 17 13 95 19 67 28 46 17 58 19 58 11
23 18 23 76 81 61 99 88 25 11 44 19 23 17 18 11 51 42 51
37 93 18 23 61 44 88 61 81 11

1.3. Используется русский алфавит (33 буквы) с добавленным символом пробела. Каждому символу присвоен номер: А = 1, Б = 2, , Я = 33, пробел = 34. Шифрование заключалось в следующем: к порядковому номеру каждой буквы прибавлялось значение многочлена f(x) = x5 – 2x4 – 20x3 + 26x2 +51x – 53, вычисленное либо при x1, либо при x2, либо при x3, либо при x4, где x1, x2 – корни уравнения x2 + 2x – 7 = 0, а x3, x4 – корни уравнения x2 – 3x – 8 = 0. Затем полученное число заменялось соответствующей ему буквой.
Расшифруйте сообщение : Ц Ъ Л Ф Я В Р Г В Ч Л Ф Ц

1.4. Известно, что используется русский алфавит (33 буквы) с добавленным символом пробела. Каждому символу присвоен номер: А = , Б = 2, , Я = 33, пробел = 34. Шифрование заключалось в следующем: пусть x1, x2 – корни уравнения x2 + x – 5 = 0, а x3, x4 – корни уравнения x2 + 2x – 7 = 0. К порядковому номеру символа открытого текста прибавлялось значение многочлена f(x) = x5 – 19x3 + 13x2 + 86x – 136, вычисленное либо при x1, либо при x2, либо при x3, либо при x4, а затем полученное число заменялось соответствующей ему буквой.
Найдите открытый текст: Т С Ф Х Ц Т Г М В Р Г В Ч Л Ф Ц

1.5. В этом задании каждая буква и каждая звездочка обозначают цифры от 0 до 9, Ф ( 0. Различные буквы обозначают различные цифры, звездочка может обозначать любую цифру.
Замените буквы и звездочки цифрами:
ФИСУ(ФИСУ=****ФИСУ

1.6. В этом задании каждая буква и каждая звездочка обозначают цифры от 0 до 9, Ф ( 0. Различные буквы обозначают различные цифры, звездочка может обозначать любую цифру.
Замените буквы и звездочки цифрами: КБИТ(КБИТ=****КБИТ

1.7. Попробуйте себя в качестве криптоаналитика.
Известно, что зашифровано стихотворение Р. Киплинга в переводе С. Я. Маршака. Шифрование заключалось в замене каждой буквы двузначным числом. Отдельные слова разделены несколькими пробелами, знаки препинания сохранены. Таблицу частот букв русского языка см. в прил. к решению задачи 1.8.

29 15 10 17 29 22 25 31 15 33 35 41 43 45 35 57 45 25 17 59 15 10 25 41 25 69,
59 78 29 82 25 78 25 17 15
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
· Попробуйте себя в качестве криптоаналитика. Известно, что зашифровано стихотворение. Шифрование заключалось в замене каждой буквы двузначным числом. Отдельные слова разделены несколькими пробелами, знаки препинания сохранены. Таблицу частот букв русского языка см. в прил. к решению задачи 1.8.

29 35 87 41 29 58 43 44 31 58 31 68 95 58 31 25 63, 32 58 31 87 41 31 68 31
58 68 31 35 68 41 31 68 63 71 95 63 77 91 35 68 91 45 99 45 35 58 77 41 63 58,
29, 77 31 58 35 91 77 35 68 95 91 63 71 35 51 75 35, 25 31 61 35 71 75 87 51 31 68 45 -
82 35 17 77 91 35 61 51 29 19 87 29 41 - 68 31 17 31 82 51 31 68 29 58 75 87 68 31 29 58 91 63 54

1.9. Доступ к сейфу имеют одиннадцать членов комиссии.
Каким наименьшим числом замков следует снабдить сейф для того, чтобы при определенном наборе ключей любые шесть членов комиссии, собравшись вместе, могли его открыть, а любых пяти членов комиссии было бы недостаточно? Указать, каким образом следует распределить ключи от сейфа с минимальным числом замков между членами комиссии.

1.10. Доступ к сейфу имеют девять членов комиссии.
Каким наименьшим числом замков следует снабдить сейф для того, чтобы при определенном наборе ключей любые пять членов комиссии, собравшись вместе, могли его открыть, а любых четырех членов комиссии было бы недостаточно? Указать, каким образом следует распределить ключи от сейфа с минимальным числом замков между членами комиссии.

Решения задач

1.1. Подсчитаем количество шифрообозначений в текстах. В первом тексте их 25, во втором – 28. Английский алфавит содержит 26 букв, следовательно, второй шифртекст не может соответствовать английскому открытому тексту. Значит, второй текст – это зашифрованный русский текст.
Ответ: первый текст – это зашифрованный английский текст, а второй – русский.

1.2. В первом тексте 30 шифрообозначений, а во втором 35. Следовательно, второй текст зашифрован с ошибками, а про первый ничего сказать не можем.

1.3. Представим многочлен f(x) в виде: 13 EMBED Equation.DSMT4 1415. Это можно сделать разными способами, например, делением «уголком».
Таким образом, 13 EMBED Equation.DSMT4 1415. Значит, к порядковому номеру буквы прибавлялось число 3. Следовательно, для расшифрования необходимо каждую букву шифрованного текста заменить на букву, расположенную левее на 3 позиции (циклический сдвиг на 3 позиции). Так, ЦУ, ЪЧ и т. д., см. таблицу. Заметим, что буква В, имеющая номер 3, переходит в символ пробела « ».

Шифртекст
Ц
Ъ
Л
Ф
Я
В
Р
Г
В
Ч
Л
Ф
Ц

Открытый текст
У
Ч
И
С
Ь
« »
Н
А
« »
Ф
И
С
У


Ответ: УЧИСЬ НА ФИСУ.

1.4. Представим f(x) в виде: 13 EMBED Equation.DSMT4 1415. Значит, 13 EMBED Equation.DSMT4 1415. Итак, к порядковому номеру символа открытого текста прибавлялось число –31, т. е. шифрование заключалось в циклическом сдвиге на 31 позицию влево. Таким образом, расшифрование заключается в сдвиге на 31 позицию вправо. Можно так и расшифровывать, однако заметим, что сдвиг на 31 позицию вправо равносилен сдвигу на 3 позиции влево. В итоге получаем:

Шифр-текст
Т
С
Ф
Х
Ц
Т
Г
М
В
Р
Г
В
Ч
Л
Ф
Ц

Открытый текст
П
О
С
Т
У
П
А
Й
« »
Н
А
« »
Ф
И
С
У


Ответ: ПОСТУПАЙ НА ФИСУ.

1.5. Обозначим неизвестное число, записанное словом ФИСУ, буквой x. Число x четырехзначное, следовательно 13 EMBED Equation.DSMT4 1415. Из условия задачи следует, что x состоит из различных цифр. Последняя цифра не ноль, так как в этом случае две последние цифры результата были бы нулями, а в задании они различны.
Результат есть x2. С другой стороны, при вычитании из него числа x получим число, оканчивающееся четырьмя нулями, т. е. 13 EMBED Equation.DSMT4 1415, где n – натуральное число. Перепишем это равенство в виде 13 EMBED Equation.DSMT4 1415. Число x оканчивается не нулями, число (x – 1) не может быть кратным 104, кроме того, числа x и (x – 1) взаимно просты.
Из сказанного следует, что возможны два случая: 1) число x делится на 24, число (x – 1) делится на 54; 2) число x делится на 54, число (x – 1) делится на 24.
Рассмотрим оба случая.
1. x = 16k, x – 1 = 625m, т. е. x = 625m + 1, где m < 16 (напомним, что x < 104). Значит, 13 EMBED Equation.DSMT4 1415. Поделим 625 на 16 с остатком: 13 EMBED Equation.DSMT4 1415. Итак, 13 EMBED Equation.DSMT4 1415 или 13 EMBED Equation.DSMT4 1415. Запишем это равенство в виде 13 EMBED Equation.DSMT4 1415. Вывод: (m + 1) кратно 16. Учитывая, что m < 16, получаем единственную возможность: m = 15. Тогда x= 9376.
2. x – 1 = 16k, x = 625m, где m < 16. Получаем: 13 EMBED Equation.DSMT4 1415 или 13 EMBED Equation.DSMT4 1415. Запишем это равенство следующим образом: 13 EMBED Equation.DSMT4 1415. Вывод: (m – 1) кратно 16, тогда наименьшее значение m будет 17. Таким образом, данный случай невозможен.
Ответ: 9376
·9376=87909376

1.6. Число, зашифрованное КБИТ, обозначим x. Уравнение имеет вид 13 EMBED Equation.DSMT4 1415, n – натуральное. Далее см. решение задачи 1.5.
Ответ: 9376

1.7. Подсчитаем частоты шифробозначений:

Обозначение
29
15
10
17
22
25
31
33
35
41
43
45
57

Количество
7
10
4
7
4
12
2
1
5
3
2
4
5
















Обозначение
59
69
78
82
88
90
62
73
79
67
54
70


Количество
3
3
4
2
6
5
1
2
1
1
1
1



Из таблицы частот букв русского языка (см. прил. к решению задачи 1.8.) видно, что чаще всего встречается буква О, на втором месте Е. В нашем шифртексте чаще всего встречается обозначение 25 (12 раз), на втором месте идет обозначение 15 (10 раз), остальные обозначения им существенно уступают. Поэтому можем выдвинуть гипотезу: 25 = О, 15 = Е. Однако текст у нас не очень большой, поэтому закономерности русского языка проявляются в нем не обязательно в строгом соответствии с таблицей частот. Поэтому возможен и вариант: 25 = Е, 15 = О. Но тогда последнее слово в третьей строке имеет окончание ЕО, что возможно, но все же более вероятный вариант ОЕ. Итак, будем работать с текстом, считая, что 25 = О, 15 = Е.
Теперь нам поможет знак препинания: «29, ». Крайне маловероятно, чтобы запятая стояла после согласной. Итак, 29 – гласная, причем вероятнее всего 29 = И или 29 = А, так как гласные Я, Ю, Э, У встречаются в осмысленных текстах на русском языке намного реже, чем И и А, что не противоречит таблице частот шифртекста.
В последней строке: 88 15, но 15 = Е, следовательно, 88 – согласная, причем наиболее вероятные значения – это Н и Т. Итак, 25 = О, 15 = Е, 29 = 13 EMBED Equation.DSMT4 1415, 88=13 EMBED Equation.DSMT4 1415. Теперь третье слово в третьей строке имеет 4 варианта:
29=И, 88=Н: 22 Н Е Н И Е
29=И, 88=Т: 22 Т Е Т И Е
29=А, 88=Н: 22 Н Е Н А Е
29=А, 88=Т: 22 Т Е Т А Е
Из рассмотренных вариантов лишь один является осмысленным и он позволяет найти значение 22. Имеем: 22 = М и третье слово в третье строке М Н Е Н И Е.
Теперь рассмотрим второе слово в первой строке. Е 10 17 И, причем 10 и 17 – согласные, и это не М и не Н. Наиболее вероятное слово Е С Л И, т. е. 10 = С, 17 = Л. Конечно, если мы, продолжая работать с текстом, вдруг получим «нечитаемое» слово, то придется вернуться к этому этапу и рассмотреть другие варианты. Однако это маловероятно, поскольку вряд ли в стихотворении были слова наподобие Е Р Т И, Е В Л И и т. п.
Далее, первое слово второй строки: 59 78 И, причем 59 и 78 – согласные, и это не С, не Л, не М и не Н. Так что это слово П Р И, т. е. 59 = П, 78 = Р. Тогда шестое слово первой строки 45 О Л П Е, что дает значение 45 = Т и тогда при 57 = В получаем фрагмент «В Т О Л П Е». Также второе слово последней строки П Е Р Е 62 дает нам значение 62 = Д.
Далее рассмотрим начало второй строки: «П Р И 82 О Р О Л Е С Н 90 Р О Д О М ». Из него следует, что 82 = К и 90 = А. Зная, что 82 = К, посмотрим на самое последнее слово К Л О Н И Т 35, откуда станет ясно, что 35 = Ь.
Перед последней атакой* выпишем текст, заменяя известные обозначения буквами.
И Е С Л И М О 31 Е 33 Ь 41 43 Т Ь В Т О Л П Е С О 41 О 69,
П Р И К О Р О Л Е С Н А Р О Д О М С В 73 79 Ь 67 Р А Н И Т Ь
И, 54 В А 31 А 73 М Н Е Н И Е Л 69 41 О Е,
70 Л А В 43 П Е Р Е Д М О Л В О 69 Н Е К Л О Н И Т Ь
Из последней строки: 69 = Ю, тогда слова Л Ю 41 О Е и С О 41 О Ю определяют 41: 41 = Б. Теперь из четвертого слова первой строки Б 43 Т Ь получаем, что 43 = Ы. А первое слово из последней строки 70 Л А В Ы – это Г Л А В Ы. Слово в первой строке М О 31 Е 33 Ь угадывается из контекста: М О Ж Е Ш Ь, т. е. 31 = Ж, 33 = Ш. Теперь второе слово в третьей строке запишется как 54 В А Ж А 73, откуда, с учетом контекста: 54 = У, 73 = Я. После этого окончание второй строки имеет вид « С В Я 79 Ь 67 Р А Н И Т Ь». Легко определяются буквы 79 = З, 67 = Х.
Ответ:
И Е С Л И М О Ж Е Ш Ь Б Ы Т Ь В Т О Л П Е С О Б О Ю,
П Р И К О Р О Л Е С Н А Р О Д О М С В Я З Ь Х Р А Н И Т Ь
И, У В А Ж А Я М Н Е Н И Е Л Ю Б О Е,
Г Л А В Ы П Е Р Е Д М О Л В О Ю Н Е К Л О Н И Т Ь

1.8. Составим таблицу частот шифрообозначений:

Обозначение
29
35
87
41
58
43
44
31
68
95
25
63
32

Количество
7
11
5
5
10
1
1
15
11
2
2
6
1
















Обозначение
71
77
91
45
99
51
75
61
82
17
19
54


Количество
3
5
6
3
1
4
3
2
2
2
1
1



Сравнение таблицы частот букв русского языка (см. прил. ниже) с таблицей частот шифрообозначений позволяет выдвинуть гипотезу: 31 = О. И есть три «кандидата» на букву Е, это обозначение 68, 35, 58.
Посмотрим на третье слово в первой строке. Если 58 = Е, то получим 44 О Е О 68, что нехарактерно для русского языка. Если 68 = Е, то последнее слово первой строки имеет вид: 87 41 О Е О – снова маловероятное сочетание букв. Поэтому будем считать, что 35 = Е. Конечно, если в процессе работы над текстом мы придем к противоречию, то придется вернуться к началу и пробовать другие варианты.
Обратим внимание на начало второй строки 58 68 О Е. Можем сделать вывод, что 58 и 68 – согласные. В тексте эти обозначения встречаются часто, уступая лишь 31. Из таблицы частот видно, что наиболее распространенные согласные – это Т и Н.
Если 58 = Н, то слово Н 68 О Е трудно прочитать: подставляя вместо 68 различные буквы, всякий раз получаем сочетание, не имеющее смысла. Итак, 58
· Н.
Если 58 = Т, то слово Т 68 О Е читается: Т В О Е, и 68 = В.
Запишем первую строку: «29 Е 87 41 29 Т 43 44 О Т О В 95 Т О 25 63, 32 Т О 87 41 О В О». Теперь 32 = Ч или 32 = К. Кроме того, 43 = Ы. Два слова «Т Ы 44 О Т О В» позволяет найти значение 44: ясно, что 44 = Г. Фрагмент «Т Ы Г О Т О В 95 Т О 25 63, 32 Т О» позволяет уверенно считать, что 95 = К, 32 = Ч, 25 = М, 63 = У.
Обратим теперь внимание на запятую в начале третьей строки. Слово из одной буквы и запятая – ясно, что это не согласная. Варианты для 29: Ы, У, Ю, Э отбросим, О уже используется, О=31. Возможные варианты для 29 – это Я, А, И.
Вернемся к первой строке. С учетом уже прочитанных обозначений получаем: «13 EMBED Equation.DSMT4 1415 Е 87 4113 EMBED Equation.DSMT4 1415 Т Ы Г О Т О В К Т О М У, Ч Т О». Единственный осмысленный вариант теперь: 29 = И. Тогда второе слово Е С Л И, и мы знаем еще два значения: 87 = С, 41 = Л.
Запишем текст, заменяя шифрообозначения на их известные значения.

И Е С Л И Т Ы Г О Т О В К Т О М У, Ч Т О С Л О В О
Т В О Е В Л О В У 71 К У 77 91 Е В 91 45 99 45 Е Т 77 Л У Т,
И, 77 О Т Е 91 77 Е В К 91 У 71 Е 51 75 Е, М О 61 Е 71 75 С 51 О В 45 –
82 Е 17 77 91 Е 61 51 И 19 С И Л – В О 17 О 82 51 О В И Т 75 С В О И Т 91 У 54
Последнее слово второй строки сразу позволяет угадать: 77 = П. Тогда второе слово третьей строки П О Т Е 91 П Е В, и 91 = Р. Четвертое слово второй строки: П Р Е В Р 45 99 45 Е Т = П Р Е В Р А Щ А Е Т, и мы знаем: 45 = А, 99 = Щ. Конец третьей строки: С 51 О В А = С Н О В А, 51 = Н. Кроме того, третье слово второй строки позволяет найти: 71 = Ш.
Запишем две последних строки.
И, П О Т Е Р П Е В К Р У Ш Е Н 75 Е, М О 61 Е Ш 75 С Н О В А –
82 Е 17 П Р Е 61 Н И 19 С И Л – В О 17 О 82 Н О В И Т 75 С В О И Т Р У 54
Отсюда следует, что 75 = Ь, но тогда 17 = З, 82 = Б, 61 = Ж.
Теперь последняя строка: «Б Е З П Р Е Ж Н И 19 С И Л – В О З О Б Н О В И Т Ь С В О И Т Р У 54». Второе слово позволяет понять, что 19 = Х. Учтем, что И и Й не различаются в данном алфавите. Тогда последние слова С В О Й Т Р У Д.
Ответ:
И Е С Л И Т Ы Г О Т О В К Т О М У, Ч Т О С Л О В О
Т В О Е В Л О В У Ш К У П Р Е В Р А Щ А Е Т П Л У Т,
И, П О Т Е Р П Е В К Р У Ш Е Н Ь Е, М О Ж Е Ш Ь С Н О В А –
Б Е З П Р Е Ж Н И Х С И Л – В О З О Б Н О В И Т Ь С В О Й Т Р У Д
Приложение
Частоты букв русского языка
(в 32-буквенном алфавите со знаком пробела)

-
0,175
О
0,090
Е, Ё
0,072
А
0,062

И
0,062
Т
0,053
Н
0,053
С
0,045

Р
0,040
В
0,038
Л
0,035
К
0,028

М
0,026
Д
0,025
П
0,023
У
0,021

Я
0,018
Ы
0.016
З
0,016
Ь, Ъ
0,014

Б
0,014
Г
0,013
Ч
0,012
Й
0,010

Х
0,009
Ж
0,007
Ю
0,006
Ш
0.006

Ц
0,004
Щ
0,003
Э
0,003
Ф
0,002


Диаграмма частот букв русского языка
(в 32-буквенном алфавите со знаком пробела)



1.9. Предположим, что при некотором натуральном n ключи к n замкам можно распределить среди одиннадцати членов комиссии с учетом всех условий задачи. Пусть Ai – множество замков, которые может открыть i-й член комиссии, где i = 1, 2, , 11, а A – множество всех замков. Из условий задачи следует, что
13 EMBED Equation.DSMT4 1415 (1)
для любого подмножества {i1, , i5} из 5 элементов множества {1, 2, , 11}.
Из условия также следует:
13 EMBED Equation.DSMT4 1415 (2)
для любого подмножества {j1, , j6} из 6 элементов множества {1, 2, , 11}.
Формула (1) означает, что множество 13 EMBED Equation.DSMT4 1415 не пусто. Пусть 13 EMBED Equation.DSMT4 1415- один из его элементов. А именно, это тот замок, который не может открыть группа членов комиссии с номерами i1, , i5. Например, x12357 – это замок, который не может открыть группа членов комиссии с номерами 1, 2, 3, 5,7, а x24689 – это замок, который не может открыть группа, состоящая из 2, 4, 6, 8, 9-го членов.
Формула (2) означает, что 13 EMBED Equation.DSMT4 1415, при любом 13 EMBED Equation.DSMT4 1415. Так, например, если 13 EMBED Equation.DSMT4 1415, то замок, который не могут открыть, собравшись вместе, 1, 2, 3, 5 и 7-й члены комиссии, откроет любой из следующих: 4, 6, 8, 9, 10, 11-й.
Предположим теперь, что для некоторых подмножеств из 5 элементов 13 EMBED Equation.DSMT4 1415 и 13 EMBED Equation.DSMT4 1415множества {1, 2, 3, 5, 7} выполняется равенство 13 EMBED Equation.DSMT4 1415. Если подмножества эти не совпадают, 13 EMBED Equation.DSMT4 1415, то найдется 13 EMBED Equation.DSMT4 1415 при некотором 13 EMBED Equation.DSMT4 1415. Тогда 13 EMBED Equation.DSMT4 1415. Но 13 EMBED Equation.DSMT4 1415. Полученное противоречие доказывает, что 13 EMBED Equation.DSMT4 1415.
Итак, мы доказали, что если один замок соответствует двум подмножествам, то эти подмножества совпадают. Другими словами, различным подмножествам из 5 элементов соответствуют различные замки. Следовательно, число замков не меньше числа подмножеств, содержащих по 5 элементов, т. е. 13 EMBED Equation.DSMT4 1415.
Докажем теперь, что если сейф снабжен 13 EMBED Equation.DSMT4 1415 замками, то ключи между членами комиссии можно распределить так, чтобы удовлетворить всем условиям задачи.
Для этого каждому из 13 EMBED Equation.DSMT4 1415 замков мы поставим во взаимно однозначное соответствие подмножество, содержащее 5 элементов из 11 элементов множества {1, 2, , 11}. Если замку соответствует подмножество 13 EMBED Equation.DSMT4 1415, то ключи от него получат все члены комиссии с номерами, отличными от 13 EMBED Equation.DSMT4 1415.
Докажем, что любые 5 членов комиссии не смогут открыть один из замков, а следовательно, и сейф. Действительно, у членов комиссии с номерами 13 EMBED Equation.DSMT4 1415 нет ключа от замка, которому соответствует подмножество 13 EMBED Equation.DSMT4 1415.
Докажем теперь, что любые 6 членов комиссии смогут открыть любой замок, а значит и сейф. Действительно, если члены комиссии имеют номера 13 EMBED Equation.DSMT4 1415 и хотят открыть замок, которому соответствует подмножество 13 EMBED Equation.DSMT4 1415, то, по крайней мере, одно из чисел 13 EMBED Equation.DSMT4 1415 не принадлежит этому подмножеству, например 13 EMBED Equation.DSMT4 1415. Следовательно, у члена комиссии с номером 13 EMBED Equation.DSMT4 1415 найдется ключ от замка, которому соответствует подмножество 13 EMBED Equation.DSMT4 1415.
Итак, наименьшее число знаков, удовлетворяющее условиям задачи равно 13 EMBED Equation.DSMT4 1415.
Ответ: 462.

1.10. См. решение задачи 1.9.
Ответ: 13 EMBED Equation.DSMT4 1415 = 126


Комментарии

1.1. Заимствована из [1] (см. задача 15.2), мы лишь сократили шифрованные тексты и заменили шифробозначения. Решение оценивается в 1 балл.
1.2. Придумана членами жюри по аналогии с задачей 15.2 [1]. 1 балл.
1.3–1.4. Представляют собой усложнение задачи 1.2 [1]. Иллюстрируют усложненный вариант одного из древнейших шифров – шифр Цезаря. 3 балла.
1.5–1.6. Встречаются во многих сборниках олимпиадных задач. Отметим, например задачу 221 в [2]. 4 балла.
1.7–1.8. Составлены членами жюри. Было зашифровано для каждого варианта по одному четверостишию из стихотворения Р. Киплинга «Если» («If»). 7 баллов.
1.9–1.10. Предлагалась на олимпиаде Польской Народной Республики в 1970 г.[3. С. 30] и в сборнике подготовительных задач к Московской олимпиаде, [4] (задача 60). Объясняет «схему разделения секрета». Такая схема используется сейчас во многих системах защиты ресурса (информации, материальных средств и т. д.), только ключом является не металлический предмет, а целое число с определенными свойствами. 10 баллов.
Таблица частот букв русского языка и диаграмма взяты из [5].










2. Вторая краевая олимпиада
по криптографии для школьников
(Красноярск, 2008)

В 2008 г. олимпиада проводилась в два тура. Победители отборочного (заочного) тура были приглашены для участия в финале. Олимпиада проводилась отдельно для школьников 8–9 и 10–11 классов.
Задачи отборочного тура: 2.1–2.8 (для 8–9 классов), 2.9–2.17 (для 10–11 классов).
Задачи финального тура: 2.18–2.23 (для 8–9 классов), 2.24–2.28 (для 10–11 классов).

Условия задач

2.1. Шахматная перестановка. Зашифровано высказывание, ключом является маршрут движения по доске, неизвестный вам. Движение начинается с отмеченной клетки. Переход в следующую клетку осуществляется ходом шахматного коня. Клетки, где нет букв, определяют пробел между словами.
Н
А
Р


Ь

У

Е
Т
О
Ш
В
Ю
С
Л

Я
Ж
А
Э
Т
И
К
А

О
М

С
Т
-
О
Д

О
А
Т
Р
Н
А
Т
,

О
Л
Е

Ь
А
Е
Б

М
М
К
Т
Я
А
К
А

Ь

А
Т
О
Р

Л

(Один из исторических шифров).

2. 2. Логика. Два мудреца написали на семи карточках числа от 5 до 11. После этого они перемешали карточки, первый мудрец взял себе три карточки, второй взял две, а две оставшиеся карточки они, не глядя, спрятали в мешок. Изучив свои карточки, первый мудрец сказал второму: «Я знаю, что сумма чисел на твоих карточках четная!».
Какие числа написаны на карточках первого мудреца? Единственный ли ответ в задаче?

2.3. Логика. Каждый из семнадцати ученых переписывается с остальными, в их переписке речь идет лишь о трех темах. Каждая пара ученых переписывается друг с другом лишь по одной теме. Докажите, что не менее трех ученых переписываются друг с другом по одной и той же теме.

2.4. Что больше: (20072008!)2 или 2007200820072008?

2.5. Встреча посередине. Решите уравнение
x2 + y2 + z2 – 2 = u2 – 2v2 + uv,
если переменные принимают значения согласно таблице:

x
y
z
u
v

0
0
-1
1
1

1
1
1
-1
2


2.6. Вариация на тему встречи посередине. Числа a, b, c удовлетворяют неравенству max(a, b) + max(c, 2007) = min(a, c) + min(b, 2008).
Докажите, что b
· c.

2.7. Английский язык. Открытый текст на английском языке (различие между строчной и прописной буквой не делается) кодируется, то есть переводится в числовую форму, по правилу: букве А присваивается номер 0, букве В – номер 1, букве Z – номер 25, пробелу соответствует номер 26. Затем текст шифруется по следующему алгоритму: вычисляется число aP + b, где Р – номер буквы открытого текста, а числа a и b – ключ шифрования (неизвестный вам). Вычисленное число заменяется остатком от деления на 27, полученному числу соответствует буква шифрованного текста. Вам известен алгоритм, неизвестен ключ.
Перед вами перехваченный шифрованный текст. Этих данных недостаточно для расшифровки. Однако из агентурных сведений стало известно – первый символ открытого текста – буква Q. Теперь данных достаточно. Прочитайте открытый текст.
Шифртекст: IQTHX

2.8. Лингвистика. Используется русский алфавит, Е и Ё не различаются. Буквы алфавита кодируются следующим образом: каждой букве ставится в соответствие двоичная запись её номера, начиная с нуля. Таким образом, А соответствует 00000, Б соответствует 00001, В соответствует 00010, , Ю – > 11110, Я – >11111. Для передачи используется пять проводов. По каждому передается соответствующий разряд пятизначного двоичного числа. Один из проводов (вы не знаете, какой именно), иногда работает правильно, а иногда дает сбой. Именно на одном из выходов принимающего устройства может быть получен 0 независимо от того, что было отправлено. Восстановите передавшийся текст. Известно, что это осмысленный текст на русском языке.
Полученный текст: А О А Д К Ь

2.9. Столбцовая перестановка. Открытый текст, сохраняя пробелы между словами, записали в таблицу. Начало было в первой строке, текст записывали слева направо, переходя со строки на следующую, шифрование заключалось в перестановке столбцов. Найдите открытый текст.
Шифрованный текст:
Д
В


Ы
Т


Г
О
Е
Р
О

У
Ь
Д

У
Б

М
М
Я
Ы
Р
П


2.10. Ребус. Найти такие цифры, которые при подстановке их вместо букв в выражение
13 EMBED Equation.3 1415forty
+ ten
ten
sixty
дают верный пример на сложение (различным буквам соответствуют различные цифры).

2.11. Логика. На олимпиаде были предложены три задачи: А, В, С. Известно, что 25 школьников решили хотя бы одну задачу. Школьников, не решивших задачу А, но решивших задачу В, в два раза больше, чем решивших С, но не решивших А. Школьников, решивших только задачу А, на одного больше, чем остальных школьников, решивших задачу А.
Сколько школьников решили только задачу В, если среди школьников, решивших только одну задачу, половина не решила задачу А?

2.12. Количество вопросов. Играют двое, один загадывает набор из целых однозначных чисел (х1, х2, , хn), как положительных, так и отрицательных. Второму разрешается спрашивать, чему равна сумма a1x1 + a2x2 + + anxn, где (a1, a2, , an) – любой набор чисел.
Каково наименьшее число вопросов, за которое отгадывающий узнает задуманный набор?

2.13. Встреча посередине. Решите уравнение
х + y + z + xy – yz + xz – 5 = u + v + w + uv +–vw + uw + 2u –2 v + 2w,
если переменные принимают значения согласно таблице:
x
y
z
u
v
w

0
-1
1
-1
0
0

1
2
2
0
3
1


2.14. Вариация на тему встречи посередине. Найдите все положительные решения уравнения
max (a, b)
·max (c, 2008) = min (a, c)
·min (b, 2008).

2.15. В квадратную таблицу NЧN вписаны все целые числа от 1 до N2 по следующему закону: 1 стоит на любом месте; 2 стоит в строке с номером, равным номеру столбца, содержащего 1; 3 стоит в строке с номером, равным номеру столбца, содержащего 2, и т. д.
На сколько сумма чисел в строке, содержащей 1, отличается от суммы чисел в столбце, содержащей N2?

2.16. Английский язык. Открытый текст на английском языке (различие между строчной и прописной буквой не делается) кодируется, т. е. переводится в числовую форму, по правилу: букве А присваивается номер 0, букве В – номер 1, букве Z – номер 25, пробелу соответствует номер 26. Затем текст шифруется по следующему алгоритму: вычисляется число aP+b, где Р – номер буквы открытого текста, а числа a и b – ключ шифрования (неизвестный вам). Вычисленное число заменяется остатком от деления на 27, полученному числу соответствует буква шифрованного текста. Вам известен алгоритм, неизвестен ключ.
Перед вами перехваченный шифрованный текст. Этих данных недостаточно для расшифровки. Однако из агентурных сведений стало известно: второй символ открытого текста – пробел. Теперь данных достаточно. Прочитайте открытый текст.
Шифртекст: TBUEC

2.17. Лингвистика. Используется русский алфавит, Е и Ё не различаются. Буквы алфавита кодируются следующим образом: каждой букве ставится в соответствие двоичная запись её номера, начиная с нуля. Таким образом, А соответствует 00000, Б соответствует 00001, В соответствует 00010, , Ю – > 11110, Я – >11111. Для передачи используется пять проводов. По каждому передается соответствующий разряд пятизначного двоичного числа. При монтаже 5 проводов были перепутаны, и теперь мы не знаем, по какому проводу приходит цифра старшего разряда и т. д. Перед вами полученный текст. Известно, что исходный текст был осмысленным. Восстановите его.
Полученный текст: ЫАДАФЭС

2.18. Алфавит состоит из n букв. Какова максимальная длина слова, если выполнены два условия:
а) в нем две рядом стоящие буквы всегда различны;
б) из него нельзя получить вычеркиванием букв слова вида abab, где a и b – различные буквы?

2.19. При умножении «столбиком» трехзначного числа на двузначное получилась следующая запись:
р р р
* р р
р р р р
р р р р_
р р р р р
Буквы р означают «простые» цифры, т. е. однозначные простые числа. Найти значения цифр. Единственное ли решение имеет задача?

2.20. При установке кодового замка с каждой из 26 латинских букв, расположенных на его клавиатуре, сопоставляется произвольное натуральное число, известное лишь обладателю замка. Разным буквам соответствуют не обязательно разные числа. После набора произвольной комбинации попарно различных букв происходит суммирование числовых значений, соответствующих набранным буквам. Замок открывается, если сумма делится на 26.
Докажите, что для любых числовых значений букв существует комбинация, открывающая замок.

2.21. Рассмотрим преобразование цифрового текста, в котором каждая цифра заменяется остатком от деления значения многочлена на число 10, где a, b – фиксированные натуральные числа.
Выясните, при каких значениях a, b указанное преобразование может быть шифрпреобразованием, т. е. допускает однозначное расшифрование.

2.22. Два криптографа выясняют, чей шифр содержит больше ключей. Первый говорит, что ключ его шифра состоит из сорока упорядоченных символов, каждый из которых принимает одно из восьми значений. Второй говорит, что ключ его шифра состоит из тридцати шести упорядоченных символов, зато каждый из них принимает девятьзначений. Чей шифр содержит больше ключей?

2.23. Сообщение, зашифрованное в пункте А шифром простой замены в алфавите из букв русского языка и знака пробела (–) между словами, передается в пункт Б отрезками по двенадцать символов. При передаче очередного отрезка сначала передаются символы, стоящие на четных местах в порядке возрастания их номеров, начиная со второго, а затем – символы, стоящие на нечетных местах (также в порядке возрастания их номеров), начиная с первого. В пункте Б полученное шифрованное сообщение дополнительно шифруется с помощью некоторого другого шифра простой замены в том же алфавите, а затем таким же образом, как и из пункта А, передается в пункт В. По перехваченным в пункте В отрезкам:
С
О
-
Г
Ж
Т
П
Н
Б
Л
Ж
О

Р
С
Т
К
Д
К
С
П
Х
Е
У
Б

-
Е
-
П
Ф
П
У
Б
-
Ю
О
Б

С
П
-
Е
О
К
Ж
У
У
Л
Ж
Л

С
М
Ц
Х
Б
Э
К
Г
О
Щ
П
Ы

У
Л
К
Л
-
И
К
Н
Т
Л
Ж
Г

Восстановите исходное сообщение, зная, что в одном из переданных отрезков зашифровано слово КРИПТОГРАФИЯ.

2.24. Известно, что A, B, C, D говорят правду лишь в одном случае из трех (независимо друг от друга). А утверждает, что В отрицает, что С говорит, будто D солгал. Какова вероятность, что D сказал правду?

2.25. Разделение секрета. Сейф с документами открывается, если набрано секретное число М. Для разделения секрета используется многочлен 13 EMBED Equation.3 1415 где a, b – целые числа. Каждый из трех членов комиссии получил свою долю секрета. Именно: первый знает, что F(2) делится на 13 с остатком 3, второй знает: F(3) делится на 13 с остатком 7, третий знает: F(5) делится на 13 с остатком 5.
Докажите, что объединив свои знания, эти трое смогут открыть сейф (и найдите число М), а любые двое из них не смогут (числа a и b члены комиссии не знают).

2.26. Найдите последнюю цифру числа 13 EMBED Equation.3 1415(возведение в степень 7 повторяется 2008 раз).

2.27. Ключом шифра, называемого «поворотная решётка», является трафарет, изготовленный из квадратного листа клетчатой бумаги размером n Ч n (n – четно). Некоторые из клеток вырезаются. Одна из сторон трафарета помечена. При наложении этого трафарета на чистый лист бумаги четырьмя возможными способами (помеченной стороной вверх, вправо, вниз, влево) его вырезы полностью покрывают всю площадь квадрата, причем каждая клетка оказывается под вырезом ровно один раз.
Буквы сообщения, имеющего длину n2, последовательно вписываются в вырезы трафарета, сначала наложенного на чистый лист бумаги помеченной стороной вверх. После заполнения всех вырезов трафарета буквами сообщения трафарет располагается в следующем положении и т. д. После снятия трафарета на листе бумаги оказывается зашифрованное сообщение.
Найдите число различных ключей для произвольного четного n.

2.28. Первый шифртекст получен из исходного текста перестановкой букв. Второй шифртекст получен из того же исходного текста заменой каждой буквы на другую букву так, что разные буквы заменены разными, а одинаковые – одинаковыми.
Восстановите исходный текст.
Первый шифртекст:
И Т Ш И Ь О К Т С О Г М А О Ф О К Е Т А П С С Е О Н С С Ы А В М Ь Ю З Т Ы Т А Ф О Ь В В Б А С О Ж Е З Т С И Н Й А Я Р Р Р Т О С Н М Я П Н Н О А Т Ш А О В О
Второй шифртекст:
Ф Я Р Ф Р У Ч Р Ф Ц Ы С А Б О В Я О Р Ц А Г Р Ф Ц Р Э Ц Ы Г Ф И Г Р Х Н Р Ш Ч Д Н В Ц В Т В Н Ч В Ч И Ж Р Ч В Х Д Г В И Ц Ф Э Ф Ц Р Л Т Р Ф Ц Ы М С А Б О В

Решения задач

2.1. Сделав несколько пробных «ходов коня», можно определить первые три буквы. После этого уже легко дойти до конца первого слова. Дальше просто.

37
12
59
26
39
10
57
21

60
27
38
11
58
25
40
9

13
36
17
48
15
64
23
56

28
61
14
1
18
47
8
41

35
2
49
16
63
22
55
20

50
29
62
33
46
19
42
7

3
34
31
52
5
44
21
54

30
51
4
45
32
53
6
43


Самая большая трата, какую только можно сделать – это трата времени (Теофраст).

2.2. Первый мудрец знает числа, написанные на тех четырех карточках, которые находятся не у него, но не знает, какие именно из них достались второму. Поэтому он может сделать своё заявление только в том случае, если для любых двух находящихся не у него карточек сумма написанных на них чисел четна. Для этого необходимо, чтобы числа на этих четырех карточках были все одинаковой четности, то есть были либо все четными, либо все нечетными. Четными они быть не могут, так как карточек с четными числами всего три. Поэтому они все нечетны, а три карточки с четными числами должны быть у первого мудреца.

2.3. Выберем наугад одного ученого. Он переписывается с каждым из остальных шестнадцати ученых только по одной теме. Докажем, что хотя бы по одной теме из трех он переписывается с шестью учеными. Пусть это не так. Тогда по каждой теме он переписывается не более чем с пятью учеными. Следовательно, по трем темам он переписывается не более чем с пятнадцатью учеными, что противоречит условию. Эту тему будем называть темой А. Если среди этих шестерых найдутся два, переписывающихся друг с другом по теме А, то задача решена. Возможен другой вариант: никто из этих шести ученых не переписывается по теме А. Тогда они переписываются по двум другим темам. Рассмотрим одного из шести ученых. Он переписывается с остальными пятью учеными шестерки. Найдется тема, по которой он переписывается с тремя из пяти ученых. В противном случае он переписывался бы только с четырьмя учеными. Назовем эту тему темой В. Если один из этих трех ученых переписывается с другим по теме В, то задача решена. Если они все трое переписываются между собой по третьей теме (теме С), то они и составили искомую тройку. Все случаи рассмотрены. Тем самым доказано, что указанная тройка всегда найдется.

2.4. Докажем, что для любого n Є N, n > 2, справедливо неравенство
13 EMBED Equation.3 1415.
Доказательство:
13 EMBED Equation.3 1415,
так как 13 EMBED Equation.3 1415, и 13 EMBED Equation.3 1415 при
13 EMBED Equation.3 1415

2.5.
x
y
z
Левая часть

0
0
-1
-1

0
0
1
-1

0
1
-1
0

0
1
1
0

1
0
-1
0

1
0
1
0

1
1
-1
1

1
1
1
1


u

·
Правая часть

1
1
0

1
2
-5

-1
1
-2

-1
2
-9




Ответ:
(0,
1,
-1,
1,
1)

(0,
1,
1,
1,
1)

(1,
0,
-1,
1,
1)

(1,
0,
1,
1,
1)


2.6. Заметим, что max (a, b)
· min (a, c), так как первое из этих чисел не меньше а, а второе – не больше а. Значит, max (с, 2007)
· min (b, 2008). Но max (с, 2007)
· с, а min (b, 2008)
· b.

2.7. Известно, что в английском языке после буквы Q следует буква U. Таким образом, нам известны 2 буквы открытого текста. Буква Q кодируется числом 16, далее шифруется по формуле: 13 EMBED Equation.3 1415, p – некоторое целое.
Аналогично получаем ещё одно условие: 13 EMBED Equation.3 1415. Вычитая первое уравнение из второго, получим: 13 EMBED Equation.3 1415, т.е. число 4а делится на 27 с остатком 8. Итак, а = 2, тогда b= 3.
Имеем уравнения для нахождения номеров букв открытого текста:
13 EMBED Equation.3 1415
где x, y, z – номера 3, 4, 5 букв, а r, s, t – некоторые целые числа. Легко видеть, что x= 8, y = 2, z= 10 удовлетворяют условиям. Но 8 – это код буквы I, 2 – код C, 10 – код K.
Ответ: открытый текст QUICK

2.8. При передаче двоичного представления буквы либо не произошло искажения, либо одна из единиц была заменена нулем.
Выпишем буквы, в двоичной записи которых не больше одной единицы: А, Б, В, Д, И, Р.
Первая буква полученного текста А, значит, первая буква переданного текста – это одна из букв: А, Б, В, Д, И, Р. Вторая буква полученного текста О, её двоичная запись 01110. Либо была передана буква О, либо буква П = 01111, либо Ю = 11110. Четвертая буква полученного текста Д, её двоичная запись 00100. Возможные варианты для четвёртой буквы: 00100 = Д, 10100 = Ф, 01100 = М, 00110 = Ж, 00101 = Е.
Аналогично для пятой буквы варианты: К, Л, О, Ъ. И для шестой буквы варианты: Ь, Ю, Э.
Теперь выпишем таблицу вариантов:
А
О
А
Д
К
Ь

Б
П
Б
Ф
Л
Ю

В
Ю
В
М
О
Э

Д

Д
Ж
Ъ


И

И
Е



Р

Р











Варианты начала слова БП, ВП, ДП, РП отбрасываем как крайне маловероятные для русского осмысленного текста. Далее, три гласных подряд также маловероятны. Посмотрим на 5-ю и 6-ю буквы. Мягкий знак может следовать только за согласной, но КЬ не может быть окончанием слова, а вот ЛЬ – вполне может. Окончания ОЮ, ОЭ, КЭ, ЛЭ отбросим. Теперь достаточно легко прочитать слово АПРЕЛЬ.

2.9. Присвоим столбцам номера в порядке их следования. Наша задача – найти такой порядок столбцов, при котором текст будет осмысленным.
Составим таблицу:

1
2
3
4
5
6

1
Х






2

Х





3


Х




4



Х



5




Х


6





Х

Клетка (k, m) в этой таблице означает, что столбец с номером m следует за столбцом с номером к. Знаком «Х» отметим невозможные случаи.
Сочетания столбцов 1, 2 и 5, 2 невозможны, так как гласная не может находиться перед мягким знаком. Невозможны и следования столбцов 2, 1 и 2, 5. Теперь из третьей строки следует, что 1, 5 и 5, 1 невозможны, так как УУ – нехарактерная для русского языка биграмма. Далее, два пробела подряд не могут быть в тексте, значит, ставим «Х» в клетках 3, 4 и 4, 3. Снова обратимся к третьей строке. Если бы столбец 2 следовал за столбцом 4, то слово началось бы с мягкого знака. Ставим «Х» в клетке 4, 2. Из первой строки: невозможна комбинация 4, 5, невозможна и 3, 5. Итог наших рассуждений представлен в таблице:

1
2
3
4
5
6

1
Х
Х


Х


2
Х
Х


Х


3


Х
Х
Х


4

Х
Х
Х
Х


5
Х
Х


Х


6





Х

Итак, после столбца 6 обязательно следует столбец 5. Но тогда поставим «Х» в клетке 6, 2 и получим: столбец 2 следует за столбцом 3. Далее, мы вычеркнули 5, 1 и 2, 1, следовательно, надо проверить варианты: 6532 и 65432 . Но (4, 3) вычеркнуто ранее. Итак, остались варианты:

1
6
5
3
2
4



4
6
5
3
2
1




6
5
3
2
1
4



6
5
3
2
4
1

4
1
6
5
3
2



1
4
6
5
3
2




Запишем 6, 5, 3, 2 столбцы подряд:
6
5
3
2

т
ы
-
в

о
р
о
г

б
у
д
ь

п
р
я
м

Попытка поставить столбец 1 перед столбцом 6 приведет к биграмме МП в последней строке и сочетанию ДТЫ в первой. Остались варианты: 465321, 653214, 653241, 146532.
Ответ: 653241 – ключ, открытый текст:
ты_в_д
ороге_
будь_у
прямым
(строка из популярной в 1970-е гг. песни).

2.10. Заметим, что число ten + ten оканчивается двумя нулями, отсюда следует: n = 0, e = 5. При сложении цифр третьего разряда: r + t + t + 1 получается менее 30, значит, в четвертый (с конца) разряд переходит не более двух единиц, а так как в пятый разряд также должна переходить единица, то 0 = 9, i = 1, поэтому из третьего разряда переходят две единицы. Пусть t
· 5, тогда r + t + t + 1
· r + 11, но r + 11 должно быть не меньше 20, что возможно лишь при r = 9, но цифра 9 уже занята, 0 = 9. Итак, t > 5. Пусть t = 6. Тогда r = 7 или r = 8. Напишем пример в каждом из вариантов:
f 9 7 6 y f 9 8 6 y
+ 6 5 0 + 6 5 0
6 5 0 6 5 0
s 1 0 6 y s 1 1 6 y
В первом случае получилось: x = 0, во втором: x = 1. Однако цифры 0 и 1 уже заняты. Итак, t = 7 или t = 8.
f 9 r 7 y
+ 7 5 0
7 5 0 , r = 6 или r = 8.
s 1 x 7 y
Если r = 6, то x = 1 – противоречие.
Если r = 8, то x = 3. Но тогда f не может быть равно 2, 3, 4, 1. А другие варианты для f исключены раннее.
f 9 r 8 y
+ 8 5 0
8 5 0 , r = 3, 4, 6, 7.
s 1 x 8 y
Противоречивы все варианты, кроме одного: 29786 + 850 + 850 = 31486.

2.11. Обозначим число участников, решивших только задачу А, через А, только задачу В – через В, число решивших задачи А и В, обозначим АВ, и т. д.
Тогда условия задачи запишутся в виде уравнений:
(1)
(2)
(3)
(4)

Конечно, числа A, B, C, AB, AC, BC, ABC – целые неотрицательные.
Сложим (1) и (3), получим:
2A + B + C + BC – 1 = 25 (5)
Далее:
BC = B – 2C (2')
A = B + C (4')
Теперь из (5) вычтем (2') и удвоенное (4'), получим:
4B + C = 26, отсюда
C = 26 - 4B, (6)
BC = B – (52 – 8B) = 9B – 52 (7)
Из (6) следует В
· 6, а из (7): В
· 6. Значит, если решение существует, то В = 6.
Решение существует, так как условиям удовлетворяют хотя бы такие значения: А = 8, В= 6, С = 2, АВ = 3, АС = 2, ВС = 2, АВС = 2.
Итак, только задачу В решили шесть школьников.

2.12. Покажем, что задуманный набор можно определить, задав всего один вопрос. Именно, достаточно взять а1 = 100, а2 = 1002, , an = 100n.
Теперь, 13 EMBED Equation.3 1415, покажем, что 13 EMBED Equation.3 1415
Действительно, 13 EMBED Equation.3 1415, так как x1, x2, , xn–1 – однозначные числа. Число 13 EMBED Equation.3 1415 имеет 2n – 1 десятичных знаков и состоит из нулей и девяток, т. е. оно меньше, чем 13 EMBED Equation.3 1415, и тем более меньше, чем 13 EMBED Equation.3 1415. Таким образом, интересующая нас дробь меньше, чем 13 EMBED Equation.3 1415.
Итак, 13 EMBED Equation.3 1415 отличается от целого числа xn меньше, чем на 13 EMBED Equation.3 1415. Это позволяет однозначно определить xn. Зная xn, мы можем найти 13 EMBED Equation.3 1415 и по ней найти xn–1, и т. д.

2.13. Наша цель – найти все наборы из шести чисел (x, y, z, u, v, w), удовлетворяющие уравнению. Мы найдем эти наборы, проведя перебор вариантов. Но рассматривать все 26 = 64 варианта не нужно. Заметим, что левая часть зависит от трех переменных, правая от трех других.
Составим таблицу для левой и аналогично для правой части.
x
y
z
Левая часть

0
-1
1
-2

0
-1
2
2

0
2
1
-2

0
2
2
-1

1
-1
1
-1

1
-1
2
4

1
2
1
2

1
2
2
4


u
v
w
Правая часть

-1
0
0
-1

-1
0
1
-1

-1
3
0
-1

-1
3
1
-2

0
0
0
0

0
0
1
3

0
3
0
3

0
3
1
3



Левая часть равна правой при следующих значениях:
(0,
-1,
1,
-1,
3,
1)

(0,
2,
1,
-1,
3,
1)

(0,
2,
2,
-1,
0,
0)

(0,
2,
2,
-1,
0,
1)

(0,
2,
2,
-1,
3,
0)


(1,
-1,
1,
-1,
0,
0)

(1,
-1,
1,
-1,
0,
1)

(1,
-1,
1,
-1,
3,
0)




2.14. Запишем уравнение: max(a, b)∙ max(c, 2008) = min(a, c)∙ min(b, 2008). Но  max(a, b) ≥ b, max(c, 2008) ≥ c. Значит, левая часть не меньше bc. Очевидно, что min(a, c) ≤ c, min(b, 2008) ≤ b. Следовательно, правая часть не больше bc. Но левая часть равна правой, поэтому во всех неравенствах достигается равенство.
Итак, max(a, b) = b, max(с, 2008) = с, min(a, c) = с, min(b, 2008) = b, т. е. a ≤ b, с ≥ 2008, с ≤ a, b ≤ 2008. Имеем неравенство 2008 ≤ c ≤ a ≤ b ≤ 2008.
Ответ: a = b = c = 2008.
2.15. Будем обозначать клетку, находящуюся на пересечении строки № а и столбца № b, через (a, b). Каждое из чисел 1, 2, , N встречается в такой записи всех клеток ровно 2N раз: N раз как номер столбца и N раз как номер строки.
Пусть теперь 1 стоит в клетке (a, x). Номер строки, в которой стоит 2, по условию, равен номеру столбца, содержащего 1, т. е. равен x. Значит, 2 стоит на поле (x, y). Далее, 3 стоит на поле (y, z) и т. д., наконец, N2 стоит на некотором поле (m, n).
Номер а встречается внутри (т. е. не на первом и не на последнем месте) цепочки (a, x), (x, y), (y, z), , (m, n) четное число раз. Так как а при этом стоит в начале цепочки и всего использован 2N раз, то этот номер должен стоять и в конце цепочки: n = a. Итак, строка, содержащая 1, имеет тот же номер, что и столбец, содержащий N2.
Рассмотрим любое, кроме 1 и N2, число p из столбца, в котором стоит N2. Следующее число, т. е. p + 1, стоит в строке, содержащей число 1. Итак, каждому числу из столбца, содержащего N2, соответствует на единицу большее число из строки, содержащей 1. Исключение составляет лишь N2. Кроме того, число 1 тоже не имеет себе пары в столбце. Следовательно, искомая разность равна
–1
·(N – 1) + N2 – 1 = N2 – N.

2.16. Так как второй символ открытого текста – пробел, то текст начинается с однобуквенного слова. Но таких слов в английском языке всего два: А (неопределённый артикль) и I («Я»). Значит, возможны два варианта: 1) А_... ; 2) I_... .
Рассмотрим первый вариант. Буква А кодируется числом ноль, далее шифруется по формуле: 13 EMBED Equation.3 1415 получается 19 – код буквы Т. Итак, b = 19. Пробел кодируется числом 26, шифруется: 13 EMBED Equation.3 1415
Имеем условие на а: 13 EMBED Equation.3 1415 или 13 EMBED Equation.3 1415 где p, q – некоторые целые числа (сдвиг на 27 позиций не меняет текста). Из чисел от 1 до 26 только одно удовлетворяет условию: a = 18. Итак, a = 18, b= 19. Имеем уравнения для оставшихся букв:
13 EMBED Equation.3 1415
где r, s, t – некоторые целые числа.
Запишем систему в виде
13 EMBED Equation.3 1415
Последнее уравнение запишем в виде 13 EMBED Equation.3 1415или 13 EMBED Equation.3 1415
Так как z и t – целые, то и число 2z – 3t – целое. Но тогда в левой части произведение числа 9 на некоторое целое число, получим противоречие с тем, что 17 – простое число.
Рассмотрим второй вариант. Имеем систему
13 EMBED Equation.3 1415
Решение: a = 2, b = 3. Теперь открытый текст находится:
I_WON («Я ПОБЕДИЛ»).

2.17. Перепутывание проводов не могло изменить количество единиц в двоичной записи буквы. Поэтому вторая и четвертая буквы исходного текста находятся сразу, это буквы А, так как А кодируется как 00000. Первая буква полученного текста Ы. Её код 11011, количество единиц четыре. Запишем буквы с четырьмя единицами в двоичной записи: П, Ч, Э, Ю. Варианты начала слова: ЫА, ПА, ЧА, ЭА, ЮА. Третья буква полученного текста Д. Её двоичная запись 00100, найдём буквы, имеющие, как и Д, одну единицу в двоичной записи. Это буквы: Б, В, И, Р. Вариант начала ЫА отбросим как невозможный, имеем следующие варианты для первых четырех букв:
13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415 13 EMBED Equation.3 1415
Шестая буква полученного текста Э, её код 11101, и есть следующие буквы, коды которых содержат те же четыре единицы: П, Ч, Ы, Ю. Учёт осмысленности исходного текста вариантов для 5 и 7 букв позволяют прочитать: ПАРАШЮТ.

2.18. Если буква встречается только один раз, назовем ее буквой первого рода. В противном случае – буквой второго рода. Буквы, стоящие рядом с буквой второго рода, различны, это следует из свойства «б».
Если слово содержит хотя бы два вида букв, то оно содержит хотя бы одну букву первого рода. В противном случае мы можем получить из него слово вида abab, что противоречит условию. Вычеркнув все буквы второго рода, совпадающие с некоторой, получим слово из n – 1 различных букв. Вычеркивая буквы второго рода и далее, придем к слову, состоящему только из букв первого рода.
Докажем методом математической индукции, что слово имеет длину не более 2n – 1 буквы. Для n = 1 утверждение верно. Предположим теперь, что оно верно для n = k букв и докажем его для n = k + 1.
Пусть слово содержит k + 1 различную букву,
· – буква первого рода, а
· – соседняя с ней буква. Если
· – первого рода, то при вычеркивании
· возникает слово из k различных букв, максимальная длина которого не превышает 2k – 1 букв (по предположению индукции), а само исходное слово имеет длину не более 2k. Если
· – второго рода, то или обе соседние буквы пары
·,
· различны, или имеется только одна соседняя буква, то есть пара
·,
· стоит с краю. Поэтому пару
·,
· можно вычеркнуть, оставшееся слово удовлетворяет условию «а» задачи. Длина оставшегося слова 2k – 1 букв, а первоначального – 2k – 1 + 2 = 2(k + 1) – 1.
Утверждение доказано. Итак, слово имеет длину не более 2n – 1 букв.
Приведем пример слова, имеющего длину в точности 2n – 1 букв. Из алфавита можно составить слово 13 EMBED Equation.3 1415.

2.19. Каждая из цифр может принимать лишь четыре значения: 2, 3, 5, 7. Нужно найти трехзначное и однозначное числа, произведение которых будет четырехзначным числом, а запись обоих сомножителей и произведения содержит только цифры 2, 3, 5, 7.
Если однозначное число – 2, то какой бы ни была последняя цифра трехзначного числа, условие задачи будет нарушено. Итак, однозначные числа, подлежащие проверке: 3, 5, 7. Если однозначное – 3, то трехзначное не может начинаться с 5 и с 3, не может заканчиваться на две пятерки, не может быть его последней цифрой ни 3, ни 7, ни 2. Итак, если однозначное число – 3, то трехзначное число заканчивается цифрой 5, вторая цифра – не 5. Но если вторая цифра – 3, то произведение будет содержать 0 – противоречие. Итак, число трехзначное имеет вид: а25 или а75, где а – цифра 2 или 7. Проверку проходит только число 775. Значит, однозначному числу 3 соответствует трехзначное 775.
Теперь в качестве сомножителя рассмотри число 5. Последней цифрой соответствующего трехзначного не может быть 2. Первой цифрой не может быть 2 и не может быть 3. Но если последняя цифра 3, то какова бы ни была вторая цифра, получим противоречие с условием. Итак, последняя цифра либо 5, либо 7. Разбор вариантов для второй и первой цифр показывает: непротиворечивы только случаи 5
·555 = 2775 и 5
·755 = 3775.
Пусть теперь однозначное число-сомножитель будет 7. Тогда для последней цифры трехзначного числа только одна возможность: цифра 5. Отсюда сразу следует: вторая цифра – не 3 и не 5. Перебрав оставшиеся варианты, получим: 7
·325 = 2275, и это единственный непротиворечивый случай для множителя 7.
Заметим, что каждому трехзначному числу соответствует лишь одно однозначное число. Следовательно, двузначное число состоит из одинаковых цифр. Итак, есть 4 «кандидата»: 775
·33, 555
·55, 755
·55, 325
·77. Выполняя умножение, получаем единственное решение:
775
* 33
2325
2325_
25575

2.20. Пусть S(n) – остаток от деления на 26 суммы чисел, которые соответствуют первым n буквам алфавита, n = 1, 2, , 26, 13 EMBED Equation.3 1415.
Если среди чисел S(1), S(2), , S(26) нет нуля, то существуют два одинаковых числа: S(k) = S(m), так как 26 чисел S(n) принимают 25 значений. Можно считать, что 13 EMBED Equation.3 1415. Теперь искомая комбинация – это участок алфавита, начинающийся (k + 1)-й буквой и заканчивающийся m-й буквой, так как этой комбинации соответствует S(m) – S(k).

2.21. Пусть f(x) – остаток от деления значения F(x) на 10. Для однозначного расшифрования необходимо и достаточно, чтобы разным значениям x соответствовали разные значения f(x). Поэтому f(0), f(1), , f(9) принимают все значения от 0 до 9. Найдем эти значения. Для удобства записи обозначим – остаток от деления t на 10. Имеем:

Теперь заметим, что b должно быть нечетным, иначе все значения f(x) будут четными. Далее, b не должно делиться на 5, иначе f(x) будут только 0 и 5. Поэтому число b может быть одним из числе вида: 1) 5p + 1, p – четно; 2) 5p + 2, р – нечетно; 3) 5р + 3, р – четно; 4) 5р + 4, р – нечетно. Легко заметить, что числа эти имеют запись соответственно: 10k + 1, 10k + 7, 10k + 3, 10k + 9, k – целое. В первом случае имеем:

При любом значении a эти числа различны. Непосредственной проверкой убеждаемся, что и для b = 10k + 7, b = 10k + 3, b = 10k + 9 все числа f(x), x = 0,1, , 9 будут различными при любом a.
Ответ: а – любое, b имеет вид: 10k + m, где m – одно из чисел 1, 3, 7, 9.

2.22. Нужно сравнить два числа: и .Запишем неравенство: , здесь ? – знак > или <. Но 13 EMBED Equation.3 1415, а 13 EMBED Equation.3 1415, поэтому знак в неравенстве тот же, что и в неравенстве .
Далее, 13 EMBED Equation.3 1415, а 13 EMBED Equation.3 1415. Задача свелась к сравнению чисел 13 EMBED Equation.3 1415 и 13 EMBED Equation.3 1415. Но 13
· EMBED Equation.3 1415, а 13 EMBED Equation.3 1415. Итак, 13 EMBED Equation.3 1415, отсюда следует: 13 EMBED Equation.3 1415, теперь 13 EMBED Equation.3 1415, то есть 13 EMBED Equation.3 1415.
Ответ: шифр первого криптографа содержит больше ключей.

2.23. Если символы одного отрезка занумеровать последовательно числами от 1 до 12, то после передачи его из А в Б символы расположатся в порядке (2, 4, 6, 8, 10, 12, 1, 3, 5, 7, 9, 11), а после передачи этого отрезка (замена символов не меняет порядка) из Б и В – в порядке (4, 8, 12, 3, 7, 11, 2, 6, 10, 1, 5, 9). Переставим символы перехваченных отрезков в соответствии с их номерами до передачи из пункта А. Именно: столбец, записанный в условии задачи первым, нужно записать четвертым, второй столбец из условия задачи – это восьмой столбец текста до передачи из пункта А, и т. д. Получим отрезки вида:
Л
П
Г
С
Ж
Н
Ж
О
О
Б
Т
-

Е
С
К
Р
У
П
Д
С
Б
Х
К
Т

Ю
У
П
-
О
Б
Ф
Е
Б
-
П
-

Л
Ж
Е
С
Ж
У
О
П
Л
У
К
-

Щ
К
Х
С
П
Г
Б
М
Ы
О
Э
Ц

Л
К
Л
У
Ж
Н
-
Л
Г
Т
И
К

Поскольку в пунктах А и Б одинаковые буквы заменялись одинаковыми, а разные – разными, то найденные отрезки можно рассматривать как замену одинаковых символов исходного текста одинаковыми, а разных – разными. Сравнивая места одинаковых букв слова КРИПТОГРАФИЯ и места одинаковых букв в отрезках, находим, что слово КРИПТОГРАФИЯ зашифровано во втором отрезке (вторая и восьмая, третья и одиннадцатая буквы одинаковы). Теперь имеем таблицу для дешифрования: Е нужно заменить на К, С заменить на Р и т. д.
Итак:
ЕК, СР, КИ, РП, УТ, ПО, ДГ, БА, ХФ, ТЯ
Запишем текст, заменяя шифробозначения известными буквами (прописные буквы – буквы найденные, а строчные – символы шифртекста):
л
О
г
Р
ж
н
ж
о
о
А
Я
-

К
Р
И
П
Т
О
Г
Р
А
Ф
И
Я

ю
Т
О
-
о
А
ф
К
А
-
О
-

л
ж
К
Р
ж
Т
о
О
л
Т
И
-

щ
И
Ф
Р
О
г
А
м
ы
о
э
ц

л
И
л
Т
ж
н
-
л
г
Я
и
И

Из третьей строки: ЮЭ. Слово в третьей строке НАУКА, то есть ОН, ФУ. Гипотеза ОН хорошо согласуется с первой строкой, где удвоенная согласная зашифрована оо. Обратимся к четвертой строке: лжКРжТНОлТИ – слово СЕКРЕТНОСТИ, теперь ЛС, ЖЕ. В пятой строке читается начало слова: ШИФРОВА, то есть ЩШ, ГВ. Теперь обратимся к последней строке: СИСТЕн_СВЯиИ – это, конечно, СИСТЕМ_СВЯЗИ. Получилось (четыре буквы в пятой строке угадываются):
С
О
В
Р
Е
М
Е
Н
Н
А
Я
_

К
Р
И
П
Т
О
Г
Р
А
Ф
И
Я

Э
Т
О
_
Н
А
У
К
А
_
О
_

С
Е
К
Р
Е
Т
Н
О
С
Т
И
_

Ш
И
Ф
Р
О
В
А
Л
Ь
Н
Ы
Х

С
И
С
Т
Е
М
_
С
В
Я
З
И

















2.24. Обозначим логические значения высказываний: И = «истина», Л = «ложь». С высказыванием «А утверждает, что В отрицает, что С говорит, будто D солгал» совместимы некоторые комбинации истины и лжи. Выясним, какие именно. Итак, начнем заполнять таблицу истинности, начиная с D. Нас интересует случай, когда D сказал истину.
Начало таблицы: и .
Если D сказал истину и С – тоже, то С НЕ говорил, будто D солгал. В этом случае, если В говорит истину, то и А может сообщать только истину. Если в случае высказывание В ложно, то есть В НЕ отрицал, что С говорил, будто D солгал, то А, утверждая, что В отрицает и т. д., лжет. Итак, если D сказал истину и С сказал истину, то обязательно либо и А, и В говорят истину, либо оба лгут. Другими словами, из следует, что возможны два варианта: и 13 EMBED Equation.3 1415.
Рассмотрим случай , то есть D сказал правду, а С говорит, будто D солгал. Если В говорит истину, то он НЕ отрицает, что С говорит, будто D солгал, но тогда А лжет. Если же В лжет, то он отрицает, что С сказал, что D солгал. Тогда А, утверждая, что В отрицает, и т. д., говорит правду. Вывод: из 13 EMBED Equation.3 1415 следует, что либо А лжет, а В говорит правду, либо наоборот.
Подведем предварительный итог. Непротиворечивы следующие варианты, и только они: , , , 13 EMBED Equation.3 1415.
Поскольку каждый из высказывающихся говорит правду в одном случае из трех и делает это независимо от других, то таблица всех возможных случаев имеет 34 = 81 строку.
Комбинацию можно получить лишь одним способом (1 строка в таблице) а каждую из комбинаций , 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 – четырьмя способами (на каждое ложное высказывание одного приходится два ложных высказывания другого).
Понимая вероятность как отношение числа исходов, благоприятных наступлению события, к общему числу исходов, получаем 13 EMBED Equation.3 1415.

2.25. Нужно найти М из условий:
13 EMBED Equation.3 1415
где p, q, t – некоторые целые числа.
Складывая первое равенство со вторым и вычитая из их суммы третье, получим: 13 EMBED Equation.3 1415, где 13 EMBED Equation.3 1415 – некоторое целое. Вычитая первое из второго, получим 13 EMBED Equation.3 1415.
Теперь подставим 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415 в первое уравнение. Получим 13 EMBED Equation.3 1415, u – целое число. Так как каждое число заменяется его остатком от деления на 13, то 13 EMBED Equation.3 1415.
Поскольку a, b, M – неизвестны, то любые двое, объединившись, получат систему из двух уравнений относительно трех неизвестных.

2.26. Если перемножить два числа, одно из которых заканчивается на цифру а, а второе – на цифру b, то их произведение будет оканчиваться на ту же цифру, что и произведение ab. Будем последовательно производить возведения в степень, следя только за последней цифрой: 13 EMBED Equation.3 1415 оканчивается 9, 13 EMBED Equation.3 1415 оканчивается цифрой 3, 13 EMBED Equation.3 1415 оканчивается цифрой 1, и 13 EMBED Equation.3 1415 оканчивается цифрой 3.
Далее, число 13 EMBED Equation.3 1415 оканчивается цифрой 9, 13 EMBED Equation.3 1415 - цифрой 7, 13 EMBED Equation.3 1415 – цифрой 1, и 13 EMBED Equation.3 1415 – цифрой 7. Отсюда следует, что число 13 EMBED Equation.3 1415 оканчивается той же цифрой, что и 13 EMBED Equation.3 1415, то есть цифрой 3, число 13 EMBED Equation.3 1415 – снова цифрой 7, и т. д. Продолжая таким образом, после четного числа возведений в степень будем приходить к числу, оканчивающемуся цифрой 7, а после нечетного числа возведений в степень – к числу, оканчивающемуся цифрой 3. Так как 2008 – четное число, то получаем ответ: 7.

2.27. Все клетки квадрата размера 13 EMBED Equation.3 1415 разобьем на непересекающиеся группы по четыре клетки в каждой. Отнесем клетки к одной и той же группе, если при каждом повороте квадрата до его самосовмещения они перемещаются на места клеток этой же группы. На рисунке показано такое разбиение на группы всех клеток квадрата 13 EMBED Equation.3 1415, причем клетки одной группы помечены одной и той же цифрой:


1
2
3
4
5
1

5
6
7
8
6
2

4
8
9
9
7
3

3
7
9
9
8
4

2
6
8
7
6
5

1
5
4
3
2
1

Всего таких групп будет 13 EMBED Equation.3 1415 (целое, так как n – четное число).
При наложении трафарета на квадрат ровно одна клетка из каждой группы окажется под его вырезами. Каждому трафарету поставим в соответствие упорядоченный набор всех клеток из таких групп, оказавшихся под вырезами трафарета при наложении его на квадрат помеченной стороной вверх. Такое соответствие является взаимнооднозначным, поскольку каждому ключу будет однозначно соответствовать упорядоченный набор из 13 EMBED Equation.3 1415 клеток (по одной из каждой группы), вырезанных в трафарете, и наоборот. Всего таких наборов 13 EMBED Equation.3 1415. В самом деле, существует ровно четыре различных варианта выбора клетки из каждой группы независимо от выбранных клеток из других таких групп. Таким образом, число различных ключей шифра «поворотная решетка» при четных значениях n равно 13 EMBED Equation.3 1415.
2.28. Подсчитаем частоты букв первого шифртекста. Эти частоты будут частотами букв исходного текста, так как первый шифртекст получен перестановкой букв из исходного текста. Одновременно подсчитаем частоты шифробозначений второго текста.
Первый шифртекст
Второй шифртекст

О – 11
Р – 11

Т, А, С – 8
Ц, Ф, В – 8

Н – 5
Ч – 5

В – 4
Г – 4

И, Ь, М, Е, Р – 3
Ы, А, О, И, Н – 3

Ш, К, Ф, П, Ы, З, Я – 2
Я, С, Б, Э, Х, Д, Т – 2

Й, Г, Ю, Б, Ж – 1
У, Ш, Ж, Л, М – 1

Сразу можно сделать вывод: шифробозначению Р соответствует буква О открытого текста, Ч соответствует Н, а Г – В.
Будем постепенно «проявлять» текст. Запишем второй шифртекст (в нем порядок следования букв не менялся), заменяя уже известные нам шифробозначения их значениями (прописные буквы – это буквы открытого текста, строчные – шифробозначения):
фяОфОуНОфцысабов
Далее, шифробозначение Ф скрывает одну из букв: Т, А, С. Шифробозначение Я скрывает либо букву Я, либо согласную. Предположим, что ЯЯ, пробуем читать начало:
ФТ: ТЯОТО
ФА: АЯОАО
ФС: СЯОСО
Не читается. Вывод: Я скрывает согласную, причем одну из следующих: Ш, К, Ф, П, З (вариант ЯЫ мы отбросили сразу). Но если ФТ, то слово не читается. Проверим вариант ФС. Пробуем читать: СяОСОуНОСцы, и из всех возможных замен для Я подходит только П, тогда начало текста: СПОСОБНОСТЬ, и мы знаем теперь, что ЯП, УБ, ЦТ, ЫЬ.
Обратим внимание на фрагмент яорцагрфцрэцы С учетом наших знаний это: ПоОТаВОСТОэТЬ, и мы находим еще соответствия: ОР, АИ, ЭЯ. Кроме того, так как ФС, ЦТ, то из таблицы: ВА.
Теперь исследуем последний фрагмент текста: фцрлтрфцымсабов. Заменим обозначения их значениями: СТОлтОСТЬм Обратимся к таблице. Обозначению Л соответствует одна из букв Й, Г, Ю, Б, Ж. Пробуем читать, получаем: ЛЙ, и из таблицы: ТК. Но тогда МЮ, и слово получилось СТОЙКОСТЬЮ.
Теперь начало второй строки: АТАКАнНА, ясно, что НМ. Далее, записываем вторую строку:
АТАКАМНАНижОНАхдВАиТСЯСТОЙКОСТЬЮ
И мы знаем: ИЕ, ЖГ, ХЗ, ДЫ.
Текст: «Способность шифра противостоять всевозможным атакам на него называется стойкостью шифра».

Комментарии

2.1. Заимствована из [6] (см. задачу 133).
2.2. Предлагалась на Санкт-Петербургской математической олимпиаде 1997 г. для 6 классов [7. С. 83].
2.3. Предлагалась на Шестой международной олимпиаде, проходившей в 1964 г. в Москве [2. С. 30].
2.4. Впервые встречается во втором туре олимпиады Москвы по математике в 1958 г. [2. С. 175]. Отметим еще , что эта задача предлагалась на олимпиаде Голландии в 1982 г. [8. С. 17].
2.5. Составлена по образцу задачи 10.2 из [1. С. 53]. Задача иллюстрирует метод «встречи посередине», который применяется для решения многих математических задач, являясь в то же время методом работы криптоаналитиков. Можно сказать, что это «криптоаналитический метод решения математических задач».
2.6. В несколько иной формулировке эта задача предлагалась на Санкт-Петербургской олимпиаде 1998 г. [7. С.118]. Является вариацией на тему «встречи посередине».
2.7. Придумана членами жюри Красноярской олимпиады по криптографии, и похожих задач найти в учебной литературе нам не удалось. Задача моделирует в миниатюре работу криптоаналитика: известен алгоритм, неизвестен ключ, дополнительное условие позволяет (при знании свойств языка!) четко сформулировать математическую задачу, в данном случае – систему сравнений. Заметим, что мы старались избегать введения новых понятий, поэтому не приводим в решении слово «сравнение».
2.8. Образцом при составлении этой задачи послужили задачи 11.3, 12.2 и 16.3 из [1].
2.9. Является в какой-то мере стандартной, шифр «столбцовая перестановка» встречается во многих пособиях по криптографии и в популярной литературе. Члены жюри олимпиады зашифровали в этой задаче строку из песни «Твоя судьба».
2.10. Предлагалась на подготовительном туре олимпиад Москвы, [4. С. 115], встречается также в известном сборнике Отто Данкеля, см.новое русское издание [9. С. 108].
2.11. Одна из задач Восьмой международной олимпиады, София, 1966 г. [2. С. 31].
2.12. Задача олимпиады Москвы 1961 г. [4. С. 187].
2.13–2.14. См. комментарий соответственно к задачам 2.5 и 2.6.
2.15. Предлагалась на олимпиаде Москвы в 1959 г. [4. С. 177].
2.16. См.комментарий к задаче 2.7.
2.17. Составлена по образцу задач 11.3, 12.2, 16.3 из [1].
2.18. См. задачу 139 [2. С. 45].
2.19. См. [9. С. 94].
2.20. Задача 2.4 [1. С. 41], без изменений.
2.21. Задача 2.3 [1. С. 41].
2.22. Задача 12.1 [1. С. 56].
2.23. Задача 3.3 [1. С. 42].
2.24. Заимствована из [9. С. 76].
2.25. Заимствована из [10]. Полезно сравнить эту задачу с задачами 1.9–1.10 первой олимпиады, это еще один вариант разделения секрета.
2.26. Является, по-видимому, математическим фольклором, во всяком случае, она встречается (с разными показателями степени) во многих сборниках и установить первого автора не представляется возможным. Задача содержит криптографический мотив: имеет связь с алгоритмом RSA, более того, на идее этой задачи основана атака на RSA, имеющая название «атака перешифрованием».
2.27. Задача 1.1 [1. С. 38].
2.28. Для этой задачи образцом послужила задача 6.3 [1], шифробозначения и текст мы заменили. Полезно сравнить эту задачу с задачей 1.4 первой олимпиады.





Третья краевая олимпиада по криптографии для школьников
Задачи для 8-9 классов

Ученики A,B,C,D,E участвовали в одном конкурсе. Пытаясь угадать результаты соревнований, некто предполагал, что получится последовательность A,B,C,D,E. Но оказалось, что он не указал верно ни места какого-либо из участников и никакой пары следующих непосредственно друг за другом учеников. Некто другой, предполагая результат D,A,E,C,B, угадал правильно места двух учеников, а также две пары (непосредственно следующих друг за другом учеников).Каков был на самом деле результат конкурса?
Сколько различных пар непересекающихся подмножеств имеет множество, состоящее из n элементов?
Найти остаток от деления числа a=20112011+20112010+20112009+20112008+20112007 на число 2010.
При зашифровании некоторые буквы открытого текста были сдвинуты на 2 позиции вправо в алфавите, например, А заменена на В.Другие сдвинуты на 2 позиции влево. А некоторые буквы открытого текста не были изменены.Использовался русский алфавит из 33 букв. Перед Вами зашифрованный текст. Найдите открытый текст.
Шифрованный текст:
ЙВЧЖТВ КНЦРРКАФИК

Цифры заменены буквами, разные цифры- разными буквами, одинаковые -одинаковыми. В фразе
И ВСЕ ЖЕ ОН НЕ ПРАВ
Каждое слово является квадратом некоторого натурального числа. Найдите соответствие между цифрами и буквами.
Алгоритм зашифрования следующий.К порядковому номеру в алфавите буквы открытого текста прибавляется номер буквы ключевого слова, затем полученное число заменяется соответствующей буквой алфавита, используются 33 буквы.Ключевое слово записывается подряд столько раз, сколько потребуется для зашифрования текста.Пример: зашифруем слово ХЛЕБ,используя ключ МИР.Буква М имеет номер 14 в алфавите,буква И-10,Р-18.По указанному алгоритму, к номеру буквы Х,то есть 23,прибавляем 14, получили37,то есть букву Г(алфавит испоьзуем циклически, то есть 33=Я,34=Б, т.д)Далее: Л перейдет в Х, Е в Ц,Б в О( снова использовалась буква М).
Х Л Е Б
М И Р М
Г Х Ц О
Шифрованный текст ,представленный ниже, получен зашифрованием с использованием секретного ключевого слова.Однако из агентурных сообщений стало известно: ключом является русское слово, последние две буквы которого СО.Найдите открытый текст.
Шифртекст:
ЛГЯКАВФДХРТЁФО.



.


Задачи для 10-11 классов

1. На математической олимпиаде было предложено пять задач. Среди участников олимпиады не оказалось двух, решивших одни и те же задачи. Если не принимать во внимание любую из задач, то, выбрав любого участника, можно найти и другого, решившего из оставшихся четырех задач те же, что и он. Сколько человек участвовало в олимпиаде?
2. Для каждого натурального n найти наибольшее k, обладающее свойством: в множестве, состоящем из n элементов, можно выбрать k различных подмножеств, любые два из которых имеют непустое пересечение.
3. Пусть 9876543212007a=9876543212008, 9876543212008b=9876543212009.Сравните числа a и b.
4. На каждой из трех осей установлено по одной вращающейся шестеренке и неподвижной стрелке. Шестеренки соединены последовательно. На первой шестеренке 33 зубца, на второй - 10, на третьей - 7. На каждом зубце первой шестеренки по часовой стрелке написано по одной букве русского языка в алфавитном порядке: А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
На зубцах второй и третьей шестеренки в порядке возрастания по часовой стрелке написаны цифры от 0 до 9 и от 0 до 6 соответственно. Когда стрелка первой оси указывает на букву, стрелки двух других осей указывают на цифры. Буквы сообщения шифруются последовательно.
Зашифрование производится вращением первой шестеренки против часовой стрелки до первого попадания шифруемой буквы под стрелку. В этот момент последовательно выписываются цифры, на которые указывают вторая и третья стрелки. В начале шифрования стрелка 1-го колеса указывала на букву А, а стрелки 2-го и 3-го колес - на цифру 0.
Расшифруйте сообщение 948593312255334486.
5. Алгоритм зашифрования был применён следующий: Каждая буква открытого текста была заменена другой буквой, разным буквам соответствуют разные буквы, одинаковым одинаковые, Е и Ё не различаются. Перед вами зашифрованный текст, найдите открытый текст:
А БВГД, ЕГЕ ЖЗИГЙК БГЛГМН.
А ОЕПЖП ЖЗИН ЗЗ. ЕЙП ЖЗИГЗЙ БГЛГМР ОЕПЖЗЗ,
ЙПЙ ЖЗИРЙ СПТКИЗ БГЛГМ. БГ ЕГУЛНД
БГЛГМН ВГМРОТАДЙОА ПМЕР.
Решения задач для 8-9 классов

Решение задачи 1.
Очевидно, что если в правильно указанную пару входит один правильно указанный элемент, то и другой элемент пары --правильно указанный.
Последовательность DAECB содержит четыре пары:DA, AE, EC, CB.Две из них угаданы верно. Допустим, что эти две пары содержат общую букву. Тогда образуется тройка, в которой верно угадан порядок. Теперь решим, где могут быть две верно угаданные буквы. Если хотя бы одна из них в тройке, то вся тройка состоит из верно угаданных букв, чего быть не может, так как таких букв только две. Если же обе они вне тройки, то все пять букв стоят на своих местах, чего тем более не может быть.
Итак, из четырех пар надо выбрать две, не имеющие общей буквы. Это можно сделать тремя способами:
(DA,EC ) ; ( DA, CB) ; (AE, CB).
Теперь заметим, что в каждом случае одна из двух пар должна содержать верно угаданные буквы, а другаяневерно. Рассмотрев наши три случая, видим, что в первом и третьем возможен только один вариант, а во второмдва .Получаем четыре варианта:
DABEC, EDACB, DACBE, AEDCB.
Три варианта приводят к противоречию, всем условиям удовлетворяет лишь один: EDACB.
Решение задачи 2.
Найдем количество различных пар непересекающихся подмножеств при условии, что в паре выделены первое и второе подмножества. Для каждого из n элементов есть три возможности: его можно или включить в первое подмножество, или включить во второе подмножество, или не включать ни в одно из них. Поэтому количество указанных пар равно 3n.Среди них есть одна пара, в которой оба подмножества пусты. Оставшиеся (3n-1) пары в свою очередь разбиваются на двойки совпадающих пар, если разрешить переставлять в парах местами первое и второе подмножества. Таким образом, существует (3n-1)/2 (неупорядоченных) пар подмножеств, из которых хотя бы одно не пусто. Всего же имеется (3n-1)/2+1=(3n+1)/2 различных пар подмножеств, удовлетворяющих условию задачи.
Решение задачи 3.
Рассмотрим многочлен P(x)=x2011+x2010+x2009+x2008+x2007. Многочлен P(x) можно представить в виде: P(x)=(x2011-1)+(x2010-1)+(x2009-1)+(x2008-1)+(x2007-1)+5. Так как xm-1 делится на x-1 без остатка при любом натуральном m, то каждое выражение в скобках делится на x-1.Следовательно, P(x)=(x-1)S(x)+5,где S(x) -некоторый многочлен. Подставим в последнее равенство значение x=2011, получим: 20112011+20112010+20112009+20112008+20112007 =2010*S(2011)+5, и S(2011) -целое число.Ответ:5.




Решение задачи 4.
Первая буква открытого тексталибо Й, либо получается из Й сдвигом на две позиции влево, то есть это буква З, либо получается из Й сдвигом на две позиции вправо, то есть это Л.Запишем в столбец возможные варианты первой буквы открытого текста:
З
Й
Л.
Аналогично для второй буквы, для третьей и т.д.Получили три строки:
З А Х Е Р А И Л Ф О О И Ю Т Ж И
Й В Ч Ж Т В К Н Ц Р Р К А Ф И К
Л Д Щ И Ф Д М П Ш Т Т М В Ц К М.
Теперь нужно в каждом столбце выбрать по букве, чтобы получить осмысленный текст. Открытый текст: ЗАЩИТА ИНФОРМАЦИИ. Выбранные буквы выделены .
Решение задачи 5.
Заметим,что в этой задаче буквы Е и Ё не различаются,иначе цифр было бы 11.Двузначные числа, являющиеся квадратами: 16, 25, 36, 49, 64, 81.Запишем варианты для слов ЖЕ , ОН и НЕ:
ЖЕ ОН НЕ
16 16 16
25 25 25
36 36 36
49 49 49
64 64 64
81 81 81.

Вторая цифра числа из первого столбца должна совпадать со второй цифрой числа из третьего столбца, а первые цифры должны быть разными.Следовательно, либо ЖЕ=16,НЕ=36, либо ЖЕ=36,НЕ=16.Но первая цифра числа из третьего столбца совпадает со второй цифрой числа из второго столбца,поэтому остался единственный вариант: НЕ=16,ОН=81,ЖЕ=36.Теперь обратим внимание на слово ВСЕ.Этому слову соответствует число, последняя цифра которого 6.Квадрат двузначного числа оканчивается цифрой 6, следовательно, это двузначное число может иметь вторую цифру либо 4, либо 6.Такие числа : 14, 16, 24, 26.Но 142=196,а букве В не может соответствовать 1.Далее, 162=256,но тогда В=2, и слову ПРАВ соответствует число, оканчивающееся цифрой 2, что невозможно: квадрат натурального числа не может иметь последнюю цифру 2.Проверяем число 26, получаем: 262=676, но тогда В=6, то есть В=Е,противоречие.Вычисляем:242=576, и это единственный вариант для слова ВСЕ, не противоречащий условиям задачи.Итак,В=5.Значит, число, квадрат которого соответствует слову ПРАВ, оканчивается цифрой 5, но тогда последние две цифры числа, соответствующего ПРАВ, это 25, то есть А=2.Двузначное число,вторая цифра которого 5 и квадрат которого состоит из различных цифр, только одно, это 95, так что ПРАВ=9025.И для буквы И остался единственный вариант, это 4.Ответ: 4 576 36 81 16 9025.
Решение задачи 6.
Известно,что русских слов, имеющих последние две буквы СО,всего три: МЯСО,ПРОСО,КОЛЕСО.(Есть,конечно,ЛАССО,но это слово не русское).Итак, у нас есть три варианта ключа.Опробуем каждое из возможных слов.Будем от порядкового номера буквы шифртекста отнимать порядковый номер буквы предполагаемого ключа.Пробуем ключ МЯСО:13-14=-1,то есть 32(алфавит используется циклически),тогда первая буква открытого текста Ю.Аналогично,вторая буква Г,третья М,четвертая Ы, и выражение ЮГМЫ трудно назвать осмысленным текстом на русском языке.Пробуем вариант ключа ПРОСО,получаем начало слова:ЫСПСнова нет смысла.Остался последний вариант ключа:КОЛЕСО.От номера Л,то есть 13,отнимаем номер К,то есть12,первая буква открытого текста А.Далее,от номера Г, это 4,отнимаем номер О,то есть 16,получили -12,прибавив 33, получим 21,поэтому вторая буква У.Продолжая дальше, найдем остальные буквы открытого текста.Ответ: АУТЕНТИФИКАЦИЯ.
Решения задач 1011 классов
Решение задачи 1.
Составим для каждого школьника таблицу из пяти клеток. В каждой клетке будем писать единицу, если школьник решил задачу, и ноль, если не решил. По первому условию каждая таблица присваивается не более чем одному школьнику(у разных школьниковразные таблицы).Таким образом, школьников не более 25=32.Покажем, что второе условие будет выполнено только тогда, когда школьников ровно 32.Предположим, что некоторый набор задач не решил ни один школьник, т.е. набор чисел a5 a4 a3 a2 a1 не присвоен никакому школьнику, так как по смыслу задачи в олимпиаде принимал участие хотя бы один человек, то найдётся присвоенный номер b5 b4 b3 b2 b1.

Построим цепочку
N0 =b5 b4 b3 b2 b1 , N1 =b5 b4 b3 b2 a1 , N2 =b5 b4 b3 a2 a1 ,
N3 =b5 b4 a3 a2 a1 , N4 =b5 a4 a3 a2 a1 , N5 =a5 a4 a3 a2 a1 .
В этой цепочке либо два соседних номера Ni-1 и Ni совпадают при bi= ai и поэтому являются номерами одного и того же школьника, либо различаются в i-м разряде, тогда, выбросив из рассмотрения i-ю задачу, получаем один и тот же набор задач, и школьнику за номером Ni-1 соответствует по второму условию школьник Ni. А так как номер N0 присвоен, то присвоены номера N1, N2, N3, N4, N5. Полученное противоречие показывает, что все номера присвоены и школьников ровно 32.


Решение задачи 2.Зафиксируем элемент a1 множества X={a1; a2; ; an} и будем рассматривать только подмножества, содержащие a1. Число таких подмножеств равно числу подмножеств множества {a2; ; an}, т.е. числу 2n-1. Следовательно, k
·2n-1.С другой стороны, пусть выбрано более чем 2n-1 подмножеств множества X.Разобьем все возможные подмножества множества X на 2n-1 пар, объединяя в пару подмножество и его дополнение. Тогда по принципу Дирихле хотя бы два выбранных подмножества обязательно составляют пару и, следовательно, не пересекаются. Таким образом, k= 2n-1 .

Решение задачи 3.
Заметим, что a>1, b>1.Рассмотрим дробь 9876543212009
9876543212008 .Воспользовавшись условиями задачи,запишем равенство: 9876543212009 =9876543212008b
9876543212008=9876543212007a .
Заметим, что 9876543212009 < 9876543212008
9876543212008 9876543212007.
Итак, 9876543212008b <9876543212008
9876543212007a 9876543212007.
Последнее неравенство можно записать так:

9876543212008 b *(9876543212007)b-a< 9876543212008
9876543212007 9876543212007.
Теперь делением на 9876543212008 получаем неравенство:
9876543212007
9876543212008 b-1 * (9876543212007)b-a<1.
9876543212007
Т.к. 9876543212008 >1, а b-1>0, то 9876543212008 b-1 >1.
9876543212007 9876543212007
Следовательно, (9876543212007)b-a<1, значит,b-a<0, т.е. a>b.

Решение задачи 4.
Очевидно, что если начать вращение первой шестерёнки ПРОТИВ часовой стрелки, то вторая начнёт вращаться ПО часовой стрелке, а третья ПРОТИВ часовой стрелки. Шифровалась первая буква. При этом цифра 0 на второй шестерёнке заменена на 9. Замена 0 на 9 могла произойти при повороте второй шестерёнки на 1 позицию или на 11 или на 21, 31. На третьей шестерёнке цифра 0 оказалась заменена на 4. Это могло произойти при повороте на 4 позиции или на 11 или 18 или 27 позиций. Из возможных вариантов для сдвига шестерёнок лишь число 11 является общим. Итак при шифровании первой буквы произошёл сдвиг на 11 позиций каждой шестерёнке, в том числе на первой. Таким образом, место под стрелкой заняла буква, отстоящая от А на 11 позиций. Сдвиг на одну позицию заменяет А на Б, сдвиг на две позиции заменит А на В, и т. д. Сдвиг на 11 позиций заменит А на К. Следовательно, первая буква открытого текста - это буква К.
Далее, пара цифр 94 при шифровании второй буквы перешла в 85. Цифра 9 на второй шестерёнке переходит в 8 при повороте на 1 позицию, а также на 11, 21, 31. А цифра 4 на третьей шестерёнке переходит в 5 при повороте на 8, 15, 22, 29. Мы видим, что общим для вариантов сдвига на двух шестерёнках является число 1, и только оно. Вывод: при шифровании второй буквы первая шестерёнка вращалась так, что буква К заменена на отстоящую от неё на ОДНУ ПОЗИЦИЮ, а это буква Л. И мы знаем первые две буквы открытого текста: КЛ. продолжая рассуждать описанным способом, находим (вычисляем!) все буквы.
Ответ: КЛЮЧШИФРА.
Решение задачи 5.
Начнем с четвертого слова второй строки.Слову из двух одинаковых букв ЗЗ может соответствовать в открытом тексте только слово ЕЁ(напомним,Е и Ё при шифровании не различались).Итак, при расшифровании нужно З заменить на Е(Ё).Теперь обратим внимание слова из трёх букв: ЕТЕ , ЙПЙ , ЕЙП.Будем рассматривать варианты слов из трёх букв, в которых первая и третья буквы одинаковы.Заметим, что мы должны поставить в соответствие словам ЕГЕ и ЙПЙ слова, не имеющие общих букв.Варианты для ЕГЕ и ЙПЙ: ТОТ, ТУТ, ОНО, КАК, ИЛИ, ЛИЛ ,ОКО, ОГОПри этом слово ЕЙП должно быть заменено на слово, имеющее смысл( в открытом тексте каждое слово осмысленно).Например, рассмотрим вариант: ЕГЕТОТ,ЙПЙКАК.Тогда ЕЙПТКА,получили слово, не имеющее смысла.Еще вариант:ЕГЕТОТ,ЙПЙИЛИ.Тогда ЕЙПТИЛ,снова нет смысла.Довольно быстро можно найти вариант:ЕГЕКАК,ЙПЙТОТ.При этом получаем:ЕЙПКТО.Таким образм, мы имеем соответствия:Е нужно заменить на К,Й на Т, П на О,Г на А.Конечно, мы могли не учесть еще возможные варианты для трехбуквенных слов русского языка, поэтому полученную таблицу замен следует считать пока ГИПОТЕЗОЙ, а не доказанным утверждением.Но эта гипотеза уже достаточно хорошо обоснована.Если же полученная часть таблицы замен ошибочна, то это обязательно выяснится, то есть мы на очередном этапе замен придем к слову, не имеющему смысла.Тогда придется вернуться к началу и искать другие варианты.Наша работа сейчас моделирует в миниатюре процесс ``взлома`` шифра: именно так часто и работают криптоаналитики, проверяя гипотезы.Итак, воспользуемся нашими знаниями: запишем текст,заменяя шифрообозначения буквами открытого текста.Шифрообозначения мы записали строчными буквами, а найденные буквы открытого текстапрописные:

а бвАд, КАК жЕиАТк бАлАмн.
а оКОжО жЕин ЕЁ. КТО жЕиАЕТ бАлАмр оКОжЕЕ,
ТОТ жЕирт сОткиЕ бАлАм. Ба КАулнд
бАлАмн вАмротадТоа ОмКр.

Теперь второе слово во второй строке оКОжО и слово оКОжЕЕ позволяют достаточно уверенно сделать замены: ОС, ЖР.Но тогда слово жЕиАЕТ – это РЕиАЕТ, то есть РЕШАЕТ, и у нас есть соответствие: ИШ.А это позволяет записать четвертое слово первой строки так: РЕШАТк, и ясно, что КЬ.Обратим внимание на слово в третьей строке жЕирт, с учетом новых соответствий это РЕШАрТ, то есть РЕШИТ,и мы уверенно заменяем Р на И.Далее, слово жЕин теперь записывается так: РЕШн,и букве Н соответствует,конечно, гласная.При этом гласные О, А, Е,И заняты.Из оставшихся гласных лишь У не противоречит условию осмысленности и грамматике.Итак, НУ. Запишем последнее слово: ОмКИ. И у нас есть достаточно оснований считать, что М соответствует Ч.Запишем снова текст, заменяя известные на этот момент шифрообозначения буквами открытого текста.

а бвАд, КАК РЕШАТЬ бАлАЧУ.
а СКОРО РЕШУ ЕЁ. КТО РЕШАЕТ бАлАЧИ СКОРЕЕ,
ТОТ РЕШИТ сОтЬШЕ бАлАЧ. бА КАулУд
бАлАЧУ вАЧИСтадТСа ОЧКИ.
Третье слово в третьей строке позволяет сделать вывод: СБ, Т Л. Теперь последние два слова выглядят так:
вАЧИСЛадТСа ОЧКИ.
Конечно, это означает, что ВН, АЯ, ДЮ. Значит, начало текста имеет вид:
Я бНАЮ,КАК РЕШАТЬ бАлАЧУ. И легко найти соответствия:БЗ, Л Д. Теперь слово КАулУд принимает вид:КАуДУЮ,и УЖ.

Ответ:
Я ЗНАЮ, КАК РЕШАТЬ ЗАДАЧУ.
Я СКОРО РЕШУ ЕЁ. КТО РЕШАЕТ ЗАДАЧИ СКОРЕЕ,
ТОТ РЕШИТ БОЛЬШЕ ЗАДАЧ. ЗА КАЖДУЮ
ЗАДАЧУ НАЧИСЛЯЮТСЯ ОЧКИ.








































3. ОБЗОР НЕКОТОРЫХ ОСНОВНЫХ ОНЯТИЙ КРИПТОГРАФИИ

Как передать нужную информацию нужному адресату втайне от других?
И много лет назад, и в наше время люди вынуждены решать эту задачу. Есть три возможности.
Создать абсолютно надежный, недоступный для других канал связи между абонентами.
Использовать общедоступный канал связи, но скрыть сам факт передачи информации.
Использовать общедоступный канал связи, но передавать по нему нужную информацию в преобразованном виде, так, чтобы восстановить ее мог только адресат.
Прокомментируем эти три возможности.
При современном уровне развития науки и техники сделать такой канал связи между удаленными абонентами для неоднократной передачи больших объемов информации практически нереально.
Разработкой средств и методов скрытия факта передачи сообщения занимается стеганография.
Первые следы стеганографических методов теряются в глубокой древности. Например, известен такой способ сокрытия письменного сообщения: голову раба брили, на коже головы писали сообщение и после отрастания волос раба отправляли к адресату.
Из детективных произведений хорошо известны различные способы тайнописи между строк обычного, незащищаемого текста: молоком или сложными химическими реактивами с последующей обработкой.
Также из детективов известен метод «микроточки»: сообщение записывается с помощью современной техники на очень маленький носитель (микроточку), который пересылается с обычным письмом, например, под маркой или где-нибудь в другом, заранее обусловленном месте.
3. Разработкой методов преобразования (шифрования) информации с целью ее защиты от незаконных пользователей занимается криптография. Такие методы и способы преобразования информации называются шифрами.
Шифрование (зашифрование) – процесс применения шифра к защищаемой информации, т. е. преобразование защищаемой информации (открытого текста) в шифрованное сообщение (шифртекст, криптограмму) с помощью определенных правил, содержащихся в шифре.
Расшифрование – процесс, обратный шифрованию, т. е. преобразование шифрованного сообщения в защищаемую информацию с помощью определенных правил, содержащихся в шифре.
Криптография – прикладная наука, она использует самые последние достижения фундаментальных наук и, в первую очередь, математики. С другой стороны, все конкретные задачи криптографии существенно зависят от уровня развития техники и технологии, от применяемых средств связи и способов передачи информации.
Предмет криптографии. Что же является предметом криптографии? Для ответа на этот вопрос вернемся к задаче тайной передачи информации.
Прежде всего заметим, что эта задача актуальна только для информации, которая нуждается в защите. Обычно в таких случаях говорят, что информация содержит тайну, или является защищаемой, приватной, конфиденциальной, секретной. Для наиболее типичных, часто встречающихся ситуаций такого рода введены даже специальные понятия: государственная тайна, военная тайна, коммерческая тайна, юридическая тайна, врачебная тайна и т. д.
Мы будем говорить о защищаемой информации, имея в виду следующие признаки такой информации:
– наличие строго определенного круга законных пользователей, которые имеют право владеть этой информацией;
– наличие незаконных пользователей, которые стремятся овладеть этой информацией с тем, чтобы обратить ее себе во благо, а законным пользователям во вред.
Для простоты мы вначале ограничимся рассмотрением только одной угрозы – угрозы разглашения информации. Существуют и другие угрозы для защищаемой информации со стороны незаконных пользователей: угроза подмены, имитации и др.
Отметим, что исторически в криптографии закрепились некоторые военные термины (противник, атака на шифр и др.). Они наиболее точно отражают смысл соответствующих криптографических понятий.
Криптография занимается методами преобразования информации, которые бы не позволили противнику извлечь ее из перехватываемых сообщений. При этом по каналу связи передается уже не сама защищаемая информация, а результат ее преобразования с помощью шифра. Таким образом, одна из важных задач криптографии – обеспечение конфиденциальности информации.
Вскрытие (взламывание, дешифрование) шифра – процесс получения защищаемой информации из шифрованного сообщения без знания примененного шифра.
Однако помимо перехвата и вскрытия шифра противник может пытаться получить защищаемую информацию многими другими способами. Наиболее известным из таких способов является агентурный, когда противник каким-либо путем склоняет к сотрудничеству одного из законных пользователей и с помощью этого агента получает доступ к защищаемой информации. В такой ситуации криптография бессильна.
Противник может пытаться не получить, а уничтожить или модифицировать защищаемую информацию в процессе ее передачи. Это – совсем другой тип угроз для информации, отличный от перехвата и вскрытия шифра. Для защиты от таких угроз разрабатываются свои специфические методы.
Следовательно, на пути от одного законного пользователя к другому информация должна защищаться различными способами, противостоящими различным угрозам. Возникает ситуация цепи из разнотипных звеньев, которая защищает информацию. Естественно, противник будет стремиться найти самое слабое звено, чтобы с наименьшими затратами добраться до информации. А значит, и законные пользователи должны учитывать это обстоятельство в своей стратегии защиты: бессмысленно делать какое-то звено очень прочным, если есть заведомо более слабые звенья («принцип равнопрочности защиты»).
Можно использовать хороший шифр для шифрования как можно большего количества сообщений. Однако при этом возникает опасность, что противник уже разгадал (вскрыл) шифр и читает защищаемую информацию. Если же в шифре есть сменный ключ, то, заменив ключ, можно сделать так, что разработанные противником методы уже не дадут эффекта.
Под ключом в криптографии понимают сменный элемент шифра, который применяется для шифрования конкретного сообщения. Например, в шифрах типа шифра Цезаря ключом является величина сдвига букв шифртекста относительно букв открытого текста.
Описанные соображения привели к тому, что безопасность защищаемой информации стала определяться в первую очередь ключом. Сам шифр, шифрмашина или принцип шифрования стали считать известными противнику и доступными для предварительного изучения, но в них появился неизвестный для противника ключ, от которого существенно зависят применяемые преобразования информации. Теперь законные пользователи, прежде чем обмениваться шифрованными сообщениями, должны тайно от противника обменяться ключами.
Отметим теперь, что не существует единого шифра, подходящего для всех случаев. Выбор способа шифрования зависит от особенностей информации, ее ценности и возможностей владельцев по защите своей информации. Прежде всего подчеркнем большое разнообразие видов защищаемой информации: документальная, телефонная, телевизионная, компьютерная и т. д. Каждый вид информации имеет свои специфические особенности, и эти особенности сильно влияют на выбор методов шифрования информации. Большое значение имеют объемы и требуемая скорость передачи шифрованной информации. Выбор вида шифра и его параметров существенно зависит от характера защищаемых секретов или тайны. Некоторые тайны (например, государственные, военные и др.) должны сохраняться десятилетиями, а некоторые (например, биржевые) – уже через несколько часов можно разгласить. Необходимо учитывать также и возможности того противника, от которого защищается данная информация. Одно дело противостоять одиночке , а другое дело – мощной государственной структуре.
Под атакой на шифр понимают попытку вскрытия этого шифра. Способность шифра противостоять всевозможным атакам на него называют стойкостью шифра.
Понятие стойкости шифра является центральным для криптографии. Хотя качественно понять его довольно легко, но получение строгих доказуемых оценок стойкости для каждого конкретного шифра – проблема нерешенная. Это объясняется тем, что до сих пор нет необходимых для решения такой проблемы математических результатов. Поэтому стойкость конкретного шифра оценивается только путем всевозможных попыток его вскрытия и зависит от квалификации криптоаналитиков, атакующих шифр. Такую процедуру иногда называют проверкой стойкости.
Важным подготовительным этапом для проверки стойкости шифра является продумывание различных предполагаемых возможностей, с помощью которых противник может атаковать шифр. Появление таких возможностей у противника обычно не зависит от криптографии, это является некоторой внешней подсказкой и существенно влияет на стойкость шифра. Поэтому оценки стойкости шифра всегда содержат те предположения о целях и возможностях противника, в условиях которых эти оценки получены.
Прежде всего, как это уже отмечалось выше, обычно считается, что противник знает сам шифр и имеет возможности для его предварительного изучения. Противник также знает некоторые характеристики открытых текстов, например, общую тематику сообщений, их стиль, некоторые стандарты, форматы и т. д.
Из более специфических приведем еще три примера возможностей противника:
– противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов;
– противник может перехватывать все шифрованные сообщения и добывать соответствующие им открытые тексты;
– противник имеет доступ к шифру (но не к ключам!) и поэтому может зашифровывать и дешифровывать любую информацию.
Математические основы криптографии. Большое влияние на развитие криптографии оказали появившиеся в середине XX в. работы американского математика Клода Шеннона. В этих работах были заложены основы теории информации, а также разработан математический аппарат для исследований во многих областях науки, связанных с информацией. Более того, принято считать, что теория информации как наука родилась в 1948 г. после публикации работы К. Шеннона «Математическая теория связи».
В другой своей работе, «Теория связи в секретных системах», Клод Шеннон обобщил накопленный до него опыт разработки шифров. Оказалось, что даже в очень сложных шифрах в качестве типичных компонентов можно выделить такие простые шифры как шифры замены, шифры перестановки или их сочетания.
Шифр замены является простейшим, наиболее популярным шифром. Типичными примерами являются шифр Цезаря, «цифирная азбука» Петра Великого и «пляшущие человечки» А. Конан Дойла. Как видно из самого названия, шифр замены осуществляет преобразование замены букв или других «частей» открытого текста на аналогичные «части» шифрованного текста. Легко дать математическое описание шифра замены. Пусть X и Y – два алфавита (открытого и шифрованного текстов соответственно), состоящие из одинакового числа символов. Пусть также g: X > Y – взаимнооднозначное отображение Х в Y. Тогда шифр замены действует так: открытый текст х1х2...хп преобразуется в шифрованный текст g(x1)g(x2)... g(хп).
Шифр перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Обычно открытый текст разбивается на отрезки равной длины и каждый отрезок шифруется независимо. Пусть, например, длина отрезков равна п и
· – взаимнооднозначное отображение множества {1, 2, ..., п} в себя. Тогда шифр перестановки действует так: отрезок открытого текста х1...хп преобразуется в отрезок шифрованного текста.
С целью повышения надежности шифрования шифрованный текст, полученный применением некоторого шифра, может быть еще раз зашифрован с помощью другого шифра. Всевозможные такие композиции различных шифров приводят к третьему классу шифров, которые обычно называют композиционными шифрами. Заметим, что композиционный шифр может не входить ни в класс шифров замены, ни в класс шифров перестановки.
Если ключ зашифрования совпадает с ключом расшифрования: kз = kр, то такие шифры называют симметричными, если же kз 13 EMBED Equation.3 1415 kр – асимметричными.
На протяжении многих веков среди специалистов не утихали споры о стойкости шифров и о возможности построения абсолютно стойкого шифра.
Важнейшим для развития криптографии был результат К. Шеннона о существовании и единственности абсолютно стойкого шифра. Единственным таким шифром является какая-нибудь форма так называемой ленты однократного использования, в которой открытый текст «объединяется» с полностью случайным ключом такой же длины.
Этот результат был доказан К. Шенноном с помощью разработанного им теоретико-информационного метода исследования шифров.
Обсудим особенности строения абсолютно стойкого шифра и возможности его практического использования. Типичным и наиболее простым примером реализации абсолютно стойкого шифра является шифр Вернама, который осуществляет побитовое сложение n-битового открытого текста и n-битового ключа:
yi = xi13 EMBED Equation.3 1415ki, i = 1,...,n.
Здесь x1...хп – открытый текст, k1,...,kп – ключ, у1...уn – шифрованный текст.
Подчеркнем, что для абсолютной стойкости существенным является каждое из следующих требований к ленте однократного использования:
1) полная случайность (равновероятность) ключа (это, в частности, означает, что ключ нельзя вырабатывать с помощью какого-либо детерминированного устройства);
2) равенство длины ключа и длины открытого текста;
3) однократность использования ключа.
В случае нарушения хотя бы одного из этих условий шифр перестает быть абсолютно стойким и появляются принципиальные возможности для его вскрытия (хотя они могут быть трудно реализуемыми).
Но, оказывается, именно эти условия и делают абсолютно стойкий шифр очень дорогим и непрактичным. Прежде чем пользоваться таким шифром, мы должны обеспечить всех абонентов достаточным запасом случайных ключей и исключить возможность их повторного применения. А это сделать необычайно трудно и дорого.
За сутки могут быть зашифрованы сотни тысяч слов. Создание миллионов ключевых знаков потребовало бы огромных финансовых издержек и было бы сопряжено с большими затратами времени. Так как каждый текст должен иметь свой собственный, единственный и неповторимый ключ, применение идеальной системы потребовало бы передачи по крайней мере такого количества знаков, которое эквивалентно всему объему передаваемой полезной информации.
В силу указанных причин абсолютно стойкие шифры применяются только в сетях связи с небольшим объемом передаваемой информации, обычно это сети для передачи особо важной государственной информации.
Теперь уже понятно, что чаще всего для защиты своей информации законные пользователи вынуждены применять неабсолютно стойкие шифры. Такие шифры, по крайней мере теоретически, могут быть вскрыты. Вопрос только в том, хватит ли у противника сил, средств и времени для разработки и реализации соответствующих алгоритмов. Обычно эту мысль выражают так: противник с неограниченными ресурсами может вскрыть любой неабсолютно стойкий шифр.
Как же должен действовать в этой ситуации законный пользователь, выбирая для себя шифр? Лучше всего, конечно, было бы доказать, что никакой противник не может вскрыть выбранный шифр, скажем, за 10 лет, и тем самым получить теоретическую оценку стойкости. К сожалению, математическая теория еще не дает нужных теорем – они относятся к нерешенной проблеме нижних оценок вычислительной сложности задач.
Поэтому у пользователя остается единственный путь – получение практических оценок стойкости. Этот путь состоит из следующих этапов:
1) понять и четко сформулировать, от какого противника мы собираемся защищать информацию; необходимо уяснить, что именно противник знает или сможет узнать о системе шифра, а также какие силы и средства он сможет применить для его вскрытия;
2) мысленно встать в положение противника и пытаться с его позиций атаковать шифр, т. е. разрабатывать различные алгоритмы вскрытия шифра, при этом необходимо в максимальной мере обеспечить моделирование сил, средств и возможностей противника;
3) наилучший из разработанных алгоритмов использовать для практической оценки стойкости шифра.
Здесь полезно для иллюстрации упомянуть о двух простейших методах вскрытия шифра: случайное угадывание ключа (он срабатывает с маленькой вероятностью, зато имеет маленькую сложность) и перебор всех подряд ключей вплоть до нахождения истинного (он срабатывает всегда, зато имеет очень большую сложность). Отметим также, что не всегда нужна атака на ключ: для некоторых шифров можно сразу, даже не зная ключа, восстанавливать открытый текст по шифрованному.
Формальные модели шифров. Для того чтобы иметь возможность доказывать в криптографии точные результаты, нужны математические модели основных исследуемых объектов, к которым относятся в первую очередь шифр и открытый текст. Как мы уже знаем, криптография защищает информацию с помощью шифрования – процедуры, использующей некое обратимое преобразование. При этом преобразование открытого текста в шифрованный называется зашифрованием, а обратный процесс – расшифрованием. Шифрование предполагает наличие множества обратимых преобразований. Выбор преобразования из указанного множества для зашифрования данного сообщения осуществляется с помощью ключа. Имеется однозначное соответствие между множеством ключей и множеством преобразований.
Выбор ключа естественным образом определяет функцию (вообще говоря, многозначную), отображающую множество возможных открытых текстов в множество возможных шифрованных текстов. Способ вычисления значения этой функции для произвольного аргумента будем называть правилом зашифрования. Выбранный ключ будем называть ключом зашифрования. Требование однозначности расшифрования определяет обратную функцию, отображающую множество возможных (при выбранном ключе) шифрованных текстов в множество возможных открытых текстов. Способ вычисления значения этой функции для произвольного аргумента будем называть правилом расшифрования. Ключ, определяющий выбор правила расшифрования, будем называть ключом расшифрования.
Неформально, шифр – это совокупность множеств возможных открытых текстов (то, что шифруется), возможных ключей (то, с помощью чего шифруется), возможных шифртекстов (то, во что шифруется), правил зашифрования и правил расшифрования.
Математические модели открытого текста. Потребность в математических моделях открытого текста продиктована, прежде всего, следующими соображениями. Во-первых, даже при отсутствии ограничений на временные и материальные затраты по выявлению закономерностей, имеющих место в открытых текстах, нельзя гарантировать того, что такие свойства указаны с достаточной полнотой. Например, хорошо известно, что частотные свойства текстов в значительной степени зависят от их характера. Поэтому при математических исследованиях свойств шифров прибегают к упрощающему моделированию, в частности, реальный открытый текст заменяется его моделью, отражающей наиболее важные его свойства. Во-вторых, при автоматизации методов криптоанализа, связанных с перебором ключей, требуется «научить» ЭВМ отличать открытый текст от случайной последовательности знаков. Ясно, что соответствующий критерий может выявить лишь адекватность последовательности знаков некоторой модели открытого текста.
Один из естественных подходов к моделированию открытых текстов связан с учетом их частотных характеристик, приближения для которых можно вычислить с нужной точностью, исследуя тексты достаточной длины. Основанием для такого подхода является устойчивость частот k-грамм или целых словоформ реальных языков человеческого общения (то есть отдельных букв, слогов, слов и некоторых словосочетаний).
Учет частот k-грамм приводит к следующей модели открытого текста. Пусть Р(k)(А) представляет собой массив, состоящий из приближений для вероятностей р(b1,b2,...,bk) появления k-грамм b1b2...bk в открытом тексте, k13 EMBED Equation.3 1415N,
А = (а1,...,ап) – алфавит открытого текста, bi13 EMBED Equation.3 1415A, i = 1, k.
Тогда источник «открытого текста» генерирует последовательность с1,с2,...,сk,сk+1,... знаков алфавита А, в которой k-грамма с1с2...сk появляется с вероятностью р(с1с2...сk) е Р(k)(А),
следующая k-грамма с1с2...сk+1 появляется с вероятность р(с2с3...сk+1)13 EMBED Equation.3 1415Р(k)(А) и т. д. Назовем построенную модель открытого текста вероятностной моделью k-го приближения.
Таким образом, простейшая модель открытого текста – вероятностная модель первого приближения – представляет собой последовательность знаков с1,с2,... , в которой каждый знак ci, i = 1,2,... , появляется с вероятностью р(сi) 13 EMBED Equation.3 1415 P(1)(A), независимо от других знаков. Будем называть также эту модель позначной моделью открытого текста. Модели открытого текста более высоких приближений учитывают зависимость каждого знака от большего числа предыдущих знаков. Чем выше степень приближения, тем более «читаемыми» являются соответствующие модели. Проводились эксперименты по моделированию открытых текстов с помощью ЭВМ.
О цифровой подписи. В настоящее время все большее распространение получает электронный документооборот, в связи с чем актуальной является задача выработки цифровой подписи и задача ее проверки. Электронная цифровая подпись (далее ЭЦП) для сообщения является числом, зависящим от самого сообщения и от некоторого секретного, известного только подписывающему субъекту, ключа. При этом она должна быть легко проверяемой без получения доступа к секретному ключу.
Цифровая подпись позволяет решить следующие задачи:
– осуществить аутентификацию источника сообщения;
– установить целостность сообщения;
– обеспечить невозможность отказа от факта подписи конкретного сообщения.
Приведем один из вариантов вычисления подписи (схема Эль-Гамаля). Для генерации пары ключей сначала выбирается простое число р и два случайных числа g и x, оба меньше р. Затем вычисляется . Открытый ключ: y, g, p. И g, и p можно сделать общими для группы пользователей. Секретным ключом является x.
Чтобы подписать сообщение М, сначала выбирается случайное число k, взаимно простое с р – 1. Затем вычисляется . Далее с помощью расширенного алгоритма Евклида решается следующее уравнение: .
Подписью является пара чисел а и b. Случайное значение k должно храниться в секрете. Для проверки подписи нужно убедиться, что .
Каждая подпись требует нового значения k, и это значение должно быть выбрано случайным образом. Если злоумышленник узнает k, используемое вами, то он сможет узнать ваш секретный ключ х. Если злоумышленник сможет получить два сообщения, пописанные с помощью одного и того же k, то он сможет раскрыть х, даже не зная k.
Приведем пример. Пусть р = 11, g = 2, секретный ключ х = 8. (Конечно, на практике используются числа из 120130 знаков, но сейчас мы хотим проиллюстрировать схему устным примером). Вычисляем: . Открытый ключ: y = 3, g = 2, р =1 1. Пусть нужно подписать сообщение М = 5. Будем считать, что выбрано случайное K = 9. Убеждаемся, что k и р – 1 взаимно просты: (9, 10) = 1. Вычисляем: . Теперь с помощью расширенного алгоритма Евклида находим b: , т. е. 5 = (8
·6 + 9
·b)mod10.
Решением будет b = 3, а подпись представляет собой пару: а = 6, b = 3.
Проверяющий вычисляет , сравнивает с . Так как , то подпись признается правильной, принимается.
Существует много других схем. В России с 2001 г. действует Государственный cтандарт цифровой подписи, основанный на эллиптических кривых. Принят также закон о цифровой подписи. Студенты, обучающиеся по специальности «Компьютерная безопасность», изучают подробно и математические основы алгоритма ЭЦП, и законы, регламентирующие применение ЭЦП.
Успехи, достигнутые в разработке схем цифровой подписи, позволили применить эти идеи также и к другим задачам взаимодействия удаленных абонентов. За последние годы криптография все шире входит в нашу жизнь и даже быт. Вот несколько примеров. Отправляя e-mail, мы в некоторых случаях отвечаем на вопрос меню: «Нужен ли режим зашифрования?» Владелец интеллектуальной банковской карточки, обращаясь через терминал к банку, вначале выполняет криптографический протокол аутентификации карточки. Пользователи сети Интернет наверняка знакомы с дискуссиями вокруг возможного принятия стандарта цифровой подписи для тех страниц, которые содержат «критическую» информацию (юридическую, прайс-листы и др.). С недавних пор пользователи сетей стали указывать после своей фамилии наряду с уже привычным «e-mail...» и менее привычное – «Отпечаток открытого ключа...». С каждым днем таких примеров становится все больше. Именно новые практические приложения криптографии и являются одним из источников ее развития.
















Библиографический список

1. Олимпиады по криптографии и математике для школьников / А. Ю. Зубов, А. В. Зязин, В. Н. Овчинников, С. М. Рамоданов. – М. : МЦНМО, 2006. – 136 с. : ил.
2. Морозова, Е. А. Международные математические олимпиады. Задачи, решения, итоги : пособие для учащихся /Е. А. Морозова, И. С. Петраков, В. А. Скворцов. – 4-е изд., испр. и доп. – М. : Просвещение, 1976. – 288 с. : ил.
3. Страшевич, С. Польские математические олимпиады / С. Страшевич, Е. Бровкин ; предисл. А. Пелчинского и А. Шинцеля ; пер. с польск. Ю. А. Данилова под ред. В. М. Алексеева. – М. : Мир, 1978. – 338 с. : ил.
4. Леман, А. А. Сборник задач московских математических олимпиад : пособие для внеклассной работы по математике / А. А. Леман ; под ред. В. Г. Болтянского. – М. : Просвещение, 1965. – 298 с. : ил.
5. Основы криптографии : учеб. пособие /А. П. Алфёров, А. Ю. Зубов, А. С. Кузьмин, А. В. Черёмушкин. – М. : Гелиос АРВ, 2001. – 480 с. : ил.
6. Овсянников, Э. Ф. От «А» до «Я»: словесные игры / Э. Ф. Овсянников. – Минск. : Полымя, 1994. – 233 с. : ил.
7. Берлов, С. Л. Петербургские математические олимпиады / С. Л. Берлов, С. В. Иванов, К. П. Кохась. – СПб. : Лань, 1998. – 448 с.
8. Зарубежные математические олимпиады /С. В. Конягин, Г. А. Тоноян, И. Ф. Шарыгин и др.; под ред. И. Н. Сергеева. – М. : Наука, 1987. – 416 с. – (Б-ка мат. кружка).
9. Избранные задачи по математике из журнала «American Mathematical Monthly» : учеб. пособие. : пер. с англ. / под ред. и с предисл. В. М. Алексеева. – 3-е изд. – М. : Либроком, 2009. – 600 с.
10. Шнайер, Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си / Б. Шнайер. – М. : Триумф, 2003. – 816 с. : ил.
11. Введение в криптографию / под общ. ред. В. В. Ященко ; Моск. центр непрерыв. мат. образования. – М., 2000. – 288 с.
12. Жданов, О. Н. Методы и средства криптографической защиты информации : учеб. пособие / О. Н. Жданов, В. В. Золотарев ; Сиб. гос. аэрокосмич. ун-т. – Красноярск, 2007. – 253 с.
* В криптографии традиционно используются термины «противник» и «атака на шифр».









13PAGE 15


13PAGE 145515








13 EMBED Equation.3 1415





































Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation Native

Приложенные файлы


Добавить комментарий