Программирование для многопроцессорных систем в стандарте MPI - Шпаковский Г.И., Серикова Н.В.. Программирование для многопроцессорных систем в стандарте MPI -. Организация вычислений в многопроцессорных системах
 Скачать 1.61 Mb.
|
|
Глава 9. ПАРАЛЛЕЛИЗМ В РЕШЕНИИ ЗАДАЧ КРИПТОАНАЛИЗА 9.1. КРИПТОЛОГИЯ И КРИПТОАНАЛИЗ Криптология – раздел прикладной математики, изучающий мето- ды, алгоритмы, программные и аппаратные средства для защиты ин- формации (криптография), а также предназначенный для оценки эф- фективности такой защиты (криптоанализ). Общие сведения по крип- тологии, представленные в параграфах 9.1 и 9.2, с разрешения авторов взяты из книги [22]. Информация по криптографии также содержится в [23]. В параграфе 9.3 приводится пример разработки параллельной программы, реализующей некоторый алгоритм криптоанализа. Любая математическая теория наряду с прямыми задачами рас- сматривает обратные задачи, которые часто оказываются вычисли- тельно более сложными. Криптоанализ занимается задачами, обрат- ными по отношению к криптографии. Основная цель криптоанализа состоит не в проникновении в компьютерные сети для овладения конфиденциальной информацией, а в оценке стойкости (надежности) используемых и разрабатываемых криптосистем. Методы криптоана- лиза позволяют оценивать стойкость (уровень безопасности) крипто- систем количественно в виде числа W компьютерных операций, необ- ходимых криптоаналитику для вскрытия ключа (или исходного тек- ста). Для пользователя криптосистемы важно, чтобы это число W бы- ло настолько велико (например, несколько лет счета на современной вычислительной технике), чтобы за время криптоанализа информация потеряла свою ценность. Под криптоатакой здесь понимается задача оценивания ключевой информации при условии, что сама используе- мая криптосистема известна. В зависимости от условий взаимодействия криптоаналитика с криптосистемой различают следующие четыре типа криптоатак: 1) криптоатака с использованием криптограмм; 2) криптоатака с использованием открытых текстов и соответствую- щих им криптограмм; 3) криптоатака с использованием выбираемых криптоаналитиком от- крытых текстов и соответствующих им криптограмм; 4) криптоатака с использованием активного аппаратного воздействия на криптосистему. Эти четыре типа криптоатак упорядочены по возрастанию степени активности криптоаналитика при взаимодействии с криптосистемой. 202 Далее мы рассмотрим только криптоатаку типа 2. Для нее возможны четыре метода криптоанализа: метод “опробования” (полного перебо- ра); метод криптоанализа с использованием теории статистических решений; линейный криптоанализ; разностный криптоанализ. Из этих четырех методов далее рассматривается только метод “опробования” ввиду его относительной простоты и наглядности в компmютерной реализации. Пусть рассматривается произвольная симметричная криптосисте- ма. Пусть n N n 1 V ) x ,..., (x X ∈ = – открытый текст, подлежащий шиф- рованию; L m 0 L 0 1 0 V И ) и ,..., (и и ⊆ ∈ = – истинное значение ключа, ис- пользованное в данном сеансе шифрования; ) ( ⋅ f – криптографическое преобразование, а n N n 1 V ) y ,..., (y Y ∈ = – криптограмма (зашифрован- ный текст), тогда: ) и f(X; Y 0 = (9.1) Обязательным условием любой криптосистемы является условие биективности преобразования при фиксированном значении ключа (параметра) 0 θ , так что выполняется соотношение X. ) и (Y; f 0 1 = − (9.2) Соотношение (9.1) определяет алгоритм расшифрования зарегист- рированной криптограммы Y санкционированным получателем ин- формации, который знает ключ 0 θ Метод опробования базируется на соотношении (9.2) и заключает- ся в следующем: 1. На основе имеющейся криптограммы n N V Y ∈ и соответствующего ей открытого текста n N V X ∈ составляется система уравнений отно- сительно ) ,..., ( 1 L θ θ θ = n i x Y f i i , 1 , ) ; ( 1 = = − θ . (9.3) 2. Полным перебором всех возможных значений ключевого пара- метра L m V ⊆ Θ ∈ θ находится подмножество } € ,..., € { ) 1 ( 0 l θ θ = Θ l решений этой системы; 3. Если число найденных решений l = 1, то в силу (9.2) определено истинное значение параметра 0 θ θ = ; в противном случае 0 Θ не 203 является одноточечным множеством и определено подмножество l значений искомого параметра, одно из которых в силу (9.2) совпа- дает с истинным значением 0 θ В случае l>1 целесообразно увеличить число уравнений в системе (9.3). Для этого необходимо увеличить число символов n в исходном сообщении X либо получить и использовать в (9.3) q>1 пар (сооб- щение, криптограмма) : ) , ( ),..., , ( ) ( ) ( ) 1 ( ) 1 ( q q Y X Y X q j X Y f j j , 1 , ) ; ( ) ( ) ( 1 = = − θ . (9.4) Увеличивая n или q, можно достичь случая l = 1 и, следовательно, достичь безошибочного оценивания ключа: 0 € θ θ = Вычислительная сложность метода «опробования» характеризует- ся количеством компьютерных операций, необходимых для реализа- ции этого метода: ), , ( , , ( 1 q n W q n W W ⋅ Θ = Θ = (9.5) где Θ – количество всевозможных допустимых значений ключа, W 1 (n, q) – число компьютерных операций, затрачиваемых на “опробо- вание (проверку (9.4) для одного значения θ ). Обычно W 1 (n, q) за- висит от q линейно: , ) ( ) , ( 1 q n q n W ⋅ = ω (9.6) где ) (n ω – число компьютерных операций, затрачиваемых на провер- ку (9.3) применительно к n – символьным сообщениям для единично- го значения Θ ∋ θ ; ) (n ω фактически совпадает с числом компьютер- ных операций при расшифровании криптограммы (вычисление обрат- ной функции ) ( 1 ⋅ − f при известном ключе). Заметим, что величина ) (n ω является известной характеристикой для каждой реальной крип- тосистемы, причем чем выше быстродействие криптосистемы, тем эта величина меньше. 9.2. КРИПТОСИСТЕМА DES В широко известной криптосистеме DES используется блочный принцип шифрования двоичного текста. Длина блока шифрования со- ставляет 64 бита. Размер ключа также составляет 64 бита. При этом каждый 8-й бит является служебным и в шифровании не участвует. Каждый такой бит является двоичной суммой семи предыдущих и 204 служит лишь для обнаружения ошибок при передаче ключа по каналу связи. Процесс криптопреобразования включает следующие три ос- новных этапа. 1. Биты исходного сообщения x подвергаются начальной подстановке IP в соответствии с табл. 9.1. Таблица 9.1 Система замены битов исходного сообщения 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 IP 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 Это означает, что 58-й бит становится первым, 50-й – вторым и т.д. Затем полученный вектор ) ( 0 x IP x = представляется в виде 0 0 0 R L x = , где L 0 – левая половина из 32 бит, а R 0 – правая полови- на из 32 бит. 2. Сообщение 0 0 R L преобразуется далее 16 раз по так называемой схеме Фейстеля, приведенной на рис.9.1: 16 1,2,..., i ), K , f(R L R , R L i 1 i 1 i i 1 i i = ⊕ = = − − − , где функция f и расписание ключей 16 2 1 K ,.., K , K будут описаны отдельно. Рис. 9.1 Алгоритм криптопреобразования 3. Сообщение 16 16 R L перемешивается подстановкой 1 − IP : ) 16 16 1 L (R IP y − = есть зашифрованное сообщение. L i-1 R i-1 + f i R i L i K i 205 Функция f. Эта функция имеет два аргумента A и B. Первый из них состоит из 32 бит, а второй из 48 бит. Результат имеет 32 бита. 1. Первый аргумент А, имеющий 32 бита, преобразуется в 48-бито- вый вектор P(A) путем перестановки с повторениями исходного вектора A. Эта процедура одна и та же для всех раундов. Она зада- ется табл. 9.2. Таблица 9.2 Преобразование 32-разрядного аргумента А в 48-разрядный вектор Р(А) 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 P 1 22 23 24 25 24 25 26 27 28 29 28 29 30 31 30 1 2. Далее вычисляется сумма B A P ⊕ ) ( и записывается в виде конкате- нации восьми 6-битовых слов: B A P ⊕ ) ( = 8 7 6 5 4 3 2 1 B B B B B B B B 3. На этом этапе каждое слово B i поступает на соответствующий S- блок S i . Блок S i преобразует 6-битовый вход B i в 4-битовый выход C i . S-блок есть матрица 4х16 с целыми элементами в диапазоне от 0 до 16. Два первых бита слова B i , если их рассматривать как дво- ичную запись числа, определяют номер строки матрицы. Четыре последних бита определяют некоторый столбец. Тем самым най- ден некоторый элемент матрицы. Его двоичная запись является выходом. В табл. 9.3 представлен один из S-блоков. Таблица 9.3 Содержание блока S 1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 S 1 5 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 4. Выход C =C 1 ,C 2 …C s перемешивается фиксированной подстанов кой P 2 : Таблица 9.4 Подстановка Р 2 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 P 2 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 206 Расписание ключей определяется следующим алгоритмом: 1. В 64-битовом ключе K устраняются биты 8, 16, …, 64. Оставшиеся биты перемешиваются подстановкой P 3. Таблица 9.5 Подстановка для перемешивания ключей с устраненными битами 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 53 55 47 39 31 23 15 7 62 54 46 38 30 22 P 3 14 6 61 53 45 37 29 2 13 5 28 20 12 4 Выход P 3 (K) представляется в виде 0 0 3 ) ( D C K P = , где 0 C – левая половина, 0 D – правая половина. 2. Очередные значения i i D C вычисляются по схеме ), ( ), ( 1 1 − − = = i i i i i i D L D C L C где L i – циклический сдвиг влево на одну позицию, если i= 1,2,9,16. В остальных случаях L i – сдвиг влево на две позиции. 3. На этом этапе выход перемешивается подстановкой P 4. Таблица 9.6 Подстановка для перемешивания 14 17 11 24 1 5 3 28 15 6 2 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 P 4 44 49 39 56 34 53 46 42 50 36 29 32 Дешифрация в стандарте DES. В процессе дешифрования по- следозвательно используются преобразования , , ,..., , , 1 16 2 1 − Φ Φ Φ IP T IP Каждое из преобразований Фейстела остается композицией двух преобразований. Первое из них – транспозиция L и R: T(L,R)= (R,L). Таким образом, для любого i T V i i = Φ . Кроме того, легко убедиться, что id T V i = = 2 2 – тождественное преобразование. Такие преобразо- вания (элементы группы) принято называть инволюциями. Для них, в частности, верно , 1 1 T T V V i i = = − − По правилу обращения элементов неабелевой группы имеем ). ( ) ( )) ( ) (( 16 2 1 1 1 1 15 16 1 1 IP T V TV TV IP IP T V T TV TV IP E D − − − − = = = 207 Это означает, что дешифрование осуществляется теми же алго- ритмом и ключом, но в расписание ключей надо внести некоторое из- менение: поменять на обратный порядок генерации ключей. Из (9.5), (9.6) следует, что основным фактором, определяющим вычислительную сложность метода “опробования” и одновременно криптостойкость алгоритма шифрования по отношению к рассматри- ваемому методу криптоатаки, является мощность пространства клю- чей Θ . С учетом этого оценим вычислительную сложность метода “опробования” криптосистемы DES. В этом случае двоичный текст (N = 2) шифруется блоками разме- ра n= 64 и используется 64-битовый ключ: } 56 , 1 , : ) ,..., { 2 56 1 = ∋ = Θ i V i θ θ θ , поэтому ) 64 ( 2 , 2 56 56 ω q W = = Θ Для суперЭВМ 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-раз- 208 рядными (unsigned int) или восемью 8-разрядными беззнаковыми це- лыми (unsigned char). Выберем первый способ представления ключа: unsigned long key_data[2]. Последовательный алгоритм для метода «опробования» при опре- делении ключа будет выглядеть следующим образом. int main(argc,argv) int argc; char argv[]; { int i,j,err=0; unsigned char in[8],out[8],outin[8]; /* 64-битовые сообщения */ unsigned long key_data[2]; /* 64-битовый ключ */ unsigned long i1=0,i2=0; unsigned long imin[2]={0,0}; /* нижняя граница */ unsigned long imax[2]={0xffff,0xffff}; /* верхняя граница диапазона ключа */ procedure_shifr(in,out); /* вызов процедуры шифрации */ i1=0;i2=0; /*перебор значений старшей части ключа*/ for (i1=imin[0]; i1 /*перебор значений младшей части ключа*/ for (i2=imin[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 – коли- 209 чество процессов приложения, n1 – нижняя, n2 – верхняя границы диапазона ключа для данного процесса. Тогда можно предложить сле- дующий способ распределения работы по процессам: h= (max-min+1)/numprocs /* частное */ ost=(max-min+1)%numprocs /* остаток */ n1=min+myid*h n2=n1+h if ((ost !=0) &&(myid==numprocs)) n2=n2+ost /* в последний процесс – остаток работы, если он есть */ Так как количество вариантов ключей намного больше количества процессов, то можно считать, что общий объем вычислений будет распределен между процессами равномерно. Чтобы узнать, найден ли ключ, удобно использовать кол- лективную функцию MPI_Allgather, которая позволяет каждому про- цессу иметь информацию обо всех процессах. MPI_Allgather( &num, 1, MPI_INT, buf, 1, MPI_INT, MPI_COMM_WORLD). В результате вызова этой функции в массиве buf будут находиться значения переменной num всех процессов коммуникатора, которая будет иметь значение 0xff, если ключ найден, и нуль – в противном случае. Если ключ найден, необходимо остановить работу всех процессов. Имеется два варианта остановки процессов. Если при проверке каж- дого варианта ключа опрашивать процессы о необходимости продол- жать работу, то получится, что все процессы синхронизируют свои действия и постоянно опрашивают друг друга, что, естественно, нера- ционально. Если опрашивать процессы не на каждой итерации цикла перебора, а, например, при каждом новом значении старшей части ключа (после полного перебора всех значений младшей части), то это приведет к дополнительному счету по поиску ключа, когда он уже найден, но процессы не знают об этом. Анализ показывает, что реа- лизация второго способа позволяет получить хороший параллельный алгоритм для решения задачи. Возможны следующие случаи нахождения ключа процессами при полном переборе вариантов: • ключ найден одним из процессов, • ключ из заданного диапазона не найден ни одним процессом, • часть процессов закончила перебор значений ключа, а другая – продолжает перебор значений. 210 В первом случае коллективный опрос процессов приведет к пре- кращению работы всех процессов приложения в случае нахождения ключа. Это можно реализовать вызовом функции MPI_Allgather и анализом полученных данных. Программа представлена ниже. MPI_Allgather( &num,1,MPI_INT,buf,1,MPI_INT,MPI_COMM_WORLD); for (i=0; i MPI_Finalize(); /* прерывание работы процессов */ return 0; } В двух оставшихся случаях может возникнуть ошибка вызова кол- лективной функции. Коллективная функция должна вызываться всеми процессами коммуникатора без исключения, но некоторые из процес- сов могут закончить работу по перебору ключей, что вызовет “зависа- ние” программы. Поэтому необходимо введение цикла после перебора ключей, в будем выполнять коллективный опрос процессов о нахож- дении ключа до тех пор, пока либо он не будет найден, либо перебор ключей закончат все процессы приложения. Это можно осуществить следующим образом: num=myid; /* номер процесса, закончившего перебор */ do /* опрос всех процессов, найден ли ключ */ { MPI_Allgather(&num,1,MPI_INT,buf,1,MPI_INT,MPI_COMM_WORLD); for (i=0; i MPI_Finalize(); /* прерывание работы процессов */ return 0; } /* возможен вариант, когда ключ не найден ни одним процессом */ PR=0; for (i=0; i }while (PR!=0); В num заносится собственный номер процесса, закончившего перебор вариантов ключей. Тогда полное окончание работы всех процессов 211 произойдет, когда после выполнения коллективной функции в масси- ве buf будут номера всех процессов приложения: 0,…numprocs-1. Ниже приведен текст параллельной программы метода опробова- ния для DES алгоритма криптоатаки с использованием открытых тек- стов, который является обобщением вышеописанного алгоритма. int main(argc,argv) int argc; char *argv[]; { int i,numprocs,myid,PR; unsigned long key_data[2]; /* 64-битовый ключ */ unsigned char in[8],out[8],outin[8]; /* 64-битовые тексты */ unsigned long i1=0,i2=0; int h,n1,n2,ost,num,*buf; unsigned long imin[2]={0,0}; /* нижняя граница */ unsigned long imax[2]={0xffff,0xffff}; /* верхняя граница диапазона ключа */ double t1,t2; MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&numprocs); MPI_Comm_rank(MPI_COMM_WORLD,&myid); /* вызов процедуры шифрации */ procedure_shifr(in,out); /* определение диапазонов значений ключей для каждого процесса */ h=(imax[0]-imin[0]+1)/numprocs; ost=(imax[0]-imin[0]+1)%numprocs; n1=imin[0]+myid*h; n2=n1+h; if ((ost!=0)&&(myid==numprocs-1)) n2=n2+ost; num=0; buf= (int *)malloc(numprocs*sizeof(int)); for (i=0; i /* перебор значений младшей части ключа для всех процессов одинаков*/ for (i2=imin[1]; i2 /* вызов процедуры дешифрации с помощью ключа key_data */ procedure_de_shifr(out,outin,key_data); if (memcmp(in,outin,8) == 0) /* ключ найден */ { t2 = MPI_Wtime(); 212 printf("key is: 0x%x 0x%x \n",i1,i2); printf("process %d %d \n",myid,i1); printf("time %f \n",t2-t1); num=0xFF; } /* ключ найден */ } /* опрос всех процессов, найден ли ключ */ MPI_Allgather( &num,1,MPI_INT,buf,1,MPI_INT,MPI_COMM_WORLD); for (i=0; i MPI_Finalize(); /* прерывание работы процессов */ return 0; } } /* данный процесс ключ не нашел */ if (num==0) printf(" no key! in process %d \n",myid); num=myid; /* номер процесса, закончившего перебор */ do { /* опрос всех процессов, найден ли ключ */ MPI_Allgather(&num,1,MPI_INT,buf,1,MPI_INT,MPI_COMM_WORLD); for (i=0; i MPI_Finalize(); /* прерывание работы процессов */ return 0; } /* возможен вариант, когда ключ не найден ни одним процессом */ PR=0; for (i=0; i /* все процессы закончили работу, ключ не найден */ MPI_Finalize(); return 0; } Рис. 9.3. Параллельная программа определения ключа по DES алгоритму КОНТРОЛЬНЫЕ ВОПРОСЫ К ГЛАВЕ 9 Контрольные вопросы к 9.1 1. Что такое криптология, крипография, криптоанализ? Каково основное назна- чение криптоанализа? 2. Какие виды криптоатак Вы знаете? 213 3. Что такое криптоатака с использованием открытых текстов и соответствую- щих им криптограмм? 4. Что такое метод «опробования»? 5. Что означают преобразования: прямое преобразование ) ; ( 0 θ X f Y = и обрат- ное ему преобразование X ) и (Y; f 0 1 = − ? 6. В чем заключается метод полного перебора? 7. Возможны ли множественные решения при поиске ключей? Как это устра- нить? 8. Каковы временные затраты на проведение криптоанализа для системы DES? Контрольные вопросы к 9.2 1. Что такое криптосистема DES? Опишите основные этапы шифрования в сис- теме DES. 2. Что такое преобразование Фейстела? Что такое функция f, роль ключа в реали- зации этой функции? 3. Как выглядит дешифрация в системе DES? Контрольные вопросы к 9.3 1. Предложите другой (более равномерный) способ распределения работы по процессам в параллельной программе криптографии. 2. Почему для опроса процессов о нахождении ключа удобно использовать кол- лективную функцию MPI_Allgather? 3. Почему необходимо введение цикла do … while после циклов перебора всех значений ключа? 4. Предложите вариант параллельной программы для данной задачи без исполь- зования коллективной функции. 5. Почему опрос процессов о том, найден ли ключ, на каждой итерации цикла перебора не позволяет получить ускорение на сети компьютеров? |