lec07 производная булевой функции

Пример 7.12.						x1		x2	f0	f1		f2		f3	f4	f5	f6	f7	f8		f9	f10		f11	f12	f13	f14	f15
						0		0	0	0		0		0	0	0	0	0	1		1	1		1	1	1	1	1
15) f14 =	1 2.					0		1	0	0		0		0	1	1	1	1	0		0	0		0	1	1	1	1
						1		0	0	0		1		1	0	0	1	1	0		0	1		1	0	0	1	1
						1		1	0	1		0		1	0	1	0	1	0		1	0		1	0	1	0	1
f14(1, 2)
		=	f			, 0 f						, 1 =				( 0) ( 1) =
				14							14
2							1						1				1	?			1				1
16) f15 ≡	1.	f15(1, 2)									= f15 1, 0						f15		1, 1			=	?1
				2

1 2 = {f3; f7; f11} = { 1; 1 2; 1 2}

31

Использование аппарата интегродифференциального исчисления БФ в криптографии.

Интерес в том, что БФ существует строго определенный набор интегральных функций большей размерности, а программный вид БФ может быть легко закодирован в числовой эквивалент (ключ).

Для верификации (проверки ключа на подлинность) используется программный алгоритм дифференцирования.

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

Общее количество БФ размерности n – f (x1,x2,...,xn): 22n

32

Взяв в качестве верифицируемого значения БФ размерности 5, для нее количество интегральных БФ, равно: 226 264 ~ 1.8·1018

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

Если нахождение полного множества интегральных функций для БФ уже от 5-ти переменных для специализированных сверхмощных ЦОД непростая, но решаемая вычислительная задача, то при увеличении размерности БФ еще на 3 порядка, количество интегральных БФ: 229 ~ 10170

Не существует даже типов данных, способных хранить такое количество информации, не говоря уже о размерах оперативной и физической памяти. Однако и задаваться такая БФ будет вектором размера 512 бит.

33