Методы гаммирования

Шифр гаммирования со случайной равновероятной гаммой. Пусть имеется сообщение t₁…t_n, представляющее собой последовательность символов из алфавита А, со­стоящего, как и ранее, из 32 букв русского языка и пробела (буквы Е и Ё не различаются). Ключ К представляет собой последовательность чисел k₁...k_n из множества чисел М ={0...32}. Зашифрованный текст S₁…S_n вы­числяется по следующей формуле:

S_i=(C(t_i)) + k_i) mod 33, i= 1...n,

где С: А ® М функция, отображающая символ в его порядковый номер. Запись d=(a+b)mod m означает, что d совпадает с остатком от деления на m суммы чисел а и b, например, 1=(4 + 5) mod 8.

Расшифровать сообщение можно с помощью формулы:

t_i=C^-1 ((s_i+(33 - k_i)) mod 33).

В данном случае через С^-1 обозначается функ­ция, отображающая число из множества от 0 до 32 в символ (букву или пробел) с соответствующим номером.

Будем предполагать, что ключ выбирается случайно равновероятно из Мⁿ - множества векторов длины n, координаты которых принимают значения из М (или, что то же самое, каждый из элементов ключа k_i, i=1...n, выбирается случайно равновероятно и независимо из М).

Определенный таким образом шифр называется шифром гаммирования со случайной равновероятной гаммой (гаммой принято называть последовательность чисел k₁...k_n, складываемую по модулю с шифруемым сообщением).

При таком методе шифрования количество символов в крипто­грамме совпадает с количеством символов сообщения, то есть совпадают их длины. Чтобы скрыть от противника длину сообщения, его можно до­полнить пробелами до некоторой фиксированной длины, которую не пре­восходит стандартное сообщение. В приведенном ниже примере, мы бу­дем дополнять сообщения до 10 символов.

Зашифруем с помощью описанного выше шифра гаммирования со­общение «НАСТУПАТЬ» на ключе «05 12 03 29 24 12 30 14 11 31». Для этого, заменим буквы нашего сообщения их порядковыми номерами в алфавите и сложим эти номера с элементами ключевой последовательно­сти по модулю 33:

13 00 17 18 19 15 00 18 28 32 - шифруемое сообщение в цифровом виде;

05 12 03 29 24 12 30 14 11 31 - ключ;

18 12 20 14 10 27 30 32 06 30 - результат шифрования.

Криптоаналитик противника, зная алгоритм шифрования и имея зашифрованный текст, но, не имея ключа, не сможет извлечь для себя ни какой другой информации, кроме самого факта передачи сообщения (факт передачи сообщения можно замаскировать, передавая с определенной частотой "пустые" сообщения). Делая разные предположения о ключе, криптоаналитик будет получать разные открытые тексты. Изменяя значе­ние k_i от 0 до 32, он получит все возможные значения i-го символа откры­того текста, независимо от значения i-го символа криптограммы. Таким образом, из любого шифрованного текста можно получить произвольный текст такой же длины. В частности, если предположить, что был выбран ключ, удовлетворяющий соотношению k_i,=(33-C(t_i,)+s_i)mod33, i=l...n, криптограмма s₁...s_n будет расшифрована в сообщение t₁...t_n. Например, в нашем случае, в предположении, что использовался ключ "04 27 03 29 24 12 30 14 11 31", криптограмма "18 12 20 14 10 27 30 32 06 30" будет дешифрована в сообщение «ОТСТУПАТЬ» - прямо противоположное по смыслу исходному («НАСТУПАТЬ»). Так как ключи выбирались случай­но равновероятно, криптоаналитик противника на основе шифротекста не сможет отдать предпочтение ни одному из возможных сообщений из де­сяти символов (всего их 33¹⁰). Единственное, что может сделать против­ник в данном случае - это отсортировать сообщения на более вероятные и менее вероятные, исходя из анализа обстановки. Например, если сторона, которой адресовано сообщение, имеет превосходство над своим против­ником, то сообщение «ОТСТУПАТЬ» является менее вероятным, чем со­общение «НАСТУПАТЬ», а получение приказа «СДАВАЙТЕСЬ» - со­всем неправдоподобно. Однако чтобы прийти к подобным выводам, нет необходимости перехватывать криптограммы противника.

Рассмотренный метод шифрования можно было бы считать иде­альным, если бы не один существенный недостаток - длина ключа при гаммировании случайной равновероятной гаммой совпадает с длинной шифруемого текста. Конечно, современные технические средства позво­ляют обеспечить хранение большого объема ключевых данных, используя для этого, например, лазерные диски. Однако во многих случаях реализа­ция данного метода будет слишком дорогой и неудобной. Например, что­бы обеспечить шифрование изображения со спутника-шпиона необходи­мо будет отправить в космос целый контейнер с несколькими тысячами лазерных дисков. Большие трудности возникают также при попытке объ­единить в сети связи большое количество абонентов. Ведь в этом случае необходимо иметь возможность быстро получать доступ к ключу любого абонента (а их может быть несколько тысяч). Таким образом, на практике, как правило, приходится довольствоваться шифрами, которые не являют­ся совершенными. В частности, распространены шифры гаммирования с использованием псевдослучайной гаммы.

ШИФРЫ ГАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ ПСЕВДОСЛУЧАЙНОЙ ГАММЫ. Проанализируем стойкость, рассматривавшегося выше шифра гам­мирования в предположении, что вместо случайной гаммы используется псевдослучайная последовательность. Для того чтобы упростить даль­нейшее изложение, перейдем к алфавиту из 32 символов, отбросив пробел из нашего исходного алфавита М. Вместо пробела в сообщениях будем использовать одну из редко встречающихся букв, например "Ф".

Будем предполагать, что ключ K=(Y₁,Y₂,Y₃) состоит их трех чисел, выбранных случайно равновероятно и независимо из множества {0...31}. С помощью рекуррентного соотношения Y_t =(Y_t-1+Y_t-3)mod 32 порожда­ются элементы последовательности Y₁...Y_n+1 для t > 3. Затем по формуле

Z_t = (Y_t + Y_t+1) mod 32, t=l,…n, (2.1)

вычисляется псевдослучайная последовательность Z₁...Z_n, используемая вместо случайной гаммы. Как и в предыдущем примере, шифрование за­ключается в сложении по модулю 32 элементов гаммы с порядковыми номерами символов шифруемого текста.

Зашифруем на ключе K=(04,31,15) сообщение

«ПРИКАЗЫВАЮ НАСТУПАТЬ».

Рекуррентная последовательность Y₁...Y_n+1 в данном случае будет иметь вид: "04 31 15 19 18 01 20 06 07 27 01 08 03 04 12 15 19 31 14 01 00".

Сложим по модулю 32 порядковые номера символов нашего сооб­щения с элементами псевдослучайной последовательности (гаммы), полу­ченной по формуле (2.1):

15 16 08 10 00 07 27 02 00 30 20 13 00 17 18 19 15 00 18 28 - сообщение;

03 14 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 символов составляет 32²⁰, а количество различных ключей в данном случае 32³=32768. Следователь­но, количество возможных вариантов расшифрования при неизвестном ключе не превосходит 32768 и, имея перехваченную криптограмму, а также зная алгоритм шифрования, криптоаналитик может отбросить большую часть текстов как недопустимые (в частности, будет отброшено сообщение «ПРИКАЗЫВАЮ ОТСТУПАТЬ»).

Таким образом, криптоаналитик имеет 32768 вариантов сообщения, из которых он должен выбрать единственный правильный. Возникает во­прос - можно ли вообще отличить настоящее сообщение от ошибочных вариантов? Если сообщение представляет собой осмысленный текст на русском языке, то его наверняка удастся отличить от ложных, так как, из 32²⁰ слов из рассматриваемого алфавита осмысленными текстами является только малая часть. Согласно исследованиям, проведенным еще К. Шен­ноном, осмысленных текстов из 20 букв на английском языке порядка 10⁶. Приблизительно такая же оценка справедлива и для русского языка.

Оценим вероятность появления среди всех вариантов расшифрова­ния второго осмысленного текста, сделав разумное допущение о том, что тексты длины 20, являющиеся ложными вариантами расшифрования на­шей криптограммы, выбираются из совокупности всех последовательно­стей, состоящих из 20 символов, совершенно случайно, независимо от того, имеют они смысл или нет. Вероятность того, что выбранный слу­чайным образом текст не окажется осмысленным, равна приблизительно (32²⁰-10⁶)/32²⁰. Следовательно, вероятность появления среди 32767 случайных текстов осмысленного текста, оценивается следующим образом:

Для сравнения, вероятность угадать 6 чисел, выбранных случайно из 36, больше чем 10^-10.

Таким образом, мы показали, что в нашем случае криптоаналитик, прочитав варианты расшифрования криптограммы для всех возможных ключей, с вероятностью близкой к единице правильно определит пере­данное сообщение. Если он будет отбрасывать по одному ложному сооб­щению в секунду, то ему понадобится на просмотр всех вариантов около 9 часов. Гораздо больше времени (546 часов при скорости один вариант в минуту) необходимо для получения вручную самих вариантов расшиф­ровки. Таким образом, трудоемкость ручного дешифрования рассматри­ваемой криптограммы методом перебора всех возможных ключей состав­ляет 555 часов.

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

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

Во-первых, если для проверки правильности сообщения использу­ется контрольная сумма, то она же может послужить и для отбраковки опробуемых вариантов.

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

Может, однако, оказаться, что проверку указанных типов пройдет большое количество сообщений. Например, если контрольная сумма со­держит 32 бита, а ключ - 56 бит, то мы получим приблизительно 2²⁴ = 8388608 сообщений, имеющих правильную контрольную сумму, среди которых нужно найти единственное подлинное. В таких случаях, а также, если контрольная сумма отсутствует и неизвестна даже часть за­шифрованного текста, при отбраковке ложных сообщений не обойтись без так называемых "критериев на открытый текст". Такие критерии предназначены для выявления тех последовательностей символов задан­ного алфавита, которые допустимы в качестве открытых сообщений.

Построим критерий на открытый текст для отбраковки ложных ва­риантов в рассматриваемом нами примере.

Проанализировав частоты встречаемости различных пар соседних букв в текстах русского языка (см. таблицу 2.4), можно сделать вывод, что вероятность появления 317 из них практически равна нулю. Для нашего случая, когда вместо пробела используется буква "Ф", столбец, соответст­вующий букве "Ф", объединяется со столбцом, соответствующим пробе­лу, и аналогичная операция проводится со строками. Поэтому в рассмат­риваемом алфавите из 32 букв число невозможных сочетаний соседних символов составляет 287. Данная особенность позволяет сформулировать критерий на открытый текст: если в тексте имеется хотя бы одна запрет­ная биграмма, то он не является открытым сообщением.

Очевидно, что с помощью такого критерия мы не сможем отбрако­вать все ложные варианты расшифрования, так как не любая последова­тельность символов без запретных биграмм является осмысленным сооб­щением. Вероятность появления любой фиксированной пары символов, в конкретном месте случайно равновероятно выбранного текста (из множе­ства текстов заданной длины), равна 1/32² для алфавита из 32 символов. Если пренебречь зависимостью соседних биграмм, то несложно подсчи­тать вероятность того, что из 19 пар соседних символов ни одна не ока­жется запретной:

(1-287/32²)¹⁹≈0,002.

Следовательно, среди 32 768 вариантов сообщения лишь около 65 не содержат ни одного невозможного сочетания соседних букв. Восполь­зовавшись ЭВМ, отбросить тексты с недопустимыми сочетаниями сосед­них букв можно практически мгновенно. Затем из оставшихся нескольких десятков вариантов выбрать правильный несложно и вручную.

Читатель, знакомый с основами математической статистики, может попробовать построить и рассчитать другие - более совершенные крите­рии на открытый текст, с помощью которых в данном примере и без участия человека можно определить единственный правильный вариант де­шифрования.

Рассмотренный метод дешифрования, заключающийся в переборе всех возможных ключей, называют методом тотального опробования. Очевидно, что время необходимое для дешифрования таким методом бу­дет зависеть от мощности используемой ЭВМ. Поэтому, в случае полной автоматизации перебора, трудоемкость алгоритма удобнее всего измерять числом элементарных операций, производимых при выполнении этого алгоритма. Оценим трудоемкость дешифрования рассматриваемого шиф­ра методом тотального опробования.

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

При построении критерия на отбраковку ложных вариантов рас­шифрования вовсе не обязательно использовать все знаки сообщения. Скорее всего, достаточно будет небольшого отрезка из нескольких десят­ков знаков. Соответственно нет и необходимости расшифровывать сразу весь текст. Данные соображения позволяют прийти к выводу, что в боль­шинстве случаев трудоемкость метода тотального опробования на качест­венном уровне не зависит от длины текста и определяется только количе­ством возможных ключей.

Не очень добросовестные производители средств шифрования дан­ных, рекламируя свои продукты, сообщают время, необходимое для взло­ма этих средств, исходя из того, что противник будет применять именно метод тотального опробования. Однако этот метод далеко не всегда ока­зывается наилучшим.

Вернемся к рассмотрению нашего алгоритма шифрования, для ко­торого, как мы выяснили, трудоемкость дешифрования методом тоталь­ного опробования составляет несколько миллионов операций. Сделаем предположение, что противник знает значение нескольких символов за­шифрованного сообщения (это может быть стандартный заголовок, адрес, обращение или служебная информация используемого редактора текстов). В нашем примере будем считать известным, что первое слово сообщения начинается с приставки "при": приказ, приказываю, приказание и т.д. Бук­вы "П", "Р", "И" идут под номерами "15", "16", "08". Следовательно, вы­полняются соотношения: (15+Z₁,)mod 32 = 18, (16+Z₂)mod 32 = 30, (8+Z₃)mod 32 = 10, согласно которым первые три знака гаммы принимают значения Z₁,=3, Z₂=14. Z₃=2. Исходя из этой информации, криптоаналитик противника может составить систему уравнений:

(Y₁+Y₂)mod 32 = 3

(Y₂+Y₃)mod 32 = 14

(Y₃+Y₄)mod 32 = 2.

Воспользуемся для вычисления Y₄рекуррентным соотношением Y_t =(Y_t-1+Y_t-3)mod 32. В итоге, получим систему из трех уравнений, с тремя неизвестными:

(Y₁+Y₂)mod 32 = 3

(Y₂+Y₃)mod 32 = 14

(Y₁+2Y₃)mod 32 = 2.

Выразим Y₁и Y₃ через Y₂, используя первое и второе уравнения:

Y₁=(3 - Y₂)mod 32

Y₃=(14-Y₂)wod32.

Затем, подставив результат в последнее уравнение, получим:

(3-Y₂+28-2Y₂)mod 32 = 2.

Отсюда (3Y₂)mod 32 = 29.

Несложно убедиться, что последнее уравнение имеет единственное решение Y₂=31. В итоге находим ключ Y₁=4, Y₂=31, У₃⁼15, воспользовав­шись которым можно расшифровать наше сообщение.

Таким образом, мы нашли ключ, проделав всего пару десятков опе­раций вместо нескольких миллионов, необходимых для опробования всех возможных ключей.

Вернемся теперь к рассмотрению вопроса о способе измерения стойкости криптографических алгоритмов. Все алгоритмы шифрования можно разделить на три группы.

К первой группе относятся совершенные шифры, заведомо непод­дающиеся дешифрованию (при правильном использовании). Примером такого шифра является шифр гаммирования случайной равновероятной гаммой.

Во вторую группу входят шифры, допускающие неоднозначное дешифрование. Например, такая ситуация возникает, если зашифровать с помощью шифра простой замены, рассмотренного выше, очень короткое сообщение.

Основная масса используемых шифров относится к третьей группе и может быть в принципе однозначно дешифрована. Сложность дешиф­рования шифра из этой группы будет определяться трудоемкостью ис­пользуемого алгоритма дешифрования. Следовательно, для оценки стой­кости такого шифра необходимо рассмотреть все известные алгоритмы дешифрования, и выбрать из них имеющий минимальную трудоемкость, то есть тот, который работает в данном случае быстрее всех остальных. Трудоемкость этого алгоритма и будет характеризовать стойкость иссле­дуемого шифра.

Удобнее всего измерять трудоемкость алгоритма дешифрования в элементарных операциях, но более наглядным параметром является вре­мя, необходимое для вскрытия шифра (при этом необходимо указывать технические средства, которые доступны криптоаналитику). Не следует только забывать, что вполне возможно существование неизвестного на данный момент алгоритма, который может значительно снизить вычис­ленную нами стойкость шифра. К большому сожалению разработчиков шифросистем, строго доказать с помощью математических методов невоз­можность существования простых алгоритмов дешифрования удается чрезвычайно редко. Очень хорошим результатом в криптографии является доказательство того, что сложность решения задачи дешифрования иссле­дуемого шифра эквивалентна сложности решения какой-нибудь известной математической задачи. Такой вывод хотя и не дает 100% гарантии, но позволяет надеяться, что существенно понизить оценку стойкости шифра в этом случае будет очень не просто.