Для 2-го раунда получаем
V2,6 V2,8 U2,6 с вероятностью 14 .	(3.3)
Поскольку V2,6 V1,6 U2,6 , мы будем иметь
V2,6 V2,8 V1,6 k 2,6 с вероятностью 14 .(3.4)
Подставляя (3.2) в (3.4), получим	k 2,6 0.(3.5)
V26 V2,8 Р5 Р7 Р8 k1,5 k17 k18

Взаимосвязи аппроксимируемых блоков показаны на рис. 3.6.

23

Для расчета вероятности выполнения равенства (3.5) используем

лемму [5].

Лемма.Пусть x1 , x2 , ..., xn – случайные независимые двоичные переменные, причем заданы вероятности P xi 0 12 i . Тогда

P x1 x2 ... xn 0 1 2n 1 n i .

2 i 1

X1 X2 X3

+

Y

24

(3.5)

25

Используя эту лемму, получаем вероятность выполнения равенства (3.5):

				P		(3.5)						1				3		1				1		1			3	.
												2		2		4		2				4		2			8
	Аналогичным образом получим соотношение для 3-го раунда,
используя линейную аппроксимацию S32 :
														V3,6 V3,8							U3,6 с вероятностью (1/4);(3.6)
			V3,14 V				3,16 U3,14 с вероятностью (1/4).																															(3.7)
	Из схемы шифра видно, что:
											U3,6 V2,6 k3,6;																											(3.8)
											U3,14			V2,8 k3,14 .																								(3.9)
	Объединяя (3.6)–(3.9), получаем:
V	V	V	V	V k							V			k			0 с вероятностью												1	2		1		1		2	5	(3.10)
									3,6						3,14
3,6	3,8	3,14	3,16			2,6							2,8																2			4		2			8

26

3.10

3.13

27

Подставим в (3.10) V 2,6 V 2,8 из(3.5):

V3,6 V3,8 V3,14 V3,16 P5 P7 P8 k1,5 k1,7 k1,8 k2,6 k3,6 k3,14 0.(3.11)

Из схемы шифра, представленной на рис. 3.6, для входов 4-го раунда получаем:

U4,6 V3,6 k4,6 ; U4,8 V3,14 k4,8;U4,14 V3,8 k4,14; U4,16 V3,16 k4,16.

Подставляя уравнения (3.12) в (3.11), окончательно получаем:

1,если k 1;

U4,6 U4,8 U4,14 U4,16 P5 P7 P8 k 0, если k 0,

где k k1,5 k1,7 k1,8 k2,6 k3,6 k3,14 k4,6 k4,8 k4,14 k4,16 .

Использование леммы дает вероятность выполнения (3.13):

1	2	3		3		1			1		1 3			15	с перекосом			1		.
2				4		2			4		2			32				32

(3.12)

(3.13)

28

29

Из равенства (3.13) видно, что оно принимает значения 0 или 1, в

зависимости от значения суммы ключей k . Этот факт позволяет

определить ключи последнего 5-го раунда методом перебора, не обращая пока внимания на другие ключи. Делается это следующим образом:

1) задается множество входных и выходных сообщений Pi , Ei , где

i1,2, ,T ;

2)по известной криптограмме Ei вычисляются V4 для различных

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

вектора:V4,5 ,...,V4,8...;V4,13...V4,16 ;

3) по известной структуре S-блоков вычисляются входы 4-го раунда:

U4,5 , ,U4,8;U4,13, ,U4,16 ;

4)рассчитывается количество выполнений равенства (3.13) для различных входных сообщений и каждого из всех возможных ключей

k5,5 k5,8;k5,13 ,k5,16 ;

30

Принцип линейного КА

М

1 раунд	M

2 раунд

3 раунд

	V3		V3 U4 ?
	U4
4 раунд
K5		K5i	E
	Е		31

Подсчет количества совпадений линейной аппроксимации

Пары

(Р,Е)

Р1,Е1

Р2,Е2

Р3,Е3

….

Рi,Еi

. . .

. . .

РT,ЕT

Колич.

символов

		Перебираемые ключи
К5,1	К5,2	К5,3	. . .	К5,255	К5,256
+		+			+
	+	+		+
					+
+	+	+		+
	+			+	+
		+
+				+
	+	+
L1	L2	L3		L255	L256

P	Li		В качестве истинного ключа Ki выбирается ключ, который
совпi		T	дает наибольшее отклонение от Т/2.	32