tanenbaum_seti_all.pages (525408), страница 221
Текст из файла (страница 221)
В этом случае 1 становится ключом к общему методу циклически сдвигаемых алфавитов. Шифр Цезаря, возможно, и сумел обмануть жителей Помпеи, но с тех пор ему более уже никого не удалось ввести в заблуждение. Следующее усовершенствование состоит в установлении соответствия каждому встречающемуся в открытом тексте символу другого символа. Например, открытый текст: а Ь с й е ! я Ь !1 !г 1 т и о р г! г з ! и ъ х у х зашифрованный текст: Я% Е К Т У У 1 О Р А 3 Р Е С Н ! К !. Е Х С Ч В И М Такая система называется моноалфавитной подстановкой, ключом к которой является 26-символьная строка, соответствующая полному алфавиту. В нашем примере слово агщй будет выглядеть, как ЯУУЯЕА. На первый взгляд такая система может показаться надежной, так как даже если криптоаналитику известна общая система, он не знает, какой из 26! ~ 4 10" вариантов ключа применить.
В отличие от шифра Цезаря, применение метода простого перебора в данном случае весьма сомнительна. Даже при затратах 1 нс на проверку одного варианта ключа, чтобы перепробовать все ключи, компьютеру понадобится около 10" лет. Тем не менее, подобный шифр легко взламывается даже при наличии довольно небольших кусков зашифрованного текста. Для атаки шифра может быть использовано преимущество статистических характеристик естественных языков. Например, в английском языке, буква е встречается в тексте чаще всего. Следом за ней по частоте использования идут буквы г, о, а, и, ! и т. д. Наиболее часто встречающимися комбинациями из двух символов (биграммами) являются Й, Й, ег, гв и ап.
Наиболее часто встречающимися комбинациями из трех символов, или триграммами, являются Йе, !пя, апп и юп. Криптоаналитик, пытающийся взломать моноалфавитный шифр, начнет с того, что сосчитает относительные частоты всех символов алфавита, Затем он может попытаться заменить наиболее часто встречающийся символ буквой е, а следующий по частоте — буквой д Затем он посмотрит на триграммы и попытается найти что-либо похожее на гХе, после чего он сможет предположить, что Х вЂ” это й.
диалогично, если последовательность Йуг встречается достаточно часто, то, вероятно, У обозначает символ а. Обладая этой информацией, криптоаналитик может поискать часто встречающуюся триграмму вида аЕИ', что, скорее всего, означает апй Продолжая в том же духе, угадывая буквы, биграммы, триграммы и зная, какие последовательности символов являются наиболее вероятными, криптоаналитик побуквенно восстанавливает исходный текст. Криптография 828 Метод перестановки Шифры, основанные на методе подстановки, сохраняют порядок символов, но подменяют их.
Шифры, использующие метод перестановки, меняют порядок следования символов, но не изменяют сами символы. На рис. 8.2 показан простой перестановочный шифр с колоночной перестановкой. Ключом к шифру служит слово или фраза, не содержащая повторяющихся букв. В данном примере в качестве ключа используется слово МЕСАВПСК. Цель ключа — пронумеровать колонки. Первой колонкой становится колонка под буквой, расположенной ближе всего к началу алфавита, и т. д.
Открытый текст записывается горизонтально в строках. Шифрованный текст читается по колонкам, начиная с колонки с младшей ключевой буквой. МЕЯАВОСК Т 4 З рге 2 в 3 з е ! г Открытый текст а и в 1 в г о п ргеаве1гапвйггопепт11!!опас!!ага!о гпувч1вкЬапхассоипГв1хвноьто его!11 С о 1 1 в !оп г в ! 1 в в Зашифрованный текст АРЫ.ЗКЗОЗЕЬАУУА1АТООЗЗСТСЬММОМАМТ ЕЗгкУМТЮЯММТЗОУУОРАЕСОВСОЕН1Я!СХВ о гп у в ы васка с с о х ! тт с с Рис.
В.2 и ! в 1 о!игра Пврестановонный шифр Другой метод заключается в угадывании сразу целого слова или фразы. Например, рассмотрим следующий зашифрованный текст, полученный от бухгалтерской фирмы (разбитый на блоки по пять символов): СтВМХ ВУСТС Вт)1)3 ОХВХ8 СВТ)С ВТ8)!(гХ СТЦТ2 С(~ЧЦ) Р~8О8 Т)ЦЕХ МХЩЯ Ъ"ЕХБХ ЧБЕ)() .П)БТЯ „(Я(Л)Б )()ВХ) ОБКЯ) (ЯХТК ВОАЯ ЕВСт ТЕСТЕ ВХУВХ 0)811(г В сообщении бухгалтерской фирмы, скорее всего, должно встречаться слово )гпапсга1 (финансовый). Используя тот факт, что в этом слове буква г встречается дважды, разделенная четырьмя другими буквами, мы будем искать в зашифрованном тексте повторяющиеся символы, отстоящие друг от друга на это расстояние.
В результате мы найдем 12 таких мест в тексте в позициях 6, 15, 27, 31, 42, 48, 56, 66, 70, 71, 76 и 82. Однако только в двух случаях, в позициях 31 и 42, следующий символ (соответствующий букве и в открытом тексте) повторяется в соответствующем месте. Из этих двух вариантов символ а будет иметь правильное расположение только для позиции 31. Таким образом, теперь нам известно, что слово (тапсга1 начинается в позиции 30. Далее можно продолжать, применяя лингвистическую статистику английского языка и угадывая целые слова.
824 Глава 8. Безопасность в сетях Чтобы взломать перестановочный шифр, криптоаналитик должен вначале понять, что он имеет дело именно с перестановочным шифром. Если взглянуть на частоту символов Е, Т, А, О, Е й( и т. д., легка заметить, что их частоты соответствуют нормальным частотам открытого текста. В таком случае очевидно, что этот шифр является перестановочным, так как каждая буква в таком шифре представляет сама себя. Затем нужно угадать число колонок.
Во многих случаях по контексту сообщения можно угадать слово или фразу. Например, предположим, что криптоаналитик подозревает, что где-то в сообщении должно встретиться словосочетание т(111опЫоПагз. Обратите внимание, что в результате того, что эти слова присутствуют в исходном тексте, в шифрованном тексте встречаются биграммы МО, П., ЕЕ, ЕА, И и 05. Символ 0 следует за символом М (то есть они стоят рядом по вертикали в колонке 4), так как они разделены в предполагаемой фразе дистанцией, равной длине ключа. Если бы использовался ключ длиной семь, тогда вместо перечисленных выше биграмм встречались бы следующие: МР, 10, ЕЕ, ЕЕ, ЕА, ОЯ и М5.
Таким образом, для каждой длины ключа в шифрованном тексте образуется различный набор биграмм. Перебрав различные варианты, криптоаналитик часто довольно легко может определить длину ключа. Остается узнать только порядок колонок. Если число колонок я невелико, можно перебрать все я(Е' — 1) возможных комбинаций пар соседних колонок, сравнивая частоты образующихся биграмм со статистическими характеристиками английского языка.
Пара с лучшим соответствием считается правильно позиционированной. Затем все оставшиеся колонки по очереди проверяются в сочетании с уже найденной парой. Колонка, в которой биграммы и триграммы дают максимальное совпадение со статистикой, предполагается правильной. Весь процесс повторяется, пока не будет восстановлен порядок всех колонок. Есть шанс, что на данном этапе текст уже будет распознаваемым (например, если вместо слова ии111оп мы увидим япйот, то сразу станет ясно, где сделана ошибка).
Некоторые перестановочные шифры принимают блок фиксированной длины на входе и выдают блок фиксированной длины на выходе. Такие шифры полностью определяются списком, сообщающим порядок, в котором символы попадают в выходной блок. Например, шифр на рис. 8.2 можно рассматривать в виде шифра с 64-символьным блоком. Его выход описывается последовательностью чисел 4, 12, 20, 28, 36, 44, 52, 60, 5, 13,, 62, Другими словами, четвертая входная буква, а, первой появится на выходе, за ней последует двенадцатая, ~, и т.
д. Одноразовые блокноты Разработать шифр, который невозможно взломать, на самом деле весьма просто. Методика для этого известна уже несколько десятилетий. В качестве ключа выбирается произвольная битовая строка, длина которой совпадает с длиной исходного текста. Открытый текст также преобразуется в последовательность двоичных разрядов, например, с помощью стандартной кодировки АЗСП. Наконец, эти две строки поразрядно складываются по модулю 2 (операция чисключаюшее ИЛИ», ХОн). Полученный в результате зашифрованный текст сломать невоз- Криптография 825 можно, поскольку в достаточно большом отрывке любая буква, биграмма илн триграмма будет равновероятной. Этот метод, известный как одноразовый блокнот, теоретически является панацеей от любых атак, независимо от вычислительных мощностей, которыми обладает или будет когда-либо в будущем обладать взломщик. Объясняется этот невероятный факт с помощью теории информации: дело в том, что в зашифрованном сообщении не содержится никакой информации для взломщика, поскольку любой открытый текст является равновераятным кандидатом.
Пример практического использования одноразового блокнота показан на рис. 8.3. Для начала фраза «1 !оуе уоп.» («Я люблю тебя.») преобразуется в 7-битный АЗС11-код. Затем выбирается одноразовая последовательность, Последовательносаь 1, которая складывается по модулю 2 с сообщением. В результате получается некий шифр. Для того чтобы его разгадать, криптоаналитику придется перебрать все возможные одноразовые последовательности, всякий раз проверяя, каким получается открытый текст. Например, если попробовать расшифровать послание с помощью Последовательности 2 (рис. 8.3), получится текст «Е!у!з 1!уез» («Элвис жив»).
Обсуждение правдоподобности этого утверждения выходит за рамки данной книги, однако, как мы видим, исходное сообщение разгадать не удалось, но при этом получилась вполне нормальная с точки зрения английской грамматики фраза. На самом деле, для любой последовательности из 11 символов в кодировке АБС11 найдется одноразовый блокнот для ее генерации. Именна это мы имеем в виду, говоря, что в зашифрованном тексте не содержится никакой информации: из него можно извлечь любое сообщение подходящей длины. Сообщение 1; тоотоот отоооот пот!оо 1!о!111 !!том!о Поп!от отооооо ттпоо1 11отттт птотот ототио Последовательность 1: то!об!о тоо1от! тиоо1о то!о!о! то!опто Попом боота!1 о!ото!о то!опт ттоомо ото!оп Зашифрованный текст: об!то» потом оопт1о о!мото отоо1оо попо!то ото!оп 1отоо11отмооо оотооп оооото! Последовательность 2: !омыв оооомт 11отооо1о1ооы то1оыт о!оот1о тооотп отио!о !во!по тпо11о !!топо Открытее сообщение 2 1ооото! помбо тпо1то По!вот тпоом отооооо мопоо по1оо1 птомо моото1 птоотт Рис.
В.З. Использование одноразового блокнота для шифрования сообщений и возможность получения произвольного открытого сообщения из зашифрсввннсгс путем подстановки другой ключевой последовательности Одноразовые ключи теоретически являются очень мощным инструментом, однако у них есть ряд практических недостатков. Во-первых, такой длинный ключ невозможно запомнить, поэтому и отправитель, и получатель должны носить с собой письменную копию ключа. Если есть опасность того, что одна из этих копий может быть захвачена неприятелем, хранение письменных копий оказывается весьма нежелательным, Кроме того, полный объем данных, которые могут быть переданы, ограничен размером доступного ключа.
Если шпиону повезет и он добудет большое количество информации, может выясниться, что он не сможет пе- а26 Глава 8. Безопасность в сетях редать все эти сведения в центр, так как ему не хватит длины ключа. Еще одна проблема заключается в чувствительности данного метода к потерянным или вставленным символам.
Если отправитель или получатель потеряют синхронизацию, все данные, начиная с этого места, будут испорчены. С появлением компьютеров метод одноразового блокнота может получить практическое применение. Ключ можно хранить на специальном диске РУР, содержащем несколько гигабит информации. Он даже не вызовет особых подозрений, если его перевозить в коробке от видеокомпакт-диска и в начале даже записать несколько минут фильма. Конечно, в сетях со скоростями передачи данных, исчисляющимися гигабитами„необходимость менять компакт-диск через каждые 30 секунд быстро утомит. Получается, что РЪ'Р с одноразовым ключом нужно вручить лично в руки будущему получателю секретного сообщения, а такой подход резко снижает вероятность практического использования метода одноразового блокнота. Квантовая криптография Интересно, что решение проблемы передачи по сети одноразовой последовательности пришло из давольно далекой науки — квантовой механики.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
