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

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

- функция D должна соответствовать функции E,

- ключ k2 должен соответствовать ключу k1.

Алгоритмы шифрования можно разделить на две  категории:

1. алгоритмы   симметричного шифрования, в которых k2 = k1 = k;

2. алгоритмы   асимметричного шифрования (алгоритмы  с открытым ключом), в которых  ключ k1 вычисляется из ключа k2 таким образом, что обратное вычисление невозможно, например, по формуле

k1 = a^k2 mod p,

где a и p – параметры алгоритма.

Большинство симметричных алгоритмов работают следующим  образом: над шифруемым текстом  выполняется некоторое преобразование с участием ключа шифрования, которое  повторяется определенное число  раз (раундов).

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

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

Модификацией шифров-перестановок являются шифры-перестановки со словом-ключом, которое определяет порядок взятия слов-столбцов. Наиболее простой способ шифрования с ключом следующий: под символами сообщения записывается раз за разом ключ, затем номера соответствующих знаков сообщения и ключа складываются. Если полученная сумма больше общего числа знаков, то от нее отнимается это общее число знаков. Полученные числа будут номерами символов кода. С ростом длины ключа трудоемкость дешифровки подобного шифра стремительно растет.

 

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

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

Примером  ассиметричного алгоритма является система RSA, разработанная в 1978 году Р.Ривестом, Э.Шамиром и Л.Адлеманом. Его принцип заключается в следующем. Пусть абоненты A и B решили организовать для себя возможность секретной переписки. Для этого каждый из них независимо выбирает два больших простых числа ( , и , ), находит их произведение (r_A и r_B), функцию Эйлера от этого произведения (j(r_A) и j(r_B)) и случайное число (a и b), меньшее вычисленного значения функции Эйлера и взаимно простое с ним. Кроме того, абонент A из уравнения

aa º 1 (mod j(r_A))

находит a  (0 < a < j(r_A)), а абонент B из уравнения

bb º 1 (mod j(r_B))

 находит b  (0 < b < j(r_B)). Затем A и B публикуют доступную всем информацию вида:

A: r_A, a;

B: r_B, b.

Теперь кто угодно может отправлять конфиденциальные сообщения A или B. Например, если пользователь C хочет отправить сообщение m для B (m должен быть меньшим r_B или делится на куски, меньшие r_B), то он использует ключ b для получения шифрованного сообщения m₁ по формуле

m₁ º m^b (mod r_B),

которое и  отправляется B. Получатель сообщения B для дешифрирования m₁ использует ключ b в формуле

º m^bb º m (mod r_B),

так как bb º 1 (mod j(r_B)), следовательно, bb = kj(r_B) + 1 для некоторого целого k и m^{kj(rB) + 1} º (m^j(rB) )^km º m (mod r_B), так как m^j(rB)  º 1 (mod r_B) по теореме Эйлера-Ферма.

Функция Эйлера j(n), где n – натуральное число, определяется следующим образом:

1. j(1) = 1;

2. ,

где p_i – простые сомножители числа n, a_i – кратности простых сомножителей числа n.

 

 

4.3 Программная реализация и алгоритмы.

 

4.3.1 Запуск программы, входные и  выходные данные.

 

Для запуска  программы необходимо кликнуть на файл названием tik_lab4.exe, после этого откроется консольное окно с текстом. В окне будет написан порядок дальнейших действий.

Программа попросит пользователя ввести число  P1, для ассиметричного кодирования RSA, после этого программа сама подберет число P2,a-открытый ключ и alpha-закрытый ключ. Программа попросит пользователя ввести сообщение(число), которое он хочет зашифровать. После нажатия enter, она выведет на экран зашифрованное, а потом дешифрованное сообщение по методу RSA.

Затем программа  приступит к шифрованию с ключом, используя латинский алфавит. Необходимо ввести длину входного сообщения, затем  ввести само сообщение  с алфавитом {a,b,c,d} которое необходимо шифровать. Далее вводится длина ключа и сам ключ. Алфавит ключа -латинский алфавит. На экран будет выведено зашифрованное сообщение, а затем дешифрованное.

 

 

4.3.2 Алгоритмы и функции.

 

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

Использование метода  симметричного кодирования  с ключом была использована пошаговая  подстановка индексов ключа к  индексам входного сообщения. Дальнейшие действия по шифрованию и дешифрованию эквивалентны методам, описанным в  теоретической части.

 

 

 

• Описание функций программы.

Программа состоит из нескольких функций, которые вызываются в главной  функции main(). Далее представлены эти функции:

• ABCFeling- модуль заполнения латинского алфавита.
• SimpleCh- модуль заполнения массива простых чисел от 2-100.
• GetClue- модуль получения ключа для ассиметричного шифрования.
• Shifrovanie- модуль симметричного шифрования с ключом.
• Deshifrovanie- модуль дешифрования.
• RSA- модуль асимметричного  шифрования по методу RSA.

 

Модули ABCFeling и SimpleCh являются модулями заполнения , и не требуют описания.

 

 

 

 

 

• Описание модулей симметричного шифрования.

 

Симметричное  шифрование с ключом происходит в 2 этапа:

1. Шифрование  входного сообщения.

2. Дешифрование  полученного шифра.

• Модуль Getclue.

 

Данный  модуль предназначен для получения  ключа.

void GetClue(int C[],int n,struct alphabet ABC[])

{

  

  Вводим ключ;

   for(i=0;i<длина ключа; i++)

   { 

 Распознаем символы  ключа;

 Придаем им соответствующие  индексы;

   }

 

 

 

• Модуль Shifrovanie.

 

Данный модуль служит для преобразования входного  сообщения в шифр.

void Shifrovanie(struct alphabet STR[],int n, int C[],int nc,struct alphabet ABC[])

{

 

  for(i=0;i<кол-во символов;i++)

  {

  Суммируем индексы  символов входной строки с  индексом ключа;

  if(сумма индексов больше 26) начать нумерацию сначала;  

 

  for(int e=0;e<26;e++)

  распознавание символов  по  новым индексам;

  if(подошли к концу ключа) начать ключ заново;

  }

    Вывод на экран шифрованного сообщения;

}

 

• Модуль Deshifrovanie.

 

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

 

void Deshifrovanie(struct alphabet STR[],int n, int C[],int nc,struct alphabet ABC[])

{

 

  for(i=0;i<кол-во символов;i++)

  {

  Вычитаем индексы символов  ключа из индексов символов  шифра;

  if(вышли за рамки алфавита) начать нумерацию заново;

 

  for(int e=0;e<26;e++)

  распознавание символов  по индексам;

 

  if(подошли к концу ключа) начать ключ заново;

  }

       Вывод  на экран дешифрованного сообщения;

}

 

 

 

• Описание модуля асимметричного шифрования.

 

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

void RSA(int M,int C,int C1,int r)

{

 

for(int i=0;i<ключ 1;i++)

{

Возводим в степень  ключа 1 и получаем остаток от деления  на  r;

}

     Вывод на  экран шифрованного сообщения; 

 

for(int i=0;i<ключ 2;i++)

{

  Возводим в степень  ключа 2 и получаем остаток  от деления;

}

Вывод на экран дешифрованного сообщения;

 

}

 

• Описание главного модуля main().

 

В этом модуле происходит  ввод входных данных  и пошаговый вызов модулей, описанных  выше.

int _tmain(int argc, _TCHAR* argv[])

{

Алфавит ABC[26];

наша строка символов STR[50]; 

кол во символов в вводимой строке n;

кол-во символов в ключе nc;

число p1;

значение r;

значение эйлеровой функции  f;

открытый и закрытый ключ- a и alp;

 

заполнение алфавита ABCFeling(..);

 

       заполнили  массив простых чисел от 2-100 SimpleCh(..);

Ввод р1;

for(int i=2; i<кол-во эл-тов;i++)

  { 

 if(флаг поднят) break;

 считаем r;

              считаем f;

for(int j=0;j< кол-во эл-тов;j++)

 if(флаг поднят) break;

else

for(int e=0;e< кол-во эл-тов;e++)

    if(остаток от деления произведение a на alpha на f==1 )

      {

Нашли a и alpha;            Вывод на экран их;                                  поднять флаг;

break;

   

      }

  }

 Ввод сообщения для шифрования;

        Вызов  метода шифрования RSA(..);

 

 

Ввод сообщения;

 

for( i=0;i<длина сообщения;i++)

{

 Присвоить индексы  каждому символу;

}

Ввод ключа;

 

    получение ключа GetClue(..);

    функция шифрование входной строки Shifrovanie(..);

    функция дешифровки Deshifrovanie(..);

 

return 0;

}

 

 

4.3.3 Тестирование.

 

 

RSA:

Входное значение Р1:9

Сообщение:8.

 

Симметричное  шифрование с ключом.

 

Сообщение	abbcdaaddcabbacdbb
Ключ	kod

 

 

 

Результат работы программы приведен на рисунке

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Заключение.

 

В ходе курсового  проекта по дисциплине «Теория информации и кодирования» были изучены информационные характеристики дискретных случайных  величин, методы оптимального кодирования, основные методы и виды помехоустойчивого  кодирования, а также были изучены  базовые методы по шифрованию данных. Кроме того все выше перечисленные  теоретические знания были программно реализованы на ЭВМ.  Для программной  реализации курсового проекта была использована система программирования Microsoft Visual Studio 2010 и язык программирования С/С++.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение 1. Листинг tik_lab1.

#include "stdio.h"

#include "conio.h"

#include "string.h"

#include "math.h"

 

int main()

{

char a[]="abcaaaaabbacbaacccabaccbbaccbbddadd";

char b[]="bcaddcdbabbbacbbddcbbaccbbdbdadacc";

int i,j;//переменные для перебора 

int ch,ch1,ch2;//переменные для  перебора символа а-д

int c;//переменные для подсчета

double entX=0,//h(x)

           entY=0,//h(y)

           entXlY=0,//h(x/y)

           entYlX=0,//h(y/x)

           entXY=0,//h(x,y)

           temp;//хз=)

double verX[4],//вер букв а-д  в Х

           verY[4],//вер букв а-д в У

           verXY[4][4],//вер отн Х/У

           verYX[4][4];//вер отн У/Х

int cX[4],cY[4],cXY[4][4];//колва букв  а-д в Х,У и Х/У

puts("Veroyatnosti");

printf("     X     Y     \n");

//перебирается буква а-д

for (ch=0;ch<=3;ch++) {

printf("%c    ",(char)('a'+ch));

c=0;

for (i=0;i<=strlen(a);i++)//перебираются  всё собщ и сравн с букв

if (a[i]==('a'+ch)) c++;//увелич колв

cX[ch]=c;//пишем ей в массив  для тек буквы

        verX[ch]=(double)c/strlen(a);//вычисл вер

printf("%.3f ",verX[ch]);

entX+=-verX[ch]*log(verX[ch])/log(2.0);//считаем энтропию

//ниже аналогично с  У

c=0;

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

if (b[i]==('a'+ch)) c++;

cY[ch]=c;

verY[ch]=(double)c/strlen(b);

printf("%.3f \n",verY[ch]);

entY+=-verY[ch]*log(verY[ch])/log(2.0);

}

printf("\nEntropiya X %.3f",entX);

printf("\nEntropiya Y %.3f",entY);

    puts("\n\nUslovnoe kolvo");

printf("X|Y  a     b     c     d     \n");

for (ch1=0;ch1<=3;ch1++) {//перебираем  первую букву(строчку)

printf("%c    ",(char)('a'+ch1));//перебираем  вторую букву(столбец)

for (ch2=0;ch2<=3;ch2++) { 

int c=0;

for (i=0;i<=strlen(a);i++) {//двигаемся  по сооб

if (a[i]==('a'+ch1)&&b[i]==('a'+ch2)) c++;//если  в Х- первая буква, а в  У-вторая считаем

}

cXY[ch1][ch2]=c;//пишем