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