Системы с открытым ключом: алгоритм шифрования RSA
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
{
comp a, b, M, u, Cp, Cq, Bmp;= crt (cipher, prime1);
b = crt (cipher, prime2);
u = inverse (prime2, prime1);= (unsigned long) prime1;
Cq = (unsigned long) prime2;= b%Cp;(a >= Bmp)
M=(((a-Bmp)*u)%Cp)*Cq+b;
else
M=(((a+Cp-Bmp)*u)%Cp)*Cq+b;M.lo();
}
unsigned long crt (unsigned long c, unsigned int m)
{
unsigned long dmm;
unsigned int i;
unsigned long res=1, cmm;= c%m;
dmm = (unsigned long) (m-1);
dmm = priv_exp%dmm;(i=0; i<dmm; i++) {
res*=cmm%m;
if (res>=m) res %= m;
}res;
}
/*************************************** MATH.CPP *************************************/
#include
#include
#include
/**************************************/
/************* Prototypes *************/
/**************************************/long inverse(unsigned int x, unsigned long iModulus);get_primes(unsigned int *p1, unsigned int *p2);get_exponents(unsigned int *pbe, unsigned long *pve);
/**************************************/
/********** Function bodies ***********/
/**************************************/
int iter;inv (unsigned int x, unsigned long n, unsigned long *a, unsigned long *b)
{
unsigned long q, r, t;
q = n/x;
r = n%x;(r==1) { *b=q; *a=1; }
else {
inv(r, x, a, b);
iter++;= *a;
*a = *b;
*b = t+q*(*b);
}
}
unsigned long inverse (unsigned int x, unsigned long n)
{
unsigned long a,b;=0;
inv (x, n, &a, &b);
if (iter%2==0) return n-b; else return b;
}
unsigned long rnd(unsigned long upto)
{
unsigned long t=time(NULL);=t*rand();
return t%upto;
}
#define MaxE 32767get_primes(unsigned int *p1, unsigned int *p2)
{
char *c;
unsigned long i=1, j, k;=(char *)malloc(MaxE+1);
if (c==NULL) {
cout<<"Error: Out of memory!\n";
exit(1);
};
memset (c, 0, MaxE);
while (i<MaxE) {
for(j=3;(k=(j*(2*i+1)-1)/2)<MaxE;j+=2) *(c+k)=1;
i++;
while ((i<MaxE) && *(c+i)) i++;
}
while (((i=rnd(MaxE))<MaxE/2) || *(c+i));
*p1=2*i+1;
j=i;
while (((i=rnd(MaxE))<MaxE/2) || *(c+i) || (i==j));
*p2=2*i+1;(c);
}
void get_exponents(unsigned int *pbe, unsigned long *pve)
{
unsigned int n=random(10);{
n=random(10);
*pbe=n*n-n+41;
} while ((phi%*pbe)==0);
*pve=inverse(*pbe, phi);
}
/********************************* COMP.CPP *********************************/comp
{
unsigned long a,b; /* a-high, b-lower */:
comp(unsigned long lo=0, unsigned long hi=0);&operator =(comp c);
comp &operator =(unsigned long c);
comp operator +(comp c);
comp operator +(unsigned long l);
comp operator -(comp c);
comp operator *(comp c);
comp operator /(comp c);
comp operator %(comp c);
comp operator <<(int i);
int operator >(comp c);
int operator >=(comp c);
int operator ==(unsigned long l);
int operator ==(comp c);long lo(void);
unsigned long hi(void);
/*private:*/
void set1(int where);
int is1(int where);
int pow(void);
};
/**** Results of the last division op ****/
comp lastdiv, lastmod;
comp::comp(unsigned long lo, unsigned long hi)
{
a=hi;
b=lo;
}
comp &comp::operator =(comp c)
{
a=c.a; b=c.b;
return (*this);
}
comp &comp::operator =(unsigned long c)
{
a=0; b=c;
return (*this);
}
comp comp::operator +(comp c)
{
comp res;
int i;
int was, is;
unsigned long l;
res=*this;=b&(1ul<<31);
for (i=0;i<=31;i++) {
res.b+=c.b & (1ul<<i);
is=(res.b & (1ul<<31))!=0;
if (was && !is) res.a++;
was=is;
}
res.a+=c.a;
return res;
}
comp comp::operator +(unsigned long l)
{
comp t=l;*this+t;
}
comp comp::operator -(comp c)
{
comp res;
if (a<c.a || (a==c.a && b<c.b))
res=0;
else if (a>=c.a && b>=c.b) {
res.a=a-c.a;
res.b=b-c.b;
}
else {
res.b=(0xffffffff)-(c.b-b)+1;
res.a=a-c.a-1;
}
return res;
}
comp comp::operator *(comp c)
{
comp res=0;
int i, llen;=c.pow();
for(i=0;i<=llen;i++)
if (c.is1(i)) res=res+(*this<<i);res;
}
comp comp::operator /(comp t)
{
comp th, r, result=0, rt;
int s1, s2;=pow(); s2=t.pow();
if (s1<s2) {
lastdiv=0l;
lastmod=*this;
return 0;
}=*this;
while (s1>s2) {
r=0;
r.set1(s1-s2);
if(th>=(rt=r*t)) th=th-rt; else {r=0; r.set1(s1-s2-1); th=th-r*t;}
result=result+r;
s1=th.pow();
}(s1==s2 && th>=t) {
result=result+1l;
th=th-t;
}=result;
lastmod=th;
return result;
}
comp comp::operator %(comp c)
{
*this/c;
return lastmod;
}
void comp::set1(int where)
{
unsigned long *l;(where>31) {
l=&a;
where-=32;
}
else l=&b;
*l=*l|(1l<<where);
}comp::pow(void)
{
int i,j;
unsigned long *l;(a==0) {
l=&b;
j=0;
}
else {
l=&a;
j=32;
}(*l==0) return 0;
for (i=31;!(*l>>i);i--);
return i+j;
}
comp comp::operator <<(int i)
{
comp t=*this;(;i>0;i--) {
t.a=(t.a)<<1;
if(t.b & (1ul<<31)) (t.a)++;
t.b=(t.b)<<1;
}t;
}
int comp::operator >(comp c)
{
comp t=*this-c;
return (t.a!=0) || (t.b!=0);
}
int comp::operator >=(comp c)
{
return (*this==c) || (*this>c);
}
int comp::is1(int where)
{
unsigned long *l;
unsigned long res;
if (where>31) {where-=32; l=&a; }
else l=&b;
res = *l & (1ul<<(unsigned long)where);
return res!=0;
}
int comp::operator ==(unsigned long l)
{
return ((a==0) && (b==l));
}
int comp::operator ==(comp c)
{
return ((a==c.a) && (b==c.b));
}
unsigned long comp::lo(void)
{
return b;
}
unsigned long comp::hi(void)
{
return a;
}
Литература
1.Баричев С., Криптография без секретов
2.Е.Бубнова, Системы с открытым ключом: алгоритм дешифрования RSA
.RSA Laboratories, Frequently Asked Questions About Todays Cryptography, 1995
.Д.Сяо, Д. Керр, С.Мэдник, Защита ЭВМ
.Л.Дж.Хоффман, Современные методы защиты информации
.James Nechvatal, Public key cryptography, 1991
.Chris K.Caldwell, Finding Primes and proving primality