Системы с открытым ключом: алгоритм шифрования RSA
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
nbsp;
Пусть u >, тогда
Единственность
Пусть
Следовательно,
Отсюда окончательно имеем
Наконец, последняя теорема доказывает корректность самого алгоритма.
Теорема
При соответствующем условиям алгоритма выборе e и d,
Обозначим это выражение за (*).
Если m взаимно просто с n, то по теореме Эйлера что и требовалось. В противном случае либо m=tp, либо m=tq, так как у n нет других делителей; без ограничения общности будем предполагать m=tp. При этом t необходимо меньше q, так как m<n=pq
.
Но (т. Эйлера); следовательно, это равно
(+)
Найдем r. Выражение (+) на самом деле означает, что t*p*тАж*p = Apq+r. Так как это равенство в целых числах, то отсюда следует, что r делится на p. То есть, t*p*тАж*p=Aq+r/p=r1;
Теперь т.к. по т.Эйлера .
Следовательно, (*)=r=tp=m и в этом случае.
Комментарии к программе
В качестве иллюстрации предлагается реализация алгоритма RSA с длиной модуля 32 бита. В программе используются настоящие простые числа, генерируемые с помощью решета Эратосфена. Для возведения в степень при шифровании используется последовательное возведение в квадрат; при дешифровании - Китайская теорема об остатках. В программе реализован аппарат длинной 64-битной арифметики.
Текст программы
#include
#include
#include
#include
#include "compcl.cpp"
/*************************************/
/** The following global variables **/
/** are required for all encryption **/
/** and decryption operations. **/
/*************************************/
/* The modulus */long modulus=0;
/* The primes; n=pq */int prime1=0, prime2=0;
/* The public exponent */int pub_exp=0;
/* The private exponent */long priv_exp;
/* The Euler Phi = (p-1)(q-1) */
unsigned long phi=0;
#include "math.cpp"
/*************************************/
/** RSA functions follow. **/
/*************************************/
/* Generate the keys for the first time*/
void InitRSA(void);
/* Initialize RSA for encryption */InitRSAe(unsigned int apub_exp, unsigned long amodulus);
/* Initialize RSA for decryption */InitRSAd (unsigned int aprime1, unsigned int aprime2, comp apriv_exp);
/* Encrypt one LONG of data */
unsigned long encrypt (unsigned long data);
/* Decrypt one LONG of ciphertext */
unsigned long decrypt (unsigned long cipher);
/*************************************/
/** Hehe - the actual function **/
/** instances follow **/
/*************************************/InitRSA(void)
{
get_primes(&prime1,&prime2);
modulus=((unsigned long)prime1)*((unsigned long)prime2);
phi=((unsigned long)(prime1-1))*((unsigned long)(prime2-1));
get_exponents(&pub_exp, &priv_exp);
}
void InitRSAe(unsigned int apub_exp, unsigned long amodulus)
{
modulus=amodulus; pub_exp=apub_exp;
}
void InitRSAd (unsigned int aprime1, unsigned int aprime2, unsigned long apriv_exp)
{
prime1=aprime1; prime2=aprime2;
phi=((unsigned long)prime1-1)*((unsigned long)prime2-1);
modulus=(unsigned long)prime1*(unsigned long)prime2;
priv_exp=apriv_exp;
}
#include "encr.cpp"ErrCommand(char *Msg)
{
cout << "Error: ";
cout << Msg;
cout << "\n";
exit(1);
}
/************************************************************/
/************************** M A I N *************************/
/****************888***********************888***************/main()
{
char name[128];
FILE *f, *fi, *fo;
time_t st=time(NULL);int i, j;
unsigned long l;
cout << "\nRSA implementation (c) 1997 M.Skulsky & K.Bubnova.\n";
cout << "Special thanks to Rivest, Shamir, Aldeman for their invaluable help, to\n";
cout << "Euclid, Euler, Fermat and Galois for having provided a bunch of very useful\n";
cout << "theorems and to V.N. Shevchenko for having made us able to understand them.\n\n";
switch (_argc) {
case 4:
case 2:
case 1:
cout \n";
cout << " - for encryption\n";
cout that you specify.\n";
exit(0);
case 3:
if (strcmp(strlwr(_argv[1]),"-k")) ErrCommand("Command not recognized.\n");();(name, _argv[2]);(name, ".pbk");=fopen(name, "wb");(f==NULL) ErrCommand("Invalid path.");(&modulus, sizeof(modulus), 1, f);(&pub_exp, sizeof(pub_exp), 1, f);(f);(name, _argv[2]);(name, ".pvk");=fopen(name, "wb");(&prime1, sizeof(prime1), 1, f);(&prime2, sizeof(prime2), 1, f);(&priv_exp, sizeof(priv_exp), 1, f);(f);<< "Private and public keys successfully created.\n";
break;5:
if (!strcmp(strlwr(_argv[1]),"-e")) { /* encrypting */
f=fopen (_argv[4], "rb");
if (f==NULL) ErrCommand ("Can't open public key!");
fread (&l, sizeof(l), 1, f);
fread (&i, sizeof(i), 1, f);
fclose(f);
InitRSAe (i, l);((fi = fopen(_argv[2], "rb"))==NULL)
ErrCommand ("Can't open plaintext file!");
if ((fo = fopen(_argv[3], "wb"))==NULL)
ErrCommand ("Can't create ciphertext file!");=0;
while (!feof(fi)) {
l=0;
i=fread (&l, 1, 3, fi);
if (i==0) break;
l=encrypt(l);
fwrite (&l, 1, sizeof (long), fo);
if (j++==50) {j=0; cout << "+"; }
} /* while */
printf ("\n");
fclose (fi);
fclose (fo);
printf ("Successfully encrypted %s\n", _argv[2]);
break;
}if (!strcmp(strlwr(_argv[1]),"-d")) { /* decrypting */
f=fopen (_argv[4], "rb");
if (f==NULL) ErrCommand ("Can't open private key!");
fread (&i, sizeof(i), 1, f);
fread (&j, sizeof(j), 1, f);
fread (&l, sizeof(l), 1, f);
fclose(f);
InitRSAd (i, j, l);((fi = fopen(_argv[2], "rb"))==NULL)
ErrCommand ("Can't open ciphertext file!");
if ((fo = fopen(_argv[3], "wb"))==NULL)
ErrCommand ("Can't create plaintext file!");
j=0;
while (!feof(fi)) {
i=fread (&l, 1, sizeof (long), fi);
if (i==0) break;
if (i==sizeof(long)) {
l=decrypt(l);
fwrite (&l, 1, 3, fo);
}
else /* unexpected end of file encountered */
ErrCommand ("Broken ciphertext!");
if (j++==50) {j=0; cout <<"+";}
} /* while */
printf ("\n");(fi);
fclose (fo);
printf ("Successfully decrypted %s\n", _argv[2]);
break;
} else ErrCommand("Command not recognized.\n");
}; /* switch */
st = time(NULL)-st;
printf ("Time running: %lu seconds.\n", st);
}
/************************ ENCR.CPP ************************/
/************ This file contains the encryption **************/
/*************** and decryption procedures *******************/
/************************************************************/
unsigned long encrypt (unsigned long data)
{
comp c, res, cmod;
int i;=modulus;
c=data;
c=(c*c)%cmod;
res=c;
for (i=1; i<pub_exp/2; i++)
res = (res*c)%cmod;=data;
res=(res*c)%cmod;
return res.lo();
}
unsigned long crt (unsigned long c, unsigned int m);long decrypt (unsigned long cipher)