Проектная работа 4 на страницах 277-278, ГДЗ по алгебре за 9 класс к учебнику Мерзляка
План доклада:
1. Тайнопись древности: шифр Цезаря.
2. Шифр простой замены и правило произведения.
3. Частотный анализ.
4. Многоалфавитный шифр Виженера.
5. Шифровальные машины и шифры с открытым ключом.
Презентация к докладу: «От тайнописи к криптографии», 7 слайдов (.pptx)
Основное содержание.
1. Тайнопись древности: шифр Цезаря. Цель работы — описать, как тайнопись превратилась в математическую науку криптографию. Юлий Цезарь заменял каждую букву буквой, стоящей в алфавите на три места дальше. Пронумеруем буквы алфавита без Ё от 1 (А) до 32 (Я): к номеру буквы прибавляют 3, а если сумма больше 32, вычитают 32. Слово ШИФР (номера 25, 9, 21, 17) переходит в номера 28, 12, 24, 20, то есть в ЫЛЧУ, а буква Я — в букву В: \(32 + 3 - 32 = 3\). Возможных сдвигов всего 31, поэтому такой шифр взламывают перебором.
2. Шифр простой замены и правило произведения. В шифре простой замены буквы заменяют по таблице-ключу. Замену для А можно выбрать 32 способами, для Б — 31 способом и т. д., поэтому ключей по правилу произведения \(32 \cdot 31 \cdot 30 \cdot \ldots \cdot 2 \cdot 1\). Каждый из 22 множителей 11, 12, …, 32 больше 10, значит, ключей больше \(10^{22}\). Компьютеру, проверяющему миллиард ключей в секунду, нужно больше \(10^{22} : 10^9 = 10^{13}\) с, а в году меньше \(3{,}2 \cdot 10^7\) с, поэтому перебор займёт больше \(10^{13} : (3{,}2 \cdot 10^7) = 312\,500\) лет.
3. Частотный анализ. В русских текстах чаще всего встречается буква О (около 11 % букв), затем Е, А, И, поэтому в шифре замены самая частая буква шифровки обычно обозначает О; этот приём описал ещё в IX в. арабский учёный аль-Кинди. Пример: шифровка ЕФИ ШСУСЫС, ЪХС ШСУСЫС НСРЪГИХФВ получена шифром Цезаря с неизвестным сдвигом. Из 27 её букв 8 — буквы С (частота \(\frac{8}{27} \approx 0{,}3\)), остальные встречаются не больше двух раз. Считаем, что С (номер 18) обозначает О (номер 15), тогда сдвиг равен \(18 - 15 = 3\). Вычитая 3 из номера каждой буквы (если разность меньше 1, прибавляем 32), получаем: ВСЕ ХОРОШО, ЧТО ХОРОШО КОНЧАЕТСЯ.
4. Многоалфавитный шифр Виженера. Чтобы скрыть частоты букв, в XVI в. стали применять шифр, который связывают с именем Б. де Виженера: к номеру каждой буквы прибавляют номер очередной буквы ключевого слова (ключ повторяют), а если сумма больше 32, вычитают 32. Пример: слово ОКОЛО с ключом ЛЕС: \(15 + 12 = 27\) (Ъ), \(11 + 6 = 17\) (Р), \(15 + 18 - 32 = 1\) (А), \(12 + 12 = 24\) (Ч), \(15 + 6 = 21\) (Ф), шифровка — ЪРАЧФ. Три буквы О зашифрованы по-разному, и подсчёт частот не помогает. Ключей длины 5 по правилу произведения \(32^5 = 33\,554\,432\); способ взлома этого шифра нашли лишь в XIX в.
5. Шифровальные машины и шифры с открытым ключом. В XX в. шифровали машины (например, немецкая «Энигма»), а в 1940-х гг. В. А. Котельников и К. Шеннон независимо доказали, что шифр со случайным одноразовым ключом не короче сообщения взломать невозможно. В 1977 г. Р. Ривест, А. Шамир и Л. Адлеман предложили шифр RSA с открытым ключом: зашифровать может каждый, а расшифровать — лишь тот, кто знает разложение большого числа на простые множители. Учебный пример: \(n = 3 \cdot 11 = 33\), открытый ключ 3, секретный 7, причём \(3 \cdot 7 - 1 = 20 = (3 - 1) \cdot (11 - 1)\). Число 4 шифруют остатком от деления \(4^3\) на 33: \(4^3 = 64 = 33 \cdot 1 + 31\). Расшифровка — остаток от деления \(31^7\) на 33. Произведение даёт тот же остаток, что и произведение остатков множителей, а \(31^2 = 961 = 33 \cdot 29 + 4\), поэтому \(31^7 = 31^2 \cdot 31^2 \cdot 31^2 \cdot 31\) даёт тот же остаток, что и \(4 \cdot 4 \cdot 4 \cdot 31 = 1984 = 33 \cdot 60 + 4\), — получаем исходное число 4.
Резюме: Подводя итоги, можно сказать, что тайнопись стала математической наукой: стойкость шифра оценивают числом ключей по правилу произведения, шифры замены взламывают по частотам букв, а шифры с открытым ключом опираются на теорию чисел — на трудность разложения больших чисел на простые множители.
