RSA公钥密码算法的原理请看：
http://blog.csdn.net/A00553344/archive/2009/01/07/3730194.aspx
下面主要论述RSA公钥密码算法的具体实现。
预备知识
RSA公钥密码算法需要多精度算术（通常被称为"大数"数学）。RSA需要很大的整数来抵御已知的密码攻击。比如，一个典型的RSA模数至少大于10309，而现代编程语言C,JAVA,PASCAL等仅支持相对较小且单精度的整数。为了解决这个问题，我们引入了多精度整数。
n为多精度整数可表示为x=(xn-1,...,x1,x0)β,它表示整数x=∑xiβi。数组中的x表示以β为基的每一位的值。比如，x=(1,2,3)10表示整数1*102+2*101+3*100=123。为了方便编程，我们引入一个复合结构mp_int来表示多精度数，它包含其所表示的整数的每一位值，以及操作这些数据所需的辅助数据。
mp_int，它是一个结构。
C语言结构描述如下：
typedef struct{
int used,alloc,sign;
mp_digit *dp;
} mp_int;
Object Pascal语言描述如下：
mp_int = record {MP integer number }
dp : PDigitArray; {pointer to mp_digit array }
alloc : word; {allocated digits in pdigits }
used : word; {used digits in pdigits }
sign : word; {sign: MP_ZPOS or MP_NEG }
end;
这里的mp_digit是单精度整数。在C语言里，它有可能是unsigned long; 在PASCAL里，它有可能是Cadinal;它其实也代表了多精度数的基β。比如，unsigned long为32位，假如我们取其低30位来表示多精度数的每一位。那么这个多精度数的基β=230。当dp数组存放了三个数；dp[0]=1,dp[1]=2,dp[2]=3,那么这个多精度数就是x=dp[2]*β2+dp[1]*β1+dp[0]*β0=3*(230)2+2*(230)1+1*(230)0。
成员定义如下：
- used参数表示数组dp用多少位数来表示一个指定整数。used必须是正数（或0），并且不能超过alloc的值。
- alloc参数表示数组在增加大小之前可用的数据位。当used大于alloc数时，所有算法都会自动增加数组的大小，以适应结果的精度。
- dp表示动态分配的代表指定多精度整数的数组。不足的位（alloc - used）全部填0。数组中的数据按LSB在先的顺序存储。
- sign参数表示数字为0(正)或非0(负)。
一、n的长度。
RSA的安全性完全依赖于分解大数的难度。从技术上说这是不正确的，这只是一种推测。从数学上从未证明过需要分解n才能从c和e中计算出m。用一种完全不同的方法来对RSA进行密码分析还只是一种想象。如果这种新方法能让密码分析者推算出d的话，它也可以作为分解大数的一种新方法。从目前看，分解n是最显而易见的攻击方法。攻击者手里有公开密钥e和n，要想找到解密密钥，他们就必须分解n。
对大数进行因式分解是困难的。不幸的是，对算法设计者来说它正变得越来越容易。更加糟糕的是，它比数学家们所希望的还要快。1977年，Ron Rivest说过分解一个125位(十进制)的数据需要40 * 1015年。 可是，一个129位的数已经在1994年被成功分解。大数因式分解最近的记录是RSA200，一个200位的非特殊数字，在2005年计算机花了18个月时间才把它分解成两个素数。而目前一个国际组织则打破了这个保持了2年之久的记录，3月6日来自3个机构的计算机集群（EPFL，波恩大学，日本电话电报公司）在经过11个月的计算后终于成功的把一个有名的很难分解的大数—2^1039 - 1 —一个307位的数字—分解出两个素数因子。
基于目前的因式分解的发展情况，下面给出了一些公开密钥长度的推荐值(即n的位数,二进制)。
| 年度 | 对于个人 | 对于公司 | 对于政府 |
| 1995 | 768 | 1280 | 1536 |
| 2000 | 1024 | 1280 | 1536 |
| 2005 | 1280 | 1536 | 2048 |
| 2010 | 1280 | 1536 | 2048 |
| 2015 | 1536 | 2048 | 2048 |
在实际应用中，目前RSA-1024仍然是安全的，但新的应用程序真的应该使用至少RSA-1536或更高。业界的许多人设置最小为2048位的密钥，来避免将来可能的实际进展所带来的安全危机。
二、p,q的选择。
因为任何潜在的破解方都可能知道n=pq的值，为了防止通过穷举方法来发现p和q, p和q这两个素数的选择必须从足够大的集合中进行选取。另一方面，用来找到大素数的方法必须相当有效。
现在还没有产生任意的大素数的有用技术，因此解决这个问题需要其他方法。通常使用的过程是随机选取一个需要的数量级的奇数并检验这个数是否是素数。如果不是，选取后续的随机数直到找到了通过检验的素数为止。
检验素数方面已经出现了很多方法。几乎所有的检验方法都是概率性的，也就是说，这个检验只是确定一个给定的整数可能是素数。虽然缺乏完全的确定性，但是这些检验在运行时可以按照需要做到使得概率尽可能接近1。
下面介绍一下素性检验几种主要方法。为了讨论方便，我们用n表示要进行素性检验的整数。
1. 试除法(Trial Division)。
试除法是指试图最终用一个小素数除尽一个候选整数。将n除以q,q为素数且
,如果n可被整除，则显然n不是素数。此测试可实际证明一个整数是否是素数。不过，n增大时其所需的时间会大大增加。为了减少计算的时间，我们可以不用每个素数去除n，而是改用一组更小、更易于管理的素数。通过对小于
的素数的一个子集执行试除法。该算法无法确定n是否是素数，但是它可以证明n是否不是素数。
这个测试的好处在于除以小的值的试除法相当有效快速。常用于其他素性测试算法前的预筛选工作。剔除掉大部分的非素数。
算法描述：
-------------------------------------------------------------------
输入：mp_int a
返回：如果n可由小素数整除，则返回真,否则返回假。
-------------------------------------------------------------------
<1>. 预先生产一个素数表，一般选择[0x0000H, 0xFFFFH]范围内的素数组成一个素数表Prime_Table,它所包含的素数个数为PRIME_SIZE。
<2>. 将Prime_Table内的素数逐个执行
<1.1>. d ← n(mod Prime_table[i]) ; 0≤i<PRIME_SIZE
<1.2>. 如果d=0,则返回真; 否则返回假.
<3>. 结束.
--------------------------------------------------------------------
常用的Prime_table如下：
const mp_digit prime_table[] = {
0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013,
0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035,
0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059,
0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F, 0x0083,
0x0089, 0x008B, 0x0095, 0x0097, 0x009D, 0x00A3, 0x00A7, 0x00AD,
0x00B3, 0x00B5, 0x00BF, 0x00C1, 0x00C5, 0x00C7, 0x00D3, 0x00DF,
0x00E3, 0x00E5, 0x00E9, 0x00EF, 0x00F1, 0x00FB, 0x0101, 0x0107,
0x010D, 0x010F, 0x0115, 0x0119, 0x011B, 0x0125, 0x0133, 0x0137,
0x0139, 0x013D, 0x014B, 0x0151, 0x015B, 0x015D, 0x0161, 0x0167,
0x016F, 0x0175, 0x017B, 0x017F, 0x0185, 0x018D, 0x0191, 0x0199,
0x01A3, 0x01A5, 0x01AF, 0x01B1, 0x01B7, 0x01BB, 0x01C1, 0x01C9,
0x01CD, 0x01CF, 0x01D3, 0x01DF, 0x01E7, 0x01EB, 0x01F3, 0x01F7,
0x01FD, 0x0209, 0x020B, 0x021D, 0x0223, 0x022D, 0x0233, 0x0239,
0x023B, 0x0241, 0x024B, 0x0251, 0x0257, 0x0259, 0x025F, 0x0265,
0x0269, 0x026B, 0x0277, 0x0281, 0x0283, 0x0287, 0x028D, 0x0293,
0x0295, 0x02A1, 0x02A5, 0x02AB, 0x02B3, 0x02BD, 0x02C5, 0x02CF,
0x02D7, 0x02DD, 0x02E3, 0x02E7, 0x02EF, 0x02F5, 0x02F9, 0x0301,
0x0305, 0x0313, 0x031D, 0x0329, 0x032B, 0x0335, 0x0337, 0x033B,
0x033D, 0x0347, 0x0355, 0x0359, 0x035B, 0x035F, 0x036D, 0x0371,
0x0373, 0x0377, 0x038B, 0x038F, 0x0397, 0x03A1, 0x03A9, 0x03AD,
0x03B3, 0x03B9, 0x03C7, 0x03CB, 0x03D1, 0x03D7, 0x03DF, 0x03E5,
0x03F1, 0x03F5, 0x03FB, 0x03FD, 0x0407, 0x0409, 0x040F, 0x0419,
0x041B, 0x0425, 0x0427, 0x042D, 0x043F, 0x0443, 0x0445, 0x0449,
0x044F, 0x0455, 0x045D, 0x0463, 0x0469, 0x047F, 0x0481, 0x048B,
0x0493, 0x049D, 0x04A3, 0x04A9, 0x04B1, 0x04BD, 0x04C1, 0x04C7,
0x04CD, 0x04CF, 0x04D5, 0x04E1, 0x04EB, 0x04FD, 0x04FF, 0x0503,
0x0509, 0x050B, 0x0511, 0x0515, 0x0517, 0x051B, 0x0527, 0x0529,
0x052F, 0x0551, 0x0557, 0x055D, 0x0565, 0x0577, 0x0581, 0x058F,
0x0593, 0x0595, 0x0599, 0x059F, 0x05A7, 0x05AB, 0x05AD, 0x05B3,
0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
};
除了事先预备好素数表之外，也可以直接判断是否为小于0x0FFFH之内的素数，然后被n整除来试除。
2. 费马(Fermat)测试。
费马测试可能是最早的一种成功的测试方法。它基于费马小定理：如果n确定是素数，则对于所有0<a<n有an≡a(mod n)。如果n不是素数，则可能存在an≠a(mod n)。所以，如果一个非素数n满足0<a<n有an≡a(mod n)。我们称之为伪素数。幸运的是，当n增大的时伪素数非常的少见。
算法描述如下：
---------------------------------------------------------------------
给定奇整数n≥5和安全参数t,
<1>. 随机选取整数a,2≤a≤n-2。
<2>. 计算g=gcd(a,n),如果g≠1,则n不为素数。
<3>. 计算r=an(mod n)，如果r≠a,则n不为素数。
<4>. 如果不为<2>,<3>的情况，则n可能为素数。
<5>. 上述过程重复t次。如果每次得到n可能为素数，则n为素数的概率为1-(1/2t)。
---------------------------------------------------------------------
3.米勒-罗宾(Miller-Rabin)测试。
米勒-罗宾测试是另一种素数测试方法。它对错误的限制比费马测试更严格，尤其是当按顺序选择候选整数时。它的定义如下。
[定义]设n(≥3)是一个奇整数且n-1=2sm，其中s≥0,m是一个奇整数。如果bm≡1(mod n)或者bm≡-1(mod n)或者有r(1≤r≤s-1)使b2^rm≡-1(mod n),则称n通过以b为基的Miller-Rabin测试。
算法描述如下：
----------------------------------------------------------------------
给定奇整数n(≥3,且n-1=2sm,其中s≥0,m是一个奇整数)和安全参数t。
<1>. 随机选取整数b,1≤b≤n-1。
<2>. r ← 0。
<3>. z=bm(mod n)。
<4>. 如果z=1或z=n-1,则n可能是素数；转<10>。
<5>. 如果r=s-1,则n是合数；转<10>。
<6>. r=r+1。