1. Криптографические системы «докомпьютерной эры» и проблемы современной криптографии
1.1 Криптография древнего мира. Шифр Цезаря и его криптостойкость
Истоки криптографии ведут нас к Древнему Египту около 4000 лет назад, когда использовались иероглифы, которые в свое время произошли от пиктографии. В письмах где были нарисованы иероглифы, часто писали идеограммами и из-за того что эти письма читались, но не говорились вслух, так как это были лишь рисунки, которые выражали действие или событие, начали создаваться фонограммы по принципу ребусов. В основном, египтяне использовали подобные письма не для того, чтобы затруднить чтение, а скорее всего, писцы этого народа пытались превзойти друг друга своим остроумием и изобретательностью, кроме того пытались придать письму необычный и загадочный вид, тем самым привлечь особое внимание в свою сторону.
Чаще всего в Египте использовали шифрование в написании религиозных текстов и медицинских рецептов. Но, помимо этого они также пользовались и символическим языком. Так, в 1998 году был дешифрован текст, записанный на каменных плитах. Этому тексту более 6000 лет и он получил название Великие Арканы Таро. В нем в символической форме говорится о принципах мироздания, об абсолютной и относительной истине.
В криптографии древних времен были два вида шифрования: перестановка и замена. Одним из примеров замены является Шифр Цезаря, которая будет рассмотрена далее.
Шифр Цезаря назван в честь Юлия Цезаря, который использовал данный метод шифрования при помощи «сдвига» букв на 3 порядка вперед для того, чтобы защищать военные сообщения. Хотя Цезарь и является первым человеком, использовавшим эту схему, другие шифры подстановки использовались и до него.
Шифрование по схеме Цезаря ведется следующим образом: используется ключ k=3 и каждый символ открытого текста делает 3 «сдвига вперед». Если зашифровать русский алфавит используя шифр Цезаря, то можно получить следующее:
Исходный алфавит: А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я |
Шифрованный: Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В |
То есть, буква «С» «сдвигается» на три буквы вперёд и становится буквой «Ф». Твёрдый знак, перемещённый на три буквы вперёд, становится буквой «Э», и так далее.
Если пронумеровать каждый символ алфавита начиная с нуля, то шифрование и дешифрование можно выразить формулами модульной арифметики:
.
Где x — символ открытого текста, y — символ шифрованного текста, n — мощность алфавита, а k — ключ.
Приведем пример:
Съешь же ещё этих мягких французских булок, да выпей чаю.
Используя таблицу, где был зашифрован русский алфавит, находим соответствующие символы данного текста в первой строке и заменяем их символами, которые находятся под ними во второй строке. И получаем вот такой зашифрованный текст:
Фэзыя йз зьи ахлш пвёнлш чугрщцкфнлш дцосн, жг еютзм ъгб.
Во времена Цезаря данная схема шифрования была весьма безопасна, так как большинство его врагов были не грамотными и думали, что сообщения были написаны на неизвестном иностранном языке.
Шифр Цезаря со сдвигом на один используется на обратной стороне мезузы, чтобы зашифровать имена Бога. Вероятно, такое шифрование мезузы делалось в ранние времена, когда еврейскому народу не резрешили иметь мезузы.
Также Шифр Цезаря со сдвигом на тринадцать также используется в алгоритме ROT13, простом методе запутывания текста, широко используемого в Usenet.
В 19-ом столетии личная секция рекламных объявлений в газетах иногда использовалась, чтобы обмениваться сообщениями, зашифрованными с использованием простых шифров. Кан (1967) описывает случаи, когда любители участвовали в секретных коммуникациях, зашифрованных с использованием шифра Цезаря в «Таймс». Даже позднее в 1915, шифр Цезаря находил применение: российская армия использовала его как замену для более сложных шифров, которые оказались слишком сложными для войск.
Рисунок 1. Диск с шифром Цезаря
Чтобы было удобно пользоваться шифром Цезаря, можно взять 2 диска с разными диаметрами, затем насадить их на общую ось и прорисовать по краям дисков алфавитами. Изначально диски нужно повернуть так, чтобы напротив каждой буквы алфавита внешнего диска находилась та же буква алфавита малого диска. Если теперь повернуть внутренний диск на несколько символов, то мы получим соответствие между символами внешнего диска и внутреннего — шифр Цезаря. Получившийся диск можно использовать как для шифрования, так и для расшифровки.
Таблица 1. Примеры шифра Цезаря с различными сдвигами
Например, если внутреннее колесо повернуть так, чтобы символу A внешнего диска соответствовал символ D внутреннего диска, то мы получим шифр со сдвигом 3 влево.
Взлом Шифр Цезаря может пройти легко, даже если взломщик знает только зашифрованный текст. Можно рассмотреть две ситуации:
взломщик знает (или предполагает), что использовался простой шифр подстановки, но не знает, что это — схема Цезаря;
взломщик знает, что использовался шифр Цезаря, но не знает значение сдвига.
В первом случае шифр может быть взломан, используя те же самые методы, что и для простого шифра подстановки. Используя эти методы, взломщик, наверняка быстро заметит регулярность в решении и поймёт, что используемый шифр — это шифр Цезаря.
Во втором случае, взлом шифра проходит еще проще. Есть не так много вариантов значений сдвига (26 для английского языка), и все они могут быть проверены методом грубой силы. Один из способов сделать это — выписать отрывок зашифрованного текста в столбец всех возможных сдвигов — техника, которая иногда называется как «завершение простого компонента». Рассмотрим пример для зашифрованного текста «EXXEGOEXSRGI». Открытый текст можно опознать уже в четвертой строке.
Для обычного текста на естественном языке, скорее всего, будет только один вариант декодирования. Но, если использовать очень короткие сообщения, то есть случаи, когда возможны несколько вариантов расшифровки с различными сдвигами. Например, зашифрованный текст MPQY может быть расшифрован как «aden» так и как «know» (предполагая, что открытый текст написан на английском языке). Точно также «ALIIP» можно расшифровать как «dolls» или как «wheel»; «AFCCP» как «jolly» или как «cheer».
Если одно и то же сообщение зашифровать 2 раза, это не улучшить результат. То есть, если сперва зашифровать сообщение, к примеру со сдвигом на 3, а потом зашифровать это же сообщение со сдвигом на 3, то это то же самое, что если зашифровать это сообщение со сдвигом на 6.