Дисциплины:
Краткое описание алгоритмов
Новосибирск, 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;
}