Целью курса является ознакомление слушателей с основными понятиями защиты информации, основными принципами построения систем защиты информации, а также основными категориями мер защиты информации, их возможностями с точки зрения защиты информации, сильными и слабыми сторонами. В процессе освоения курса слушатели получат навыки выбора решений из различных категорий методов и средств защиты информаций, соответствующих требованиям защиты информации в конкретных информационных системах, оценки соответствия существующих решений таким требованиям, разработки предложений по совершенствованию системы обеспечения информационной безопасности. Для освоения материала курса будут полезны основные знания из общего курса физики, высшей алгебры, теории чисел, информационных технологий. Их наличие позволит понять принципы действия криптографических средств защиты информации, средств технической защиты информации, а также цифровых стеганографических систем. В качестве эксперта в курсе участвует Алексей Викторович Уривский, заместитель генерального директора по науке и инновациям компании ИнфоТеКС (ОАО «Информационные Технологии и Коммуникационные Системы») – отечественного разработчика и производителя средств защиты информации, действующего с 1989 года, являющегося одной из крупнейших компаний России в сфере защиты информации.
Шифр многоалфавитной замены и его анализ
Loading...
Из курса от партнера National Research University Higher School of Economics
Методы и средства защиты информации
13 оценок
Из урока
ИСТОРИЧЕСКИЙ ОБЗОР КРИПТОГРАФИЧЕСКИХ МЕТОДОВ ЗАЩИТЫ ИНФОРМАЦИИ
Добрый день, уважаемый слушатель! В этом модуле вы познакомитесь с историей развития криптографических методов защиты информации с древних времён до наших дней. Вместе мы окунёмся в увлекательное путешествие и узнаем, как сохраняли информацию в тайне наши предки и какие есть возможности для дальнейшего развития защиты информации на сегодняшний день. Желаем успехов в изучении!
Познакомьтесь с преподавателями
Сорокин Александр ВладимировичСтарший преподаватель
МИЭМ им. А. Н. Тихонова НИУ ВШЭ
[МУЗЫКА] Следующим этапом эволюции
шифров явился шифр многоалфавитной замены, который давайте далее рассмотрим.
Основное слабое место шифра простой замены заключалось в том,
что он подвержен частотному анализу, а это происходило из-за того, что все буквы
открытого текста зашифровывались по одной единожды определенной таблице.
Отход от этого положения, то есть от того,
что таблица единожды определена и каждая буква имеет свою замену,
которая применяется в течение всего шифра, пусть даже и таких замен несколько
вариантов — есть переход к так называемой многоалфавитной замене.
Впервые такую идею выдвинул Леон Батиста Альберти в 1466 году
в труде «Трактат о шифрах».
Он предложил использовать специальный шифровальный диск, у которого один из двух
надетых на одну ось дисков мог вращаться относительно другого, таким образом
меняя алфавиты зашифрования через какое-то количество символов открытого текста.
Сам Альберти назвал свой диск шифром, «достойным королей».
В различных описаниях, в том числе в трудах последователей Альберти,
содержатся описания множества, как бы режимов применения этого шифра,
то есть того, каким образом его следует использовать, но чаще всего самому
Альберти приписывается следующий принцип зашифрования.
В диске Альберти буквы открытого текста, они же и буквы шифр-текста,
на внешнем неподвижном диске записаны в алфавитном порядке,
а на внутреннем диске, который мог вращаться, — в произвольном.
То есть смешанный алфавит на нем был записан.
В классическом диске Альберти на внутреннем диске помимо букв существовали
еще дополнительные обозначения, то есть могли заменяться цифры,
но мы рассмотрим такой вариант диска,
более позднюю его интерпретацию, в которой на обоих дисках просто указан алфавит.
На внешнем — в естественном порядке, а на внутреннем — смешанный алфавит.
В данном примере, который сделан для букв русского языка,
требуется для реализации того режима, который приписывается чаще всего Альберти,
установить некую первую выбранную букву напротив первой буквы алфавита.
Пусть это будет буква «м»,
ее мы устанавливаем напротив буквы «А» на внешнем диске.
На рисунке слева это положение изображено.
Тогда эту первую букву, которую мы установили напротив буквы «А»,
мы записываем как заглавную в нашем шифр-тексте.
Через, допустим, пять символов (в нашем примере через пять), мы эту букву сменим.
Допустим, требуется зашифровать слово «Венеция».
Тогда мы отыскиваем каждую букву открытого текста на внешнем диске и
заменяем ее на соответствующую букву на внутреннем диске.
Значит, первая буква «В» заменяется на букву «а»,
далее буква «Е» на букву «ч», далее буква «Н» на букву «д»,
буква «Е» опять же на букву «ч», и затем, пятая буква,
в первой пятерке буква «Ц» заменяется на букву «т»,
после чего мы порядок взаимного расположения дисков меняем.
Устанавливаем напротив буквы «а», например букву «р».
И продолжаем шифровать по той же схеме.
При этом букву «Р» записываем как заглавную в наш шифр-текст.
В итоге наш шифр-текст имеет вот такой вид: «Мачдчт Ръэ».
Получатель, видя этот шифр-текст по заглавным буквам, определяет,
какие буквы нужно установить напротив первой буквы алфавита на внешнем диске,
и после чего отыскивает буквы шифр-текста на внутреннем диске,
заменяет их на соответствующие буквы на внешнем диске.
Таким образом, читает открытый текст.
Данный способ шифрования не использует никакого ключа в общем-то,
поскольку все параметры зашифрования передаются вместе с сообщением,
но в диске Альберти ключевым элементом, то есть секретом,
считалось именно расположение букв на внутреннем диске.
Диск Альберти не сразу получил широкое признание, в частности потому,
что это действительно были металлические диски,
вероятнее всего было изготовлено небольшое количество таких устройств,
поэтому быстро и легко менять ключ было неудобно,
и если вдруг расположение букв на этом диске становилось кому-то известным,
то секрет переставал быть секретом, и нарушитель мог таким образом читать
секретную переписку двух абонентов, что было, разумеется, неудобно,
и ограничивало распространение диска Альберти.
Но диск эволюционировал, и последователи Альберти довели его до
такого состояния, в котором он заслужил признание и стал популярен.
В 1518 году Иоганнес Тритемий предложил вместо того,
чтобы использовать диск, просто записать алфавиты замены,
сохраняя тот же порядок букв, в виде таблицы, притом,
что каждая строка этой таблицы просто циклически сдвигается на один символ.
В самом деле, не так важно как расположены символы в этом смешанном алфавите,
поскольку более секретно то, в каком порядке эти алфавиты применяются.
Это более разумно сделать ключом.
Но тогда встает вопрос о том,
в каком порядке выбирать эти строки в такой получившейся таблице.
То есть если говорить о диске Альберти,
в каком порядке устанавливать взаимное расположение дисков.
Вот в 1553 году итальянец Джованни Белазо предложил использовать
для этого так называемый пароль, или лозунг, для выбора этих алфавитов замены,
то есть строк таблицы Тритемия.
Ну это было некое слово, каждая буква которого отыскивалась в первой
колоночке этой таблицы, и таким образом выбиралась та или иная строка.
Далее, Джамбаттиста делла Порта где-то до 1563 года,
когда он опубликовал свою книгу, предложил использовать случайные алфавиты замены.
То есть в каждой строке записывать не сдвинутый на некоторое количество
символов естественный алфавит, а перемешанные буквы,
но при этом во всех строках снова одинаковые со сдвигом.
Просто не в естественном порядке, а в перемешанном.
На самом деле, это не усиливает стойкости шифра, если используются правильным
образом выбранный и составленный пароль или лозунг, как предлагал Белазо.
Ну и итоговую версию этого шифра предложил француз Блез де Виженер в 1585 году,
и в таком виде этот шифр, в общем-то придуманный не столько Виженером,
сколько его предшественниками (он просто обобщил их предложения и результаты),
данный шифр получил его имя в дальнейшем и сейчас известен как шифр Виженера.
Он представляет собой вот такую квадратную таблицу, в которой в заголовках
строк и столбцов также указан алфавит в естественном порядке,
а в каждой строке за заголовочным столбцом каждая строка имеет
циклический сдвиг на один символ влево, и таким образом, по сути,
представляет собой замену по шифру Цезаря на некоторое количество символов.
Тогда берется некий ключ, который определяет то,
какие строки таблицы следует выбирать.
В классической версии шифра Виженера ключ достаточно короткий,
он многократно меньше, чем длина текста, который требуется зашифровать,
и давайте рассмотрим пример того, как зашифровывается текст Attack tonight,
то есть «Атакуйте сегодня вечером», с ключевым словом «темнота»,
или по-английски dark.
Для того чтобы использовать этот ключ для длинного текста, его нужно несколько
раз повторить столько, сколько требуется, для того чтобы каждому символу
открытого текста поставить в соответствие какой-то символ ключевого слова.
Пример этого вам показан на слайде.
После этого мы отыскиваем символ открытого текста в заголовке столбца,
а символ ключевого слова — в заголовке строки.
Тогда символ шифр-текста мы видим на пересечении этих строки и столбца.
Первый символ нашего шифр-текста зашифровывается в букву D, то
есть остается буква первая без изменения относительно символа ключевого слова.
Это происходит всякий раз, когда в открытом тексте мы встречаем букву A,
то есть первую букву алфавита, поскольку в этом случае мы действуем в первом столбце,
в котором буквы совпадают с буквами заголовочного столбца.
Следующая буква у нас встречается в первой строке,
поскольку уже в ключевом слове мы видим букву A.
Далее, мы продолжаем это шифрование по такой же схеме, выбирая всякий раз букву,
стоящую на пересечении столбца, помеченного буквой
открытого текста и строки, помеченной буквой из ключевого слова.
И продолжая этот порядок, мы получаем вот такой шифр-текст.
Данный шифр-текст хорош тем, что в нем разрушены закономерности,
которые используются для частотного анализа.
В нем одинаковые символы могут заменять совершенно разные буквы, и наоборот,
одинаковые буквы открытого текста могут вполне без нарушения каких-либо
закономерностей шифра заменяться разными буквами.
Поэтому частотный анализ неприменим, поскольку если мы посчитаем, например,
сколько раз здесь встречается буква K, то никакой информации о том,
как это связано с закономерностями естественного языка, мы не получим,
поскольку не один какой-то конкретный символ заменяет эти символы замены,
а разные символы, зависящие от того, какое ключевое слово мы выбрали.
Данный шифр на протяжении достаточно длительного времени (с XVI века до
примерно середины XIX века) считался не взламываемым, абсолютно стойким, надежным.
Однако математика позволила найти подход и к такому шифру, и этот метод
взлома стал известен как тест Касисски в честь некоего прусского офицера Касисски,
который опубликовал книгу, содержащую данный метод анализа шифра Вижинера.
Данный результат был также получен за несколько лет до публикации
этой книги англичанином Бэббиджем.
Но по некоторым сведениям, Бэббидж был связан с английскими спецслужбами и
опубликовать такой результат ему не позволили,
поскольку несколько дипломатических служб разных государств, шифры которых
английские спецслужбы желали читать, были уверены в надежности шифра Вижинера,
и опубликуй Бэббидж свою книгу, наверняка сменили бы шифр на что-то более надежное,
что не позволило бы англичанам продолжать чтение чужой переписки.
Тест Касисски заключается в следующем.
Он основан на том, что если где-то в шифртексте встречаются одинаковые
подстроки, то это может означать одно из двух: либо так случайно совпало,
либо это одинаковые кусочки открытого текста,
зашифрованные одинаковыми же фрагментами ключа.
Начиная с некоторой длины этих подстрок, примерно с четырех символов,
вероятность случайного совпадения становится очень-очень маленькой,
ей можно пренебречь.
То есть одинаковые подстроки длиной где-то от четырех символов и более почти
однозначно означают, что в этом месте одинаковые фрагменты открытого текста
совпали с одинаковыми же фрагментами ключа.
И именно на этом обстоятельстве основан так называемый тест Касисски.
Он состоит из двух этапов.
На первом этапе определяется та самая длина ключа,
которая вообще неизвестна в шифре Вижинера.
Для этого отыскиваются эти самые пары одинаковых подстрок в шифртексте,
вычисляются расстояния между их одинаковыми элементами, например между
первыми символами или между последними – главное, что именно между одинаковыми.
После чего составляется таблица расстояний и для этих расстояний выписываются
делители.
Затем общие делители рассматриваются как возможные длины ключа,
проверяются такие гипотезы.
Ну а уже на втором этапе определяются сами символы ключа,
после чего, зная таблицу Вижинера, которая не является секретной,
не составляет уже никакого труда прочесть открытый текст.
Для того чтобы определить символы ключа, шифртекст делится на группы,
зашифрованные одним шифралфавитом, то есть одной строкой, то есть, по сути,
соответствующей одному и тому же символу ключа, и затем для каждой такой группы
проводится частотный анализ как для шифра простой замены.
Или по гистограмме определяется сдвиг – порядковый номер алфавита.
Если для букв, зашифрованных одним таким алфавитом построить гистограмму,
то есть столбчатый график, то будет видно,
какие буквы заменяют наиболее частые буквы в открытом тексте.
Поняв, что это за буквы, можно вычислить, насколько они сдвинуты
относительно гистограммы открытого текста без какой либо замены, то есть,
если в английском языке самая частая буква – это буква «e», то можно найти
самую частую букву в этой группе, то есть явный пик в этой столбчатой диаграмме,
посмотреть на сколько символов она сдвинута, это буква, заменяющая букву «e»,
и понять, какой сдвиг применен в данной строке таблицы Вижинера,
то есть какой символ ключа использован для этой строки.
Рассмотрим пример.
Здесь зашифрован некий художественный текст.
В нем мы находим ряд одинаковых подстрок, после чего составляем таблицу,
в которой расставляем возможные делители этих длин.
Здесь у нас интервалы между повторениями – 95, 5, 20 и 120 символов.
Здесь нам совсем повезло: здесь единственный общий делитель – это 5.
Вероятнее всего, он и есть длина ключа, что мы и проверяем,
разделяя наш шифртекст на группы,
зашифрованные различными символами ключа данного шифра.
Вот эти символы, первые в каждой пятерке, зашифрованы одним, по предположению,
символом ключа, то есть соответствуют одной строке в таблице Вижинера.
Эти символы, вторые в каждой пятерке, – вторым символам...
третьим, четвертым, пятым...
И для каждой такой группы мы можем применить частотный анализ и восстановить
значения открытого текста и прочесть этот текст.
Таким образом, шифр Вижинера,
наиболее совершенная версия шифра многоалфавитной замены,
тоже оказался взламываемым, то есть уязвимым к дешифрованию.
Поэтому в дальнейшем требовалось придумать что-то более совершенное,
ну, например, каким-то образом удлинить ключ с тем,
чтобы такой тест Касисски не мог бы быть слишком простым и желательно вообще не был
бы очень простым, но новые требования к шифру формировались,
главным образом, в процессе применения его в военных действиях.
О требованиях к шифрам при их массовом применении мы поговорим в следующей части.
[МУЗЫКА] [МУЗЫКА]
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
