Последовательности максимальной длины

Естественно, что желательно получить как можно более длинный период последовательности от многочлена заданной степени. Ответ на вопрос, каков максимальный период, получаемый от последовательности, мы уже имеем - не больше 2**N-1 в GF(2^). Можно было бы и поверить в существование примитивных многочленов, порождающих такие последовательности. Тем не менее, желательно иметь процедуру, позволяющую находить такие многочлены пусть не практически, то хоть теоретически, если они только существуют. Поэтому приведем теорему:

ТЕОРЕМА 5. Если многочлен f(x) степени n делит многочлен х**k-1 лишь при k>2**n-1, то период его любой ненулевой последовательности равен 2**n-1.

Пусть f(x) делит многочлен х**k-1 при k=2**n-1, тогда длина периода любой, порожденной им ненулевой последовательности делит 2**N-1. Если 2**N-1 простое число, то последовательность максимального периода обеспечена. Иначе допустим, что длина периода некоторой последовательности равна k<2**N-l. В этом случае f(x) делит многочлен х**N-1 вопреки условию, следовательно, всегда выполняется строгое равенство k=2**N-1.

Например, многочлен х**4+х+1 делит х*15+1, но не делит ни один многочлен х**K-1 при k<15, то есть является многочленом максимального периода 15. Этому многочлену соответствует рекуррентное соотношение:

                 Gi+G(i-1)+G(i-4)=0

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

0001=>(000111101011001), 0010=> (001000111101011),
0011=> (001111010110010) и т. д.

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

ТЕОРЕМА 6.
Если S - последовательность максимального периода, то она имеет равномерный спектр.

Если S - последовательность максимального периода, то она состоит из 2**(N-1)-1 нулей и 2**(N-1) единиц. Последовательность {(Si*Si+j)} при любом j>0 представляет собой сдвиг исходной последовательности, а при j=0 состоит из 2**N-1 единиц. Таким образом, автокорреляционная функция R равна: 2**N-1 при j=0 и 0 при j>0. А, поскольку Rj представляет собой дельта-функцию, то ее спектр равномерный и последовательность этим похожа на случайный белый шум. Теперь мы знаем, что грех искать лучший материал для псевдослучайных последовательностей, чем рекуррентные последовательности описанного вида. Они обладают исключительным набором свойств: предельно большая длина периода, отсутствие скрытых периодичностей, статистическая равномерность, что делает их незаменимыми в криптографии. Однако читатель, искушенный в математике, скорее будет огорчен, чем обрадован предыдущим изложением. И вот почему: мы рассуждали о замечательных свойствах последовательностей, существование которых не доказано. Придется лишь поверить в существование неприводимых многочленов любой степени и, значит, соответствующих им последовательностей, потому что это дается в самом красивом и, наверное, самом сложном из разделов чистой математики теории Галуа. Вот что о ее авторе сообщает Большой энциклопедический словарь:

ГАЛУА (Galois) Эварист (1811-32), франц. математик. Тр. по теории алгебр, ур-ний положили начало развитию современной алгебры. С идеями Г. связаны такие ее важнейшие понятия, как группа, поле и др. Науч. наследие Г. - небольшое число весьма кратко написанных работ, из-за новизны идей не понятых при жизни Г. Опубл. в 1846 Ж. Лиувиллем.

Нельзя не отметить, что теория Галуа представляет собой жемчужину современной математики. Согласно преданию, Эварист Галуа в ночь на 30 мая 1832 года перед дуэлью вместе с письмом другу написал на 41 странице работу, обессмертившую его имя и получившую название теории Галуа. Одна бессонная ночь двадцатилетнего французского гения навеки обрекла миллионы студентов на хроническую бессонницу перед экзаменом по этому предмету, и многие из них будут сетовать на черствость подруги Эвариста, оставившей его в ночь перед дуэлью безутешным, хотя стрелялся он из-за нее. Злые языки утверждают, что разработанная им теория представляет собой акт мести системе высшего образования за то, что его дважды срезали на вступительном экзамене по математике в Политехнической школе. Для нас важно лишь то, что этот гениальный юноша создал теорию, доказывающую существование многочленов, дающих последовательности максимального периода сколь угодно большой степени. Таким образом, в существование их поверить можно. А вот нахождение таких многочленов до сих пор покрыто мраком. Без сомнения, криптографические службы высокоразвитых стран работали и работают над поиском многочленов как можно более высокой степени, но свои последние результаты они почти не освещают в открытой печати. Хуже всего дела идут в России, где не было ни одной открытой публикации отечественных полиномов высокой степени пригодных для помехоустойчивого кодирования и криптографии и колоссальные средства налогоплательщиков оказались, по образному выражению Балоуна из "Бравого солдата Швейка", в сортире. Поэтому приведем старые и открытые данные из демократических стран.

В следующей таблице приведены номера 4 бит, которые можно использовать при генерации последовательностей максимальной длины для случайных чисел длиной 8, 16, 24 и 32 бита, то есть для целого числа байт в памяти ЭВМ. Эти биты задают коэффициенты неприводимых многочленов ненулевой степени над GF(2).

n               биты переноca
8       1       2       3       8
16      0       2       11      16
24      0       1       6       24
32      0       1       21      32

Известен неприводимый многочлен x**61+x**3+1, a по многочленам больших степеней в литературе данных найти не удалось. Поэтому естественно возникает вопрос: как ведут себя последовательности, порожденные произведением взаимно простых многочленов. Ответ на него дает следующая теорема, доказательство которой мы опустим, так как оно в нашем контексте неинтересно.

ТЕОРЕМА 7. Если f(x)и h(x)- взаимно простые многочлены, то тогда многочлен f(x)*h(x) порождает последовательности, являющихся суммами последовательностей для f(x) и h(x).

Итак, период последовательности от f(x)*h(x) равен произведению периодов соответствующих последовательностей f(x) и h(x). Однако причин для радости мало, так как сюда же входят и последовательности периода 1 для нулевых данных. Приведем пример. Многочлены f(x)=x**3+x+1 и h(x)=x**2+x+1 неприводимы и взаимно просты. В зависимости от начальных данных многочлен f(x) имеет одну последовательность периода 1 и 7 последовательностей периода 7. Многочлен h(x) имеет одну последовательность периода 1 и 3 последовательности длины 3, а многочлен f(x)*h(x) имеет такой спектр периодов:

период  число последовательностей
1*1=1   1*1=1
1*3=3   1*3=3
1*7=7   1*7=7
3*7=21  3*7=21

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

n          биты                 взаимная     простота    периодов
                       17      18      20      21      22      23      25      28      29      31
17      2       17      -       +       +       +       +       +       +       +       +       +
18      6       18      +       -       -       -       -       +       +       -       +       +
20      2       20      +       -       -       +       -       +       -       -       +       +
21      1       21      +       -       +       -       +       +       +       -       +       +
22      0       22      +       -       -       +       -       +       +       -       +       +
23      4       23      +       +       +       +       +       -       +       +       +       +
25      2       25      +       +       -       +       +       +       -       +       +       +
28      2       28      +       -       -       -       -       +       +       -       +       +
29      1       29      +       +       +       +       +       +       +       +       -       +
31      2       31      +       +       +       +       +       +       +       +       +       -

В таблице знаком "+" указана взаимная простота периодов этих рядов, а знаком "-" наличие общих делителей. Так, если взять 3 генератора с длинами чисел 28, 29 и 31 бит, то при одновременной их работе период будет длиной около 10**26 , что вполне устроит достаточно серьезную криптографическую систему. Начальное заполнение всех рядов должно быть при этом опять таки ненулевым. Такие реализации генераторов гаммы выглядят некрасиво. Однако они гораздо более стойки криптологически, так как в их многочленах много коэффициентов, которые при взламывании шифра криптоаналитиком ему придется подбирать. Кроме того, вовсе не обязательно просто складывать эти последовательности, но можно одной последовательностью шифровать другую. Так, если у'и у" - гаммы с разными периодами, а Г" и Г" шифры типа DES, образуемые ими, то гамма у=Г"у'+Г'у" будет очень длинной и весьма стойкой к взлому.

Анализ псевдослучайных последовательностей

Пусть известен участок ключа {g1, g2, ... G(2n+2)), полученного с помощью рекуррентного соотношения длиной n. Здесь Gi и другие переменные рассматриваются как биты, то есть над полем GF(2). В этом случае есть возможность восстановить весь ключ, реконструировав рекуррентное соотношение. Рекуррентное соотношение:

        Cn*Gi + C(n-1)G(i+1) + ... + C0*G(i+n) = О
выполняется при i=1, 2, ... n+1. Поэтому имеем систему из n+1 линейных уравнений с n+1 неизвестными, при решении которой получаем коэффициенты использованного рекуррентного соотношения Ci, позволяющие продлить известный участок ключа вперед или назад на любую длину. Фактически неизвестных коэффициентов только n-1, так как Co=Cn=1. Есть ряд алгоритмов решения этой системы, но и обычный метод исключения переменных тоже хорош, так как при вычислениях в конечных полях ошибок округления нет, а полученная система линейных уравнений не вырождена. Допустим имеется участок гаммы ...10101111... из 8 бит. Степень больше 4 мы реконструировать не сможем, а меньшая недопустима, так как подряд встречаются 4 единицы. Поэтому, составив систему из 4 уравнений:
     С4+С2=1 C3+С1=1 C4+C2+C1=l C3+C2+C1=1
и решая ее, получаем С4=1, C3=1, C2=0 и C1=0, что отвечает многочлену х**4+х**3+1. Таким образом, получаем еще один довод в пользу дополнительного усиления шифра многоалфавитной замены дополнительной перестановкой, потому что иначе участок последовательности можно попытаться вскрыть, отгадывая текст исходного сообщения. Для длины рекуррентного соотношения n=60 и кодировании символов группами по 5 бит достаточно отгадать 24 символа, чтобы свести задачу к подбору перестановки. На первый взгляд кажется, что невозможно отгадать столь длинный участок текста. Однако большую помощь в этом может оказать ориентировочное знание содержания исходного сообщения, в котором могут встречаться устойчивые словосочетания большой длины, например, "государства среднеазиатского региона". Эта область достаточно сложна и деликатна, чтобы углубляться в нее дальше. Отметим лишь достоинство блочных шифров, заключающееся в том, что желающим их расколоть криптоаналитикам при достаточной длине блока ничего не остается, как вести атаку прямым подбором ключа, так как надежда отгадать кусок исходного текста большой длины весьма химерична. Кроме того, так как избыточность исходного текста существенно ослабляет шифр, то нужно перед шифрованием преобразовать его, используя оптимальный код, уменьшающий избыточность. Естественно, что для этого непригодны стандартные программы сжатия и архивации как ARC, ZIP и им подобные, так как создают в файле заголовок с множеством полей, содержимое которых легко предсказать. Необходимо пользоваться собственным сжатием, согласованным с программой шифрования, как это сделано в системе PCSecure.

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

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

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

Чтобы сбить с толку криптоаналитиков многие генераторы гаммы основаны на комбинации двух или более генераторов с использованием нелинейных логических функций. Один из наиболее простых способов комбинации двух сдвиговых регистров с линейными обратными связями состоит в применении переключателя с отношением переключаемых разрядов 2:1 и носит имя генератора Джеффи. Слабое место такого генератора связано с тем, что такая система может быть легко раскрыта методом криптоанализа с использованием так называемых линейных синдромов. При современном состоянии техники сдвиговых регистров с линейными обратными связями выходная последовательность может быть раскрыта по перехваченному сегменту гаммы длиной в строку текста. Известен еще один генератор этого типа - генератор Дженнинга - тоже использующий переключатель для объединения двух регистров с линейными обратными связями. И он довольно несложно вскрывается криптоаналитиками. Таким образом, хотя множество возможных нелинейных комбинаций последовательностей, образующих гамму, очень большое, вклад их в криптографическую стойкость системы в целом незначителен и необходимо применять перестановки, как это сделано в DES.

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

Теперь приведу вольный пересказ старой газетной статьи. Шпион несколько раз прикурил, фотографируя спрятанным в зажигалке фотоаппаратом открытую шифровальную машину с разных сторон. Затем, введя ключ из одних пробелов, он несколько сот раз нажал букву А. Полученная перфолента шифровки была после внимательного рассматривания туго свернута в рулон и небрежно отброшена, но в конце концов незаметно очутилась в его кармане. Теперь вопрос: почему шпиона заинтересовала шифровка дурацкого текста из одной повторяющейся буквы? Надеюсь, что читатели смогут теперь ответить на этот вопрос точно и обстоятельно.

[MAIN] [BACK] [NEXT]
Hosted by uCoz