Кpиптогpафия от папиpуса до компьютеpа

       

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


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

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

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

справедливость которой просто проверить, приравнивая коэффициенты при х в уравнении s(x)*f(x)=a(x). Таким образом, получена связь между линейными рекуррентными последовательностями, делением многочленов над GF(2) и алгоритмом реализации деления на ЭВМ. Например, пусть имеем над GF(2) рекуррентное соотношение Gi+G(i-1)+G(i-3)=0. Многочлен, который ему отвечает, равен 1+х+х**3. Это неприводимый многочлен над GF(2), который порождает расширение GF(8). Мультипликативная группа в GF(8) имеет 7 элементов и циклична в силу простоты числа 7. Электронная схема этого рекуррентного генератора представляется так:

    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,



или пятое, а через сто лет в 1883 году русский самоучка Первушин нашел уже шестое число Мерсенна, равное:

     2**61-1 =2305843009213693951.

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


Содержание раздела