ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ

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

Получаемые программно из ключа, случайные или псевдослучайные ряды чисел называются на жаргоне отечественных криптографов гаммой, по названию у - буквы греческого алфавита, которой в математических записях обозначаются случайные величины. Интересно отметить, что в книге "Незнакомцы на мосту", написанной адвокатом разведчика Абеля, приводится термин гамма, который специалисты ЦРУ пометили комментарием - "музыкальное упражнение?", то есть в пятидесятые годы они не знали его смысла. Получение и размножение реализаций настоящих случайных рядов опасно, сложно и накладно. Физическое моделирование случайности с помощью таких физических явлений, как радиоактивное излучение, дробовой шум в электронной лампе или туннельный пробой полупроводникового стабилитрона не дают настоящих случайных процессов. Хотя известны случаи удачных применений их в генерации ключей, например, в российском криптографическом устройстве КРИПТОН. Поэтому вместо физических процессов для генерации гаммы применяют программы для ЭВМ, которые хотя и называются генераторами случайных чисел, но на самом деле выдающие детерминированные числовые ряды, которые только кажутся случайными по своим свойствам. От них требуется, чтобы, даже зная закон формирования, но не зная ключа в виде начальных условий, никто не смог бы отличить числовой ряд от случайного, как будто он получен бросанием идеальных игральных костей. Можно сформулировать три основных требования к криптографически стойкому генератору псевдослучайной последовательности или гаммы:

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

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

Вторая проблема состоит в следующем: на основании чего можно сделать заключение, что гамма конкретного генератора является непредсказуемой? Пока в мире нет еще универсальных и практически проверяемых критериев, позволяющих утверждать это. Неизвестна и общая теория криптоанализа, которая могла бы быть применена для такого доказательства, за исключением все возрастающего количества конкретных способов анализа, выработанных для различных практических целей. Интуитивно случайность воспринимается как непредсказуемость. Чтобы гамма считалось случайной, как минимум необходимо, чтобы ее период был очень большим, а различные комбинации бит определенной длины равномерно распределялись по всей ее длине. Итак, второе требование к ряду заключается в подтверждаемом статистически подобии его свойств настоящей случайной выборки. Каждый порядок элементов гаммы должен быть так же случаен, как и любой другой. Это требование статистики можно толковать и как сложность закона формирования ряда псевдослучайных чисел. Практически, если по достаточно длинной реализации этот закон вскрыть не удается ни на статистическом уровне, ни аналитически, то этим нужно удовлетвориться. Чем длиннее требуемая длина ряда, тем жестче к нему требования. Теперь подробнее расскажем, как вскрывались скрытые закономерности в последовательностях чисел. С древнейших времен люди наблюдали и изучали периодически повторяющиеся процессы, как фазы Луны, движения планет, чередования времен года, но не все такие цикличности выражены явно. Например, солнечные пятна, наблюдаемые невооруженным глазом с начала нашей эры и в телескопы с начала XVII века, дают пример скрытой периодичности в II лет, впервые обнаруженной Генрихом Швабе лишь в 1843 году. А вот среднегодовые температуры и изменение климата Земли связаны с циклами в 19 лет. Работы Винера и Хинчина поставили анализ периодичностей с головы на ноги. Ими предложено оценивать спектр случайных колебаний значений элементов гаммы как преобразование Фурье функции автокорреляции. При этом шумоподобному равномерному спектру гаммы без скрытых периодичностей соответствует автокорреляционная функция в виде одиночного выброса в нуле, то есть так называемая дельта-функция. Этот результат можно интерпретировать как непохожесть последовательности на себя при любом ее сдвиге.

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

Простейшие алгоритмы генерации

Заслуга конструирования длинных псевдослучайных рядов с хорошими статистическими свойствами полностью принадлежит криптографии. Не следует думать, что они нужны лишь криптографам - картирование Венеры стало возможным, когда длина периода случайного ряда импульсов превысила 10**40. Фотографирование этой планеты нельзя было сделать потому, что она всегда закрыта плотным слоем облаков. Локация же ее с Земли затруднена обилием помех и высокими требованиями к разрешению. Поэтому зондирование выполнялось случайной последовательностью импульсов указанного периода. После 300 зондирований, на что ушло более полгода, была получена карта, где различимы объекты размером около километра, а по высоте разрешение получено такое, какое достигнуто не везде на Земле. Генераторы псевдослучайных чисел используются очень широко в сотнях программных приложений от конструирования ядерных реакторов и радиолокационных систем раннего обнаружения до поисков нефти и многоканальной связи. Генерация псевдослучайных последовательностей давно занимала математиков. Одним из первых было предложение получать их как значения дробной части многочлена первой степени:

                Yn = Ent (a*n+b)

Если n пробегает значения натурального ряда чисел, то поведение Yn выглядит весьма хаотичным. Еще Карл Якоби доказал, что при рациональном коэффициенте а множество {Yn} конечно, а при иррациональном бесконечно и всюду плотно в интервале от 0 до 1. Для многочленов больших степеней такая задача была решена лишь в 1916 году выдающимся математиком нашего века Германом Вейлем. Кроме того, он установил критерий равномерности распределения любой функции от натурального ряда чисел. Небезынтересно привести его в краткой формулировке.

КРИТЕРИЙ ВЕЙЛЯ. Чтобы ряд х1, х2, x3, ... был распределен равномерно в интервале от 0 до 1, необходимо и достаточно, чтобы для любой интегрируемой по Риману функции f(x) было справедливо соотношение P{=Mf(x)}=1.

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

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

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

     G(n+1)=KGn+C MOD M 

В нем каждое последующее псевдослучайное число G(n+1) получается из предыдущего Gn умножением его на К, сложением с С и взятием остатка от деления на М. Весь фокус здесь в том, чтобы подобрать хорошие значения К, С и М, на что были потрачены десятилетия работы математиков. Подбор почти иррациональных К ничего не дает. Например, выбрав закон генерации последовательности G(N+1) = Ent (sqr(2)*Gn) на IBM PC при формате представления чисел с плавающей запятой IEEE в 4 байта, получим псевдослучайные ряды, обязательно заканчивающиеся циклами с периодами длиной всего лишь 1225 и 147 в зависимости от начального заполнения. Разумнее вычисления вести в целых числах. Для них было установлено, что при С=0 и М=2**N наибольший период М/4 достигается при K=3+8*i или K=5+8*i и нечетном начальном числе. При достаточно больших К ряд производит впечатление случайного. Насколько это верно читатель может выяснить самостоятельно следующей программой:

'----------проверка  случайности ряда чисел
DEFINT  A-Z: SCREEN  2: CLS
n =  1
DO
nold = n: n =  FnRnd% (n)
PSET (nold/64,CVL(MKI$(n)+MKI$(0) )\512)
LOOP UNTIL n =  1
END
'----генерация ряда чисел с периодом 16384
DEF FnRnd% (n) =CVI(LEFT$(MKL$(1381&*n) ,2))

В ней случайность ряда проверяется отображением на экране дисплея пар его чисел (Gn+1, Gn) в прямоугольнике размером 128 х 512. Это простой и удобный способ проверки случайности рядов чисел, так как на глаз заметны малейшие закономерности в получаемом орнаменте. Из опытов с этой программой можно убедиться, что как ни экспериментируй с подбором К, все равно закономерности видны и чисто случайного ряда чисел не получишь. Вспомните ехидное предложение Додо "становиться строго в беспорядке" из "Алисы в стране чудес". Результат можно несколько улучшить. Если С нечетно и K=1+4*i, то период ряда равен М. После долгих поисков К исследователи остановились на значениях 69069 и 71365. Кроме значений М=2**N широко используются выборы простых М, например, простого числа М=2**31-1, известного со времен Эйлера (Это число "плохо" тем, что в двоичной записи содержит лишь единицы. Однако оно может использоваться, если вычисления выполняются в десятичной арифметике.)

Однако обратимся к фактам. В 1948 году фон Нейман предложил генератор псевдослучайных чисел, который через год подвергся резкой критике. В 1972 году в пакете прикладных программ IBM 360 на языке Фортран появилась программа RANDU, а в 1977-м Форсайт показал, что тройки ее последовательных значений лежат на 15 параллельных плоскостях. В 1979 году Скраг опубликовал компактный алгоритм генерации псевдослучайных чисел, а через год Плаке доказал его статистическую неудовлетворительность. Этому списку нет конца: более месяца работы автор потерял из-за некомпетентно сделанного генератора случайных чисел в системе М86 ЕС 1840, который использовался для моделирования сложных процессов. В журнале "Наука и жизнь" за октябрь 1986 года М. Максимов поместил статью-предупреждение под названием "Случайны ли случайные числа?", где совершенно справедливо отметил негодность используемых генераторов. По его данным, генератор FRAN у БК-0010 имеет длину периода всего лишь 2**15, а бьет рекорды бессмыслицы генератор Бейсика ДВК, который имеет период лишь 8192 и последовательные тройки его "случайных" чисел, функционально связанные уравнением Gn-6*G(n+1)+9*G(n+2), равны целым числам. Не иначе, как от отчаяния, рад исследователей одновременно использует два и даже три разных генератора, смешивая их значения. Если разные генераторы независимы, то сумма их последовательностей обладает дисперсией, равной сумме дисперсий отдельных последовательностей. Иначе говоря, случайность рядов возрастает при их суммировании. Это дает слабую надежду на возможность конструирования генератора с приемлемыми для криптографии свойствами: случайностью и большой длиной периода.

Заметим, что некоторые "запутывания" последовательностей псевдослучайных чисел лишь ухудшают их статистические свойства. Далеко не всегда сложность формирования рада порождает случайность распределения. Например, генератор случайных чисел из игровой программы неизвестного происхождения для программируемого калькулятора использовал в качестве случайных чисел первые цифры последовательности {83**K}. Легко доказывается, что такой генератор будет на 14% чаще давать цифру 7, чем 8. В литературе приводится громадное количество формул для генерации случайных рядов, и автору довелось испытать их не один десяток, но, не то чтобы хорошей, а даже удовлетворительной по статистическим свойствам найти не удалось. Сдается, что часть подобных способов генерации случайных рядов предложена в качестве шутки криптографами, желающими упростить себе работу. Однако в системах программирования обычно используют все же конгруэнтные генераторы по алгоритму, предложенному Национальным бюро стандартов США, который, имея длину периода 2**24, обеспечивает очень неплохие статистические свойства. К сожалению, длина его периода для криптографии слишком мала и, кроме того, было доказано, что последовательности, генерируемые конгруэнтными генераторами, не являются криптографически стойкими. Если дана часть такой последовательности достаточной длины, то ее параметры могут быть восстановлены.

Интересный класс генераторов случайных чисел неоднократно предлагался многими специалистами целочисленной арифметике, в частности Джорджем Марсалиа и Арифом Зейманом. Генераторы этого типа основаны на использовании последовательностей Фибоначчи. Классический пример такой последовательности {0, 1, 1, 2, 3, 5, 8, 13, 21, 34...}. За исключением первых двух ее членов, каждый последующий член равен сумме двух предшествующих. Если брать только последнюю цифру каждого числа в последовательности, то получится последовательность чисел {0, 1, 1, 2, 5, 8, 3, 1, 4, 5, 9, 4...} Если эта последовательность применяется для начального заполнения массива большой длины, то, используя этот массив, можно создать генератор случайных чисел Фибоначчи с запаздыванием, где складываются не соседние, а удаленные числа. Марсалиа и Зейман предложили ввести в схему Фибоначчи "бит переноса", который может иметь начальное значение 0 или 1. Построенный на этой основе генератор "сложения с переносом" приобретает интересные свойства, на их основании можно создавать последовательности, период которых значительно больше, чем у применяемых в настоящее время конгруэнтных генераторов. По образному выражению Марсалиа, генераторы этого класса можно рассматривать как усилители случайности. "Вы берете случайное заполнение длиной в несколько тысяч бит и генерируете длинные последовательности случайных чисел". Однако большой период сам по себе еще не является достаточным условием. Слабые места гамм бывает трудно обнаружить и аналитику требуется применять утонченные методы анализа последовательностей, чтобы выделить определенные закономерности, которые скрыты в большом массиве цифр.

Последнее, на чем следует остановить внимание, это особенности использования стандартных генераторов случайных чисел в различных языках программирования, если уж ими пришлось воспользоваться. Так отметим, что известный в Бейсике оператор RANDOMIZE (Он такой же, как и во всех других языках программирования. например. Pascal или C++.), применяемый для начальной установки генератора случайных чисел, может ошарашить пользователя. Ибо после выполнения:

RANDOMIZE 231
х = RND
RANDOMIZE 231
у = RND

FUNCTION Rand (х, у)
х = RND (-х)
у = RND (-у): IF у = О THEN у = RND (-у)
Rand =  (х+у)  MOD  1
END FUNCTION

Период такой функции равен 2**24-(2**24-1), но вот свойства его ряда не обязаны при любых исходных х и у быть такими же хорошими, как у RND.

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

FOR i = 1 ТО 5
х = RND (-gamma (i))
FOR j = 0 TO 32
SWAP map (j), map (32 * RND)
NEXT: NEXT

Рекуррентные двоичные последовательности

Изложим теперь способ построения последовательностей случайных чисел с гарантировано хорошими для криптографии свойствами. Читатели, не интересующиеся практикой криптографии или стохастического моделирования, могут спокойно опустить эту подглавку и перейти к следующей. Для тех, кто решит все-таки изучить ее, сделаем несколько замечаний. Автор не рассчитывал на серьезную математическую подготовку читателей - в подавляющем большинстве институтов и университетов страны курс теории конечных полей если и читается, то лишь факультативно. Поэтому систематичности и строгости изложения ожидать не приходится. Цель - освоение принципов программной реализации хороших рядов псевдослучайных чисел, что достигается приведением аналогов и разбором конкретных примеров. Тем не менее, программисты по-видимому будут удовлетворены приведенной детальностью изложения, а ценители математической строгости могут уточнить неясные для себя вопросы, обратившись к книге "Современная прикладная алгебра" Г. Биркгоф и Т. Барти (Москва, "Мир", 1976) или же анналам математики Бурбаки.

По определению сложности закона генерации ряда чисел, если сложность последовательности {Gi} равна m, то любые m+1 последовательные ее значения зависимы. Если же эта зависимость представима линейной, то получается рекуррентное соотношение следующего вида:

          C0*Gi+C1*G(i-1)+...+Cm*G(i-m)=0

При этом C0 и Cm обязаны быть неравными нулю. По начальным данным Go, Gi, ... Gm-1 длины m строится бесконечная последовательность. Каждый ее последующий член определяется из m предыдущих. Последовательности такого вида легко реализуются на ЭВМ. Особенно простой вид их реализации получается когда все с, и д, принимают лишь значения 0 и 1, что соответствует значениям отдельных бит. На множестве таких чисел определены алгебраические операции сложения и умножения, то есть имеется поле из двух элементов. Поля указанного типа с конечным числом элементов называются по фамилии их первооткрывателя Эвариста Галуа и для поля с n элементами обозначаются как GF(n), где GF - аббревиатура от слов Galois Field (поле Галуа). Они существуют, лишь когда n равно простому числу, и тогда называются простыми, или степени простого числа, и тогда называются расширениями соответствующего простого поля. Так, поле из 2 элементов GF(2) - простое поле порядка 2, a GF(4) - его расширение. При вычислениях на ЭВМ используются поля Галуа из элементов {0, 1}, обозначаемые GF(2**N) и соответствующие строкам данных длиной в N бит. Таблицы арифметических операций в GF(2) будут следующими:

   +  0  1            * 0 1
   0  0  1            0 0 0
   1  1  0            1 0 1

На ЭВМ такому сложению соответствует операция XOR, уже известная нам по машинному шифру ручной замены, а умножению - операция AND. Это поле обладает замечательным свойством - операция вычитания в нем тождественна операции сложения и в записях не употребляется. Поля бит, как байт или слово, можно представить векторами, каждая компонента которых принимает значения из GF(2). Такие вектора удобно рассматривать как многочлены. Байт, например, можно представить многочленом седьмой степени, каждый член которого соответствует одному ненулевому биту в байте:

             (10010101 )=x**7+x**4+x**2+1 

Представление битовых полей данных в ЭВМ многочленами упрощает рассмотрение операции их сдвига. Сдвигу данных влево на один бит соответствует умножение многочлена на х, а вправо - деление на х.

Совокупность всех многочленов степени меньше n представляет собой векторное пространство размерности n над GF(2), так как многочлены можно складывать, вычитать или умножать на константу.

Теперь, фиксировав неразрешимый над GF(2) многочлен f(x) степени n+1, рассмотрим остатки от деления на него других многочленов. Их множество совпадает с множеством многочленов степени не больше n. Например, f(x)=x**2+x+1 над GF(2) неприводим, потому что f(0)=1 и f(1)=1. Для него остатками будут элементы {0, 1, х, х+1}. На множестве этих остатков можно задать арифметические операции сложения и умножения, рассматривая остатки от деления на многочлен f(x). Легко проверить, что определенные таким образом сложение и умножение обладают всеми необходимыми свойствами обычных арифметических операций: коммутативностью, ассоциативностью и дистрибутивностью. Результат сложения или умножения над двумя элементами из приведенного множества тоже ему принадлежит. И, наконец, в множестве определены О и 1 так, что для произвольного элемента х имеем 0+х=х и 1*х=х. Таким образом, получено GF(4) - расширение поля GF(2) присоединением к нему остатков от деления произвольных многочленов на неприводимый над ним многочлен х**2+х+1. Выбирая разные неприводимые многочлены, можно получать разные расширения GF(2).

Из школьного курса математики известно, что над полем комплексных чисел любой многочлен разложим на линейные множители или, что то же самое, имеет столько корней, какова его степень. Однако это не так для других полей - в полях действительных или рациональных чисел многочлен х**2+х+1 корней не имеет и не может быть разложен на линейные множители. Аналогично, в поле GF(2) многочлен х**2+х+1 тоже не имеет корней, что просто проверить непосредственно: 1*1+1+1=1 и 0*0+0+1=1. Тем не менее у f(x)=x**2+x+1 в поле Галуа GF(4) существует корень х, соответствующий многочлену х из таблиц выше, так как f(x)=х**2 +х+1 по модулю f(x).

Элементы поля Галуа GF(2**N) относительно умножения образуют абелеву группу, то есть на этом множестве для любых его элементов х, у и z выполняются аксиомы:

     x*y=y*x*x*(y*z)=(x*y)*zx*1=1*xx*1/x=1/x*x=1

Если рассмотреть степени произвольного элемента х из GF(2**N), то обнаружим, что они образуют абелеву подгруппу. Такие подгруппы принято именовать циклическими. Число элементов этой подгруппы называют порядком элемента х. Из такого определения порядка следует, что если многочлен р(х) принадлежит GF(2**N) и имеет порядок k, то р(х)**K=1. Разберем теперь несколько важных свойств, касающихся порядка элементов в GF(2 ), изложенных в виде теорем.

ТЕОРЕМА 1. Если f(x)-неприводимый многочлен над GF(2), то выполняется равенство f(x**2)=f(x)**2.

Это равенство доказывается тем, что все попарные произведения в f(x)**2 равны нулю над GF(2). Например,

(х**2+х+1)**2=х**4+x**2+1.

ТЕОРЕМА 2. Если неприводимый многочлен f(x) над GF(2**N) имеет порядок k, то k делит 2**N-1.

Это следует из теоремы Лагранжа, утверждающей, что число элементов группы G делится на число элементов любой своей подгруппы Н. Подгруппа Н расслаивает группу G на смежные классы элементов, не пересекающиеся меж собой. Так, элементы х и у считаются принадлежащими одному классу по подгруппе Н, если у/х принадлежит Н. Поскольку классы не пересекаются и содержат одинаковое число элементов, то число элементов группы делится на число элементов в подгруппе. Из теоремы 2 вытекает важное следствие, что если 2**N-1 простое число, то мультипликативная группа GF(2**N) циклическая и порядок любого ее неединичного элемента тоже равен 2**N-1.

ТЕОРЕМА 3. Любой многочлен р(х) из GF(2**N) удовлетворяет уравнению х**k=х, где К=2**N.

Порядок ненулевого р(х) делит 2**N-1 и имеем х**(K-1)=1, а так как для р(х)=0 имеем уравнение х=0, то в результате любой р(х) удовлетворяет уравнению х**K=х.

Отметим особое положение уравнения х**K=х, где К=2**N, поскольку его корни порождают все элементы поля GF(2 ). Так как уравнение х**(K-1)-х=0 имеет корнем х=0, то, разделив его на х, получаем уравнение х**(K-1)-1=0, все корни которого ненулевые. Производная уравнения имеет вид (x**k-x)=2*N*x**(n-1)-1=1, и у нее нет общих корней с исходным уравнением. Следовательно, в этом уравнении все корни различны, и так как их число равно 2**n, то они совпадают со всеми элементами поля GF(2).

ТЕОРЕМА 4. Многочлен х**k-1 делит х**M-1 в том и только в том случае, если k делит M.

Это вытекает из того факта, что если все корни х**k-1 являются также и корнями х**m-1, то m должно делиться на k.

Теперь обратимся к использованию полиномов в практике вычислений на ЭВМ, широко распространено и легко реализуется программно. Рассмотрим электронную схему деления данных в поле из N бит на полином:

            f(x) = C0+C1*x+...+ Cn*х**N 


      N  N-1               3  2   1
         --¬ --¬          --¬--¬ --¬
  ------>+++>+++----->----++++++>+++------¬
  ¦      LT- LT-          LT-LT- L+-      ¦
  L-T---T-+-T-+-T---------T+-T+-T-+-<------
    L---+---+---+---------+--+--+----

 --¬
 ¦+¦ сумматор XOR
 L--
 --¬
 ¦ ¦ регистр сдвига
 L--

На схеме биты показаны квадратными клетками. Шаг процедуры деления состоит в сдвиге данных влево на один бит и дозаписи освобождающегося крайнего правого бита суммой значений бит по модулю 2, умноженных на соответствующие коэффициенты многочлена f(x), то есть не все ячейки сдвига соединены с относящимися к ним сумматорами. В результате последовательного выполнения отдельных шагов деления исходных данных а(х), справа в данные дозаписывается последовательность s(x), которая выражается формулой:

             s(x)=a(x)/f(x)=S0+S1*x+S2*x**2+...

                3   2     1
                         --¬
            ------>------+++-------¬
            ¦            LT-       ¦
            ¦  ---T----T--+--¬     ¦
            L--+--+----+-----<------

Он будет генерировать следующие последовательности при разных начальных данных (периоды в скобках):

000 => (0)
001 => (0011101)
010 => (0100111)
O11 => (0111010)
100 => (1001110)
101 => (1010011)
110 => (1101001)
111 => (1110100)

Рассмотрим теперь программную процедуру, реализующую деление на примитивный неприводимый многочлен х**3+х+1 в поле Галуа GF(8), представленную короткой программой на языке Бейсик. Переменные в ней рассматриваются как целые числа.

'программа деления на многочлен х**З+х+1
DEFINT A-Z
n = 1
DO
m = О

'-----------расчет бита переноса
IF n AND 2^2 THEN m = m+1
IF n AND 2^0 THEN m = m + 1
n = 2 *  (n AND (2^2-1)) OR (m AND 1)
LOOP UNTIL n = 1
END

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

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

 2**31-1 =2147483647,

    2**61-1 =2305843009213693951.

Самое большое известное сейчас простое число - так называемое 32-е число Мерсенна, найденное лишь в 1992 году. Его запись содержит 227832 десятичные цифры или примерно сто страниц текста.

Нахождение неприводимых многочленов для генерации гаммы представляет сложную вычислительную задачу. Неприводимые многочлены, с помощью которых фактически строятся поля Галуа для криптографии, по своей роли напоминают простые числа в натуральном ряду. Нахождение их, как и простых чисел, производится подбором и требует больших затрат вычислительных мощностей сверхбыстродействующих ЭВМ. Поэтому в открытых публикациях данные о неприводимых многочленах очень больших степеней просто отсутствуют. Отметим, что всегда с(n)=с(0)=1, так как используется неприводимый многочлен степени п. Сложность программной реализации генератора существенно зависит от числа ненулевых коэффициентов неприводимого многочлена f(x): чем их меньше, тем проще и быстрее программа. Заметим, что в этом случае и криптоаналитикам проще жить: известно, что у них есть секретные теоремы, касающиеся трехчленов. Поэтому практически применяются многочлены с довольно большим числом ненулевых членов. Четного числа ненулевых членов быть не может, так как в этом случае корнем будет х=1 и многочлен можно разделить на х+1, а это доказывает приводимость.