Главная Обратная связь

Дисциплины:






Краткое описание алгоритмов



Новосибирск, 2014г.

 


 

Оглавление

Задание на курсовую работу. 3

Краткое описание алгоритмов. 4

Программная реализация на языке C++. 6

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

 

 

 

Задание на курсовую работу

Номер варианта k определяется по формуле: k=N mod 3, где N – номер студента в журнале.

 

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

 

k Метод
Шифр Шамира

 

2. Программно реализовать на языке C++ алгоритм электронной подписи сообщения и проверки его подлинности c помощью метода:

 

k Метод
Электронная подпись RSA

 

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

 

 

Краткое описание алгоритмов

1.Шифр Шамира

Пусть есть два абонента А и В, соединенные линией связи. А хочет передать сообщение m абоненту В так, чтобы никто не узнал его содержание. А выбирает случайное большое простое число р и открыто передает его В. Затем А выбирает два числа сА и dА, такие, что сАdА mod (p-1) = 1. Эти числа А держит в секрете и передавать не будет. В тоже выбирает два числа cВ и dВ, такие, что cВdВ mod (p-1) = 1 и держит их в секрете.

После этого А передает свое сообщение m, используя трехступенчатый протокол. Если m<p (m рассматривается как число), то сообщение m передается сразу, если же m>=p, то сообщение представляется в виде m1, m2 … , mt, где все mi<p, и затем передаются последовательно m1, m2 … , mt.. При этом для кодирования каждого mi лучше выбирать случайно новые пары (сА ,dА) и (cВ,dВ) – в противном случае надежность системы понижается. Мы будем рассматривать случай m<p.

 

Шаг1. А вычисляет число

х1 = mcA mod p, где m – исходное сообщение, и пересылает х1 к В.

Шаг2. В, получив х1, вычисляет число

x2 = х1cB mod p и передает х2 к А.

Шаг3. А вычисляет число

х3 = х2dA mod p и передает его В.

Шаг4. В, получив х3, вычисляет число

х4 = х3dB mod p.

 

 

2.Электронная подпись RSA.

А хочет подписать сообщение m. Для этого А выбирает два больших простых числа P и Q, вычисляет N=PQ и pr=(P-1)(Q-1). Затем А выбирает число pb, взаимно простое с pr, и вычисляет c=pb-1 mod pr. Где pr-приватное число, а pb-публичное число.

Дальше А вычисляет число

s=yc mod N, число s и есть электронная подпись.

Чтобы проверить подлинность подписи нужно сравнить сообщение m с числом w=spb mod N:

w= spb mod N= yc*pb mod N = m.

 

 



3.RC4.

Алгоритм RC4 работает с n-битовыми словами. Все вычисления проводятся по модулю 2n. RC4 использует L-словный ключ К =K0K1...Kl-1 и генерирует последовательность слов Z = Z1Z2Z3... , конкретный вид которой определяется ключом К. Состояние генератора задается таблицей S из 2n слов и двух переменных i и j. В каждый момент времени таблица S содержит все возможные n-битовые числа в перемешанном виде. Секретный ключ задает только начальное перемешивание чисел в таблице, которое формируется с помощью следующего алгоритма:

 

j ← 0, S ← (0,1,... 2n — 1);

FOR i = 0,1,... ,2n - 1 DO

j ← (j + Si + Kx mod L) mod 2n,
Sj ↔ Si;

i ← 0, j ← 0.

 

После этого генератор готов к работе. Генерация очередного псевдослучайного слова zi, осуществляется следующим образом:

i ← (i+ 1) mod 2n;
J ← (j + Si) mod 2n;

Sj ↔ Si;

t← (Sj + Si) mod 2n;

zi ← St.

 

 

Программная реализация на языке C++

#include<iostream>

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<math.h>

#include<sstream>

#include<fstream>

#include<cstdlib>

#include<time.h>

 

using namespace std;

 

//функция быстрого возведения в степень по модулю

long long int vozv(long long int a,long long int x,long long int p)

{

long long int r=1;

while (x!=0)

{

if(x%2==0)

{

a=(a*a)%p;

x=x/2;

}

else

{

x--;

r=(r*a)%p;

}

}

 

return r;

}

 

// функция выполняющая обобщенный алгоритм Эвклида(возвращает значение НОД)

long long int ev(long long int a,long long int b)

{

long long int temp;

 

if (a<b)

{

temp=a;

a=b;

b=temp;

}

 

long long int c, NOD;

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

long long int x,y,xr,yr;

 

while(b>0)

{

c=a/b;

NOD=a-b*c;

if (NOD!=0)

{

xr=x1-c*x2;

yr=y1-c*y2;

x1=x2;

y1=y2;

x2=xr;

y2=yr;

a=b;

b=NOD;

}

else

{

NOD=b;

break;

}

}

return NOD;

}

 

// функция выполняющая обобщенный алгоритм Эвклида(возвращает значение y)

long long int evy(long long int a, long long int b)

{

int temp;

 

if (a<b)

{

temp=a;

a=b;

b=temp;

}

 

long long int c, NOD;

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

long long int x,y,xr,yr;

 

while(b>0)

{

c=a/b;

NOD=a-b*c;

if (NOD!=0)

{

xr=x1-c*x2;

yr=y1-c*y2;

x1=x2;

y1=y2;

x2=xr;

y2=yr;

a=b;

b=NOD;

}

else

{

NOD=b;

break;

}

}

return yr;

}

 

//функция выполняющая шифр Шамира

long long int SHAMIR(int m, int Ca, int Cb, int Da, int Db, int p)

{

long long int x1,x2,x3,x4;

 

x1=vozv(m,Ca,p);

cout<<"x1="<<x1;

x2=vozv(x1,Cb,p);

cout<<" x2="<<x2;

x3=vozv(x2,Da,p);

cout<<" x3="<<x3;

x4=vozv(x3,Db,p);

cout<<" x4="<<x4<<endl;

if (m==x4)

{

cout<<"Абонент В получил сообщение m"<<endl;

return x4;

}

else

cout<<"Error"<<endl;

}

 

// функция выполняющая шифр RSA

long long int RSA (long long int m, long long int c, long long int d,long long int N)

{

long long int s,w;

 

s=vozv(m,c,N);

w=vozv(s,d,N);

 

cout<<"m="<<m<<endl<<"s="<<s<<endl<<"w="<<w<<endl;

if (w==m)

{

cout<<"подпись подлинная"<<endl;

return w;

}

else

cout<<"Error"<<endl;

}

 

 

int Kimodl(int i, int k, int l){ //разбиение ключа на числа

int x;

x=i%l;

i=l-x;

while(i!=1){

k=k/10;

i--;

}

return k%10;

}

 

 

int main()

{

srand(time(0)); // связывает функцию rand() с системным временем

int Ch;

setlocale(0,"rus");

 

cout<<"1. Шифр Шамира"<<endl;

cout<<"2. Электронная подпись RSA"<<endl;

cout<<"3. RC4"<<endl;

cout<<"4. Завершить программу"<<endl;

cout<<"\nВыберите действие:";

cin>>Ch;

 

 

while (Ch!=4)

{

if (Ch==1)

{

cout<<"\n1. Шифр Шамира"<<endl;

long long int m,Ca,Cb,Da,Db,p;

p=2147483647;

 

fstream F; //Объявляем файловый поток

F.open("Shamir.txt",ios::in); //открываем файл Shamir.txt для чтения

F>>m; // Считываем информацию из файла в переменную m

cout<<"m="<<m<<endl;

 

Ca=rand();

while(ev(Ca,(p-1))!=1) //Находим Ca взаимно простое с (p-1)

Ca=rand();

 

Da=evy(Ca,(p-1));

if(Da<0) //с помощью ev находим Da

Da=Da+(p-1);

int rez1=(Ca*Da)%(p-1);

cout<<"(Ca*Da)mod(p-1)="<<rez1<<endl;

 

Cb=rand();

while(ev(Cb,(p-1))!=1)

Cb=rand();

 

Db=evy(Cb,(p-1));

if(Db<0)

Db=Db+(p-1);

int rez2=(Cb*Db)%(p-1);

cout<<"(Cb*Db)mod(p-1)="<<rez2<<endl;

 

cout<<"Ca="<<Ca<<endl;

cout<<"Cb="<<Cb<<endl;

cout<<"Da="<<Da<<endl;

cout<<"Db="<<Db<<endl;

 

SHAMIR(m,Ca,Da,Cb,Db,p);

}

else

if (Ch==2)

{

cout<<"\n2. Электронная подпись RSA"<<endl;

long long int p,q,pb,c,m;

p=18181;

q=115249;

 

fstream F;

F.open("RSA.txt",ios::in);

F>>m;

 

long long int N=(p*q);

long long int pr=(p-1)*(q-1);

 

pb=rand();

while(ev(pb,pr)!=1)

pb=rand();

 

c=evy(pb,pr);

if(c<0)

c=c+pr;

int rez1=(c*pb)%pr;

cout<<"(c*pb) mod pr="<<rez1<<endl;

 

RSA(m,c,pb,N);

}

else

if (Ch==3)

{

cout<<"\n3. RC4"<<endl;

int j=0, i, n, l=0, Slength=1, k, kl, t;

char x;

 

n=3;

 

cout<<"K="; //вводим ключ

cin>>k;

 

kl=k;

while (kl!=0){ //определяем l-длину ключа

kl=kl/10;

l++;

}

cout<<"l="<<l<<endl;

cout<<endl;

 

for(i=0;i<n;i++){

Slength=Slength*2; //высчитываем 2^n

}

 

int S[Slength]; //создаем генератор по ключу

int z[Slength]; //создаем генератор псевдослучайной последовательности

 

cout<<" "<<"j="<<j<<" "<<"S = ";

for(i=0;i<Slength;i++){

S[i]=i;

cout<<S[i]<<" ";

}

 

for(i=0;i<Slength;i++){ //алгоритм генератора по ключу

cout<<endl;

j=(j+S[i]+Kimodl(i,k,l))%Slength;

x=S[j];

S[j]=S[i];

S[i]=x;

cout<<"i="<<i<<" "<<"j="<<j<<" "<<"S = ";

for(int is=0;is<Slength;is++) cout<<S[is]<<" ";

}

 

i=0;

j=0;

 

FILE *f;

FILE *f1;

 

f=fopen("input.txt","rb");

f1=fopen("crypt.txt","wb");

 

cout<<endl;

cout<<endl;

 

while(true){ //чтение сообщение из файла и шифрование по Zi

i=(i+1)%Slength;

j=(j+S[i])%Slength;

x=S[j];

S[j]=S[i];

S[i]=x;

t=(S[i]+S[j])%Slength;

z[i]=S[t];

 

cout<<"i="<<i<<" "<<"j="<<j<<" "<<"S = ";

for(int is=0;is<Slength;is++) cout<<S[is]<<" ";

cout<<"z="<<z[i]<<endl;

 

x=fgetc(f);

x=x^z[i];

if (feof(f)) break;

fprintf(f1, "%c", x);

}

 

fclose(f);

fclose(f1);

 

f=fopen("crypt.txt","rb");

f1=fopen("decrypt.txt","wb");

 

i=0;

j=0;

 

while(true){ //дешифрование сообщения по Zi

i=(i+1)%Slength;

x=fgetc(f);

x=x^z[i];

if (feof(f)) break;

fprintf(f1, "%c", x);

}

}

cout<<"\nВыберите действие:";

cin>>Ch;

}

system("pause");

return 0;

}

 





sdamzavas.net - 2020 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...