страница 1
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
Похожие работы
|
Лабораторная работа по дисциплине «Защита информации»: Современные симметричные и - страница №1/1
Московский государственный институт электроники и математики Кафедра Информационно-Коммуникационных Технологий Лабораторная работа по дисциплине «Защита информации»: Современные симметричные и ассиметричные криптосистемы Выполнил: студент группы С-84, Новиков Р.О. Москва 2008
1. Постановка задачи Целью данной работы является разработка криптографического алгоритма, реализующего шифрование по схеме Полига – Хеллмана. Для реализации данного алгоритма был выбран язык С. 2. Общее описание алгоритма Схема шифрования Полига - Хеллмана сходна со схемой шифрования RSA. Она представляет собой несимметричный алгоритм, поскольку используются различные ключи для шифрования и расшифрования. В то же время эту схему нельзя отнести к классу криптосистем с открытым ключом, так как ключи шифрования и расшифрования легко выводятся один из другого. Оба ключа (шифрования и расшифрования) нужно держать в секрете. Аналогично схеме RSA криптограмма С и открытый текст Р определяются из соотношений: С = Рe mod n, Р = Сd mod n, где e*d є1 (по модулю некоторого составного числа). В отличие от алгоритма RSA в этой схеме число n не определяется через два больших простых числа; число n должно оставаться частью секретного ключа. Если кто-либо узнает значения е и n, он сможет вычислить значение d. Не зная значений е или d, противник будет вынужцен вычислять значение е = logP С (mod n). Пусть задано сравнение (1) и известно разложение p − 1на простые множители: Необходимо найти натуральное число x, удовлетворяющее сравнению (1). Заметим, что на практике всегда рассматривается случай, когда a – первообразный корень по модулю p. В этом случае сравнение (1) имеет решение при любом b, взаимно простом с p. Суть алгоритма в том, что достаточно найти x по модулям для всех i, а затем решение исходного сравнения можно найти с помощью китайской теореме об остатках. Чтобы найти x по каждому из таких модулей, нужно решить сравнение: Данное сравнение решается за полиномиальное время в случае, если qi - небольшое (то есть, не превосходит (logp)c, где c – некоторая константа). Китайская теорема об остатках. Пусть - коммутативные ассоциативные кольца с единицей, сюрьективные гомоморфизмы, обладающие свойством для всех . Тогда гомоморфизм: , где: является сюрьективным. Более того, Φ опеределяет изоморфизм: Если положить , и определить гомоморфизмы следующим образом то мы получим арифметическую версию теоремы. Также часто встречается следующая эквивалентная формулировка для колец, где Bi имеют форму A / Ii, φi являются естественными проекциями на A / Ii и требуется, чтобы Ii + Ij = A для любых . Алгоритм Полига-Хеллмана крайне эффективен, если p-1 раскладывается на небольшие простые множители. Например, для чисел вида и т.д. Если же у p-1 есть большой простой делитель то алгоритм имеет экспоненциальную сложность. Это очень важно учитывать при выборе параметров криптографических схем. 3. Структурная схема алгоритма 1. Составление таблицы. Составить таблицу значений {ri,j}, где 2. Нахождение Для i от 1 до s: Пусть где Тогда из (1) следует, что Для j от 1 до α − 1 Рассматриваем сравнение Решение опять же находится по таблице Конец цикла по i Конец цикла по j 3. Нахождение ответа Найдя для всех i, находим по китайской теореме об остатках. Сложность алгоритма Решение сравнения (1) находится за арифметических операций. Можно также сказать, что решение находится за арифметических операций, где q – наибольший простой делитель p-1. Если все простые делители qi не превосходят то алгоритм Полига-Хеллмана является полиномиальным и имеет сложность , где c1,2 – некоторые положительные постоянные. 4. Примеры Пример 1. Открытый текст: roman novikov student avt s84 Ключ: 4859 Шифротекст: 6143745089153872416921957448971406201787452212933147406493915739761010637430011008577398110215733949965177426096928741847418810131774510110360714021103 Пример 2. Открытый текст: the quick brown fox jumping over lazy dogs Ключ: 9498 Шифротекст: 519155141902911659361591547491849167141985991555015991447951639134351341981619781391719581109127587191916854141895177885129151345121914814159793159461399198390161919694169893149911149161471559136341790951734810991145921 Пример 3. Открытый текст: moscow is the capital of russia Ключ: 5859 Шифротекст: 1142218504314421148554122168421139215445217521462165852314213184412621360414442714253411215945414921640451812146654814214664611121956416182318882716848011215325 5. Листинг #include #include #include "mirdef.h" #include "miracl.h" big value1; big value2; struct pp *next; /*результаты Pohlig Hellman*/ } pair; /*результаты расчета китайской теоремы */ /* * Прототипы */ void shanks(big, big, big, big, big ); int insert(pair *, big, big); void find_elem_list(int ,int , pair *, big , big ); int search(pair * ,big , big , big ); void main(void) { int number_of_factors,k,i,comp; big y, a, p, result, dummy_base, dummy_exp, comparator, gamma, pminus1, pi, dummy,zero; big zj, delta, j, temp, bee, uno, *x_base, *moduli_base, *x_ptr, *moduli_ptr; pair factorization; pair *ptemp, bees; mirsys (155, 10); dummy_base=mirvar(1); dummy_exp =mirvar(1); dummy=mirvar(0); comparator=mirvar(0); pminus1=mirvar(1); gamma=mirvar(0); pi=mirvar(0); y=mirvar(1); a=mirvar(1); p=mirvar(1); zj=mirvar(0); delta=mirvar(0); temp=mirvar(0); bee=mirvar(0); uno=mirvar(1); result=mirvar(0); zero=mirvar(0); factorization.value2=mirvar(0); factorization.next=NULL; bees.value1=mirvar(0); bees.value2=mirvar(0); bees.next=NULL; decr(p,1,pminus1); /*Создаем p-1*/ /* Расчет полиномов p-1 */ number_of_factors=1; { /* 'x' и модули */ (*x_ptr)=mirvar(0); (*moduli_ptr)=mirvar(0); x_ptr++; moduli_ptr++; } for ( i = 1 , moduli_ptr = moduli_base , x_ptr=x_base ; i i++, x_ptr++, moduli_ptr++ ) { copy(pminus1,dummy); find_elem_list(i,(number_of_factors-1),&factorization,pi,dummy_exp); divide(dummy,pi,dummy); powmod(a,dummy,p,gamma); copy(y,zj); comp = -1; for( j=mirvar(1) ; compare(j,dummy_exp) != (1) ; incr(j,1,j) ) { powmod(pi,j,pminus1,temp); copy(pminus1,dummy); divide(dummy,temp,dummy); powmod(zj,dummy,p,delta); shanks(gamma,delta,p,pi,bee); insert(&bees,bee,j); decr(j,1,temp); powmod(pi,temp,pminus1,temp); multiply(bee,temp,temp); powmod(a,temp,p,temp); xgcd(temp,p,temp,temp,temp); powmod2(temp,uno,zj,uno,p,zj); } powmod(pi,dummy_exp,p,dummy); bee=mirvar(0); comp=-1; for( ptemp=bees.next, copy(zero,j) ; compare(j,dummy_exp) == (-1); incr(j,1,j) ) { powmod2(ptemp->value1,uno,pi,j,dummy,temp); add(bee,temp,bee); ptemp = ptemp->next; } copy(bee,*x_ptr); copy(dummy,*moduli_ptr); free(&bees); bees.value1=mirvar(0); bees.value2=mirvar(0); bees.next=NULL; } crt_init((number_of_factors-1),moduli_base); crt(x_base,result); crt_end(); } { int i; pair *ptemp; ptemp=factors; if (elem_num>maximum) { printf ("This is not a possible element\n"); exit(0); } i=0; while (1) { if (i==elem_num) { copy(ptemp->value1,exponent); copy(ptemp->value2,base); return; } ptemp=ptemp->next; i++; } void shanks(big alpha, big beta, big p, big pi, big ret) { int comp; big j,i,dummy; big t; big m; big pminus; big ein; / pair list1,list2; t = mirvar(0); list1.value1 = mirvar(0); list1.value2 = mirvar(0); list2.value1 = mirvar(0); list2.value2 = mirvar(0); list1.next = NULL; list2.next = NULL; m = mirvar(0); j = mirvar(0); ein = mirvar(1); pminus = mirvar(0); dummy = mirvar(0); comp = (-1); while ( comp == (-1) ) { comp = compare(j,m); multiply(m,j,t); powmod(alpha,t,p,t); insert(&list1,j,t); incr(j,1,j); } i = mirvar(0); comp = (-1); while ( comp == (-1) ) { comp = compare(i,m); powmod(alpha,i,p,t); xgcd(t,p,t,t,t); /* alpha^(-i) */ powmod2(t,ein,beta,ein,p,t); if (search (&list1, t, m,j)==1) { mad(m,j,i,pminus,dummy,t); copy(t,ret); return; } incr(i,1,i); } printf("Error!\n"); } int insert(pair *plist, big el1, big el2) { pair *ptemp = NULL; pair *pnew = NULL; /* Объявление */ pair *pprevious = NULL; pair *pchange = NULL; if ( (pnew = (pair *)malloc(sizeof(pair))) == NULL ) { printf("Error - out of memory.\n"); exit(1); } /* Проверка памяти */ else { pnew->value1 = mirvar(0); pnew->value2 = mirvar(0); copy(el1,pnew->value1); copy(el2,pnew->value2); pnew->next = NULL; } if (plist->next==NULL) { plist->next = pnew; /*Insert here if the list is empty */ } else { pprevious = plist; ptemp = plist; while (ptemp->next != NULL) { ptemp=ptemp->next; if ( (-1) == compare(pnew->value2,ptemp->value2) ) { pchange = ptemp; pprevious->next = pnew; pnew->next = pchange; return(0); } pprevious=ptemp; } ptemp->next = pnew; } return(1); } int search(pair *list2,big el, big m, big ret) { big top,bottom,middle; pair *temp2; big i,neg1; big temp; top = mirvar(0); bottom = mirvar(0); middle = mirvar(0); neg1 = mirvar(-1); temp=mirvar(0); i=mirvar(0); decr(m,1,top); while( compare(top,bottom) != (-1) ) { add(top,bottom,temp); subdiv(temp,2,middle); for (i=mirvar(-1), temp2 = list2->next; (compare(i,middle) == (-1)) ; temp2 = temp2->next, incr(i,1,i)); if ( compare(el,temp2->value2) == 0 ) { copy(temp2->value1,ret); return(1); } else if ( compare(el,temp2->value2) == 1 ) incr(middle,1,bottom); else decr(middle,1,top); } return(0); } |
|