RSA算法
1、公钥密码*的概念由Diffie和Hellman于1976年提出，用于解决对称密码*中**分配的问题。在公钥密码*中，**被分为公钥与私钥，公钥是公开的，用于加密；私钥是保密的，用于解密。经过四十余年的研究发展，RSA密码、ElGamal密码、椭圆曲线密码等等公钥密码*在商业、军事上都已经得到了广泛的应用。
2、RSA密码由R. Rivest、A. Shamir和L. Adleman于1977年提出，是最著名的公钥密码，能够抵抗到目前为止已知的绝大多数密码攻击，已被ISO推荐为公钥数据加密标准。RSA密码的安全性基于这样一个事实：将两个大素数p,q相乘十分容易，但对其乘积N=pq作因子分解却极其困难。在本实验中，假设p,q均为len比特素数，具体描述如下：
系统参数
大素数p、q：len比特素数（即 且p、q为素数）
乘积N：N = p*q，约为2*len比特
N的欧拉函数值：
公钥
(N,e)：其中e满足1<e<且gcd (e, ) = 1
私钥
(N,d)：其中d满足1<d<且，即
明文
正整数m：满足1<m<N-1
加密
密文
解密
密文
RSA**生成
- 生成指定bit数的大素数p,q，步骤如下：
1)生成指定bit数的随机奇数A
2)利用MillerRabin素性检测算法判断A是否为素数，若通
过，令p=A，否则返回1)继续做，直到通过为止
3)利用同样的方法生成q
单次MillerRabin素性检测算法：
要测试N是否为素数，首先将N-1分解成
再随机选择，若对所有的，都有
则N是合数，否则，有不小于3/4的概率是素数。
多次MillerRabin素性检测算法：
循环调用单次MillerRabin素性检测算法，若调用次数为loop，则合数通过素性测试(即该算法错误概率)将不超过(1/4)^loop，本次实验中，建议loop取20即可。
参考代码：
1 #include <iostream> 2 #include <time.h> 3 #include <stdlib.h> 4 #include <unistd.h> 5 #include <math.h> 6 7 #define SIZE 68 8 #define MIN 0 9 #define MAX 255 10 11 using namespace std; 12 13 typedef struct Bigint 14 { 15 unsigned char num[SIZE]; 16 }Bigint; 17 18 typedef struct Bigint2 19 { 20 unsigned char num[2*SIZE]; 21 }bigint2; 22 23 Bigint BigRand(int bytes);//随机生成一个bit为8*bytes的数 24 Bigint BigRand(Bigint n);//生成1到n之间的随机数 25 void Print(Bigint a);//输出Bigint a 26 void Print(Bigint2 a);//输出Bigint2 a 27 int Compare(Bigint a,Bigint b);//比较a，b大小 28 int Compare(Bigint2 a,Bigint2 b);//比较a，b大小 29 Bigint ByteMoveLeft(Bigint a,int n);//将a扩大n*256倍后输出 30 Bigint2 ByteMoveLeft(Bigint2 a,int n);//将a扩大n*256倍后输出 31 void BitMoveRight(Bigint &a);//缩小一个比特(2倍) 32 Bigint Add(Bigint a,Bigint b);//Bigint a与b相加 33 Bigint Sub(Bigint a,Bigint b);//Bigint a-b 34 Bigint2 Sub(Bigint2 a,Bigint2 b);//Bigint2 a-b 35 Bigint2 Mul(Bigint a,Bigint b);//a*b 36 Bigint Div(Bigint a,Bigint b);//Bigint a/b 37 void Print10(Bigint a);//以10进制输出Bigint a 38 void Print10(Bigint2 a);//以10进制数处Bigint2 a 39 int Length(Bigint a);//输出a的长度 40 int Length(Bigint2 a); 41 Bigint2 Mod(Bigint2 a, Bigint2 b); // 求余: 输入a,b, 返回 a % b 42 Bigint Mod(Bigint a, Bigint b);// 求余: 输入a,b, 返回 a % b 43 void Copy(Bigint &a, Bigint b);//复制 44 Bigint2 Extend(Bigint a);//扩充数组 45 Bigint Narrow(Bigint2 a);//截断数组 46 Bigint AddMod(Bigint a,Bigint b,Bigint n);//计算(a+b)mod n 47 Bigint SubMod(Bigint a,Bigint b,Bigint n);//计算(a-b)mod n(a>b) 48 Bigint Sub2Mod(Bigint a,Bigint b,Bigint n);//计算(a-b)mod n 49 Bigint MulMod(Bigint a,Bigint b,Bigint n);//计算(a*b)mod n 50 Bigint PowMod(Bigint a,Bigint b,Bigint n);//计算(a^b)mod n 51 bool MillerRabinKnl(Bigint &n); //单次检测, 通过返回1, 否则返回0 52 bool MillerRabin(Bigint &n, long loop); //多次素性检测 53 Bigint get1n(int bytes);//随机生成一个长为8*bytes的奇数 54 Bigint Encrypt(Bigint m, Bigint e, Bigint N); //计算c = m^e mod N 55 Bigint Decrypt(Bigint c, Bigint d, Bigint N); //计算m = c^d mod N 56 57 58 59 Bigint BigRand(int bytes)//随机生成一个bit为8*bytes的数 60 { 61 Bigint pq; 62 srand((unsigned)time(NULL)); 63 for(int i=0;i<bytes;i++) 64 { 65 pq.num[i]=(unsigned char)(rand()%(MAX-MIN+1)+MIN); 66 } 67 for(int i=bytes;i<SIZE;i++) 68 pq.num[i]='\0'; 69 return pq; 70 } 71 72 int Length(Bigint a) 73 { 74 int len; 75 for(int i=SIZE-1;i>=0;i--) 76 { 77 if(a.num[i]!='\0') 78 { 79 len=i+1; 80 break; 81 } 82 else 83 len=i; 84 } 85 return len; 86 } 87 88 int Length(Bigint2 a) 89 { 90 int len; 91 for(int i=2*SIZE-1;i>=0;i--) 92 { 93 if(a.num[i]!='\0') 94 { 95 len=i+1; 96 break; 97 } 98 else 99 len=i; 100 } 101 return len; 102 } 103 104 void Copy(Bigint &a,Bigint b) 105 { 106 for(int i=0;i<SIZE;i++) 107 { 108 a.num[i]=b.num[i]; 109 } 110 return; 111 } 112 113 Bigint2 Extend(Bigint a) 114 { 115 Bigint2 b={0}; 116 for(int i=0;i<Length(a);i++) 117 { 118 b.num[i]=a.num[i]; 119 } 120 return b; 121 } 122 123 Bigint Narrow(Bigint2 a) 124 { 125 Bigint b={0}; 126 for(int i=0;i<SIZE;i++) 127 { 128 b.num[i]=a.num[i]; 129 } 130 return b; 131 } 132 133 Bigint BigRand(Bigint n)//生成1到n之间的随机数 134 { 135 Bigint a; 136 int len; 137 srand((unsigned)time(NULL)); 138 len=rand()%(Length(n)-1)+1; 139 a=BigRand(len); 140 while(Compare(a,n)>=0||(Length(a)==1&&(int)a.num[0]==0)) 141 { 142 srand((unsigned)time(NULL)); 143 len=rand()%(Length(n)-1)+1; 144 a=BigRand(len); 145 } 146 return a; 147 } 148 149 void Print(Bigint a)//输出Bigint a; 150 { 151 if(Length(a)==0) 152 cout<<'0'<<endl; 153 else 154 for(int i=Length(a)-1;i>=0;i--) 155 { 156 cout.width(3); 157 cout<<(int)a.num[i]<<','; 158 } 159 cout<<endl; 160 } 161 162 void Print(Bigint2 a)//输出Bigint2 a; 163 { 164 if(Length(a)==0) 165 cout<<'0'<<endl; 166 else 167 for(int i=Length(a)-1;i>=0;i--) 168 { 169 cout.width(3); 170 cout<<(int)a.num[i]<<','; 171 } 172 cout<<endl; 173 } 174 175 int Compare(Bigint a,Bigint b)//比较a与b的大小 176 { 177 int max,len_a,len_b; 178 len_a=Length(a); 179 len_b=Length(b); 180 if(len_a>len_b) 181 return 1; 182 else if(len_a<len_b) 183 return -1; 184 else 185 max=len_a; 186 for(int i=max-1;i>=0;i--) 187 { 188 if(a.num[i]>b.num[i]) 189 return 1; 190 if(a.num[i]<b.num[i]) 191 return -1; 192 } 193 return 0; 194 } 195 196 int Compare(Bigint2 a,Bigint2 b)//比较大小 197 { 198 int max,len_a,len_b; 199 len_a=Length(a); 200 len_b=Length(b); 201 if(len_a>len_b) 202 return 1; 203 else if(len_a<len_b) 204 return -1; 205 else 206 max=len_a; 207 for(int i=max-1;i>=0;i--) 208 { 209 if(a.num[i]>b.num[i]) 210 return 1; 211 if(a.num[i]<b.num[i]) 212 return -1; 213 } 214 return 0; 215 } 216 217 Bigint Add(Bigint a,Bigint b)//Bigint a+b 218 { 219 Bigint c; 220 int Carry=0,temp,i,max; 221 for(int i=0;i<SIZE;i++) 222 { 223 temp=(int)a.num[i]+(int)b.num[i]+Carry; 224 Carry=temp/256; 225 temp=temp%256; 226 c.num[i]=(char)temp; 227 } 228 return c; 229 } 230 231 Bigint Sub(Bigint a,Bigint b)//Bigint a-b 232 { 233 int temp,i,Carry=0,n; 234 Bigint c; 235 n=Compare(a,b); 236 if(n==-1) 237 { 238 cout<<"Subtract error!"<<endl; 239 return a; 240 } 241 else//执行a-b 242 { 243 for(i=0;i<SIZE;i++) 244 { 245 if((int)a.num[i]-Carry>=(int)b.num[i]) 246 { 247 temp=(int)a.num[i]-Carry-(int)b.num[i]; 248 Carry=0; 249 } 250 else 251 { 252 temp=(int)a.num[i]-Carry+256-(int)b.num[i]; 253 Carry=1; 254 } 255 c.num[i]=(unsigned char)temp; 256 } 257 } 258 return c; 259 } 260 261 Bigint2 Sub(Bigint2 a,Bigint2 b)//Bigint2 a-b 262 { 263 int temp,i,Carry=0,n; 264 Bigint2 c; 265 n=Compare(a,b); 266 if(n==-1) 267 { 268 cout<<"Subtract error!"<<endl; 269 return a; 270 } 271 else//执行a-b 272 { 273 for(i=0;i<2*SIZE;i++) 274 { 275 if((int)a.num[i]-Carry>=(int)b.num[i]) 276 { 277 temp=(int)a.num[i]-Carry-(int)b.num[i]; 278 Carry=0; 279 } 280 else 281 { 282 temp=(int)a.num[i]-Carry+256-(int)b.num[i]; 283 Carry=1; 284 } 285 c.num[i]=(unsigned char)temp; 286 } 287 } 288 return c; 289 } 290 291 Bigint2 Mul(Bigint a,Bigint b)//a*b 292 { 293 Bigint2 c={0}; 294 int Carry=0,temp; 295 int i,j; 296 for(i=0;i<SIZE;i++) 297 { 298 for(j=0;j<SIZE;j++) 299 { 300 temp=(int)a.num[i]*(int)b.num[j]+(int)c.num[i+j]+Carry; 301 Carry=temp/256; 302 temp=temp%256; 303 c.num[i+j]=(unsigned char)temp; 304 } 305 } 306 c.num[2*SIZE-1]=(unsigned char)Carry; 307 return c; 308 } 309 310 Bigint ByteMoveLeft(Bigint a,int n)//将a扩大n*256倍后输出 311 { 312 Bigint c={0}; 313 int i; 314 for(i=Length(a)-1;i>=0;i--) 315 { 316 c.num[i+n]=a.num[i]; 317 } 318 for(i=0;i<n;i++) 319 c.num[i]='\0'; 320 return c; 321 } 322 323 Bigint2 ByteMoveLeft(Bigint2 a,int n)//将a扩大n*256倍后输出 324 { 325 Bigint2 c={0}; 326 int i; 327 for(i=Length(a)-1;i>=0;i--) 328 { 329 c.num[i+n]=a.num[i]; 330 } 331 for(i=0;i<n;i++) 332 c.num[i]='\0'; 333 return c; 334 } 335 336 void BitMoveRight(Bigint &a)//缩小一个比特(2倍) 337 { 338 Bigint b={2}; 339 a=Div(a,b); 340 return; 341 } 342 343 Bigint Div(Bigint a,Bigint b)//Bigint a/b 344 { 345 int len; 346 Bigint B={0}; 347 Bigint c={0}; 348 len=Length(a)-Length(b); 349 while(len>=0) 350 { 351 B=ByteMoveLeft(b,len); 352 while(Compare(a,B)>=0) 353 { 354 a=Sub(a,B); 355 c.num[len]++; 356 } 357 len--; 358 } 359 return c; 360 } 361 362 Bigint Mod(Bigint a,Bigint b)//计算Bigint a%b 363 { 364 if(Compare(a,b)<0) 365 return a; 366 else 367 { 368 Bigint B={0}; 369 int len=Length(a)-Length(b); 370 while(len>=0) 371 { 372 B=ByteMoveLeft(b,len); 373 while(Compare(a,B)>=0) 374 { 375 a=Sub(a,B); 376 } 377 len--; 378 } 379 } 380 return a; 381 } 382 383 Bigint2 Mod(Bigint2 a,Bigint2 b)//计算Bigint2 a%b 384 { 385 if(Compare(a,b)<0) 386 return a; 387 else 388 { 389 Bigint2 B={0}; 390 int len=Length(a)-Length(b); 391 while(len>=0) 392 { 393 B=ByteMoveLeft(b,len); 394 while(Compare(a,B)>=0) 395 { 396 a=Sub(a,B); 397 } 398 len--; 399 } 400 } 401 return a; 402 } 403 404 Bigint Mod10(Bigint a)//Bigint a对10做模运算 405 { 406 Bigint n={0}; 407 for(int i=0;i<Length(a);i++) 408 { 409 n.num[0]=((int)n.num[0]%10+(((int)a.num[i]%10)*(int)pow(6,i))%10)%10; 410 } 411 return n; 412 } 413 414 void Print10(Bigint a) //十进制打印输出 415 { 416 int res[2000]; 417 int i = 0; 418 Bigint b = {0}; 419 Bigint c = {10}; 420 if(Length(a) == 0) //若a==0，则输出0 421 { 422 cout<<0<<endl; 423 return; 424 } 425 Bigint d={0}; 426 while(Compare(a,b) == 1) 427 { 428 d=Mod(a,c); 429 res[i]=(int)d.num[0]; 430 a = Div(a,c); 431 i++; 432 } 433 for(int j = i-1; j>=0; j--) 434 { 435 cout<<res[j]; 436 } 437 cout<<endl; 438 } 439 440 Bigint AddMod(Bigint a,Bigint b,Bigint n) 441 { 442 Bigint c={0}; 443 c=Add(a,b); 444 c=Mod(c,n); 445 return c; 446 } 447 448 Bigint SubMod(Bigint a,Bigint b,Bigint n)//计算(a-b)mod n(a>b) 449 { 450 Bigint c={0}; 451 if(Compare(a,b)<0) 452 { 453 cout<<"ERROR!"<<endl; 454 return c; 455 } 456 else 457 { 458 c=Sub(a,b); 459 c=Mod(c,n); 460 } 461 return c; 462 } 463 464 Bigint Sub2Mod(Bigint a,Bigint b,Bigint n)//计算(a-b)mod n 465 { 466 Bigint c={0}; 467 if(Compare(a,b)<0) 468 { 469 c=Sub(Add(a,n),b); 470 c=Mod(c,n); 471 } 472 else 473 { 474 c=Sub(a,b); 475 c=Mod(c,n); 476 } 477 return c; 478 } 479 480 Bigint MulMod(Bigint a,Bigint b,Bigint n)//计算(a*b)mod n 481 { 482 Bigint2 C={0},N={0}; 483 Bigint c={0}; 484 a=Mod(a,n); 485 b=Mod(b,n); 486 C=Mul(a,b); 487 N=Extend(n); 488 C=Mod(C,N); 489 c=Narrow(C); 490 return c; 491 } 492 493 Bigint PowMod(Bigint a,Bigint b,Bigint n)//计算(a^b)mod n 494 { 495 Bigint c = {1}; 496 Bigint temp = {1}; 497 while(Length(b) > 0) 498 { 499 while(!(b.num[0] & 0x01)) 500 { 501 BitMoveRight(b); 502 a = MulMod(a,a,n); 503 } 504 b = Sub(b,temp); 505 c = MulMod(a,c,n); 506 } 507 return c; 508 } 509 510 bool MillerRabinKnl(Bigint &n) //单次检测, 通过返回1, 否则返回0 511 { 512 Bigint b,m,v,temp; 513 Bigint j = {0}; 514 Bigint one = {1}; 515 Bigint two = {2}; 516 Bigint three = {3}; 517 m = Sub(n,one); 518 while(!(m.num[0] & 0x01)) //计算m, j，使得 n-1=2^j * m 519 { 520 j = Add(j,one); 521 BitMoveRight(m); 522 } 523 b = Add(two, BigRand(Sub(n,three))); //随机取一个 524 v = PowMod(b,m,n); //计算 525 if(Compare(v,one) == 0) //若v=1，通过测试 526 return 1; 527 528 Bigint i = {1}; 529 temp = Sub(n,one); 530 while(Compare(v,temp) < 0) //若v<n-1，不通过 531 { 532 if(Compare(i,j) == 0) //若i=j，是合数，不通过 533 return 0; 534 v = MulMod(v,v,n); //, i=i+1 535 i = Add(i,one); 536 } 537 return 1; //若v=n-1, 通过测试 538 } 539 540 bool MillerRabin(Bigint &n, long loop) //多次素性检测 541 { 542 for(long i = 0; i<loop;i++) 543 { 544 if(!MillerRabinKnl(n)) 545 return 0; 546 } 547 return 1; 548 } 549 550 Bigint get1n(int bytes)//随机生成一个长为8*bytes的奇数 551 { 552 Bigint n={0}; 553 while(!(n.num[0] & 0x01)) 554 { 555 n=BigRand(bytes); 556 } 557 return n; 558 } 559 560 bool Inverse(Bigint phiN, Bigint e, Bigint &d) 561 { 562 Bigint zero ={0}; 563 Bigint one = {1}; 564 Bigint y2 = {1}; 565 Bigint x2 = {0}; 566 Bigint x3,y3,t2,t3,q; 567 Copy(x3, phiN); 568 Copy(y3, e); 569 while(1) 570 { 571 if(Length(y3) == 0) //若y3=0，求逆失败，返回0 572 return 0; 573 if(Length(y3) == 1 && y3.num[0] == 1) 574 { //若y3=1，求逆成功，令d=y2，并返回1 575 Copy(d,y2); 576 return 1; 577 } 578 q = Div(x3,y3); //利用与辗转相除法类似的方法 579 t2 = Sub2Mod(x2,MulMod(q,y2,phiN),phiN); 580 //t2 = (x2 - q*y2) mod phiN，模是为了不出现负数 581 t3 = Sub(x3,Narrow(Mul(q,y3))); // t3 = x3-q*y3 582 Copy(x2,y2); 583 Copy(x3,y3); 584 Copy(y2,t2); 585 Copy(y3,t3); 586 } 587 } 588 589 Bigint Encrypt(Bigint m, Bigint e, Bigint N) //计算c = m^e mod N 590 { 591 Bigint c; 592 c=PowMod(m,e,N); 593 return c; 594 } 595 596 Bigint Decrypt(Bigint c, Bigint d, Bigint N) //计算m = c^d mod N 597 { 598 Bigint m; 599 m=PowMod(c,d,N); 600 return m; 601 } 602 603 Bigint GetP_Q(int bytes)//得到8*bytes的pq 604 { 605 Bigint pq={0}; 606 pq=get1n(bytes); 607 while(!(MillerRabin(pq,20))) 608 { 609 pq=get1n(bytes); 610 } 611 return pq; 612 } 613 614 int main() 615 { 616 Bigint p,q,d,m,c,phiN,N,m1; 617 Bigint e={1,0,1}; 618 Bigint one={1}; 619 p=GetP_Q(32); 620 sleep(1); 621 q=GetP_Q(32); 622 N=Narrow(Mul(p,q)); 623 phiN=Narrow(Mul(Sub(p,one),Sub(q,one))); 624 while(!(Inverse(phiN,e,d))) 625 { 626 p=GetP_Q(32); 627 sleep(1); 628 q=GetP_Q(32); 629 N=Narrow(Mul(p,q)); 630 phiN=Narrow(Mul(Sub(p,one),Sub(q,one))); 631 } 632 m=BigRand(64); 633 c=Encrypt(m,e,N); 634 m1=Decrypt(c,d,N); 635 cout<<"生成大素数："<<endl; 636 cout<<"p="; 637 Print10(p); 638 cout<<"q="; 639 Print10(q); 640 cout<<endl<<"系统的参数是："<<endl; 641 cout<<"N="; 642 Print10(N); 643 cout<<endl<<"公钥是："<<endl; 644 cout<<"e="; 645 Print10(e); 646 cout<<endl<<"私钥是："<<endl; 647 cout<<"d="; 648 Print10(d); 649 cout<<endl<<"明文是："<<endl; 650 cout<<"m="; 651 m=Mod(m,N); 652 Print10(m); 653 cout<<endl<<"加密得到的密文："<<endl; 654 cout<<"c="; 655 Print10(c); 656 cout<<endl<<"解密得到的明文："<<endl; 657 cout<<"m1="; 658 Print10(m1); 659 Bigint a; 660 /*a=MulMod(e,d,phiN); 661 Print10(a);*/ 662 return 0; 663 }
运行后得到的结果（不唯一）：