Пример применения линейного криптоанализа к раскрытию ключа

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

Схема данного алгоритма представлена на рис. 3.2. Входной блок, представляющий собой последовательность из 16 бит, которые разделяются на две части, правая из которых проходит через блок шифрования f после чего складывается по модулю 2 с левой частью. Выходное шифрованное сообщение состоит из двух 8-битовых частей, правая часть которого представляет собой правую часть входного сообщения, а левая – результат сложения по модулю два.

Рассмотрим подробнее f блок (см. рис. 3.3). Входное 8-битовое сообщение проходит через блок перестановки с расширением так, что на выходе мы имеем 12 бит. Данные таблицы перестановки с расширением приведены в таблице 3.6. После этого 12 битовый ключ и преобразованное входное сообщение складываются по модулю 2. Результат сложения разбивается на три группы по четыре бита, каждая из которых проходит соответственно Блок1, Блок 2 и Блок3. При этом из первых двух блоков выходит по три бита, а из третьего блока – два.

Замена в первых двух блоках производится по приведенным таблицам замены (соответственно таблица 3.7 и 3.8) по следующему принципу. Пусть в блок входит четыре бита а1, а2, а3, а4. При этом первый бит определяет номер строки (если а1 = 0, то это соответствует первому столбцу, а если а1 = 1 - второму), а остальные три – номер столбца (000 = первому столбцу, 111 = восьмому столбцу).

Несколько иначе дело обстоит с третьим блоком. Из него в отличие от первых двух выходит не три бита, а два. Замена осуществляется согласно таблице 3.9. При этом, если а1, а2, а3, а4 – входные биты Блока 3, то биты а1 и а4 определяют номер сроки, а биты а2 и а3 – номер столбца (аналогично S-блокам алгоритма DES).

После этого восьмибитовое сообщение претерпевает перестановку согласно таблице 3.10 и на выходе получается готовый шифр – текст.

Таблица 3.6

Таблица перестановки с расширением

Таблица 3.7

Таблица замены в блоке 1

а2а3а4
а1

Таблица 3.8

Таблица замены в блоке 2

а2а3а4
а1

Таблица 3.9

Таблица замены в блоке 3

а2а3
а1 а4

Таблица 3.10

Таблица перестановки

Как и в случае с алгоритмом шифрования DES, криптоанализ данного алгоритма начнется с анализа Блоков замены и нахождения наиболее эффективного линейного уравнения. Результаты анализа Блока1, Блока2 и Блока 3 приведены соответственно в таблицах 3.11, 3.12 и 3.13.

Таблица 3.11

Анализ Блока 1.

i	Значения j
S(i,j)

Таблица 3.12

Анализ Блока 2.

i	Значения j
S(i,j)

Таблица 3.13

Анализ Блока 3.

I	Значения j
S(i,j)

Итак, согласно таблице 3.11, мы можем составить первые три наиболее эффективных линейных уравнения. Сразу следует отметить, что одно из уравнений будет более эффективным, однако его не достаточно для нахождения битов ключа, поэтому мы берем еще уравнение наиболее приближенное по своей эффективности к первому. В таблице 3.11 определены три пары (i,j) – (12,5), (14,1) и (15,2). Так как в Блок 1, согласно таблице перестановки с расширением входят биты Х3, Х4, Х1, Х2, а выходные биты после перестановки оказываются на местах Y7, Y4, Y3, то, учитывая, что мы работаем с правой 8-битовой частью исходного 16-битового сообщения, а также сложение по модулю два левой части исходного сообщения с результатом функции f, получаем следующие уравнения:

Х11ÅХ12ÅY7ÅY3ÅХ7ÅХ3 = К1ÅК2, которое выполняется с вероятностью р = 1/16, а соответственно D = |1 –2р| = 7/8.

Х11ÅХ12ÅХ9ÅY3ÅХ3 = К1ÅК2ÅК3, которое выполняется с вероятностью р = 13/16, а соответственно D = |1 –2р| = 5/8.

Х11ÅХ12ÅХ9ÅХ10ÅY4ÅY3ÅХ4ÅХ3 = К1ÅК2ÅК3ÅК4, которое выполняется с вероятностью р = 3/16, а соответственно D = |1 –2р| = 5/8.

Аналогичным образом составляем уравнения для двух остальных блоков. Результаты анализа сведены в таблицу 3.14.

Таблица 3.14

№ блока	Эффективное линейное уравнение	Р	D = \|1 – 2р\|
	Х11ÅХ12ÅY7ÅY3Å7ХÅХ3 = К1ÅК2 (1) Х11ÅХ12ÅХ9ÅY3ÅХ3 = К1ÅК2ÅК3 (2) Х11ÅХ12ÅХ9ÅХ10ÅY4ÅY3ÅХ4ÅХ3= К1ÅК2ÅК3ÅК4 (3)	1/16 13/16 3/16	7/8 5/8 5/8
	Х13ÅY6ÅХ6=К7 (4) Х14ÅХ16ÅY6ÅY8ÅX6ÅX8=К5ÅК6 (5) Х14ÅХ16ÅХ15ÅY5ÅX5=К5ÅК6ÅК8 (6) Х14ÅХ16ÅX13ÅY8ÅX8 = К6ÅК5ÅК7 (7) Х14ÅХ16ÅХ13ÅХ15ÅY5ÅY8ÅX5ÅX8= К5ÅК6ÅК7ÅК8 (8)	3/16 13/16 3/16 1/8 3/16	5/8 5/8 5/8 3/4 5/8
	Х11ÅХ16ÅХ10ÅХ12ÅY2ÅX2=К9ÅК10ÅК11ÅК12 (9)	7/8	3/4

Анализ последнего блока дает слишком мало информации для нахождения битов ключа. А вот анализ первых двух блоков предоставляет возможность определить первые биты ключа. Итак, возьмем 30 пар открытый – закрытый тест, зашифрованных с помощью данного алгоритма на ключе К = 101010101010 (см. таблицу 3 в Приложении).

Таблица 3.15

Открытый блок	Зашифрованный блок

Используя уравнения, полученные из блока 1, находим, что из N=30 открытых текстов число открытых текстов, для которых левая часть уравнения (1) равна 0 Т=22.Так как в этом случае вероятность р = 1/16, то по вышеописанному алгоритму находим, что К1ÅК2 = 1. (15)

Для уравнения (2) Т = 23, а р=13/16, тогда К1ÅК2ÅК3 = 0. (16)

Для уравнения (3) Т = 12, а р=3/16, тогда К1ÅК2ÅК3ÅК4 = 0. (17)

Зная это из уравнений (16) и (17) находим, что К4 = 0. Из уравнений (16) и (15) находим, что К3 = 1. Так как К1ÅК2 = 1, то возможны два варианта: либо К1=0 и К2 = 1; либо К1=1 и К2 = 0.

Аналогичным образом находим биты ключа для второго блока.

Для уравнения (4) Т = 4, а р=1/8, тогда К5ÅК6ÅК7 = 0. (18)

Для уравнения (5) Т = 25, а р=3/16, тогда К7 = 1. (19)

Для уравнения (6) Т = 25, а р=3/16, тогда К5ÅК6ÅК8 = 1. (20)

Для уравнения (7) Т = 6, а р=13/196, тогда К5ÅК6 = 1. (21)

Для уравнения (8) Т = 6, а р=1/8, тогда К5ÅК6ÅК7ÅК8 = 0. (22)

Из уравнений (20) и (21) находим К8 = 0. Так как К5ÅК6 = 1, то возможны два варианта: либо К5=0 и К6 = 1; либо К5=1 и К6 = 0.

Итак, после анализа двух таблиц имеем четыре возможных вариантов первых восьми бит ключа:

К1 = 01100110хххх;

К2 = 10100110хххх;

К3 = 01101010хххх;

К4 = 10101010хххх.