foundations_chap_2 (Лекции по информационной безопасности), страница 3

Для того, чтобы упростить дальнейшее изложение, перейдем к алфавиту из 32 символов,отбросив пробел из нашего исходного алфавита M. Вместо пробела всообщениях будем использовать одну из редко встречающихся букв,например, «Ф».Будем предполагать, что ключ K = (Y1 , Y2 , Y3 ) состоит их трехчисел, выбранных случайно равновероятно и независимо из множества {0, . . . , 31}. С помощью рекуррентного соотношения Yt = (Yt−1 +Yt−3 ) mod 32 порождаются элементы последовательности Y1 , .

. . , Yn+1для t > 3. Затем по формулеZt = (Yt + Yt+1 ) mod 32,t = 1, . . . , n,(2.2)вычисляется псевдослучайная последовательность Z1 , . . . , Zn , используемая вместо случайной гаммы. Как и в предыдущем примере, шифрование заключается в сложении по модулю 32 элементов гаммы спорядковыми номерами символов шифруемого текста, полученнымииз таблицы 2.4.Зашифруем на ключе K = (04, 31, 15) сообщение«ПРИКАЗЫВАЮФНАСТУПАТЬ».Рекуррентная последовательность Y1 , . . . , Yn+1 в данном случаебудет иметь вид: «04 31 15 19 18 01 20 06 07 27 01 08 03 04 12 15 19 3114 01 00».Сложим по модулю 32 порядковые номера символов нашего сообщения с элементами псевдослучайной последовательности (гаммы),полученной по формуле (2.2):15 16 08 10 00 07 27 02 00 30 20 13 00 17 18 19 15 00 18 28 — сообщение;03 04 02 05 19 21 26 13 02 28 09 11 07 16 27 02 18 13 15 01 — гамма;18 30 10 15 19 28 21 15 02 26 29 24 07 01 13 21 01 13 01 29 — зашифрованноесообщение.20Общее число возможных текстов из 20 символов составляет 32 ,3а количество различных ключей в данном случае 32 = 32768.

Следо-§ 2.1.ВВЕДЕНИЕ В ПРОБЛЕМЫ КЛАССИЧЕСКОЙ КРИПТОГРАФИИ145вательно, количество возможных вариантов расшифрования при неизвестном ключе не превосходит 32768 и, имея перехваченную криптограмму, а также зная алгоритм шифрования, криптоаналитик можетотбросить бо́льшую часть текстов как недопустимые (в частности,будет отброшено сообщение «ПРИКАЗЫВАЮ ОТСТУПАТЬ»).Таким образом, криптоаналитик имеет 32768 вариантов сообщения, из которых он должен выбрать единственный правильный.

Возникает вопрос — можно ли вообще отличить настоящее сообщениеот ошибочных вариантов? Если сообщение представляет собой осмысленный текст на русском языке, то его наверняка удастся отличить20от ложных, так как из 32 слов из рассматриваемого алфавита осмысленными текстами является только малая часть. Согласно исследованиям, проведенным еще К.

Шенноном [13], осмысленных текстов из620 букв на английском языке порядка 10 . Приблизительно такая жеоценка справедлива и для русского языка.Оценим вероятность появления среди всех вариантов расшифрования второго осмысленного текста, сделав разумное допущение о том,что тексты длины 20, являющиеся ложными вариантами расшифрования нашей криптограммы, выбираются из совокупности всех последовательностей, состоящих из 20 символов, совершенно случайно,независимо от того, имеют они смысл или нет. Вероятность того,что выбранный случайным образом текст не окажется осмысленным,20620равна приблизительно (32 − 10 )/32 .

Следовательно, вероятностьпоявления среди 32767 случайных текстов осмысленного текста оценивается следующим образом:6 3220 − 106 3276732767 × 10−20< 2.6 × 10 .<1−20203232Для сравнения, вероятность угадать 6 чисел, выбранных случайно из−1036, больше, чем 10 .Таким образом, мы показали, что в нашем случае криптоаналитик, прочитав варианты расшифрования криптограммы для всех возможных ключей, с вероятностью, близкой к единице, правильно определит переданное сообщение. Если он будет отбрасывать по одномуложному сообщению в секунду, то ему понадобится на просмотр всехвариантов около 9 часов.

Гораздо больше времени (546 часов при скорости один вариант в минуту) необходимо для получения вручнуюсамих вариантов расшифровки. Таким образом, трудоемкость ручного дешифрования рассматриваемой криптограммы методом переборавсех возможных ключей составляет 555 часов.Время дешифрования можно значительно сократить, если использовать ЭВМ для генерации вариантов сообщения. В этом случае все146КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫварианты будут получены практически мгновенно и, следовательно,трудоемкость дешифрования составит 9 часов, которые необходимыдля прочтения этих вариантов.

При этом, правда, нужно еще учестьвремя, необходимое для программирования ЭВМ. Очевидно, однако,что это время играет менее значительную роль, чем собственно времяперебора (если только речь не идет о дешифровании одной единственной криптограммы).В современных алгоритмах шифрования используются гораздо более длинные ключи, чем в нашем примере. В частности, широко используемый алгоритм шифрования DES имеет ключ объемом 56 бит.Если мы захотим просмотреть все варианты дешифрования сообщения, зашифрованного с помощью алгоритма DES (количество ключей5616в этом случае 2 ≈ 7.2 × 10 ), то для этого понадобится более 2 миллиардов лет при скорости один вариант в секунду.

Метод дешифрования перебором ключей становится действительно опасным, если имеется алгоритм, позволяющий автоматизировать отбраковку ошибочных вариантов с помощью ЭВМ. Для этого может использоваться несколько способов.Во-первых, если для проверки правильности сообщения используется контрольная сумма, то она же может послужить и для отбраковкиопробуемых вариантов.Во-вторых, если мы заранее знаем фрагмент дешифруемого сообщения (или значения некоторых служебных полей дешифруемых данных), то для отбраковки ложных сообщений достаточно произвестисравнение известного фрагмента со значением соответствующей части расшифрованных на опробуемом ключе сообщений.Может, однако, оказаться, что проверку указанных типов пройдетбольшое количество сообщений.

Например, если контрольная суммасодержит 32 бита, а ключ — 56 бит, то мы получим приблизительно242 = 16777216 сообщений, имеющих правильную контрольную сумму, среди которых нужно найти единственное подлинное. В такихслучаях, а также, если контрольная сумма отсутствует и неизвестна даже часть зашифрованного текста, при отбраковке ложных сообщений не обойтись без так называемых «критериев на открытыйтекст». Такие критерии предназначены для выявления тех последовательностей символов заданного алфавита, которые допустимы вкачестве открытых сообщений.Построим критерий на открытый текст для отбраковки ложныхвариантов в рассматриваемом нами примере.Проанализировав частоты встречаемости различных пар соседних букв в текстах русского языка (см.

таблицу 2.3), можно сделатьвывод, что вероятность появления 317 из них практически равна ну-§ 2.1.ВВЕДЕНИЕ В ПРОБЛЕМЫ КЛАССИЧЕСКОЙ КРИПТОГРАФИИ147лю. Для нашего случая, когда вместо пробела используется буква«Ф», столбец, соответствующий букве «Ф», объединяется со столбцом, соответствующим пробелу, и аналогичная операция проводитсясо строками. Поэтому в рассматриваемом алфавите из 32 букв число невозможных сочетаний соседних символов составляет 287. Данная особенность позволяет сформулировать критерий на открытыйтекст: если в тексте имеется хотя бы одна запретная биграмма, т. е.невозможное сочетание двух соседних символов, то он не является открытым сообщением.Очевидно, что с помощью такого критерия мы не сможем отбраковать все ложные варианты расшифрования, так как не любая последовательность символов без запретных биграмм является осмысленнымсообщением. Вероятность появления любой фиксированной пары символов в конкретном месте случайно равновероятно выбранного текста2(из множества текстов заданной длины) равна 1/32 для алфавита из32 символов.

Если пренебречь зависимостью соседних биграмм, тонесложно подсчитать вероятность того, что из девятнадцати пар соседних символов ни одна не окажется запретной:287 19≈ 0.002.1− 232Следовательно, среди 32768 вариантов сообщения лишь около 65 несодержат ни одного невозможного сочетания соседних букв. Воспользовавшись ЭВМ, можно практически мгновенно отбросить тексты снедопустимыми сочетаниями соседних букв. Затем несложно и вручную выбрать из оставшихся нескольких десятков вариантов правильный вариант.Читатель, знакомый с основами математической статистики, может попробовать построить и рассчитать другие, более совершенныекритерии на открытый текст, с помощью которых в данном примереи без участия человека можно определить единственный правильныйвариант дешифрования.Рассмотренный метод дешифрования, заключающийся в переборе всех возможных ключей, называют методом тотального опробования.

Очевидно, что время, необходимое для дешифрования такимметодом, будет зависеть от мощности используемой ЭВМ. Поэтому вслучае полной автоматизации перебора трудоемкость алгоритма удобнее всего измерять числом элементарных операций, производимых привыполнении этого алгоритма. Оценим трудоемкость дешифрованиярассматриваемого шифра методом тотального опробования.Для генерации одного символа опробуемого сообщения необходимо две операции сложения по модулю и несколько обращений к памяти. Проверка того, является ли сгенерированное сообщение текстом на148КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫрусском языке, реализуется с помощью n обращений к памяти и сравнений, где n — длина текста (на самом деле несколько меньше, так какесли в тексте уже найдена запретная биграмма, то проверять оставшиеся биграммы нет смысла).

Таким образом, трудоемкость метода тотального опробования ключей можно выразить формулой T = Cn |K|,где C — некоторая константа, не зависящая от размерности задачи. Внашем случае T = C × 20 × 32768 = C × 655360, то есть трудоемкостьопробования всех ключей нашего алгоритма шифрования составляетнесколько миллионов операций (современная персональная ЭВМ проделает эти вычисления практически мгновенно).При построении критерия на отбраковку ложных вариантов расшифрования вовсе не обязательно использовать все знаки сообщения.Скорее всего, достаточно будет небольшого отрезка из несколькихдесятков знаков. Соответственно, нет и необходимости расшифровывать сразу весь текст.