Иванов Криптографические методы засчиты информации в компютерных 2012

1			x3
1	2	3	4	5

x5		x7	x8 x8		x7		x5		x3		1
6	7	8		1	2	3	4	5	6	7	8

1	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	1	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0	1	0	0	0	0	0
1	0	0	1	0	0	0	0	0	0	0	1	0	0	0	0
0	1	0	0	1	0	0	0	0	0	0	0	1	0	0	0
1	0	1	0	0	1	0	0	0	0	0	0	0	1	0	0
1	1	0	1	0	0	1	0	0	0	0	0	0	0	1	0
1	1	1	0	1	0	0	1	0	0	0	0	0	0	0	1
1	1	1	1	0	1	0	0	1	1	0	1	0	1	0	0
1	1	1	1	1	0	1	0	0	1	1	0	1	0	1	0
1	1	1	1	1	1	0	1	0	0	1	1	0	1	0	1
1	1	1	1	1	1	1	0	1	1	0	0	1	1	1	0
1	1	1	1	1	1	1	1	0	1	1	0	0	1	1	1
0	1	1	1	1	1	1	1	1	1	1	0	0	1	1	1
0	0	1	1	1	1	1	1	1	0	1	0	0	1	1	1
0	0	0	1	1	1	1	1	1	0	0	0	0	1	1	1
1	0	0	0	1	1	1	1	1	0	0	1	0	1	1	1
				...							...
0	0	0	0	0	0	0	1	1	0	1	0	1	0	0	1
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
				а							б

Рис. 8.7. Два варианта построения LFSR, соответствующего образующему многочлену Ф(х) = х8 + х7 + х5 + х3 + 1:

а– генератор Фибоначчи и его диаграмма состояний;

б– генератор Галуа и его диаграмма состояний

Двоичные параллельные РСЛОС. На рис. 8.8 и 8.9 пока-

заны схемы двоичных параллельных генераторов, формирующих 8-разрядную и 32-разрядную ПСП длиной 265 – 1 соответст-

венно. Рассматривается случай

N = 65, Ф(х) = х65 + х32 + 1, Т = Т1.

251

...

...

q1

q2

q3

q31

q32

q33

q64

q65

а

1

8 8

q1

q9

q17

q25

8

q33

q41

q49

q57

q65

8

7 7

q2

q10

q18

q26

q34

q42

q50

q58

7

...

3 3	q6	q14	q22	q30	3	q38	q46	q55	q62	4
										3
2 2	q7	q15	q23	q31	2	q39	q47	q55	q63
										2
1 1	q8	q16	q24	q32	1	q40	q48	q56	q64		б

Рис. 8.8. Байтовый генератор ПСЧ:

а– битовый генератор Фибоначчи, соответствующий Ф(х) = х65 + х32 + 1;

б– байтовый генератор Фибоначчи, соответствующий Ф(х) = х65 + х32 + 1

q1(t)

q1(t)

q33(t)

q65(t)

q34(t)

...

...

...

q31(t) q31(t) q63(t) q64(t)

q32(t) q32(t) q64(t) q65(t)

Рис. 8.9. Генератор двоичной М-последовательности, соответствующий Ф(х) = х65 + х32 + 1, k = 32, Т = Т1

Программная реализация этого генератора на языке Ассемблера IBM PC в предположении, что

>q32 t ... q2 t q1 t EBX,

>q64 t ... q34 t q33 t EAX, q65 t CF ,

где qi – состояние i-го разряда LFSR ( i 1, 65), потребует всего лишь трех команд на каждый такт работы устройства:

RCR	EAX
XCHG	EAX, EAX
XOR	EBX, EAX

252

8.4.4. Основы теории конечных полей

Рассматриваются основы теории полей Галуа, в том числе особенности построения конечных полей на основе двоичных непримитивных многочленов, а также схемотехнические основы реализации полей Галуа на основе регистров сдвига [1, 20, 24,

27, 29].

Основы теории недвоичных полей Галуа, необходимые для понимания принципов построения последовательных и параллельных недвоичных генераторов ПСЧ, изложены в [29].

Группа. Группой G называется непустое множество элеметов , Ε, ϑ, ..., обладающее следующими свойствами:

1) для элементов множества G определена некоторая операция двух переменных, записываемая в виде Ε ϑ или

в виде ΔΕ ϑ в первом случае операцию условно называют сложением, во втором – умножением;

2)на множестве G выполняются следующие законы:

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

(свойство замкнутости);

для любых трех		элементов группы справедливо
( Ε) ϑ	(Ε ϑ) , если операция является сложе-
нием; или	(ΔΕ)ϑ	(Εϑ) , если операция является ум-

ножением (ассоциативный закон); в группе существует единичный элемент, который

обозначается как 0 для сложения, при этом для любого

элемента	группы справедливо 0 +					=	+ 0 =	;
либо как 1 для умножения, при этом для любого эле-
мента	группы справедливо 1				=	1 =	;
каждый элемент		группы обладает обратным эле-
ментом, который обозначается как (–						) для сложения,
при этом	+ (– ) = (–		)	+	= 0; либо как -1			для
умножения, при этом			-1	=	-1 = 1.
Если для любых элементов		, Ε группы выполняется комму-
тативный закон, т.е. справедливо			равенство			Ε	Ε	для

сложения или ΔΕ ΕΔ для умножения группа называется ком-

253

мутативной или абелевой.

Число элементов группы называется порядком группы. В дальнейшем будем рассматривать только конечные группы, т.е. группы, определенные на конечном множестве элементов.

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

Некоторое подмножество группы G называется подгруппой, если оно удовлетворяет всем свойствам группы.

Конечная группа, которая состоит из степеней 1, g, g2, g3, … одного из ее элементов g, называется циклической группой. При этом наименьшее целое число e такое, что ge = 1, называется порядком элемента g. Такие группы всегда коммутативны. Любая группа простого порядка и любая подгруппа циклической группы являются циклическими. Каждый элемент любой группы G порождает в G циклическую подгруппу, состоящую из всех его степеней.

Конечное поле. Конечным полем или полем Галуа GF(p) на-

зывается конечное множество из p (где p = qn, q – простое, n – натуральное) элементов , Ε, ϑ, ..., обладающее следующими

свойствами:

1) для элементов множества GF(p) определены две операция двух переменных, записываемая в виде Ε ϑ или

в виде ΔΕ ϑ , первую операцию условно называют сложением, вторую – умножением;

2)на множестве GF(p) выполняются следующие законы:

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

справедливо (		Ε) ϑ	(Ε ϑ) , для операции ум-
ножения справедливо			(ΔΕ)ϑ (Εϑ)	(ассоциативный
закон);
для	любых	трех	элементов	справедливо
( Ε)ϑ	Δϑ Εϑ ;

254

в GF(p) существует нулевой элемент, который обозна-

чается как 0, при этом для любого элемента		поля
справедливо 0 + = + 0 = , 0	0 0 ;

в GF(p) существует единичный элемент, который обо-

значается как 1, при этом для любого элемента		поля
справедливо 1	= 1 = ;
каждый элемент	конечного поля обладает обратны-

ми аддитивным и мультипликативным элементами,

которые	обозначаются	как	(–	) для сложения, при
этом	+ (– ) = (–	) +		= 0; либо как -1 для
умножения, при этом		-1	=	-1 = 1;

3)в GF(p) все ненулевые элементы поля могут быть представлены в виде степени примитивного элемента Ζ , т.е.

в виде Ζ i. Таким образом, поле может быть записано в

виде

GF(p) = { 0, Ζ 0 Ζ 1 Ζ 2 … Ζ p - 2 },

где Ζ 0 = 1, Ζ 1 = Ζ , Ζ p - 1= 1, Ζ p= Ζ …, а множество Z*p всех ненулевых элементов поля GF(p) образует абелеву

группу порядка p – 1.

Простейшие поля получаются следующим образом. Пусть q – простое число. Тогда целые числа 0, 1, 2, ... , (q – 1) образуют поле GF(q), при этом операции сложения, вычитания, умножения и деления выполняются по модулю q. Более строго, GF(q) – это поле классов вычетов по модулю q, т.е.

GF(q) = {0, 1, 2, ... , (q – 1)},

где через 0 обозначаются все числа, кратные q, через 1 – все числа, дающие при делении на q остаток 1, и т.д. С учетом этого вместо q – 1 можно писать –1. Утверждение = Ε в GF(q)

означает, что – Ε делится на q или что сравнимо с Ε по модулю q, т.е.

{ Ε modp .

Поле, содержащее p = qn элементов, где q – простое число, а n – натуральное, не может быть образовано из совокупности целых чисел по модулю p. Элементами поля GF(qn) являются все многочлены степени не более n – 1 с коэффициентами из поля GF(q). Сложение в GF(qn) выполняется по обычным правилам сложения многочленов, при этом операции приведения подоб-

255

ных членов осуществляются по модулю q.

Многочлен с коэффициентами из GF(q) (т.е. многочлен над полем GF(q)), не являющийся произведением двух многочленов меньшей степени, называется неприводимым.

Многочлен Ф(х) степени N с коэффициентами из GF(p) называется неприводимым, если он не делится ни на один другой многочлен степени, меньшей N и большей 0.

Многочлен Ф(х) степени N с коэффициентами из GF(p) называется примитивным, если он не делит нацело ни один многочлен вида хS – 1, где S < pN – 1. Примитивный многочлен автоматически является неприводимым.

Число примитивных многочленов степени N равно

Μ pN 1 ,

N

где Μ (n) – функция Эйлера (число натуральных чисел, меньших

n и взаимно простых с n).

Выберем фиксированный неприводимый многочлен Μ (x) сте-

пени n. Тогда произведение двух элементов поля получается в результате их перемножения с последующим взятием остатка после деления на Μ (x). Таким образом, поле GF(qn) можно пред-

ставить как поле классов эквивалентности многочленов над GF(q). Два таких многочлена объявляются эквивалентными, если их разность делится на Μ (x). Конечные поля порядка qn суще-

ствуют для всех простых q и всех натуральных n.

Рассмотрим два возможных варианта: когда многочлен Μ (x) – примитивный и когда Μ (x) не является примитивным.

Пусть

q = 2, n = 4, Μ (х) = х4 + х + 1 –

примитивный над GF(2). Элементы поля GF(24) имеют вид

0, 1, x, x + 1, ... , х3 + х2 + х + 1.

Так как Μ (x) – примитивный, ему соответствует устройство, диа-

грамма состояний которого состоит из цикла максимальной длины 24 – 1 и одного тривиального цикла, включающего состояние 0000, переходящее само в себя (рис. 8.10,а). Таким образом, в качестве Ζ можно взять корень Μ (x), а устройство, для которого

Μ (x) = х4 + х + 1 является характеристическим многочленом,

256

объявить генератором ненулевых элементов поля. В результате соответствие между различными представлениями элементов поля имеет вид, представленный на рис. 8.10,б. Состояния генератора определяют список элементов GF(24) в порядке возрастания степеней Ζ, т.е. один такт работы устройства, соответствующего характеристическому многочлену Μ (x), суть ум-

ножение текущего состояния устройства на Ζ, иначе говоря, на x по модулю Μ (x).

	q1					q2			q3		q4
	1	0						0		0
	0	1						0		0
	0	0						1		0
	0	0						0		1
	1	1						0		0
	0	1						1		0
	0	0						1		1
	1	1						0		1
	1	0						1		0
	0	1						0		1
	1	1						1		0
	0	1						1		1
	1	1						1		1
	1	0						1		1
	1	0						0		1
	1	0						0		1

23

22

21

20

В

q4

q3

q2

q1

В виде

виде

коэффициентов

степени

многочлена

примитивного

В виде

элемента

многочлена

Ζ

0001

1

Ζ0 = 1

0010

x

Ζ

0100

x2

Ζ2

1000

x3

Ζ3

0011

x + 1

Ζ4

0110

x2 + x

Ζ5 Ζn = xn mod Μx

1100

x3 + x2

Ζ6

1011

x3 + x + 1

Ζ7

0101

x2 + 1

Ζ8

1010

x3 + x

Ζ9

0111

x2 + x + 1

Ζ10

1110

x3 + x2 + x

Ζ11

1111

x3 + x2 + x + 1

Ζ 2

1101

x3 + x2 + 1

Ζ13

1001

x3 + 1

Ζ14

0001

15

...

Ζ...= 1

а

б

Рис. 8.10. Конечное поле GF(24):

а– LFSR, соответствующий примитивному многочлену Μ(х) = х4 + х + 1

иего диаграмма состояний; б – соответствие между различными формами

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

257

Пусть

q = 2, n = 4, Μ (x) = х4 + х3 + х2 + х + 1 –

неприводимый над GF(2).

На рис. 8.11,а показан LFSR, соответствующий характеристическому многочлену Μ (x) = х4 + х3 + х2 + х + 1. Его диаграм-

ма состояний состоит из трех циклов длиной 5 и одного тривиального цикла, а значит, LFSR, один такт которого суть умножение на x по модулю Μ (x) не может использоваться в качестве

генератора элементов поля. Такая ситуация всегда имеет место, когда Μ (x) не является примитивным. Определим структуру

устройства (генератора элементов поля), позволяющего сопоставить каждому ненулевому элементу поля соответствующую степень примитивного элемента.

Имеем

Μ(х + 1) = (x + 1)4 + (x + 1)3 + (x + 1)2 + (x + 1) + 1 =

=x 4 + x3 + 1 = (x),

(x) – примитивный многочлен, а значит, соответствие между

различными формами представления элементов GF(24) можно получить, моделируя работу устройства, показанного на рис. 8.11,б. Один такт его работы суть умножение на Ζ = x + 1.

8.5. Аддитивные генераторы ПСЧ

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

258

	q1						q2								q3								q4
	1			0		0				0									1					0			1	0						1	1	0	0
	0			1		0				0									0					1			0	1						0	1	1	0
	0			0		1				0									1					1			0	1						0	0	1	1
	0			0		0				1									1					0			0	1						1	1	1	0
	1			1		1				1									1					0			1	1						0	1	1	1			0	0	0	0		а
		q1								q2												q3					q4																		б
	23					22												21									20
		q4						q3										q2									q1
																														В виде
	В
		виде							коэффициентов																					степени
						многочлена																					примитивного
																В виде														элемента
													многочлена														Ζ0 = 1						Ζ
						0001												1
						0011												x + 1											Ζ
						0101											x2 + 1												Ζ2
						1111							x3 + x2 + x + 1																Ζ3
						1110								x3 + x2 + x															Ζ4					Ζn = (x + 1)n mod Μ(x)
						1101								x3 + x2 + 1															Ζ5
						1000													x3										Ζ6
						0111									x2 + x + 1														Ζ7
						1001											x3 + 1												Ζ8
						0100											x2 + 1												Ζ9
						1100										x3 + x2												Ζ10
						1011									x3 + x + 1													Ζ11
						0010														x							Ζ 2
						0110											x2 + x											Ζ13
						1010											x3 + x										Ζ	Ζ14
						0001																						15																	в
						...																						...= 1

Рис. 8.11. Конечное поле GF(24):

а – LFSR, соответствующий не примитивному неприводимому многочлену Μ(х) = х4 + х3 + х2 + х + 1 и его диаграмма состояний; б – LFSR, такт работы которого суть умножение на x + 1 по модулю Μ(х); в – соответствие между различными формами представления элементов поля

259

Аддитивный генератор состоит из N регистров разрядностью

M каждый и сумматора по модулю 2M . Начальным заполнением (ключом) генератора является массив

Q1 0 Q2 0 ... QN 0

M-битовых слов. Уравнения работы аддитивного генератора Фибоначчи имеют вид

Q1 t 1 ¦N	1	ai Q(t) mod 2M ,
i

Qj t 1 Qj -1 t , j 2, N,

где Qi t – состояние i-го регистра в момент времени t, а ai – коэффициенты многочлена Ф(х) степени N, примитивного над GF 2 . Начальное заполнение выбирается таким образом, чтобы

хотя бы в одном из регистров младший бит содержал «1». В этом случае младшие биты регистров образуют генератор двоичной M-последовательности. Учитывая, что при большом числе ненулевых коэффициентов Ф(х) быстродействие схемы снижается, возможна модификация схемы генератора с распределением

двухвходовых блоков сложения по модулю 2M между регистрами по схеме Галуа. На примере аддитивного генератора обсудим программную реализацию линейных генераторов ПСЧ, рассмотренных ранее, и нелинейных генераторов ПСЧ, которые будут рассмотрены в последующих разделах. Предлагаемый прием программирования самой производительной схемы генерации ПСЧ, суть которого – использование «плавающих» обратных связей аддитивного генератора, может использоваться и при программной реализации (в случае разреженных многочленах обратной связи) двоичных параллельных и недвоичных генераторов ПСЧ, функционирующих в поле GF(p); а также генераторов ПСЧ со стохастическими сумматорами в цепи обратной связи. Последние, как будет показано ниже, отличаются от аддитивных генераторов лишь заменой сумматора по модулю 2М на R-блок.

На рис. 8.12 показан пример аддитивного генератора для слу-

чая, когда Ф(х) x9 x4 1. Генератор формирует рекуррентную

260