文档介绍：实验名称实验四 加密编码--------RSA公钥密码
一、实验目的
1. 了解RSA公钥密码进行加密、解密的原理；
2. 理解RSA公钥密码进行加密、解密的算法和步骤；
3. 正确运用C语言编程实现RSA加密、解密功能。
二、实验内容
1. 在Visual C++环境中运用C语言熟练实现RSA加密；
2. 在Visual C++环境中运用C语言熟练实现RSA解密。
三、实验原理
1. RSA的算法结构相当简单,整个算法可以描述如下：
（1）选取两个大素数p和q(保密)；
（2）计算n=pq(公开),γ=(p一1〉(q-1)(保密)；
（3）随机选取整数e(公开,加密密钥),使得ed(ear)=1；
（4）计算d(保密,私人密钥),使得ed≡1(mod r),即d=e-1(mod r)；
（5）加密:c=me mod n；
（6）解密:m=cd mod n。
2. RSA算法的特点
利用RSA对被加密的信息m (长度小于log2n的整数)进行加密得到相应的密文c=me mod n；解密算法则是计算m=cd modn。RSA的优点是不需要密钥分配,但缺点是速度慢。
RSA的安全基于大数分解的难度。其公开密钥和私人密钥是一对大素数(100到200个十进制数或更大)的函数。从一个公开密钥和密文中恢复出明文的难度等价于分解两个大素数之积。
3. 相关数论原理
（1）剩余系
设m>0, Cr = {a | a=r+qm, q∈Z}(r=0,1,...,m-1), 则C0 ,C1 ,...,Cm-1 称为模数m的剩余系。在C0 ,C1 ,...,Cm-1 中各取一数aj∈Cj ,j=0,1,...,m-1,此m个数a0 ,a1 ,...,am-1 称为模数m的一组完全剩余系。特别地，完全剩余系0,1,...,m-1称为模数m的非负最小完全剩余系。如果Cj 里面的数与m互素，称Cj 为与模数m互素的剩余类。在与m互素的全部剩余类中，各取一数所组成的集合就称为模数m的一组既约剩余系。
（2）欧拉函数和欧拉定理
欧拉函数Φ(n)是一个定义在正整数集合上的函数，Φ(n)的值等于序列0,1,...,n-1中与n互素的数的个数。
由定义得Φ(1)=1,Φ(2)=1,Φ(3)=2,...。当p是素数时，Φ(p)=p-1。
性质：
模数m的一组既约剩余系含Φ(m)个数。
Φ(m)个数作成模数m的一组既约剩余系的充分必要条件是两两对模数m不同余且都与m互素。
gcd(m1 ,m2 )=1时，Φ(m1 ,m2 )=Φ(m1 )Φ(m2 )。
p为素数，k为正整数时，Φ(pk )=pk -pk-1 =pk-1 (p-1)。
(欧拉定理) 若gcd(a,m)=1, 则aΦ(m)≡1(mod m)。
当m=p为素数时，即得到费马小定理。
(费马小定理) 若p为素数，则ap≡a(mod p)。
四、实验步骤：
1. 产生密钥
（1）选两个大素数p和q（可运用Miller_Rabin素性检测提高运算速度）；
（2）计算n=p×q，φ