Лабораторная работа по дисциплине «Защита информации»: Современные симметричные и ассиметричные криптосистемы - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Современные симметричные и ассиметричные криптосистемы 1 90.33kb.
Современные симметричные и ассиметричные криптосистемы 1 224.22kb.
Лабораторная работа №1 по дисциплине «Информационная безопасность... 1 43.31kb.
Современные симметричные криптосистемы 1 214.75kb.
Лабораторная работа по дисциплине «Защита информации»: Криптографический... 1 68.89kb.
Защита информации в сетях связи 1 249.41kb.
Лабораторная работа № Криптология и защита информации. Основа организации... 1 16.57kb.
Лабораторная работа №6 по курсу "Информационная безопасность" Лабораторная... 1 57.72kb.
Симметричные и несимметричные криптосистемы. Схемы эцп 1 18.42kb.
I. введение. Криптографическая защита информации 1 165.75kb.
3 Симметричные криптосистемы 6 Классификация крип­то­гра­фи­че­ских... 4 543.12kb.
Определители 1 37.25kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Лабораторная работа по дисциплине «Защита информации»: Современные симметричные и - страница №1/1



Московский государственный институт электроники и математики

Кафедра Информационно-Коммуникационных Технологий



Лабораторная работа по дисциплине «Защита информации»:

Современные симметричные и ассиметричные криптосистемы

Выполнил: студент группы С-84, Новиков Р.О.

Москва 2008

Содержание

  1. Постановка задачи

3

  1. Общее описание алгоритма

4

  1. Математическое описание алгоритма

5

  1. Структурная схема алгоритма

7

  1. Примеры шифрования информации

8

  1. Листинг

9


1. Постановка задачи

Целью данной работы является разработка криптографического алгоритма, реализующего шифрование по схеме Полига – Хеллмана. Для реализации данного алгоритма был выбран язык С.



2. Общее описание алгоритма

Схема шифрования Полига - Хеллмана сходна со схемой шифрования RSA. Она представляет собой несимметричный алгоритм, поскольку используются различные ключи для шифрования и расшифрования. В то же время эту схему нельзя отнести к классу криптосистем с открытым ключом, так как ключи шифрования и расшифрования легко выводятся один из другого. Оба ключа (шифрования и расшифрования) нужно держать в секрете.

Аналогично схеме RSA криптограмма С и открытый текст Р определяются из соотношений:

С = Рe mod n,

Р = Сd mod n,

где e*d є1 (по модулю некоторого составного числа).

В отличие от алгоритма RSA в этой схеме число n не определяется через два больших простых числа; число n должно оставаться частью секретного ключа. Если кто-либо узнает значения е и n, он сможет вычислить значение d.

Не зная значений е или d, противник будет вынужцен вычислять значение

е = logP С (mod n).

3. Математическое описание алгоритма

Алгоритм Полига–Хеллмана – детерминированный алгоритм дискретного логирифмирования в кольце вычетов по модулю простого числа. Для модулей специального вида данный алгоритм является полиномиальным. Дискретное логарифмирование (DLOG) – задача обращения функции в некоторой конечной мультипликативной группе G. Важной особенностью этого метода является то, что для простых чисел специального вида, можно находить дискретный логарифм за полиномиальное время.

Пусть задано сравнение



(1)

и известно разложение p − 1на простые множители:



Необходимо найти натуральное число x, удовлетворяющее сравнению (1). Заметим, что на практике всегда рассматривается случай, когда a – первообразный корень по модулю p. В этом случае сравнение (1) имеет решение при любом b, взаимно простом с p.

Суть алгоритма в том, что достаточно найти x по модулям для всех i, а затем решение исходного сравнения можно найти с помощью китайской теореме об остатках. Чтобы найти x по каждому из таких модулей, нужно решить сравнение:

(2)

Данное сравнение решается за полиномиальное время в случае, если 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) следует, что


С помощью таблицы, составленной на шаге 1, находим x0.

Для 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"
typedef struct pp {

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.value1=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;
for(k=0;k<(number_of_factors-1);k++) /* Инициализация массивов */

{ /* 'x' и модули */

(*x_ptr)=mirvar(0);

(*moduli_ptr)=mirvar(0);


x_ptr++;

moduli_ptr++;

}
/* Запуск Pohlig-Hellman алгоритма */
/* Find x mod p_i for all 1 <= i < # of factors */

for ( i = 1 , moduli_ptr = moduli_base , x_ptr=x_base ;

i < number_of_factors ;

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();

}
void find_elem_list(int elem_num,int maximum, pair *factors, big base, big exponent)

{

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);


}