К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) будут следующими:




Содержание  Назад  Вперед