Повторное использование гаммы

Как и раньше, мы предполагаем, что алфавит А открытыx текстов, гаммы и шифртекстов представляет собой мно­жество чисел Z_n= {0,1,...,п–1} .

Пусть в распоряжении криптоаналитика оказались две криптограммы, полученные наложением одной и тойже гам­мы на два разных открытых текста:

S₁=T₁+Г(mod n), S₂ = Т₂ + Г(mod n),

где

Рассмотрим возможности криптоаналитика по восстанов­лению исходных открытых текстов.

Прежде всего, можно найти позначную разность

S = S₁ – S₂ = T₁ – Т₂ (mod n).

Пусть S = {s_i}, i=1,2… . Тогда поставленная задача сводит­ся к попытке подобрать пару открытых текстов, разность ко­торых совпадает с известной последовательностью S . Будем в связи с этим говорить о разложении S на два составляю­щих открытых текста. В случае, когда данные тексты являют­ся нормативными текстами, например, на русском, англий­ском или другом языке, для решения последней задачи ис­пользуется ряд подходов. Интуитивно понятно, что при дос­таточной длине текстов маловероятна возможность множест­венного представления данной последовательности S в виде разности T₁ – T₂. Как правило, такое разложение бывает единственным.

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

Предположим сначала, что одно из вероятных слов встре­тилось в начале первого сообщения:

вероятное слово

В таком случае можно вычислить начало второго сообщения:

T₂ =T₁ – S.

Если l > 5, легко определить, является ли начало T₂ читаемым" или нет. В первом случае нужно попытаться про­чить начало T₂ по смыслу. Во втором случае нужно сдви­нуть начало вероятного слова в T₁, и проделать то же самое.

Если удалось развить T₂ до m знаков (т> l), то можно вычислить и соответствующие m –1 знаки, используя

T₁ =T₂ + S,

и попытаться, в свою очередь, развить по смыслу T₁.

Продолжая этот процесс далее, мы частично или полностью восстановим оба текста или убедимся в том, что опробуемого вероятного слова данные тексты не содержат. В последнем случае следует попытаться ту же процедуру проделать для следующего вероятного слова.

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

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

Пример

Возьмем два текста на английском языке, содержащих наиболее часто встречающуюся триграмму THE:

T₁ = THE APPLE, T₂ = TELL THEM,

и зашифруем их одной и той же гаммой Г = ONETWOTHRE. При этом будем пользоваться числовыми значениями букв согласно следующей таблице:

В результате зашифрования получаем:

Предположим теперь, что триграмма THE находится в начале T₁, тогда можно вычислить начало T₂:

Дальнейшие попытки продолжить по смыслу T₁ или T₂к успеху не приводят. Поэтому предположим, что T₂ также содержит THE. С учетом полученного результата, мы получа­ем два варианта расположения триграммы THE в тексте T₂. В первом из них триграмма THE расположена, начиная с пя­той позиции, во втором – начиная с шестой позиции.

Рассмотрим первый вариант:

Теперь ясно, что T₁ = THE APPLE, откуда получаем T₂ = TELL THEM.

Идея другого способа разложения разности открытых текстов состоит в упорядочении возможных вариантов пар букв (t_i, z_i) по убыванию апостериорных вероятностей p(t_i = v, z₁ = v – u /s_i = и), и, v Î A, i = 1,2,... , построении для каждого i упорядоченных колонок, состоя­щих из таких пар, и попытке чтения (аналогичной изложен­ной выше) в колонках сразу двух открытых текстов. При этом (как и ранее) используются позначные модели рассматривае­мых последовательностей и аналог формулы (9).

4.5.5. Криптоанализ шифра Виженера

Рассмотрим шифр модульного гаммирования с уравнени­ем (1), для которого гамма является периодической последовательностью знаков алфавита. Как указывалось ранее, такая гамма обычно получалась периодическим повторением некоторого ключевого слова. Например, ключевое слово KEY дает гамму KEYKEYKEY... . Рассмот­рим задачу вскрытия такого шифра по тексту одной криптограммы достаточной длины.

Пусть m– длина ключевого слова. Обычно криптоанализ шифра Виженера проводится в два этапа. На первом этапе определяется число m, на втором этапе – само ключевое слово.

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

Пусть d₁,d₂,... –найденные расстояния между повторе­ниями и d – наибольший общий делитель этих чисел. Тогда m должно делить d. Чем больше повторений имеет текст, тем более вероятно, что m совпадает с d. Для уточнения значения m можно использовать так называемый индекс сов­падения, введенный в практику У. Фридманом в 1920 г.

Для строки х = (х₁,...,x_m) длины т, составленной из букв алфавита А, индексом совпадения в х, обозначаемым I_c(х), будем называть вероятность того, что две случайно выбранные буквы из х совпадают.

Пусть А = {a₁,...,а_n}. Будем отождествлять буквы алфа­вита с числами, так что а₁ º 0,..., a_n-1º n — 2, а_n º n — 1.

Теорема. Индекс совпадения в х вычисляется по формуле

(14)

где f_i– число вхождений буквы а_i в х, i ÎZ_n.

Пусть х – строка осмысленного текста. Допустим, как и ранее, что буквы в х появляются на любом месте текста с соответствующими вероятностями р₀,…,p_n-1 независимо друг от друга, где р_i– вероятность появления буквы i в осмысленном тексте, iÎZ_n. В такой модели открытого текста вероятность того, что две случайно выбранные буквы из х совпадают с iÎZ_n, равна р_i², следо­вательно,

(17)

Взяв за основу значения вероятностей р_i, приведенные в Приложении 1 для открытых текстов, получим значения индексов совпадения для ряда евро­пейских языков:

Таблица 6. Индексы совпадения европейских языков

Предположим, что х – реализация независимых испыта­ний случайной величины, имеющей равномерное распределе­ние на Z_n. Тогда индекс совпадения вычисляется по формуле I_c(х)=1/n.

Вернемся к вопросу об определении числа m.

Пусть y₁y₂,…,y_m – данный шифртекст. Выпишем его с периодом m:

… … … …

и обозначим столбцы получившейся таблицы через Y₁ ,Y₂ ,…,Y_m.

Если m – это истинная длина ключевого слова, то каждый столбец Y_{i ,} iÎ1,…, m , представляет собой участок открытого текста, зашифрованный простой заменой.

В силу сказанного выше (для английского языка) I_c(Y_i)= 0,066 при любом i. С другой стороны, если m от­лично от длины ключевого слова, то столбцы Y_i будут более "случайными", поскольку они являются результатом зашифрования фрагментов открытого текста некоторым многоалфа­витным шифром. Тогда I_c(Y_i) будет ближе (для английско­го языка) к числу 1/26=0,038.

Заметная разница значений I_c(х) для осмысленных от­крытых текстов и случайных последовательностей букв (для английского языка – 0,066 и 0,038, для русского языка – 0,053 и 0,030) позволяет в большинстве случаев установить точное значение m .

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

Пусть х=(х₁,...,х_m),у=(у₁,...,y_l) – две строки букв алфавита А. Взаимным индексом совпадения в х и у, обозначаемым МI_c(х,у), называется вероятность того, что случайно выбранная буква из х совпадает со случайно выбранной буквой из у.

Пусть f_i– число вхождений буквы а_i в х, g_i– число вхождений буквы а_i в y, iÎZ_n.

Теорема. Взаимный индекс совпадения в х и у вычисля­ется по формуле

(19)

Пусть k=(k₁,...,k_m ) – истинное ключевое слово. Попытаемся оценить индексы М1_c(Y_i, Y_j).

Для этого напомним, что Y_s является результатом за­шифрования фрагмента открытого текста простой заменой букв алфавита (подстановкой) со сдвигом s. На основании этого получаем:

(20)

Заметим, что сумма в правой части последнего равенства зависит только от разности (s_i -s_j)mod n, которую назовем относительным сдвигом Y_i и Y_j, поэтому Y_i и Y_j с относительными сдвигами s и п – s имеют одинаковые взаимные индексы совпадения. Приведем таблицу значений сумм (20) для английского языка:

Таблица 7. Взаимный индекс совпадения при сдвиге s

Аналогичные таблицы можно получить и для других языков.

Обратим внимание на то, что ненулевые "сдвиги" дают взаимные индексы совпадения, изменяющиеся в пределах от 0,032 до 0,045, в то время как при нулевом сдвиге индекс М1_с(х,у) близок к 0,066. Это наблюдение позволяет опреде­лить величины относительных сдвигов s_i– s_j столбцов Y_i и Y_j .

Используя изложенный метод, мы сможем связать систе­мой уравнений относительные сдвиги различных пар столб­цов Y_i и Y_j .В результате останется 26 вариантов для клю­чевого слова, из которых можно выбрать наиболее предпочтительный вариант (если ключевое слово является осмысленным).

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

Контрольные вопросы

1. Приведите пример шифра перестановки, который может рассматриваться и как блочный шифр замены.

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

3. Какие свойства открытого текста используются при вскры­тии шифра вертикальной перестановки?

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

5. С какими примерами шифров замены и перестановки Вы познакомились в историческом обзоре?

6. Существуют ли шифры, не являющиеся ни шифрами за­мены, ни шифрами перестановки?

7. Приведите пример шифра многозначной замены.

8. Может ли блочный шифр быть шифром разнозначной за­мены?

9. Может ли шифр простой замены быть равнозначным, разнозначным, блочным шифром?

10. В каком случае шифр гаммирования является одноалфа­витным шифром?

11. Каково максимальное число простых замен, из которых может состоять многоалфавитный шифр?

12. Можно ли рассматривать множество возможных откры­тых и шифрованных текстов как множество шифровеличин и шифрообозначений шифра замены?

13. Какие шифры называются шифрами простой замены?

14. Что является ключом шифра простой замены? Каково макси­мально возможное число ключей шифра простой замены?

15. Что более целесообразно для надежной защиты информации:

архивация открытого текста с последующим шифрованием или шифрование открытого текста с последующей архиваци­ей?

16. Имеет ли шифр Плейфера эквивалентные ключи, то есть такие ключи, на которых любые открытые тексты шифруются оди­наково? Сколько различных неэквивалентных ключей имеет шифр Плейфера?

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

18. В чем слабость шифра гаммирования с неравновероятной гаммой?

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

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

21. Почему недопустимо использовать дважды одну и ту же гамму (даже случайную и равновероятную!) для зашиф­рования разных открытых текстов?

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

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

24. Назовите основные этапы работы по вскрытию шифра Виженера.

25. Каким образом рассчитывается индекс совпадения для реального языка?

26. Из каких простых замен «состоит» шифр гаммирования (как многоалфавитный шифр)?

Тема 5. Поточные шифры

5.1. Принципы построения поточных шифрсистем

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

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

Пусть А – алфавит открытых сообщений, совпадающий с множествами шифрвеличин и шифробозначений, {j_а : А®А} – совокупность из r биекций множества А, х=а₁,а₂…,а_l – произвольный открытый текст, kÎK – выбранный ключ зашифрования. Пусть

y(k,l)=а₁^(k)...а_l^(k), (a_j^(k)ÎN_r, j=1,…,l) (5.1)

является распределителем, отвечающим данным значениям kÎK, lÎN , где y : К ´ N —> N_r. — некоторое отображение в множество N_r = {1,2,. ..,r} . Тогда правило зашифрования определяется формулой Е_k(х)=у, где y=b₁b₂ …b_l и (5.2)

Таким образом, задача построения рассматриваемого шифра сводится к выбору множества шифрующих преобразований {j_а} и отображения y, задающего распределитель.

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

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

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

Достаточно, чтобы в каждом такте шифрующий блок обеспечивал возможность зашифрования лишь текущего знака a_j открытого текста в соответствии с (5.2). При этом совсем не обязательно строить целиком подстановочное преобразование a_j^(k) на всем алфавите А.

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

x(i +m)=f(х((i),..., x(i + т -1)), i > 0,

в которой f : А ^m —> А – некоторая функция от т переменных.

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

х(i +1) = а • х(i) +b, i > 0.

Обобщением линейного конгруэнтного генератора являются конгруэнтные генераторы, определяемые формулой вида

x(i+1)=f(x(i)), i > 0, (5.3)

в которой f : A —> A – произвольное отображение, легко вычисляемое для любого аргумента. Достаточно полно исследованы свойства таких генераторов, задаваемых полиномиальными преобразованиями f .

Изучались также генераторы, определяемые неполиномиальной рекуррентной зависимостью. Примером является целочисленный генератор, основанный на ''методе середины квадратов", для которого вычисление х(i+1) с помощью (3) сводится к отбрасыванию определенного числа знаков из десятичной (или двоичной) записи числа х(i)².

Исследования подобных, а также других генераторов, определяемых некими алгоритмическими правилами, показывают, что они уступают по своим (необходимым в криптографических приложениях) аналитическим и статистическим качествам рекуррентным последовательностям. Дело в том, что аналитическое представление преобразований позволяет проводить более глубокие исследования и строить последовательности с лучшими криптографическими качествами. В настоящее время большинство датчиков псевдослучайных чисел, в том числе реализованных в программных продуктах ведущих фирм, построены на основе регистров сдвига с линейными функциями обратной связи, или коротко – линейных регистров сдвига (ЛРС).

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

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

Если множество шифрующих преобразований {j_а} достаточно велико, то можно обеспечить стойкость шифрования даже при повторном использовании ключей. Для этого достаточно, чтобы в множестве {j_а} содержались npeo6paзования, переводящие любую пару букв открытого текста в любую пару букв шифрованного текста. Тогда по паре текстов, зашифрованных на одном и том же ключе, нельзя получить информацию об открытых текстах, поскольку любой паре букв шифртекстов может соответствовать произвольная пара букв открытых текстов.

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

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

Требования к управляющему блоку:

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

– статистические свойства управляющей гаммы должны приближаться к свойствам случайной равновероятной последовательности;

– в управляющей гамме должны отсутствовать простые аналитические зависимости между близко расположенными знаками;

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

Требование к шифрующему блоку:

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

Иногда выдвигается дополнительное требование:

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

Заметим, что выполнение перечисленных требований является необходимым, но не достаточным условием криптографической стойкости поточного шифра.

Примеры поточных шифрсистем