рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

М-последовательности. ГПСЧ типа ЛРС1

М-последовательности. ГПСЧ типа ЛРС1 - Лекция, раздел Математика, Материалы лекций Математические основы криптологии   Опр Ед Ел Ени Е. Последовательностью Над Полем ...

 

Опр ед ел ени е. Последовательностью над полем


 

GF ( p)


 

будем


 


называть любую функцию


U p : N ®F p , заданную на множестве N и


 


принимающую значения в поле


GF ( p) .


 


Рассмотрим класс последовательностей


U p , получаемых на основе


 

схемы линейного регистра сдвига с обратной связью (ЛРС), изображенной на

 

рис. 2.1. Схема содержит n-разрядный регистр сдвига (запоминающие ячейки

 


регистра обозначены символами


T1,


T2 , …,


Tn ), сумматоры, обозначенные


 

символом Å, по модулю два в цепи обратной связи и цепи (отводы) с

 


коэффициентами передачи


ai Î{0,1},


i = 1, n . Если


ai =0 , это эквивалентно


 


отсутствию (наличию при


ai =1) связи между выходом i-го разряда регистра


 


и входом i-го сумматора Å. Символ a0


принимает значения 0 или 1. Схему,


 

изображенную на рис. 2.1, обозначим символом ЛРС1.

x1 x2 xn

 

 


T1 T2


. . . Tn


 

 


a1 a2


. . . an

 

a0


 

Рис. 2.1. Схема ЛРС1

 

 


В очередном такте работы регистра двоичные символы


x1 ,


x2 , …,


xn ,


 

содержащиеся в его ячейках, умножаются на соответствующие

 


коэффициенты ai


и суммируются по модулю два, после чего происходит


 

сдвиг (вправо) информации в регистре, а в освободившуюся ячейку T1

 

записывается вычисленное значение суммы. Двоичные наборы

 

< x1, x2 , ..., xn > , снимаемые в каждый такт работы схемы с выходов ячеек регистра, можно рассматривать как двоичные n-разрядные целые числа.

Последовательность двоичных символов, снимаемых с выхода одного

 


(любого) разряда регистра является последовательностью U p


над полем


 

GF (2) . Такие последовательности называют линейными рекуррентными последовательностями (ЛРП).

Устройство, реализованное по рассмотренной схеме, принято называть

 

генератором псевдослучайных чисел или генератором псевдослучайных последовательностей.

Начальное заполнение ячеек регистра двоичными символами является

 

начальным состоянием регистра.

 


Введем следующие обозначения.


X (t0 )


n-разрядный двоичный вектор,


 


начальное состояние регистра.

 

одних нулей (нулевой вектор).


X 0 – начальное состояние, состоящее из


 


Пусть


a0 =0 , тогда состояние схемы в момент времени


t + 1


 

описывается следующей системой уравнений

 

ìx1 (t +1) =a1x1 (t) +a2 x2 (t) +... +an-1xn-1 (t) +a n xn (t)


x
ï
ï (t + 1) =


x1 (t)


íx3 (t +1) =

ï...

ïîxn (t +1) =


x2 (t)


 

xn-1 (t ).


 

 

Полученную систему уравнений можно записать в матричном виде

 

 

X (t +1) =AT ×X (t) , (2.1)

 

 


æa a


... a a ö


ç
æx1 (t +1) ö


æx1 (t ) ö


ç1 2


n -1 n ÷


 

где


X (t +1) =çx2


(t +1) ÷


X (t ) =çx2


(t ) ÷


A = 0


0 ... 0 0

1 ... 0 0 .


ç
÷,
÷
ç ... ÷


ç ... ÷


T ç...


... ÷


ç
÷,
èxn (t + 1) ø


èxn (t ) ø


ç

è 0 0


÷

... 1 0 ø


 


Квадратную матрицу AT


размера n называют характеристической


 

матрицей ГПСЧ, изображенного на рис. 2.1. Элементы первой строки матрицы определяют структуру обратных связей схемы ГПСЧ.

Последовательности, порождаемые ГПСЧ, являются периодическими, то есть через определенное количество тактов (сдвигов) последовательность

повторится.

 


Опр ед ел ени е. Периодом последовательности U p


называют


 


наименьшее число


L ÎN , для которого существует натуральное число


K >0


 

такое, что для всех


 

i ³ 0


 

справедливо равенство

 

U p (K +i +L) =U p (K +i) .


Максимальный период последовательности U p


для схемы ГПСЧ равен


 


2n - 1. В самом деле, при


a0 =0


начальное состояние регистра


X (0)


 

порождает последовательность U p , состоящую из одних нулей (запрещенное

 


состояние), а число различных заполнений регистра длины n равно


2n .


 

Однако, в зависимости от структуры обратной связи и от начального состояния регистра, период последовательности может быть иным (в

частности, даже единичным (L=1)).

 


Опр ед ел ени е. Последовательность U p


над полем


GF (2) , получаемая


 


по соотношению (2.1) и имеющая максимальный период


2n -1, называется


 

максимальной линейной рекуррентной последовательностью - M -

 

последовательностью.

 


При


a0 =1


состояние регистра


X (0)


не является запрещенным. В этом


 

случае начальное состояние регистра, состоящее из всех единиц, является запрещенным, поскольку порождает последовательность U, состоящую

также из одних единиц. При других начальных состояниях

 


последовательность U над полем


GF (2)


также имеет максимальный период


 

2n - 1, но является инверсной по сравнению с M - последовательностью.


 

Период ЛРП определяется характеристическим многочленом над полем

 


GF (2)


матрицы


AT :

 

 

f (x) =xn +a1


 

xn -1 +a


 

x n-2 + ... + a


 

 

n-1


 

 

x +an


 

 

, (2.2)


 


которым является определитель матрицы


(AT +XE) , где Е – единичная


 


матрица размера n. Коэффициенты ai


многочлена


f ( x)


определяют первую


 


строку матрицы AT

 

полинома (2.2)).


(матрицу AT


называют сопровождающей матрицей


 


Если характеристический многочлен


f ( x)


над полем


GF (2)


является


 


неприводимым и примитивным, то период ЛРП равен


2n -1.


 


Замечание . Таблица примитивных многочленов для степени

 

приведена в Приложении 1, в соответствии с [9].


n = 1, 127


 

О п р е д е л е н и е . Наименьший из всех возможных периодов ЛРП

 

называется минимальным ее периодом.

 


Если характеристический многочлен


f ( x)


является только


 

неприводимым, то максимальный период ЛРП, в этом случае,

 


L =ord


f <2n -1.


 

Начальной информацией для построения ГПСЧ, порождающего ЛПР с

 

заданным периодом L, является характеристический многочлен (2.2) с

 


ord


f = L .

 

Пример 2.1. Пусть задан примитивный многочлен


 

P1 (x) =x4


 

+ x 3


 

+ 1.


 

Соответствующая схема ГПСЧ изображена на рис. 2.2 а.

 

x1 x2 x3 x4

 

 

T1 T2 T3

 

 


Рис. 2.2 а. Схема ГПСЧ, соответствующая


P1 ( x) = x 4


+ x 3 + 1


 


Пусть для этой схемы


X (t0 ) =<1001 >. В табл. 2.1 представлена


 


периодическая последовательность векторов


X (ti ),


i = 0, 14 , снимаемых с


 

выходов


 

x1 ,


 

x2 ,


 

x3 ,


 

x4 (диаграммы работы ГПСЧ), с


 

L = 15 .

 

Таблица 2.1 (начало)


 

  X (t0 ) X (t1) X (t2 ) X (t3 ) X (t4 ) X (t5 ) X (t6 )
x1
x2
x3
x4

 


При других начальных состояниях


X (t0 ) ¹X 0


получим 15


 


последовательностей векторов


X (ti )


с периодом L = 15, различающихся


 


некоторым сдвигом относительно друг друга.


 

Таблица 2.1 (окончание)


 

  X (t7 ) X (t8 ) X (t9 ) X (t10 ) X (t11) X (t12 ) X (t13 ) X (t14 )
x1
x2
x3
x4

 

 


Двоичная последовательность, снимаемая с одного выхода

 

является последовательностью U над полем GF (2) .


xi ,


i = 1, 4 ,


 


Пример . Пусть задан примитивный многочлен


P2 (x) =x4


+ x + 1 .


 

Соответствующая схема ГПСЧ изображена на рис. 2.2 б и диаграмма - в табл.

 

2.2.

 

x1 x2 x3 x4

 

 

T1 T2 T3

 

 


Рис. 2.2 б. Схема ГПСЧ, соответствующая


P2 ( x) = x 4


+ x + 1


 

Пример 2.3. Пусть задан характеристический неприводимый многочлен

 


g(x) =x4 +x3 +x2 +x +1. Порядок этого многочлена


ord g =5 , так как


g ( x)


 


является делителем многочлена


x5 +1, т.е.


 


x5 + 1 = ( x 4 + x3 + x 2 + x + 1)( x + 1) .


 

Таблица 2.2 (начало)


 

  X (t0 ) X (t1) X (t2 ) X (t3 ) X (t4 ) X (t5 ) X (t6 ) X (t7 )
x1
x2
x3
x4

 

 

Таблица 2.2 (окончание)

 

  X (t8 ) X (t9 ) X (t10 ) X (t11 ) X (t12 ) X (t13 ) X (t14 )
x1
x2
x3
x4

 


Схема ГПСЧ, соответствующая


g ( x) , представлена на рис. 2.3.


x1 x2


x3 x4


 

 

T1 T2 T3

 


Рис. 2.3. Схема ГПСЧ для


g(x) =x4 +x3 +x2 +x +1


 

 


Данная схема в зависимости от


X (t0 ),


X (t0 ) ¹X 0 , порождает три


 

диаграммы состояний, представленных в табл. 2.3, с одним и тем же


 

периодом


 

L =5 .


 

Замечание 2.2. М-последовательности имеют статистическую

 


равномерность на периоде


L = 2n - 1, то есть число единиц


N1 и нулей N2


 


определяется величинами


N1 = 2


n -1 и


N 2 = 2


n -1


- 1.


 


 

x1x2 x3 x 4


 

x1x2 x3 x 4


Таблица 2.3

 

x1x2 x3 x 4


1 11 0 0 11 0 0 01 0
1 1 1 1 0 0 1 1 1 0 0 1

 

1 1 1 1


0 0 1 1


1 0 0 1


 

– Конец работы –

Эта тема принадлежит разделу:

Материалы лекций Математические основы криптологии

В М Захаров.. Материалы лекций.. Математические основы криптологии..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: М-последовательности. ГПСЧ типа ЛРС1

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Лекция№1
    Криптология состоит из двух направлений: криптографии и криптоанализа.   Криптография – наука о способах преобразования (шифрования)

Асимметричное шифрование
    Алгоритм RSA (Revest, Shamir, Adelman) 1978г. e, n А, М В    

Алгоритм передачи секретного ключа по открытому каналу
В середине 70-х годов произошел настоящий прорыв в современной криптографии – появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь от

Алгоритм Евклида
  Алгоритм Евклида дает правило вычисления наибольшего общего делителя   (НОД) 2-х натуральных чисел. (a,b)= d , где d – НОД НОК – наименьшее общее кратное

Алгоритм рае кнута
   

Свойства делимости целых чисел
  Два числа a и b называются взаимно простыми если их НОД = 1   (a1,a2,….,an)= НОД   (a1,a2) = d1   (a3,d1) = d2

Свойства делимости целых чисел
  Свойства приведены без доказательства.   1)Свойство дистрибутивности   Пусть заданны три натуральных числа a,b,

Простые числа
  1)- каноническое разложение &nb

Получение простых чисел
  По мере того как мы будем изучать курс «Математические основы криптологии» мы будем возвращаться к этой теме. Задача получение простых чисел во многом зависит от того как с

Проверка простоты чисел Мерсенна
  Числами Мерсенна называются числа вида М(p) = 2p - 1, pÎN.   Задача для чисел Мерсенна - поиск в ряду э

Sp-2 mod M(p) ≡ 0, т.е. остаток равен 0
  Поясним, каким образом задается ряд Sk. Члены последовательности  

Алгоритм Бухштаба
  Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое необходимо разложить на 2

Алгоритм Ферма
  Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа n есть делитель (который

Функция Эйлера
  Имеется целое, положительное число m. Оно может быть как составным, так и простым. Функцию Эйлера принято обозначать, практически во всех учебниках как:  

Мультипликативная функция
  Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по фо

Числовая функция
  Это функция устанавливающая целую часть от некоторого рационального числа [a] – обозначение   может быть как положительное, так и отрицательное число

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

Возведение натуральных чисел по модулю в большие степени по схеме Горнера
Пусть задано выражение вида   y = a x mod m , (1.1)   где a ÎN - основание степени,  

Сравнимость по модулю. Модулярная арифметика
    Понятие «модулярная арифметика» ввел немецкий ученый Гаусс.   Модульная арифметика аналогична обычной арифметике: она коммутативна, ассоциатив

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

Доказательство теоремы Эйлера
  Пусть даны m и φ(m)=k   Имеем число a, причем (a,m)=1     Берем ряд натуральных чисел: a1

Модулярная арифметика (продолжение) Квадратичные вычеты Степенные вычеты
  Продолжим исследовать вычеты. Широкое применение в криптографии нашла формула: xn ≡ a mod m, n=2 xn ≡ a mod p – квадратичный выч

Элементы теории конечного поля простейшие алгебраические структуры
  Под алгебраической структурой будем понимать некоторое множество   S с одной или несколькими операциями на нем.   Пусть S х S обозначае

Кольца и поля
  Алгебраические структуры с двумя бинарными операциями - сложение и умножение.     Определение 1.7. Множество S называется кольцом, е

Характеристика поля
  Определение 1.12. Если в поле Fq все ненулевые элементы имеют аддитивный порядок k, то говорят, что поле Fq имеет характеристику k. Обозначение. р - простое число.

Вычисление обратных элементов
  В арифметике действительных чисел просто вычислить обратную величину a−1 для ненулевого a: a-1 = 1/a или a? a-1 = 1.

Многочлены над конечным полем
  Onределенuе 1.13. Многочленом (относительно х) над полем GF(p)   m

Для любого простого р и nÎN существует хотя бы один неприводимый над полем GF(p) многочлен степени n [9]
Любой неприводимый над полем GF(p) многочлен степени п делит     многочлен x pm - x   (также и мног

Алrебраические структуры над множеством многочленов
  Кольцо многочленов над полем GF(p)   Определение 1.17. Кольцо, образованное многочленами над полем GF(p), называется кольцом многочлен

Расширение полей
  Рассмотрим, какова связь полей GF(p) и GF( p n ).   Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, на

Системы уравнений сравнений
  Общий вид:   x ≡ c1 mod m1   x ≡ c2 mod m2

Pound; b£ n-1
  Если для каждого простого делителя p числа n-1 справедливы следующие утверждения:     (1) bn-1≡ 1(mod n),  

Числа Кармайкла
  Может ли составное нечетное число n быть псевдопростым по всем взаимно-простым с ним основаниям b? Забегая вперед, скачем, что «да».     Заметим

Процедура получения устойчивых простых чисел
  1. Генерируются простые числа s,t   2. Получаем простое число r такое что, (r-1) делит t без остатка: r-1|t На основе этих двух операций получаем про

M - последовательности на основе произведения многочленов
Рассмотрим способ построения схемы линейного регистра сдвига на основе характеристического многочлена, задаваемого как произведение   многочленов, при &nbs

Произведения многочленов
  Рассмотрим следующие свойства ЛРП, порождаемой схемой ГПСП,   изображенной на рис. 2.1, при a0 =1.  

ЛЕКЦИЧ 16
  Способы представления элементов поля GF(2n)   Для представления элементов в полях Галуа вида GF(2n) существуют ра

Алгоритм получения элементов поля GF(2n) в стандартном базисе
  Для построения элементов поля GF(2n) в стандартном базисе существует следующий алгоритм, использующий сдвиговыерегистры. На входе: поле GF(2n

Заданными в стандартном базисе
   

Алгоритм асимметричного шифрования RSA
  Алгоритм RSA предложили в 1978 г. 3 автора: Райвест (Rivest), Шамир (Shamir) и Адлеман (Adleman). RSA является алгоритмом с открытым ключом, работающим в режимах шифрования данных и

Математическая модель алгоритма RIJNDAEL
  Байты можно рассматривать как элементы конечного поля GF(28) -   многочлены степени не более 7   а7х7 + а6х

Раунд преобразования алгоритма RIJNDAEL
  RIJNDAEL выполняет серию однотипных раундов преобразования шифруемого блока. Шифруемый блок и его промежуточные состояния в ходе преобразования представляются в виде квадратной матр

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги