Курсовая работа по «Информатике»

Федеральное агентство связи РФ

ГОУ ВПО “CибГУТИ”

 

 

 

Кафедра ВТИТ

 

 

 

 

Курсовая  работа

По «Информатике»

 

 

 

 

 

Выполнил: студент  курса ф. МРМ Сычёв В.В.

Проверил: Рягин Б.А.

 

 

 

 

Новосибирск 2012

Содержание

1.Текст задания, с указанием номера студента в журнале и соответствующих вариантов задания.

2.Краткое описание алгоритма шифра Эль-Гамаля.

3.Реализация шифрования/дешифрования методом Эль-Гамаля.

3.1. Описание основных функций и переменных.

3.2.Результаты выполнения программы.

4. Краткое описание алгоритма электронной подписи Диффи-Хеллмана.

5. Реализация алгоритма подписи  сообщения c помощью системы Диффи-Хеллмана.

5.1. Описание основных функций и переменных.

5.2. Результаты выполнения программы.

6. Краткое описание алгоритма RC4.

7. Реализация алгоритма RC4.

7.1. Описание основных функций и переменных.

7.2. Результаты выполнения программы.

 

 

 

 

 

 

 

 

 

 

 

1.Текст задания, с указанием номера студента в журнале и соответствующих вариантов задания

. Программно  реализовать на языке C++ алгоритм шифрования и дешифрования  сообщения c помощью метода в соответствии с вариантом. Номер варианта k определяется по формуле: k=N mod 4, где N=11 – номер студента в журнале.

K=5 mod 4=1;

K=1

Метод шифрования «Шифр Эль-Гамаля»                                                   Программно реализовать на языке C++ алгоритм электронной подписи сообщения и проверки его подлинности c помощью метода в соответствии с вариантом. Номер варианта k определяется по формуле: k=N mod 3, где N – номер студента в журнале.

K=5 mod 3=2

K=2

Система Диффи-Хелмана

 Программно  реализовать на языке C++ алгоритм шифрования и дешифрования  сообщения c помощью потокового шифра RC4.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2.Краткое описание алгоритма шифра Эль-Гамаля.

Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи.

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

Генерация ключей

1. Генерируется случайное простое число   длины   битов.
2. Выбирается случайное целое число   такое, что  .
3. Выбирается случайное целое число   такое, что  .
4. Вычисляется  .
5. Открытым ключом является тройка  , закрытым ключом — число  .

Работа в режиме шифрования

Шифрсистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

Шифрование

Сообщение   шифруется следующим образом:

1. Выбирается сессионный ключ — случайное целое число   такое, что 
2. Вычисляются числа   и  .
3. Пара чисел   является шифротекстом.

Нетрудно видеть, что длина  шифротекста в схеме Эль-Гамаля длиннее исходного сообщения   вдвое.

Расшифрование

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

При этом нетрудно проверить, что

и поэтому

.

Для практических вычислений больше подходит следующая формула:

 

Пример

• Шифрование
1. Допустим что нужно зашифровать сообщение  .
2. Произведем генерацию ключей :
1. пусть  . Выберем   - случайное целое число   такое,что  .
2. Вычислим  .
3. Итак , открытым является тройка  ,а закрытым ключом является число  .
3. Выбираем случайное целое число   такое, что 1 < k < (p − 1). Пусть  .
4. Вычисляем число  .
5. Вычисляем число  .
6. Полученная пара   является шифротекстом.
• Расшифрование
1. Необходимо получить сообщение   по известному шифротексту   и закрытому ключу  .
2. Вычисляем M по формуле : 
3. Получили исходное сообщение  .

 

Так как в схему Эль-Гамаля вводится случайная величина  ,то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа   такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение   и ключ не определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины   для шифровки различных сообщений   и  . Если использовать одинаковые  , то для соответствующих шифротекстов   и   выполняется соотношение  . Из этого выражения можно легко вычислить  , если известно  .

3.Реализация шифрования дешифрования методом Эль-Гаммеля

3.1.описание основных функций и переменных

#include <iostream>//подключение встроенных библиотек

#include <fstream>

#include <stdio.h>

#include <cstdlib>

#include <math.h>//

using namespace std;

//ELGamm

void extended_euclid(__int64 a, __int64 b, __int64 *x, __int64 *y, __int64 *d)

/* calculates a * *x + b * *y = gcd(a, b) = *d */

{// алгоритм для нахождения наибольшего общего делителя двух целых чисел

  __int64 q, r, x1, x2, y1, y2;

  if (b == 0) {

    *d = a, *x = 1, *y = 0;

    return;

  }

  x2 = 1, x1 = 0, y2 = 0, y1 = 1;

  while (b > 0) {

    q = a / b, r = a - q * b;

    *x = x2 - q * x1, *y = y2 - q * y1;

    a = b, b = r;

    x2 = x1, x1 = *x, y2 = y1, y1 = *y;

  }

  *d = a, *x = x2, *y = y2;

}

 

__int64 invmod(__int64 a, __int64 n)

/* computes the inverse of a modulo n */

{

  __int64 d, x, y;

  extended_euclid(a, n, &x, &y, &d);

  if (d == 1)

    if (x>0)

      return x;

    else

      return x+n;

  return 0;

}

 

__int64 powmod(__int64 a, __int64 k, __int64 n)

{//вычисление a^k mod n

  __int64 b=1;

  while (k) {

    if (k%2==0) {

      k /= 2;

      a = (a*a)%n;

      }

    else {

      k--;

      b = (b*a)%n;

      }

  }

  return b;

}

 

main() {

__int64 P,G,X,Y,K,M,a,b,MM;

P=65537;//public

G=32768;//public

X=45621;//privat

Y=powmod(G,X,P);//public

K=37121;//privat

//Шифруем

 

FILE* f_in = fopen("ELGamm_in.txt","r"); //открываем файл для чтения

FILE* f_out= fopen("ELGamm_out.txt","w");//открываем файл для записи

if(f_in != NULL)

{

  int i=0;

  char ch;

  while((ch = getc(f_in)) != EOF)//пока не конец файла

            {

                     

                       M=ch;

                       a=powmod(G,K,P);//вычисляем шифротекст и записываем

                       fprintf(f_out,"%Ld ",a);//его в файл, для шифрованного

                       b=powmod(Y,K,P)*M % P;//сообшения

                       fprintf(f_out,"%Ld ",b);

             }

            fprintf(f_out,"%Ld\n",0);//обозначаем конец файла нулевыми a и b

            fprintf(f_out,"%Ld\n",0);

}

else printf("No file(read).\n");

fclose(f_in);//закрываем открытые ранее

fclose(f_out);//файлы

//ДеШифруем

FILE* fin = fopen("ELGamm_out.txt","r");

 f_out= fopen("ELGamm_out2.txt","w");

if(f_in != NULL)

{

            while(a||b)//пока а и b не равы 0, считываем a и b

            {

                       fscanf(fin,"%Ld %Ld \n",&a,&b);

                       MM=b*invmod(powmod(a,X,P),P) % P;//дешифруем считанное

                       fprintf(f_out,"%c",MM);          //сообщение и записываем

            }                                           //в файл

 

}

else printf("No file(read).\n");

fclose(fin);

fclose(f_out);

printf("    input file: 'ElGamm_in'\n");

printf("encrypted file: 'ElGamm_out'\n");

printf("decrypted file: 'ElGamm_out2'\n");

 

system("PAUSE");

return 0;

}

 

3.2Результаты выполнения программы.

 

 

 

 

 

 

 

 

 

 

 

 

4.Краткое описание алгоритма электронной подписи Диффи-Хеллмана.

Алгоритм Ди́ффи — Хе́ллмана — алгоритм, позволяющий двум сторонам получить общий секретный ключ, используя незащищенный от прослушивания, но защищённый от подмены канал связи. Этот ключ может быть использован для шифрования дальнейшего обмена с помощью алгоритма симметричного шифрования.

Алгоритм был впервые  опубликован Уитфилдом Диффи и Мартином Хеллманом в 1976 году.

В 2002 году Хеллман предложил называть данный алгоритм «Диффи — Хеллмана — Меркля», признавая вклад Меркля в изобретение криптографии с открытым ключом.

История

Схема обмена ключами Диффи — Хеллмана, изобретённая в 1976 году при сотрудничестве Уитфилда Диффи и Мартина Хеллмана, под сильным влиянием работы Ральфа Меркля (Ralph Merkle) о системе распространения публичных ключей, стала первым практическим методом для получения общего секретного ключа при общении через незащищенный канал связи. Для обеспечения устойчивости, по совету Джона Гилла (John Gill), была использована проблема дискретного логарифмирования.

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

В декабре 1997 года была обнародована информация, что в 1974 году Малькольм Вильямсон изобрел математический алгоритм, основанный на коммутативности показателей при последовательном возведении в степень (то есть,  ), аналогичный алгоритму Диффи-Хеллмана.

Описание алгоритма

Предположим, что обоим  абонентам известны некоторые два  числа g и p (например, они могут быть «зашиты» в программное обеспечение), которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: первый абонент — число a, второй абонент — число b. Затем первый абонент вычисляет значение   и пересылает его второму, а второй вычисляет   и передаёт первому. Предполагается, что злоумышленник может получить оба этих значения, но не модифицировать их (то есть у него нет возможности вмешаться в процесс передачи). На втором этапе, первый абонент на основе имеющегося у него   и полученного по сети   вычисляет значение  , а второй абонент на основе имеющегося у него   и полученного по сети   вычисляет значение  . Как нетрудно видеть, у обоих абонентов получилось одно и то же число:  . Его они и могут использовать в качестве секретного ключа, поскольку здесь злоумышленник встретится с практически неразрешимой (за разумное время) проблемой вычисления   по перехваченным   и  , если числа   выбраны достаточно большими.

Алгоритм  Диффи — Хеллмана, где K — итоговый общий секретный ключ

При работе алгоритма, каждая сторона:

1. генерирует случайное натуральное число a — закрытый ключ
2. совместно с удалённой стороной устанавливает открытые параметры p и g (обычно значения p и g генерируются на одной стороне и передаются другой), где

p является случайным простым числом

g является первообразным корнем по модулю p

3. вычисляет открытый ключ A, используя преобразование над закрытым ключом

A = g^a mod p

4. обменивается открытыми ключами с удалённой стороной
5. вычисляет общий секретный ключ K, используя открытый ключ удаленной стороны B и свой закрытый ключ a

K = B^a mod p

К получается равным с обеих сторон, потому что:

B^a mod p = (g^b mod p)^a mod p = g^ab mod p = (g^a mod p)^b mod p = A^b mod p

В практических реализациях, для a и b используются числа порядка 10¹⁰⁰ и p порядка 10³⁰⁰. Число g не обязано быть большим и обычно имеет значение в пределах первого десятка.

5. Реализация алгоритма подписи  сообщения c помощью системы Диффи-Хеллмана.

5.1. Описание основных  функций и переменных.

 

#include <iostream>//подключение встроенных библиотек

#include <fstream>

#include <stdio.h>

#include <cstdlib>

#include <math.h>

//using namespace std;

//Diffi-Helman

char str[1024];

void crypt(char cipher[],char k[256])  

{   //процедура симметричного шифрования RC4

    //шифрованная или дешифровання строка сохраняется

    //в глобальной переменной str[1024]

    int s[256],t[256];  

     for(int i=0;i<256;i++)

    {  

         s[i]=i;  

         t[i]=k[i%strlen(k)];   //strlen(arg)- возврашает длинну

    }                           //строки arg

   

    int j=0;  

    for(int i=0;i<256;i++)  

    {  

        int temp;  

        j=(j+s[i]+t[i])%256;  

        temp=s[i];  

        s[i]=s[j];  

        s[j]=temp;  

    }   

  

   int m,n,key[256],q;  

   m=n=0;  

   int i;  

//   cout<<"\ndecriptet text"<<endl;  

   for(i=0;i<strlen(cipher);i++) 

   {  

       int temp;  

       m=(m+1)% 256;  

       n=(n+s[n])% 256;  

       temp=s[m];  

       s[m]=s[n];  

       s[n]=temp;  

       q=(s[m]+s[n])%256;  

       key[i]=s[q];  

       str[i]=cipher[i]^key[i];  

     //  printf("%c",plaintext[i]);//cout<<plaintext[i];   

   }   

  

  //return plaintext;

}

void int_to_string(__int64 X)

{// записывает каждую цифру число Х в отдельную ячейку str.

     FILE* f_temp=fopen("temp.txt","w");