还剩2页未读,继续阅读
文本内容:
实验四算法RSA.实验目的1了解算法的特点1RSA掌握算法的加解密原理2RSA.实验内容2阅读学习本实验第三部分知识点,通过算法实现的短片,理解并掌握RSA FlashRSA算法的详细实现过程;在环境下,调试运行算法,简单了解算法的语言实VC RSA RSA C++现过程算法原理演示1RSA步骤工打开实验五文件夹中的文件如图所示;“RSA.exe”41图4・1RSA算法演示文件步骤依据演示文稿,逐步学习算法2RSA算法的实现2RSA该部分,主要通过在中,采用语言来编程实现算法来更进一步的理解和VC++
6.0C++RSA掌握算法具体步骤如下RSA步骤打开开发环境,打开文件;L VCRSA.cpp步骤依据算法实现原理.,阅读完善算法;2RSA步骤编译运行程序,并进行具体测试3:.知识点3年美国的三名数学家里维斯特,沙摩尔和阿德尔1978MIT R.Rivest A.Shamir L.Adleman曼提出了著名的公钥密码体制算法,它的安全性依赖于大数分解公钥和私钥都是两个RSA大素数长度为乂位以上的十进制数的函数据猜测,从一个密钥和密文推断出明文的难度0等同于分解两个大素数的积迄今为止,算法是思想最简单、分析最透彻、应用最广泛的RSA公钥密码体制算法非常容易理解和实现,经受住了密码分析,密码分析者不既不能证明RSA也不能否定它的安全性,这恰恰说明了具有一定的可信度RSA算法描述1RSA
①密钥对的产生•选择两个互异的大素数,和p q;•计算,其中是的欧拉函数值;n=p*q,pn=p-lq-l pnn•选一整数满足且;e,le pn,gcd pn,e=l•计算满足三即是在模下的乘法逆元;d,de1mod pn,d epn•为公钥,为私钥{e,n}d,n
②力口、解密过程•加密时首先将明文比特串分组,使得每个分组对应的十进制数小于即分组长度小n,于;log n2•对每个明文分组作加密运算m,c=me mod n•解密时对每个密文分组做如下计算m=cd mod n算法论证2RSA证明由加密过程cdmod n三me dmod n三m kpn+1dned三1mod pnmo•若与互素,由欧拉定理m nm^=1mod n有mkpn=1mod n,k pn+i=m modnm•若与不互素,即则必与两个素数、中的一个互素,假定与互素,m ngcdm,n Wl,m p q p与不互素,不妨设止匕时由欧拉定理,q m=cq cq,gcdm,p=l,m中⑻三1mod p,[mp p]kp q=i mod p即m kpn=1mod p,于是存在一整数使中吊=+中,r,81两边同乘得m=cq,k pn+i-m+rcpq=m+rcnm即k pn+i=m modnm算法参数的选择3RSA为了确保密码的安全,必须认真选择密码参数RSA和要足够大;
①P q一般应用和应重要应用和应pq512b pq1024b和应为强素数;
②P q文献指出,只要、、、四个数之一只有小的素因子,就容易分解p-1p+1q-1q+1n和的差要合适;
③P q的选择;
④e随机且含多就安全,但加密速度慢1的选择;
⑤d不能太小,要足够大d
⑥不要许多用户公用一个模n易受共模攻击快速指数运算平方乘运算4问题求,其中是正整数am modn=a,m将表示为二进制形式,即:m bkbk-i…bom=bk2k+bk-i2k-1+---+bi2+b0因此,am=...4与为a比modn2222实现平方乘法运算的伪代码如下所示m=bk2k+bk-i2k-1+***+bi2+bo,求am modn=d=l;for i=k downto0{d=dXd modn;if bi=l then{d=dXa modn}return d素性检测算法5Miller-Rabin引理若是奇素数,则方程式px2=1modp只有两个解或该引理的逆命题就是如果方程式三存在除了x=+l x=-l x21mod P+1和以外的其他解,就不是素数上述引理的逆命题就是著名的素性检验算法的-1n Miller-Rabin基本依据之一素性检测算法伪代码Miller-RabinMiller・Rabina,n:
1.represent n-1as binarybkbk-l...bO;
2.d—1;
3.For i+k downto0do
4.{x-d;
5.d^-dXd modn;
6.if d=l andxwl andx^n-
17.then return TRUE;
8.if bi=l
9.then dUdX amodn}
10.if dwl
11.then returnTRUE;
12.return FALSE;此算法的两个输入中,是待检测数,是小于的整数如果算法返回的值为则n anTRUE,n肯定不是素数;如果返回的值为则有可能是素数FALSE,n由于是简单且比较成熟的一种公钥密码体制,许多公司及研究团体都对它进行了实现RSA除公司的产品以夕卜,主要还有的、、、RSA RSArefIBM CCACryptix CryptlibCrypto++Cryptolib、及的实现等Python SSLavaSSLeay CRYPTOMAThIC算法的软硬件实现都已经比较成熟,但是其软硬件实现加解密速度都远远不及等传RSA DES统密码,多用于密钥交换和认证如果适当选择的参数,可以大大加快速度例如,RSARSA选为、或的二进制表示式中都只有两/个大大减少了运算量建议e31765537216+11,X.509用建议用而建议用当消息后填充随机数字时,不会有任何安65537
[1989],PEM3,PKCSttl65537,全问题常见问题回答
4.从密码分析的角度来讲,公钥密码体制比传统密码更安全吗?1解答事实上,任何加密方法的安全性以来于密钥的长度和破译密文所需要的计算量从抗击密码分析的角度看,原则上不能说传统密码优于公钥密码,也不能说公钥密码优于传统密码公开密钥是一种通用的方法,传统密码是不是已经过时?2解答传统密码并没有过时,由于现有的公钥密码计算量大,所以取代传统密码不太可能就像公钥密码的发明者之一所说的“公钥密码学仅限于用在密钥管理和签名这类应用之中,这几乎是被广泛接受的事实」■思考题5简述算法加解密过程1RSA如何理解算法是基于大数分解的数学难题的?2RSA算法中,令尸计算明文要求:给出详细步骤3RSA p=3,q=ll,e=714,m调试运行该实验中给出的算法源码时,密钥生成若选择、值分别为、可以吗试4RSA pq57通过修改代码测试?为什么?描述采用算法及算法进行混合加密的方法过程及特点5DES RSA。