МИСЗКИ книга (1085503), страница 19
Текст из файла (страница 19)
Если зта задюш решена, то ешьнейшая работа ничем не отличается от той, которую мы »роделали для шифра однобуквенной простой замены. Следует учитывать, что в литературных открытых текстах >лего встречаются повторения фрагментов, состоящих из трех и алльшего числа букв. При применении к тексту шифра простой >ямены соответствующие повторения остаются и в шифрованяом тексте. Если в криптограмме встретилось несколько повто»еиий, то их успешно можно использовать для определенна |алчности шифрообозначений. Очевидно, что для равнозначного шифра простой замены »>ины повторений и расстояния между ними должны быть крат- «и звачности шифра.
Находя наибольший общий делитель этих чисел, мы с большой вероятностью получаем искомую значность. Некоторые сомнения в правильности определения значакти помогает устранить подсчет общего числа шифрообозна>елий. Если зто число близко к ожидаемому числу шифрообо>лачений (скажем, к числу букв алфавита), и диаграмма их по>ооряемостн близка к табличной, то, скорее всего, значносгь >яяфра определена верно. Для разнозначного шифра дело обсгоит несколько сложа«с, В этом случае числа, равные длинам повторений и рассп>я«л»м между ними, скорее всего, взаимно просты в совокупно> в. Однако и для таких шифров задача определения множества >ялфрообозначений не безнадежна.
В этом помогает естествен>к>с ограничснис, которым обычно пользуются при составлении »>блицы шифрообозначений. Оно связано с требованием одно|алчности расшифрования и заключается в том, чтобы ни одно л> шифрообозиачевий не являлось началом никакого другого >ялфрообозиачения (в теории кодирования это называется префлксным кодом). Если значность шнфрообозначений колеблется и незначительных пределах, то перебор сравнительно небольшо> о числа вариантов приводит (с учетом ограничения) к правиль>я>му определению болынинства шифрообозначений.
Некоторые 11Э затруднения могут возникать лишь при определении значностн шифрообозначений, редко встречающихся в тексте. Как правило, они определяются при попытке прочтения тех участков криптограммы, для которых восстановленная значность шифрообозначений не вызывает сомнений.
Увеличение значности шифрообозначений делает шифр неэкономным, поэтому получили распространение шифры, ие пользующие одно- и двузначные шифрообозначения, подобные рассмотренному выше в примере шифру. Понятно, *по для таких шифров наибольшую повторяемость в шнфротексте имеют цнф ры, с которых начинаются двузначные шифрообозначения. Выдвигая гипотезы о таких цифрах и отмечая в шифротексте соответствуюпше двузначные шифрообозначения, можно восстановить и однозначные шифрообозначения, оказавшиеся в шнфротексте между некоторыми двузначными шнфрообозначениямн.
Дальнейшая работа по вскрытию открытого текста для разно значного шифра ничем не отличается от уже рассмотренного алгоритма вскрытия шифра однобуквенной простой замены. 2. Блочные шн ы п остей м ны. Как мы убедились, задача вскрытия простой однобуквен ной замены является не слишком сложной. Основная слабосп, такого шифра состоит в том, что избыточность открытого тек ста, полносп ю проникающая в шифротекст, делает (за счет мз лого — псла шнфрове/пг"ш, которыми явля/отея буквы алфавите) очень рельефной диаграмму повторяемости знаков криптограм мы. Это побудило в свое время криптографов к устранению этой слабости за счет увеличения числа шифровеличин.
Интунтивн понятно, что чем больше разница между числом шифровелнчин н числом букв алфавита, тем более равномерной должна стать диаграмма повторяемости знаков шнфротекста. Первым есгес1 венным шагом в этом направлении стало увеличение значнос/в шифровеличин, то есть использование блочных шифров просим замены. Простейший блочный шифр оперирует с биграммнымн шифровелнчннами. Одними из первых таких шифров были бн граммиые шифры Порта и Плейфера. Рассмотрим шифр Плей фера, нашедший широкое применение в начале ХХ века. 114 нара вершин, причем й— вершина, лежащая в той /кс строке, что и /. 2. Если / и ' лежат в в / 1 в р«,я одной строке, то Е н 1— / буквы той же строки, рас/ ф~ положенные непосредст/ ненно справа от / и / соот- Щ вегственно. При этом если //дна нз букв — последняя в рне. 15. Правила лжфра пхеяфер/ е/роке, то считается, что ее правым соседом» является первая буква той же строки.
3. Аналогично, если / и 1 лежат в одном столбце, то они гнменяются их «соседями снизу». При шифровании открытый текст представляется в виде последовательности биграмм. Если текст имеет нечетную длину нли содержит биграмму, соспжщую из одинаковых букв, то в него добавляются «пустышки» следующим образом. «Пустышхой» является некоторая редкая для данного типа текста буква (//ли знак), которая вставляется между одинаковыми буквами 6н/раммы или добавляется в текст для того, чтобы его длина е/зла четной. Такие изменения открытого текста, как правило, не мешиот при расшифровании. Основой шифра Плейфера является прямоугольная таблица, в которую записан перемешанный алфавит. Правило шифрования состоит в следующем . Буквы биграммы (/, /), / 4 / открытого текста находятся в данной таблице.
При шифровании биграмма (Ц) заменяется биграммой (Щ, где // и 1 определяются в соответствии с правилами 1 — 3 (слева алгоритмическое описание, на рисунке справа — графическое представление): 1. Если / и / не лежат в. в одной строке или одном столбце, то их позиции образуют противополож- ... / / ные вершины прямоу/ххльника. Тогда й и 1 — другая Рассмотрим пример.
Пусть шифр использует прямоугольник размером 5 х 6, в который записан систематически перемешанный русский 30- буквенный алфавит на основе ключевого слова командир: у = (уь...,у„) — и-грамма шифротекста, то юг(х)=й х. Соответственно х=1)г(у) =1с' у, где й ' — матрица, обратная к матрице для Е Подчеркнем, что матричные операции здесь производятся над кольцом У, то есп значение матрицы есть остаток результата перемножения поделенный на мощность алфавита. Зашифруем фразу «автором метода является Уитстои». В качестве «пустышки» будем использовать редкую букву «ф».
Представим фразу в виде последовательности биграмм: АВ ТО РО МФ МЕ ТО ДА ЯВ ЛЯ ЕТ ТЯ УИ ТС ТО НФ («Пустышку» пришлось вставить дважды.) В соответствии со сформулированными правилами получаем пшфротекст: ВП ЗД ЗР ОХ ДБ ЗД КН ЭЕ ТЫ ТШ Т(О ЩЖ ЖТ ЗД ОЧ илн без пробелов впздзрохдбздкнэетьгплтющжжгздоч Криптоанализ шифра Плейфера опирается на частотный анализ биграмм, триграмм и четырехграмм шнфротекста и особенности замены шифровелнчнн на шифрообозначения, связанные с расположением алфавита в прямоугольнике. Шифровеличинамн для другого широко известного блочного шифра — шифра Хилла (названного по имени Лесгора Хилла) — явтпотся и-граммы открытого текста (л>2), представленного некоторым числовым кодом (так что алфавитом открытого текста служит кольцо вычетов по модулю мощности алфавита У ).
Правило шифрования представляет собой линейное преобразование кожца У: если х =(хь...,х„) — и-грамма открытого текста, Ь вЂ” некоторая обратимая матрица над У (ключ) в 116 Рассмотрим пример. Положим и = 4 и зашифруем фразу: бвз труда яе вынешь рыбку из пруда записанную в 30-буквенном русском алфавите. Уаювимся о числовом кодировании букв в соответствии с таблицей: А Б В Г Е Ж 3 И К Л М Н О П 1 18 11 6 0 15 20 5 21 23 13 4 16 8 25 Р С Т У Ф Х Ц Ч Ш Щ Ь Ы Э Ю Я 24 10 19 26 12 2 28 7 17 22 3 29 27 14 9 В качестве ключа выберем матрицу 1 2 3 4 1 2 3 5 1 3 3 5 1 3 4 5 Запишем открытый текст по столбцам матрицы Т: 18 24 16 16 24 26 24 15 26 15 15 29 21 26 5 0 11 17 18 5 0 19 1 29 3 23 25 1 117 Вычислим произведение и получим шифротекст в виде матрицы 0 = й Т: 19 20 15 19 18 3 20 8 21 14 22 11 28 21 23 17 29 7 10 19 17 28 17 10 24 28 24 17 Теперь осталось воспользоваться числовым кадом, чтобы выписать шифротекст в буквенном виде: токижишшеюыспцчрбвсцьцтржишш Эамечание.
Из соображений удобства в применении получили широкое распространение шифры, для которых правила шифрования и расшнфрования идентичны. Такие шифры называются обратимыми. Шифр Хилла является обратимым в том н только том случае, когда Е' = й, или иначе: к = Е, где Š— единичная матрица. Естественным обобщением шифра Хилла является аффинный блочный шифр, правило шифрования Д х) = х А+ Ь . При этом А является обратимой матрицей лхл, а Ь вЂ” фиксированным п-мерным вектором. Яекоторые замечания по криптоанализу блочных шифров и, в частности, шифра Хилла. Увеличение значносгн шифровеличин резко усложняет попытки вскрытия открытого текста по известному тексту криптограммы. Однако свойство линейности, присущее рассматриваемым шифрам, конечно, является их критггографической слабостью.
Так, если известен некогорый набор блоков шифротекста и соответствующих нм блоков открытого текста, то операция по вскрыппо аффинного шифра сводится к вычитанию, обращению и перемножению матриц. 118 Принципы построения современных блочных шифров Как правило, алфавитом, иа котором действует блочный ьзифр, является множеспю двоичных блоков открытого текста одинаковой длины (64, 128 и т. д. бит).
Сама реализация преобразований столь больших алфавитов является сложной задачей, и использование преобразований с целью шифрования требует вт них еще ряда специальных качеств. К. Шеннон сформулировал обппш принцип построения ьзифрующих преобразований — принцип «перемешинания». Суть его состоит в требовании, чтобы применение шифрующего преобразования к наборам аргументов, отличающихся в незначительном числе позиций„приводило к существенному изменеввю результата.
Обеспечить выполнение этого требования в совсшнии с простотой реализации конкрепюго отображения в 0щем случае представляется затруднительным. Поэтому К. Шеннон предложил реализовывать сложные преобразования в видо суперпозиции нескольких простых отображений. Подход в. Шеннона, использующий итеративное построение преобразований, в настоящее время является основным путем синтеза в»очных шифров. Блочные шифры реализуются путем многократного применения к блокам открытого текста некоторых базовых преобраюваний.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
