一. RSA算法是由算法发明者以名字的缩写命名的：Ron Rivest, Adi Shamir 和Leonard Adleman
二.基础
RSA算法非常简单，原理如下：
找两素数p和q
取n=p*q
取t=(p-1)*(q-1)
取任何一个数e,要求满足e<t并且e与t互素
取d*e%t==1
这样最终得到三个数： n d e
设消息为数M (M < n)
设c=(M**d)%n就得到了加密后的消息c
设m=(c**e)%n则 m == M，从而完成对c的解密。
注：**表示次方,上面两式中的d和e可以互换。
在对称加密中：
n d两个数构成公钥，可以告诉别人；
n e两个数构成私钥，e自己保留，不让任何人知道。
给别人发送的信息使用e加密，只要别人能用d解开就证明信息是由你发送的，构成了签名机制。
别人给你发送信息时使用d加密，这样只有拥有e的你能够对其解密。
rsa的安全性在于对于一个大数n，没有有效的方法能够将其分解
从而在已知n d的情况下无法获得e；同样在已知n e的情况下无法
求得d。
三.编程实现
接下来我们来一个实践，看看实际的操作：
找两个素数：
p=23
q=29
这样
n=p*q=616
t=(p-1)*(q-1)=2668
取e=569，满足e<t并且e和t互素
d＝9489
最终我们获得关键的
n=667
d=9489
e=569
取消息M=244我们看看
加密：
c=M**d%n
解密：
我们可以用e来对加密后的c进行解密，还原M
下面是得到RSA关键码的代码
/**************************************************************************
Author : Bohemia
Time : 2006.02.10
Comment : RSA Algorithm.This code can get the RSA Key values
**************************************************************************/
#include <stdio.h>
#include <conio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#define MAXNUM 9999
#define TRUE 1
#define FALSE 0
typedef unsigned long TYPE;
void scan (TYPE *p, TYPE *q);
void check (TYPE *p, TYPE *q);
void count (TYPE *p, TYPE *q);
void print (TYPE *p, TYPE *q);
TYPE N,T,E,D;
/***************************************************************************/
void main()
{
TYPE *p, *q;
clrscr ();
scan (p,q);
check (p,q);
count (p,q);
print (p,q);
}
/**************************************************************************/
void scan (TYPE *p, TYPE *q)
{
printf ("Input two prime numbers to make keys:");
scanf ("%lu %lu", p, q);
}
/*************************************************************************/
void check (TYPE *p, TYPE *q)
{
TYPE i,j;
if ( (*p == 0) || (*q == 0) )
{
printf ("/nInput error!");
exit (1);
}
for (i = 2; i <= sqrt (*p); i++)
{
if (*p % i == 0)
{
printf ("/nInput error!");
exit (1);
}
}
for (j = 2; j <= sqrt (*q); j++)
{
if (*q % j == 0)
{
printf ("/nInput error!");
exit (1);
}
}
}
/**************************************************************************/
void count (TYPE *p, TYPE *q)
{
unsigned long j;
int flag1 = TRUE,flag;
randomize();
N = (*p) * (*q);
T = (*p - 1) * (*q - 1);
printf ("Waiting...");
while (flag1)
{
flag = random (9999) + 1;
E = T * (flag / 10000.0);
for (j = 1; j < MAXNUM; j++)
{
if ( (j * E) % T == 1)
{
D = j;
flag1 = FALSE;
}
}
}
}
/**************************************************************************/
void print (TYPE *p, TYPE *q)
{
printf ("/n/nP=%lu Q=%lu N=%lu E=%lu D=%lu", *p,*q,N,E,D);
getch ();
}
四. RSA通常的实现
RSA简单明了，但计算速度比较慢，通常加密中并不是直接使用RSA 来对所有的信息进行加密，最常见的情况是随机产生一个对称加密的密钥，然后使用对称加密算法对信息加密，之后用RSA对刚才的加密密钥进行加密。
最后需要说明的是，当前小于1024位的N已经被证明是不安全的自己使用中不要使用小于1024位的RSA，最好使用2048位的。
