Математические основы криптологии и криптографические методы и средс
..pdfXOR. Это, в принципе, генерирует достаточно случайную последова тельность бит.
По второму методу на введенные символы алгоритм не обраща ет никакого внимания, зато конспектирует интервалы времени, через которые произошли нажатия. Запись моментов производится по от счетам быстрого системного таймера (частота 1,2 МГц) или по внут реннему счетчику процессора, появившемуся в процессорах, начиная с Intel Pentium (частота соответствует частоте процессора). Посколь ку верхние и младшие биты имеют определенную корреляцию между символами (первые из-за физических характеристик человека, вторые из-за особенностей операционной системы), то они отбрасываются (обычно удаляются 0-8 старших бита и 4-10 младших).
Как более редко встречающиеся варианты можно встретить:
♦комбинацию обоих клавиатурных методов;
♦метод, основанный на манипуляторе «мышь»-он выделяет случайную информацию из смещений пользователем указа
теля мыши.
В мощных криптосистемах военного применения используются действительно случайные генераторы чисел, основанные на физиче ских процессах. Они представляют собой платы, либо внешние уст ройства, подключаемые к ЭВМ через порт ввода-вывода. Два основ ных источника белого Гауссовского шума - высокоточное измерение тепловых флуктуаций и запись радиоэфира на частоте, свободной от радиовещания.
1.3.5.Линейные рекуррентные двоичные последовательности над полем и кольцом
Изложим теперь способ построения последовательностей слу чайных чисел с гарантировано хорошими для криптографии свойст вами. По определению сложности закона генерации ряда чисел, если сложность последовательности {<7/} равна т , то любые т + 1 после довательные ее значения зависимы. Если же эта зависимость пред ставима линейной, то получается рекуррентное соотношение сле дующего вида:
Co *Gi + С i *G(,_ i) + + Ст *Ga_ ,„) - О.
При этом Со и Стдолжны быть отличны от нуля. По начальным данным Go, Gu G,n-i длины т строится бесконечная последователь ность. Каждый ее последующий член определяется из т предыдущих. Последовательности такого вида легко реализуются на ЭВМ. На множестве таких чисел определены алгебраические операции сложе ния и умножения, т.е. имеется поле из двух элементов. Поля указан ного типа с конечным числом элементов являются полями Галуа. Они существуют, лишь когда п равно простому числу, и тогда назы ваются простыми, или степени простого числа, и тогда называются расширениями соответствующего простого поля. Так, поле из 2 эле ментов GF(2) - простое поле порядка 2, a G F(4)-ero расширение. При вычислениях на ЭВМ используются поля Галуа из элементов {О, 1}, обозначаемые GF{2N) и соответствующие строкам данных длиной в N бит. Это поле обладает замечательным свойством - операция вы читания в нем тождественна операции сложения и в записях не упот ребляется. Поля бит, как байт или слово, можно представить векто рами, каждая компонента которых принимает значения из GF(2). Та кие векторы удобно рассматривать как многочлены. Байт, например, можно представить многочленом седьмой степени, каждый член ко торого соответствует одному ненулевому биту в байте:
(1 0 0 1 0 1 0 1 ) =х7 +хА+xz + 1.
Представление битовых полей данных в ЭВМ многочленами упрощает рассмотрение операции их сдвига. Сдвигу данных влево на один бит соответствует умножение многочлена на х, а вправоделение на х. Совокупность всех многочленов степени меньше п представляет собой векторное пространство размерности п над GF(2), так как многочлены можно складывать, вычитать или умножать на константу.
Теперь, фиксировав неразрешимый над GF(2) многочлен fix) степени я+ 1 , рассмотрим остатки от деления на него других много членов. Их множество совпадает с множеством многочленов степени не больше п. Например, fix) = х2 + х + 1 над GF{2) неприводим, по
тому чтоДО) = 1 иД1) = 1. Для него остатками будут элементы {0, 1, х, х + 1}. На множестве этих остатков можно задать арифметические операции сложения и умножения, рассматривая остатки от деления на многочленX*). Легко проверить, что определенные таким образом сложение и умножение обладают всеми необходимыми свойствами обычных арифметических операций: коммутативностью, ассоциа тивностью и дистрибутивностью. Результат сложения или умноже ния над двумя элементами из приведенного множества тоже ему принадлежит. И, наконец, в множестве определены 0 и 1. Таким об разом, получено GF(4) - расширение поля GF(2) присоединением к нему остатков от деления произвольных многочленов на неприво димый над ним многочлен х2 + х + 1. Выбирая разные неприводимые многочлены, можно получать разные расширения GF(2).
Из школьного курса математики известно, что над полем ком плексных чисел любой многочлен разложим на линейные множители или, что то же самое, имеет столько корней, какова его степень. Од нако это не так для других полей - в полях действительных или ра циональных чисел многочлен х2 + х + \ корней не имеет и не может быть разложен на линейные множители. Аналогично в поле GF(2) многочлен х2 + х + 1 тоже не имеет корней, что просто проверить непосредственно: 1*1 + 1 + 1 = 1 и 0*0 + 0+1 = 1. Тем не менее УЛ*) =х* + Х + 1 в поле Галуа GF(4) существует корень х, соответст вующий многочлену х из таблиц выше, так как J{x) = х2 +х + I по
модулю/(*)•
Теорема 16. Если J{x) - неприводимый многочлен над GF(2), то
выполняется равенство^*2) ~А Х)2 Это равенство доказывается тем, что все попарные произведе
ния вДх) 2 равны нулю над GF(2). Например, (х2 + х + I) 2 = х4 + х2 + 1. Теорема 17. Если неприводимый многочленДх) над GF(2N) име
ет порядок к, то к делит 1N - 1 .
Это следует из теоремы Лагранжа, утверждающей, что число элементов группы G делится на число элементов любой своей под группы Н. Подгруппа Н расслаивает группу G на смежные классы элементов, не пересекающиеся меж собой. Так, элементы х и у счи
таются принадлежащими одному классу по подгруппе Н, если у/х принадлежит Н. Поскольку классы не пересекаются и содержат оди наковое число элементов, то число элементов группы делится на число элементов в подгруппе. Из теоремы 2 вытекает важное следст вие, что если 2N - 1 простое число, то мультипликативная группа GF(2n) циклическая и порядок любого ее неединичного элемента то же равен 2 ^ - 1 .
Теорема 18. Любой многочлен р(х) из GF(2N) удовлетворяет уравнению хк = х, где к = 2Ы.
Порядок ненулевого р(х) делит 2N - 1, и имеем х - 1 = 1, а так как для р(х) = 0 имеем уравнение х = 0 , то в результате любой р(х) удовлетворяет уравнению х* = х.
Отметим особое положение уравнения х* = х, где к = 2Ы, по скольку его корни порождают все элементы поля GF{2). Поскольку уравнение хк —х = 0 имеет корнем х = 0 , то, разделив его на х, полу чаем уравнение х*- 1 - 1 = О, все корни которого ненулевые. Произ водная уравнения имеет вид (хк - х) = 2 *N*x"~' - 1 = 1, и у нее нет общих корней с исходным уравнением. Следовательно, в этом урав нении все корни различны, и, так как их число равно 2 ", они совпа дают со всеми элементами поля GF(2).
Теорема 19. Многочлен хк~ 1 делит х"‘ - 1 в том и только в том случае, если к делит М.
Это вытекает из того факта, что если все корни х - 1 являются также и корнями хт - 1 , то т должно делиться на к.
Теперь обратимся к использованию полиномов в практике вы числений на ЭВМ, что широко распространено и легко реализуется программно. Рассмотрим электронную схему деления данных в поле из N бит на полином:Дх) = Со + С\ *х + + С„ *xN
Шаг процедуры деления состоит в сдвиге данных влево на один бит и дозаписи освобождающегося крайнего правого бита суммой значений бит по модулю 2 , умноженных на соответствующие коэф фициенты многочленаДх), т.е. не все ячейки сдвига соединены с от носящимися к ним сумматорами. В результате последовательного выполнения отдельных шагов деления исходных данных а(х), справа в данные дозаписывается последовательность Дх), которая выража
ется формулой s(x) = а(х)//[х) = S0 + S\ *х + Si*x? + ..., справедливость которой просто проверить, приравнивая коэффициенты при х в урав нении S(JC) *fix) = а(х). Таким образом, получена связь между линей ными рекуррентными последовательностями, делением многочленов над GF(2) и алгоритмом реализации деления на ЭВМ. Например, пусть имеем над GF(2) рекуррентное соотношение G, + G(,_i) + G ^) = 0. Мно гочлен, который ему отвечает, равен 1 + х + х3. Это неприводимый мно гочлен над GF(2), который порождает расширение GF(8). Мультипли кативная группа в GF(8 ) имеет 7 элементов и циклична в силу простоты числа 7. Он будет генерировать следующие последовательности (табл. 6 ) при разных начальных данных (периоды в скобках):
Таблица 6 Сгенерированные последовательности при разных
начальных данных
000 |
= > |
(0) |
001 |
= > |
(0011101) |
010 |
= > |
(0100111) |
011 |
= > |
(0111010) |
100 |
= > |
(1001110) |
101 |
= > |
(1010011) |
по |
= > |
(1101001) |
111 |
= > |
(1110100) |
Всоответствии с теорией период такого генератора составляет 7
ивключает в себя все ненулевые числа из 3 бит. Реализация проце дуры деления многочленов на ЭВМ или, что то же самое, генерации рекуррентных последовательностей проста.
Особый интерес для генерации длинных последовательностей представляют элементы GF(2N), имеющие порядок, равный 2N- 1. Они называются примитивными, потому что, возводя их в степень, можно получить весь набор ненулевых элементов поля Галуа. Если 2N - 1 простое число, то все элементы мультипликативной группы (кроме 1, конечно!) примитивны. Однако такие числа, называемые простыми числами Мерсенна, расположены редко. Они с давних пор
слыли чемпионами среди простых чисел по своему размеру. Во вре мя Эйлера наибольшим простым числом было: 231 —1 =2 147 483 647, а через сто лет в 1883 году русский самоучка Первушин нашел уже шестое число Мерсенна, равное: 261 - 1 = 2 305 843 009 213 693 951.
Самое большое известное сейчас простое число-так называе мое 32-е число Мерсенна, найденное лишь в 1992 году. Его запись содержит 227 832 десятичные цифры или примерно сто страниц тек ста. Нахождение неприводимых многочленов для генерации гаммы представляет сложную вычислительную задачу. Неприводимые мно гочлены, с помощью которых фактически строятся поля Галуа для криптографии, по своей роли напоминают простые числа в нату ральном ряду. Нахождение их, как и простых чисел, производится подбором и требует больших затрат вычислительных мощностей сверхбыстродействующих ЭВМ. Поэтому в открытых публикациях данные о неприводимых многочленах очень больших степеней про сто отсутствуют. Отметим, что всегда с(п) = с(0) = 1, так как исполь зуется неприводимый многочлен степени п. Сложность программной реализации генератора существенно зависит от числа ненулевых ко эффициентов неприводимого многочлена J(x): чем их меньше, тем проще и быстрее программа. Заметим, что в этом случае и криптоа налитикам проще жить: известно, что у них есть секретные теоремы, касающиеся трехчленов. Поэтому практически применяются много члены с довольно большим числом ненулевых членов. Четного числа ненулевых членов быть не может, так как в этом случае корнем будет х = 1 и многочлен можно разделить на х + 1, а это доказывает приво димость.
1.3.6. Последовательности максимальной длины
Естественно, что желательно получить как можно более длин ный период последовательности от многочлена заданной степени. Ответ на вопрос, каков максимальный период, получаемый от после довательности, мы уже имеем - не больше в GF{2N). Можно
было бы и поверить в существование примитивных многочленов, порождающих такие последовательности. Тем не менее желательно иметь процедуру, позволяющую находить такие многочлены пусть не практически, то хотя бы теоретически, если они только сущест вуют. Поэтому приведем теорему.
Теорема 20. Если многочлен/(х) степени п делит многочлен хк ~\ лишь при к > Т - 1, то период его любой ненулевой последователь ности равен 2" - 1 .
Пусть Дх) делит многочлен хк - 1 при к = 2" - 1, тогда длина пе риода любой порожденной им ненулевой последовательности делит 2n'- 1. Если 2 ^ -1 простое число, то последовательность максималь ного периода обеспечена. Иначе допустим, что длина периода неко торой последовательности равна к < 2N - 1. В этом случае Д р с ) делит многочлен xN - 1 вопреки условию, следовательно, всегда выполня ется строгое равенство к = 2N - 1. Например, многочлен х4 + х + 1 де лит х15 + 1, но не делит ни один многочлен хк- 1 при к < 15, т.е. явля ется многочленом максимального периода 15. Этому многочлену со ответствует рекуррентное соотношение
Gi + G(/_i) + G(/_4) = 0 .
При разных его начальных значениях генерируются такие последо
вательности: 0 0 0 1 =>(0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 ), 0 0 1 0 = >(0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 ),
ООП =>(001111010110010) и т. д. Все они в соответствии с теорией имеют длину периода 15 и отличаются друг от друга лишь сдвигом. Из этого вытекает очень важное для криптографии свойство после довательностей максимального периода, что их одиночный период состоит из всех разных неповторяющихся ненулевых блоков длины л, что гарантирует хорошие статистические качества получаемых псевдослучайных чисел. В частности, такие последовательности не имеют скрытой периодичности, на чем следует остановиться не сколько подробнее. Иногда последовательности такого вида с мак симальным периодом называют последовательностями Де Брюйна в честь исследователя, подробно описавшего в открытой научной печати их свойства.
Теорема 21. Если S —последовательность максимального пе риода, то она имеет равномерный спектр.
Теперь мы знаем, что грех искать лучший материал для псевдо случайных последовательностей, чем рекуррентные последователь ности описанного вида. Они обладают исключительным набором свойств: предельно большая длина периода, отсутствие скрытых пе риодичностей, статистическая равномерность, что делает их незаме нимыми в криптографии. Однако читатель, искушенный в математи ке, скорее будет огорчен, чем обрадован предыдущим изложением. И вот почему: мы рассуждали о замечательных свойствах последова тельностей, существование которых не доказано. Придется лишь по верить в существование неприводимых многочленов любой степени и, значит, соответствующих им последовательностей, потому что это дается в самом красивом и, наверное, самом сложном из разделов чистой математики теории Галуа. Вот что о ее авторе сообщает Большой энциклопедический словарь:
«ГАЛУА (Galois) Эварист (1811-32), франц. математик. Тр. по теории алгебр, ур-ний положили начало развитию современной ал гебры. С идеями Г связаны такие ее важнейшие понятия, как группа, поле и др. Науч. наследие Г. - небольшое число весьма кратко напи санных работ, из-за новизны идей не понятых при жизни Г. Опубл. в 1846 Ж. Лиувиллем».
Нельзя не отметить, что теория Галуа представляет собой жем чужину современной математики. Согласно преданию Эварист Галуа
вночь на 30 мая 1832 года перед дуэлью вместе с письмом другу на писал на 41 странице работу, обессмертившую его имя и получив шую название теории Галуа. Одна бессонная ночь двадцатилетнего французского гения навеки обрекла миллионы студентов на хрони ческую бессонницу перед экзаменом по этому предмету, и многие из них будут сетовать на черствость подруги Эвариста, оставившей его
вночь перед дуэлью безутешным, хотя стрелялся он из-за нее. Злые языки утверждают, что разработанная им теория представляет собой акт мести системе высшего образования за то, что его дважды среза ли на вступительном экзамене по математике в Политехнической
школе. Для нас важно лишь то, что этот гениальный юноша создал теорию, доказывающую существование многочленов, дающих по следовательности максимального периода сколь угодно большой степени. Таким образом, в существование их поверить можно. А вот нахождение таких многочленов до сих пор покрыто мраком. Без со мнения, криптографические службы высокоразвитых стран работали и работают над поиском многочленов как можно более высокой сте пени, но свои последние результаты они почти не освещают в откры той печати. Хуже всего дела идут в России, где не было ни одной открытой публикации отечественных полиномов высокой степени, пригодных для помехоустойчивого кодирования и криптографии и колоссальные средства налогоплательщиков оказались, по образ ному выражению Балоуна из «Бравого солдата Швейка», в сортире. Поэтому приведем старые и открытые данные из демократических стран. В следующей таблице (табл. 7) приведены номера 4 бит, кото рые можно использовать при генерации последовательностей макси мальной длины для случайных чисел длиной 8, 16, 24 и 32 бита, т.е. для целого числа байт в памяти ЭВМ. Эти биты задают коэффициен ты неприводимых многочленов ненулевой степени над GF(2).
Таблица 7
Номера бит, которые можно использовать при генерации последовательностей максимальной длины
п |
|
Биты |
переноса |
|
8 |
1 |
2 |
3 |
8 |
16 |
0 |
2 |
11 |
16 |
24 |
0 |
1 |
6 |
24 |
32 |
0 |
1 |
21 |
32 |
Известен неприводимый многочлен х61 + х3 + 1, а по многочле нам больших степеней в литературе данных найти не удалось. По этому, естественно, возникает вопрос: как ведут себя последователь ности, порожденные произведением взаимно простых многочленов. Ответ на него дает следующая теорема, доказательство которой мы опустим, так как оно в нашем контексте неинтересно.
Теорема 22. Если fix) и h(x) - взаимно простые многочлены, то тогда многочлен fix)-h(x) порождает последовательности, являющиеся суммами последовательностей дляДдг).
Итак, период последовательности от fix)-h(x) равен произведе нию периодов соответствующих последовательностей fix) и h(x). Од нако причин для радости мало, так как сюда же входят и последова тельности периода 1 для нулевых данных. Приведем пример. Много члены fix) = х3 + х + 1 и h(x) = х2 + х + 1 неприводимы и взаимно просты. В зависимости от начальных данных многочлен fix) имеет одну последовательность периода 1 и 7 последовательностей перио да 7. Многочлен h(x) имеет одну последовательность периода 1 и 3 последовательности длины 3, а многочлен fix)-h(x) имеет такой спектр периодов (табл. 8):
Таблица 8 Зависимость между периодом и числом последовательностей
Период |
Число последовательностей |
||
1-1 |
= 1 |
1-1 |
= 1 |
1-3 |
= 3 |
1-3 |
= 3 |
1-7 = 7 |
1-7 |
= 7 |
|
3-7 |
= 21 |
3-7 = 21 |
Таким образом, произведение многочленов дает последователь ности с произведением периодов. Ненулевые начальные данные для многочленов максимальных периодов гарантируют получение про изведения этих периодов, что должно устроить конструкторов гаммы. Так, если взять 3 генератора с длинами чисел 28, 29 и 31 бит, то при одновременной их работе период будет длиной около 1026, что впол не устроит достаточно серьезную криптографическую систему. На чальное заполнение всех рядов должно быть при этом опять-таки ненулевым. Такие реализации генераторов гаммы выглядят некраси во. Однако они гораздо более стойки криптологически, так как в их многочленах много коэффициентов, которые при взламывании шиф ра криптоаналитиком ему придется подбирать. Кроме того, вовсе не обязательно просто складывать эти последовательности, но можно