Программирование для многопроцессорных систем в стандарте MPI - Шпаковский Г.И., Серикова Н.В

Глава 9. ПАРАЛЛЕЛИЗМ В РЕШЕНИИ ЗАДАЧ КРИПТОАНАЛИЗА

9.1. КРИПТОЛОГИЯ И КРИПТОАНАЛИЗ

Криптология – раздел прикладной математики, изучающий методы, алгоритмы, программные и аппаратные средства для защиты информации (криптография), а также предназначенный для оценки эффективности такой защиты (криптоанализ). Общие сведения по криптологии, представленные в параграфах 9.1 и 9.2, с разрешения авторов взяты из книги [22]. Информация по криптографии также содержится в [23]. В параграфе 9.3 приводится пример разработки параллельной программы, реализующей некоторый алгоритм криптоанализа.

Любая математическая теория наряду с прямыми задачами рассматривает обратные задачи, которые часто оказываются вычислительно более сложными. Криптоанализ занимается задачами, обратными по отношению к криптографии. Основная цель криптоанализа состоит не в проникновении в компьютерные сети для овладения конфиденциальной информацией, а в оценке стойкости (надежности) используемых и разрабатываемых криптосистем. Методы криптоанализа позволяют оценивать стойкость (уровень безопасности) криптосистем количественно в виде числа W компьютерных операций, необходимых криптоаналитику для вскрытия ключа (или исходного текста). Для пользователя криптосистемы важно, чтобы это число W было настолько велико (например, несколько лет счета на современной вычислительной технике), чтобы за время криптоанализа информация потеряла свою ценность. Под криптоатакой здесь понимается задача оценивания ключевой информации при условии, что сама используемая криптосистема известна.

В зависимости от условий взаимодействия криптоаналитика с криптосистемой различают следующие четыре типа криптоатак:

1)криптоатака с использованием криптограмм;

2)криптоатака с использованием открытых текстов и соответствующих им криптограмм;

3)криптоатака с использованием выбираемых криптоаналитиком открытых текстов и соответствующих им криптограмм;

4)криптоатака с использованием активного аппаратного воздействия на криптосистему.

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

201

Далее мы рассмотрим только криптоатаку типа 2. Для нее возможны четыре метода криптоанализа: метод “опробования” (полного перебора); метод криптоанализа с использованием теории статистических решений; линейный криптоанализ; разностный криптоанализ.

Из этих четырех методов далее рассматривается только метод “опробования” ввиду его относительной простоты и наглядности в компmютерной реализации.

Пусть рассматривается произвольная симметричная криптосистема. Пусть X =(x1 ,..., xn ) VNn – открытый текст, подлежащий шиф-

пользованное в данном сеансе шифрования; f ( ) – криптографическое

Обязательным условием любой криптосистемы является условие биективности преобразования при фиксированном значении ключа

(параметра) θ 0 , так что выполняется соотношение

Соотношение (9.1) определяет алгоритм расшифрования зарегистрированной криптограммы Y санкционированным получателем ин-

формации, который знает ключ θ0 .

Метод опробования базируется на соотношении (9.2) и заключается в следующем:

1. На основе имеющейся криптограммы Y VNn и соответствующего ей открытого текста X VNn составляется система уравнений относительно θ = (θ1,...,θL )

2. Полным перебором всех возможных значений ключевого пара-

решений этой системы;

3.Если число найденных решений l = 1, то в силу (9.2) определено истинное значение параметра θ =θ0 ; в противном случае Θ0 не

202

является одноточечным множеством и определено подмножество l значений искомого параметра, одно из которых в силу (9.2) совпа-

дает с истинным значением θ 0 .

В случае l>1 целесообразно увеличить число уравнений в системе (9.3). Для этого необходимо увеличить число символов n в исходном сообщении X либо получить и использовать в (9.3) q>1 пар (сооб-

Увеличивая n или q, можно достичь случая l = 1 и, следовательно,

достичь безошибочного оценивания ключа: θ€=θ0 .

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

где Θ – количество всевозможных допустимых значений ключа,

W1(n, q) – число компьютерных операций, затрачиваемых на “опробование (проверку (9.4) для одного значения θ ). Обычно W1(n, q) зависит от q линейно:

где ω(n) – число компьютерных операций, затрачиваемых на провер-

ку (9.3) применительно к n – символьным сообщениям для единичного значения θ Θ; ω(n) фактически совпадает с числом компьютер-

ных операций при расшифровании криптограммы (вычисление обратной функции f −1( ) при известном ключе). Заметим, что величина ω(n) является известной характеристикой для каждой реальной крип-

тосистемы, причем чем выше быстродействие криптосистемы, тем эта величина меньше.

9.2.КРИПТОСИСТЕМА DES

Вшироко известной криптосистеме DES используется блочный принцип шифрования двоичного текста. Длина блока шифрования составляет 64 бита. Размер ключа также составляет 64 бита. При этом каждый 8-й бит является служебным и в шифровании не участвует. Каждый такой бит является двоичной суммой семи предыдущих и

203

служит лишь для обнаружения ошибок при передаче ключа по каналу связи. Процесс криптопреобразования включает следующие три основных этапа.

1.Биты исходного сообщения x подвергаются начальной подстановке IP в соответствии с табл. 9.1.

Таблица 9.1

Система замены битов исходного сообщения

Это означает, что 58-й бит становится первым, 50-й – вторым и т.д. Затем полученный вектор x0 = IP(x) представляется в виде

x0 = L0R0 , где L0 – левая половина из 32 бит, а R0 – правая половина из 32 бит.

2.Сообщение L0R0 преобразуется далее 16 раз по так называемой схеме Фейстеля, приведенной на рис.9.1:

y = IP−1(R16 L16 )

есть зашифрованное сообщение.

204

Функция f. Эта функция имеет два аргумента A и B. Первый из них состоит из 32 бит, а второй из 48 бит. Результат имеет 32 бита.

1.Первый аргумент А, имеющий 32 бита, преобразуется в 48-бито- вый вектор P(A) путем перестановки с повторениями исходного вектора A. Эта процедура одна и та же для всех раундов. Она задается табл. 9.2.

Таблица 9.2

Преобразование 32-разрядного аргумента А в 48-разрядный вектор Р(А)

2.Далее вычисляется сумма P(A) B и записывается в виде конкатенации восьми 6-битовых слов:

P(A) B = B1B2B3B4B5B6B7B8 .

3.На этом этапе каждое слово Bi поступает на соответствующий S- блок Si . Блок Si преобразует 6-битовый вход Bi в 4-битовый выход Ci . S-блок есть матрица 4х16 с целыми элементами в диапазоне от 0 до 16. Два первых бита слова Bi , если их рассматривать как двоичную запись числа, определяют номер строки матрицы. Четыре последних бита определяют некоторый столбец. Тем самым найден некоторый элемент матрицы. Его двоичная запись является выходом. В табл. 9.3 представлен один из S-блоков.

Таблица 9.3

Содержание блока S1

4. Выход C =C1,C2…Cs перемешивается фиксированной подстанов

кой P2:

Таблица 9.4

Подстановка Р2

205

Расписание ключей определяется следующим алгоритмом:

1.В 64-битовом ключе K устраняются биты 8, 16, …, 64. Оставшиеся биты перемешиваются подстановкой P3.

Таблица 9.5

Подстановка для перемешивания ключей с устраненными битами

Дешифрация в стандарте DES. В процессе дешифрования последозвательно используются преобразования

IP,Φ1,Φ2,...,Φ16,T, IP−1.

Каждое из преобразований Фейстела остается композицией двух преобразований. Первое из них – транспозиция L и R: T(L,R)= (R,L). Таким образом, для любого i Φi =ViT . Кроме того, легко убедиться,

что Vi2 = T 2 = id – тождественное преобразование. Такие преобразования (элементы группы) принято называть инволюциями. Для них, в

частности, верно Vi−1 =Vi ,T −1 = T.

По правилу обращения элементов неабелевой группы имеем

D = E−1 = ((IP)−1TV16TV15T...V1T (IP))−1 = (IP)−1TV1TV2...V16T (IP).

206

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

Из (9.5), (9.6) следует, что основным фактором, определяющим вычислительную сложность метода “опробования” и одновременно криптостойкость алгоритма шифрования по отношению к рассматриваемому методу криптоатаки, является мощность пространства ключей Θ . С учетом этого оценим вычислительную сложность метода

“опробования” криптосистемы DES.

В этом случае двоичный текст (N = 2) шифруется блоками размера n= 64 и используется 64-битовый ключ:

Θ ={θ1,...,θ56 ) :θi V2,i =1,56},

поэтому

Для суперЭВМ Intel ASCI RED (9152 процессора) среднее время перебора для системы DES составляет 9.4 часа.

9.3. ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ DES АЛГОРИТМА

Пусть имеется процедура шифрации двоичного текста по DES алгоритму, описанному в парграфе 9.2:

procedure_shifr(in,out);

где in – блок исходного сообщения, длина блока шифрования составляет 64 бита, out – зашифрованное сообщение. Пусть также имеется процедура дешифрации двоичного текста:

procedure_de_shifr(out,outin,key);

где out – зашифрованное сообщение, outin – результат дешифрации сообщения с помощью ключа key.

Тогда метод «опробования» сводится к следующей задаче. Сначала открытый текст шифруется с помощью некоторого ключа. Выполняем полный перебор значений ключа в некотором диапазоне. При этом для каждого значения вызываем процедуру дешифрации с этим значением ключа. Для простоты будем считать: если дешифрованный текст совпадает с исходным, ключ найден (иначе см. параграф 9.1).

Ключ в DES алгоритме 64-битовый, следовательно, можно его представлять двумя 32-разрядными (unsigned long), четырьмя 16-раз-

207

рядными (unsigned int) или восемью 8-разрядными беззнаковыми целыми (unsigned char). Выберем первый способ представления ключа:

unsigned long key_data[2].

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

unsigned long imax[2]={0xffff,0xffff}; /* верхняя граница диапазона ключа */

/*перебор значений младшей части ключа*/ for (i2=imin[1]; i2<imax[1]; i2++)

{key_data[i][1]=i2;

/* вызов процедуры дешифрации с помощью ключа key_data */ procedure_de_shifr(out,outin,key_data);

if (memcmp(in,outin,8) == 0)

{ printf("key is: 0x%x 0x%x \n",i1,i2); /* ключ найден */ return 0;

}

}

}

return 0;

}

Рис. 9.2. Последовательная программа определения ключа по DES алгоритму

Рассмотрим параллельный алгоритм для решения этой задачи. Поиск ключа – перебор всевозможных значений из заданного диапазона. Естественно разделить диапазон изменения ключа (верхний диапазон key_data[1] или нижний диапазон key_data[2]) по процессам так, чтобы каждый процесс независимо осуществлял перебор значений своего диапазона. Пусть min – нижняя, max - верхняя граница значений диапазона ключа, myid – собственный номер процесса, numprocs – коли-

208

чество процессов приложения, n1 – нижняя, n2 – верхняя границы диапазона ключа для данного процесса. Тогда можно предложить следующий способ распределения работы по процессам:

Так как количество вариантов ключей намного больше количества процессов, то можно считать, что общий объем вычислений будет распределен между процессами равномерно.

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

MPI_Allgather( &num, 1, MPI_INT, buf, 1, MPI_INT, MPI_COMM_WORLD).

В результате вызова этой функции в массиве buf будут находиться значения переменной num всех процессов коммуникатора, которая будет иметь значение 0xff, если ключ найден, и нуль – в противном случае.

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

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

•ключ найден одним из процессов,

•ключ из заданного диапазона не найден ни одним процессом,

•часть процессов закончила перебор значений ключа, а другая – продолжает перебор значений.

209

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

MPI_Allgather( &num,1,MPI_INT,buf,1,MPI_INT,MPI_COMM_WORLD);

В двух оставшихся случаях может возникнуть ошибка вызова коллективной функции. Коллективная функция должна вызываться всеми процессами коммуникатора без исключения, но некоторые из процессов могут закончить работу по перебору ключей, что вызовет “зависание” программы. Поэтому необходимо введение цикла после перебора ключей, в будем выполнять коллективный опрос процессов о нахождении ключа до тех пор, пока либо он не будет найден, либо перебор ключей закончат все процессы приложения. Это можно осуществить следующим образом:

MPI_Allgather(&num,1,MPI_INT,buf,1,MPI_INT,MPI_COMM_WORLD); for (i=0; i<numprocs; i++)

if (buf[i]==0xFF)

{printf("process %d stopped \n",myid);

}

/* возможен вариант, когда ключ не найден ни одним процессом */

PR=0;

for (i=0; i<numprocs; i++) if (buf[i]!=i)

{ PR=0xFF; break; } }while (PR!=0);

В num заносится собственный номер процесса, закончившего перебор вариантов ключей. Тогда полное окончание работы всех процессов

210