RSA公钥密码系统.ppt
文本预览下载声明
4.2 RSA公钥密码系统 所谓公钥密码体制是指加密密钥公开、解密密钥保密的密码体制。 RSA加密系统采用了公钥密码体制,它利用数论领域的一个关键事实:虽然把两个大素数相乘生成一个合数是一件很容易的事,但是要把一个合数分解为两个素数却十分困难。 求mod m的逆元素的算法已知u 和m,求u-1使得满足同余方程:u*u-1 ≡ 1 mod m n1=m; n2=u; b1=0; b2=1; 求q和r使得n1=q*n2+ r; If ( r!=0 ) { n1=n2; n2=r; t=b2; b2=b1-q*b2; b1=t; goto step(2); } If ( n2!=1 ) 输出不存在u-1的信息 else { if ( b20 ) b2=b2+m; 输出u-1 =b2;} 求模幂算法:c=xr mod p a=x; b=r; c=1; while ( b!=0 ) { while ((b0 (b%2==0)) // b为正的偶数 { b=b/2; a=a2 mod p; } b=b-1; c=a*c mod p; } 输出c 此算法时间复杂度为O(log2r) 4.2.1 RSA密码系统 假设m为要传送的报文,则RSA算法描述如下: (l)密钥的生成: ① 任选两个秘密的大素数 p与q; ② 计算n,使得 n=p×qm,公开n; ③ 选择正整数e,使得e与ψ(n)=(p-1)(q-1)互素,公开e; ④ 计算d,使 e×d ≡ l mod ψ(n) ,d保密。 (2)加密过程: c=E(m) ≡me mod n, c即是对应于明文m的密文。 (3)解密过程: m=D(c) ≡cd mod n, m即是对应于密文c的明文。 其中公钥为(e,n),它没有包含任何有关n的因子p和q的信息;秘钥为(d,n),显然d中隐含有因子p和q的信息。 4.2.2 RSA密码系统例 【例4.3】 用RSA加解密算法对明文信息“ public key encryptions”进行加密和还原。 设素数p=43, 素数q=59, 则n=p*q=43*59=2537 , ψ(n)=42*58=2436, 选取e=13, 解方程e*d mod 2436 =1 得d=937。 将明文public key encryptions以两个字符为一组进行分组: pu bl ic ke ye nc ry pt io ns 若用00表示a, 01表示b, 02表示c, ...... , 23表示x, 24表示y, 25表示z;则将上述分组字符数字化成如下形式: 1520 0111 0802 1004 2404 1302 1724 1519 0814 1418 对明文数字m=1520的加密过程 c =E(m)≡me (mod n)=152013 (mod 2537) =(1520 2 ) 6 1520 (mod 2537) 因为 (1520 2 ) ≡1730 (mod 2537),所以 c≡(1730) 6 1520 (mod 2537)=(1730 2 ) 3 1520 (mod 2537) 但是 1730 2 ≡ 1777 mod (2537),所以 c≡(1777 ) 3 1520 (mod 2537) =(1777 ) 2 (1777 *1520) (mod 2537) 又 1777 2 ≡ 1701 mod (2537) 1777 *1520≡1672 (mod 2537) 因此 ,密文 c≡1701*1672 (mod 2537) ≡95 (mod 2537)
显示全部