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

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

ГОУ ВПО “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

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

A = ga mod p

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

K = Ba mod p

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

Ba mod p = (gb mod p)a mod p = gab mod p = (ga mod p)b mod p = Ab mod p

В практических реализациях, для a и b используются числа порядка 10100 и p порядка 10300. Число 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");

              fprintf(f_temp,"%ld",X);//записываем Х в файл

              fclose(f_temp);

     f_temp=fopen("temp.txt","r");

              fscanf(f_temp,"%s",str);//затем считываем его как строку.

              fclose(f_temp);

}

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

} 

int main()

{

    //вычисление секретного ключа

    __int64 P,G,a,b,A,B,K_bob,K_alice;

    P=65537;//public

    G=32768;//public

    a=34523;//знает только Боб

    b=24357;//знает только Алиса

    A=powmod(G,a,P);//значение А вычисляет Боб и передает Алисе

    B=powmod(G,b,P);//значение B вычисляет Алиса и передает Бобу

    K_bob=powmod(B,a,P);//privat

    K_alice=powmod(A,b,P);//privat

   

    int_to_string(K_bob);                           //меняем формат ключей

  char key_bob[256];                                //Боба и Алисы на строковый

  for(int i=0;i<strlen(str);i++)key_bob[i]=str[i];  //тип.

    int_to_string(K_alice);                         //

  char key_alice[256];                              //

  for(int i=0;i<strlen(str);i++)key_alice[i]=str[i];// 

    //создание цифровой подписи

   

    __int64 p_pow=1,p=2,H=0;

              char ch;

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

     FILE* f_out=fopen("DiffiHelman_.txt","w");//сюда запишем подписанное

    if(f_in != NULL)                          //сообщение.

         {

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

              {

                      H+=ch*p_pow;  //вычмсляем ХЭШ сообшения

                      p_pow*=p;     //

                      fprintf(f_out,"%c",ch);//копируем из "DiffiHelman.txt"

              }                             // в "DiffiHelman_.txt"         

              fprintf(f_out,"%d",0);//стравим разделительный символ 0

              int_to_string(H);//меняем формат ХЭШа

              crypt(str,key_bob);//Шифруем ХЭШ секретным ключем Боба

               fprintf(f_out,"\n%s",str); //добавляем его к сообщению.

         }

     else printf("Error: No file(DiffiHelman.txt).\n");

     fclose(f_in);

     fclose(f_out);

//_________________________________

//Проверка подлинности  сообщения и подписи

 

      H=0;p_pow=1;        

     FILE* f = fopen("DiffiHelman_.txt","r");

       if(f != NULL)

         {

              int fl=0,i=0;

              while(((ch = getc(f))!= EOF)&&(fl==0))//считываем посимвольно

              {

                      if(ch=='0'){fl=1;}//пока не достигли подписи

                      if(fl==0)

                      {

                      H+=ch*p_pow;//вычисляем ХЭШ

                      p_pow*=p; 

                      printf("%c",ch);

                      }else//если достигнута подпись, то

                      {

                           fscanf(f,"%s",str);//считываем ее как строку

                           printf("\n\n______________________\ndigital signature=%s",str);

                      }

              }

         }

     else printf("Error: No file(DiffiHelman.txt).\n");

      fclose(f);

 

     char hash[1024];

     char dhash[1024];

 

      crypt(str,key_alice);//дешифруем подпись секретным ключем Алисы

      int fl=0;

     for(int i=0;i<=strlen(str);i++)

     {

             dhash[i]=str[i];//записываем дешифрованный ХЭШ в dhash

     }

     int_to_string(H);//меняем формат вычисленного ХЭШа на строковый

     for(int i=0;i<=strlen(str);i++)

     {

             hash[i]=str[i];

             if(hash[i]!=dhash[i])fl=1;//сравниваем дэшифрованный и вычисленный

     }                                 //ХЭШи            

    

     printf("\ndecriptHASH msg=%s",dhash);

     printf("\nmsgHASH=%s\n",hash);

    

     if(!fl)printf("\nVerification OK!\n");

     else printf("\nVerification failed!\n");

    

         system("PAUSE");

    return 0;

}

 

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

 

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

Ядро алгоритма состоит  из функции генерации ключевого  потока. Эта функция генерирует последовательность битов ( ), которая затем объединяется с открытым текстом ( ) посредством суммирования по модулю два. Так получается шифрограмма ( ):

.

Расшифровка заключается  в регенерации этого ключевого  потока ( ) и сложении его и шифрограммы ( ) по модулю два. В силу свойств суммирования по модулю два на выходе мы получим исходный незашифрованный текст( ):

Другая главная часть  алгоритма — функция инициализации, которая использует ключ переменной длины для создания начального состояния генератора ключевого потока.

RC4 — фактически класс алгоритмов, определяемых размером его блока. Этот параметр n является размером слова для алгоритма. Обычно, n = 8, но в целях анализа можно уменьшить его. Однако для повышения безопасности необходимо увеличить эту величину. Внутреннее состояние RC4 представляется в виде массива слов размером 2n и двух счетчиков, каждый размером в одно слово. Массив известен как S-бокс, и далее будет обозначаться как S. Он всегда содержит перестановку 2n возможных значений слова. Два счетчика обозначены через i и j.

Алгоритм инициализации RC4 приведен ниже. Этот алгоритм также  называется алгоритмом ключевого расписания (англ. Key-Scheduling Algorithm or KSA). Этот алгоритм использует ключ, сохраненный в Key, и имеющий длину L байт. Инициализация начинается с заполнения массива S, далее этот массив перемешивается путем перестановок, определяемых ключом. Так как только одно действие выполняется над S, то должно выполняться утверждение, что Sвсегда содержит все значения кодового слова.

Генератор ключевого  потока RC4 переставляет значения, хранящиеся в S, и каждый раз выбирает различное значение из S в качестве результата. В одном цикле RC4 определяется одно n-битное слово K из ключевого потока, которое в последующем суммируется с исходным текстом для получения зашифрованного текста. Эта часть алгоритма называется генератором псевдослучайной последовательности (англ. Pseudo-Random Generation Algorithmor PRGA).

Рис 2.1- Генератор ключевого потока RC4

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

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

#include<iostream>  

#include<cstring>  

using namespace std;   

  

  

void crypt(char cipher[]);   

 

int main()  

{  

 cout<<"--------RC4---------"<<endl;  

char choose1,choose2;  

do{  

       int s[256],t[256];  

       char k[256];

       char plaintext[1024],ciphertext[1024];  

       cout<<"Enter key:";  

       cin>>k;   //считать ключ

       for(int i=0;i<256;i++)  //инициализация ключевого массива

        {  

            s[i]=i;  

            t[i]=k[i%strlen(k)];   //strlen(k)- длинна строки k

        }  

        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;  

        }  

        cout<<"\nEnter plaintext:"<<endl;  

        cin>>plaintext;   //считать текст, который требуется зашифровать

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

        m=n=0;  

        int i;  

        cout<<"\nciphertext:"<<endl;  

        for(i=0;i<strlen(plaintext);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];  

             ciphertext[i]=plaintext[i]^key[i];  

             cout<<ciphertext[i];   

  

        }  

        ciphertext[i]='\0';  

        cout<<endl;  

        cout<<"\ndecrypt (y/n)";  

        cin>>choose2;  

        while(choose2=='y'||choose2=='Y')  

        {  

            crypt(ciphertext);//вызываем функцию, для дешифрования

            choose2='n';  

        }  

        cout<<endl;  

        cout<<"\nrepeat encryption?(y/n)";  

        cin>>choose1;  

}while(choose1=='y'||choose1=='Y');   

  

cout<<"\n______________________EXID_________________________"<<endl<<endl;  

system("pause");  

}   

  

 

 

   void crypt(char cipher[])  

{  

    int s[256],t[256];  

    char k[256];

    char plaintext[1024];  

    cout<<"\nEnter key:";  

    cin>>k;  

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

    {  

         s[i]=i;  

         t[i]=k[i%strlen(k)];  

    }  

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

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

       cout<<plaintext[i];   

   }   

  

cout<<endl;  

} 

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

 

 


Курсовая работа по «Информатике». 2 📙 Курсовая → 🆔 114395

Курсовая работа по «Информатике». 2 📙 Курсовая → 🆔 114395

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