RSA算法

   欧拉,出生在瑞士的巴塞尔（Basel）城，13岁就进巴塞尔大学读书，得到当时最有名的数学家约翰·伯努利（Johann rnoulli，1667-1748年）的精心指导． 
   欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。欧拉还发现，不论什么形状的凸多面体，其顶点数V、棱数E、面数F之间总有V-E+F=2这个关系。V-E+F 被称为欧拉示性数，成为拓扑学的基础概念。以欧拉的名字命名的数学公式、定理等在数学书籍中随处可见, 与此同时，他还在物理、天文、建筑以至音乐、哲学方面取得了辉煌的成就。欧拉还创设了许多数学符号，例如π（1736年），i（1777年），e（1748年），sin和cos（1748年），tg（1753年），△x（1755年），Σ（1755年），f(x)（1734年)等。 
    1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授．1735年，欧拉解决了一个天文学的难题（计算彗星轨道），这个问题经几个著名数学家几个月的努力才得到解决，而欧拉却用自己发明的方法，三天便完成了．然而过度的工作使他得了眼病，并且不幸右眼失明了，这时他才28岁． 欧拉的一生，是为数学发展而奋斗的一生，他那杰出的智慧，顽强的毅力，孜孜不倦的奋斗精神和高尚的科学道德，永远是值得我们学习的． 
欧拉同余定理： 
如果φ(m)表示比m小且与m互素的正整数个数，整数a与m互素，则有以下等式成立： 
a^φ(m)≡1 mod  


它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, Adi Shamir 和Leonard Adleman。

     但RSA的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破。

一、RSA算法 :

     首先, 找出三个数, p, q, r, 其中 p, q 是两个相异的质数, r 是与 (p-1)(q-1) 互质的数...... p, q, r 这三个数便是 private key  

     接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1)..... 这个 m 一定存在, 因为 r 与 (p-1)(q-1) 互质, 用辗转相除法就可以得到了..... 

     再来, 计算 n = pq....... m, n 这两个数便是 public key  编码过程是, 若资料为 a, 将其看成是一个大整数, 假设 a < n.... 如果 a >= n 的话, 就将 a 表成 s 进位 (s <= n, 通常取 s = 2^t), 则每一位数均小於 n, 然後分段编码...... 

     接下来, 计算 b == a^m mod n, (0 <= b < n), b 就是编码後的资料......  解码的过程是, 计算 c == b^r mod pq (0 <= c < pq), 於是乎, 解码完毕...... 等会会证明 c 和 a 其实是相等的  :)  

     如果第三者进行窃听时, 他会得到几个数: m, n(=pq), b...... 他如果要解码的话, 必须想办法得到 r...... 所以, 他必须先对 n 作质因数分解......... 要防止他分解, 最有效的方法是找两个非常的大质数 p, q, 使第三者作因数分解时发生困难.........

   <定理> 若 p, q 是相异质数, rm == 1 mod (p-1)(q-1), a 是任意一个正整数, b == a^m mod pq, c == b^r mod pq, 则 c == a mod pq  证明的过程, 会用到费马小定理, 叙述如下: m 是任一质数, n 是任一整数, 则 n^m == n mod m (换另一句话说, 如果 n 和 m 互质, 则 n^(m-1) == 1 mod m) 运用一些基本的群论的知识, 就可以很容易地证出费马小定理的........  

#include  
int candp(int a,int b,int c) 
{ int r=1; 
b=b+1; 
while(b!=1) 
{ 
r=r*a; 
r=r%c; 
b--; 
} 
printf("%d",r); 
return r; 
} 
void main() 
{ 
int p,q,e,d,m,n,t,c,r; 
char s; 
{printf("input the p:\n"); 
scanf("%d\n",&p); 
printf("input the q:\n"); 
scanf("%d%d\n",&p); 
n=p*q; 
printf("so,the n is %3d\n",n); 
t=(p-1)*(q-1); 
printf("so,the t is %3d\n",t); 
printf("please intput the e:\n"); 
scanf("%d",&e); 
if(e<1||e>t) 
{printf("e is error,please input again;"); 
  scanf("%d",&e);} 
  d=1; 
  while  (((e*d)%t)!=1)   d++; 
  printf("then caculate out that the d is %5d",d); 
  printf("if you want to konw the cipher please input 1;\n if you want to konw the plain  please input 2;\n"); 
  scanf("%d",&r); 
  if(r==1) 
{ 
printf("input the m :" );/*输入要加密的明文数字*/ 
scanf("%d\n",&m); 
  c=candp(m,e,n); 
printf("so ,the cipher is %4d",c);} 
if(r==2) 
{ 
printf("input the c :" );/*输入要解密的密文数字*/ 
scanf("%d\n",&c); 
  m=candp(c,d,n); 
printf("so ,the cipher is %4d\n",m); 
printf("do you want to use this programe:Yes or No"); 
scanf("%s",&s); 
}while(s=='Y'); 

} 
} 

二， 
加密的时候，输入Y，然后输入要加密的文本（大写字母） 
解密的时候，输入N，然后输入一个整数n表示密文的个数，然后n个整数表示加密时候得到的密文。 
/*RSA algorithm */ 
#include  
#include  
#include  
#define MM 7081 
#define KK 1789 
#define PHIM 6912 
#define PP 85 
typedef char strtype[10000]; 
int len; 
long nume[10000]; 
int change[126]; 
char antichange[37]; 
void initialize() 
{ int i; 
char c; 
for (i = 11, c = 'A'; c <= 'Z'; c ++, i ++) 
{ change[c] = i; 
antichange[i] = c; 
} 
} 
void changetonum(strtype str) 
{ int l = strlen(str), i; 
len = 0; 
memset(nume, 0, sizeof(nume)); 
for (i = 0; i < l; i ++) 
{ nume[len] = nume[len] * 100 + change[str[i]]; 
if (i % 2 == 1) len ++; 
} 
if (i % 2 != 0) len ++; 
} 
long binamod(long numb, long k) 
{ if (k == 0) return 1; 
long curr = binamod (numb, k / 2); 
if (k % 2 == 0) 
return curr * curr % MM; 
else return (curr * curr) % MM * numb % MM; 
} 
long encode(long numb) 
{ return binamod(numb, KK); 
} 
long decode(long numb) 
{ return binamod(numb, PP); 
} 
main() 
{ strtype str; 
int i, a1, a2; 
long curr; 
initialize(); 
puts("Input 'Y' if encoding, otherwise input 'N':"); 
gets(str); 
if (str[0] == 'Y') 
{ gets(str); 
changetonum(str); 
printf("encoded: "); 
for (i = 0; i < len; i ++) 
{ if (i) putchar('-'); 
printf(" %ld ", encode(nume[i])); 
} 
putchar('\n'); 
} 
else 
{ scanf("%d", &len); 
for (i = 0; i < len; i ++) 
{ scanf("%ld", &curr); 
curr = decode(curr); 
a1 = curr / 100; 
a2 = curr % 100; 
printf("decoded: "); 
if (a1 != 0) putchar(antichange[a1]); 
if (a2 != 0) putchar(antichange[a2]); 
} 
putchar('\n'); 
} 
putchar('\n'); 
system("PAUSE"); 
return 0; 
} 
测试： 
输入： 
Y 
FERMAT 
输出： 
encoded: 5192 - 2604 - 4222 
输入 
N 
3 5192 2604 4222 
输出 
decoded: FERMAT 
出自己网上。 

package rsa; 
import java.math.BigInteger; 

public class RSA { 
private long p,q,e,d,n; 
public RSA(){ 
  int pIndex = (int)(Math.random()*10); 
  int qIndex; 
  int eIndex; 
  do{ 
   qIndex = (int)(Math.random()*10); 
  } 
  while(qIndex==pIndex); 
  do{ 
   eIndex = (int)(Math.random()*10); 
  } 
  while(eIndex==pIndex||eIndex==pIndex); 
  p = 1033; 
  q = 2017; 
  e = 29437; 
  n = p*q; 
  d = calculateD(); 
} 
private long calculateD(){ 
  long t0 = 0,t1 = 1,t2 = -1; 
  long r0 = (p-1)*(q-1), m = r0,r1 = e ,r2 = -1; 
  do{ 
   long q = r0/r1; 
   r2 = r0-r1*q; 
   if(r2==0)break; 
   t2 = t0 - t1*q; 
   while(t2<0){ 
    t2+=m; 
   } 
   if(t2>=m){ 
    t2 %= m; 
   }     
   r0 = r1; 
   r1 = r2; 
   t0 = t1; 
   t1 = t2; 
  }while(r2!=0); 
  if(r1!=1){ 
   return 0; 
  } 
  else{ 
   return t2; 
  } 
} 

public long getE() { 
  return e; 
} 
public long getN() { 
  return n; 
} 
public long getD() { 
  return d; 
} 
public BigInteger encode(BigInteger data){ 
  return pow(data,d).mod(new BigInteger(n+"")); 
} 
public BigInteger decode(BigInteger code){ 
  return pow(code,e).mod(new BigInteger(n+"")); 
} 
public BigInteger pow(BigInteger data,long p){ 
  data = data.pow((int)p); 
  return data; 
} 
public static void main(String args[]){ 
  RSA rsa = new RSA(); 

  BigInteger data = new BigInteger("222222"); 
  long oldtime = System.currentTimeMillis(); 
  BigInteger code = rsa.encode(data); 
  long newtime = System.currentTimeMillis(); 
  double codetime = ((double)(newtime-oldtime))/1000; 
  oldtime = System.currentTimeMillis(); 
  BigInteger decode = rsa.decode(code); 
  newtime = System.currentTimeMillis(); 
  double decodetime = ((double)(newtime-oldtime))/1000; 
  System.out.println("privateKey:"+rsa.d); 
  System.out.println("publickKey:"+rsa.e); 
  System.out.println("N:"+rsa.n); 
  System.out.println("data:"+data); 
  System.out.println("code:"+code+" time:"+codetime); 
  System.out.println("decode:"+decode+" time:"+decodetime); 

} 
} 

摘自漆黑之翼网站，并加以修改和测试