编码理论实验报告实验四加密编码——RSA公钥密码.docVIP

实验名称 实验四 加密编码--------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）剩余系 设m0, 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，φ（n）=（p-1）（q-1），φ（n）为欧拉函数； （3）随机选整数e，使得2≤e≤φ（n）-1，并且e与φ（n）互素，即gcd（φ（n），e）=1； （4）计算d，使得d×e≡1（modφ（n）），即d是e在模φ（n）下的乘法逆元； （5）将n，e公开，而将d，p，q作为秘密。 2. 加密 加密运算公式为c≡me（modn），其中m为明文，c为加密后的密文。 3. 解密 解密运算的公式为m≡cd（modn）。 注：在具体实现加密解密过程中可用模平方重复法，避免溢出和计算量过大。 五、参考程序 见RSA.C程序。 实验思考 公开密钥加密在防范密码分析上比常规加密更加安全，这种提法对吗？ NO 公开密钥加密是一个使得常规加密已经过时的通用技术的提法对吗？ NO 与使用常规加密时涉及密钥分配中心的相当繁琐的握手过程相比，使用公开密钥加密后密钥分配就变的非常简单的说法正确吗？ NO 思考在RSA算法中如何选取p和q等参数以提高RSA加密算法的安全性? 选取长度相等不同的两个大素数。 实验心得：通过本次试验进一步加深了对RSA公钥密码进行加密、解密的原理理解，熟悉RSA公钥密码进行加解密算法的步骤，并运用C语言编程实现RSA加密、解密功能。