RSA的加解密过程 o加密算法：c=E(m)≡me(modn) 。解密算法：m=D(c)≡cd(modn) 若m与n互素，根 据欧拉定理，RSA 证明： 加解密成立。 cd=(me)d=med mk(n)+1 =m*mkΦ(m)=m*(m中(nyk≡m*1≡m(modn) 要求： 明文分组m对应的十进制数小于n,即分组m的长度小于log2 bits。 长度为log2n的明文m的最大值为2lo,”-1=n-1, 28 所以m<n
RSA的加解密过程 加密算法 E( ) e ：c=E(m)≡m ( d ) e(mod n) 解密算法：m=D(c)≡cd 解密算法：m D(c) ≡c (mod n) (mod n) 证明： 若m与n互素，根 据欧拉定理，RSA 加解密成立。 cd=(me)d=med = mkφ(n)+1 =m*mkφ(n)= m*(mφ(n))k≡m*1 ≡m (mod n)m (mod n) 明文分组m对应的十进制数小于n,即分组m的长度小于log2n bits。 28 要求：
RSA的加解密证明过程（续) 若gcd(m,n)>1,由于n=p*q,所以gcd(m,n)必含p,q之一， 设gcd(p,q)=p,或m=s*p,1≤s≤q,由欧拉定理得： m中(a)=1(modq). 因此，对于任何k,总有：mka-)=1(modq) mkp-1)(q-10=(1)kp-1)=1(modq) 即：mkΦ(n)=1(modq)或1=mk中()+h*g 其中h是某个整数，由假定m=s*p,得： s*p=mk(n)*s*p+s*p*h*g,m=mk(n)+1+s*h*p*q m=mkΦ()+1+sh*n,即得：mkΦ(m)+1≡m(modn) 29 CNR@HEU http://machunguang.hrbeu.edu.cn
RSA的加解密证明过程（续） 若gcd(m,n)>1, gcd(m,n)>1,由于n=p*q,所以gcd(m,n) gcd(m,n)必含p,q之一， 设gcd(p,q)=p, gcd(p,q)=p,或m=s*p, 1≤s≤q, m=s*p, 1≤s≤q,由欧拉定理得： 由欧拉定理得： mφ(q)=1(mod q) (q)=1(mod q). 因此，对于任何 因此，对于任何k，总有： mk(q-1)=1(mod q) mk(p-1)(q-1)=(1)k(p-1)=1(mod q) 即：mkφ(n)=1(mod q) 或 1= mkφ(n) 即：m 1(mod q) 或 1 m +h q* 其中h是某个整数, 由假定m=s*p,得： s*p= mkφ(n) *s*p+s*p*h*q, m= mkφ(n)+1+s*h*p*q m=mkφ(n)+1+s*h*n, +s*h*n,即得： mkφ(n)+1 ≡m (mod n) 29
RSA的加解密举例说明 7 p=43,q=59,n=p*q=43*59=2539 本(2539)=42*58=2436 取e=13,解方程de=1(mod2436) 得：d=937 若有明文：cyber greatwall 1og2(2539)=11.3,m可小于等于11位 整数 先将明文分块为：cy be rg re at wa1l 编码：】 如利用英文字母表的顺序，即a为00，b为01，。。。，z为 25,将明文数字化得： 022401041706 1704 0019 2200 1111 利用加密得到密文： 1692 0803 1359 19432299 1254 0724 30 CNR@HEU http://machunguang.hrbeu.edu.cn
RSA的加解密举例说明 p=43, q=59, n=p*q=43*59=2539 φ(2539)=42*58=2436 取e=13,解方程 de ≡1 (mod 2436 1 (mod 2436） 得：d=937 若有明文：cyb t ll er grea er greatwall 先将明文分块为： 先将明文分块为：cy be rg cy be rg re at wa ll re at wa ll 如利用英文字母表的顺序，即 如利用英文字母表的顺序，即a为00，b为01，。。。，z为 25，将明文数字化得： 0224 0104 1706 1704 0019 2200 1111 利用加密得到密文： 1692 0803 1359 1943 2299 1254 0724 30 log2(2539)=11.3,m可小于等于11位 整数 编码： 7
RSA的计算技巧 >避免中间结果是天文数字，利用模运算的性质： [(a mod n)*(b mod n)]mod n=(ab)mod n >求me(modn)可通过指数e的快速取模指数算法： t←-0；c←1 fori←-k downto 0 dot←-2×t c←-(cXc)modn if b=1 then t-t+1 c←-(cXm)modn return c 注：e=(bbk.b2b) 31 CNR@HEU http://machunguang.hrbeu.edu.cn
RSA的计算技巧 ¾ 避免中间结果是天文数字 避免中间结果是天文数字，利用模运算的性质 利用模运算的性质： [(a mod n)*(b mod n)]mod n≡(ab) mod n ¾ 求me（mod n）可通过 数指 e的快 模 数算法 快速取模指数算法: t ← 0；c ← 1 for i ← k downto 0 do t ← 2×t c ← (c×c) mod n if bi=1 then t ← t+1 c ← (c×m) mod n return c 注：e=(bkbk-1…b2b1) 31 ( k k 1 2 1)
RSA算法的安全性 0 RSA同态性质 。选择密文攻击 ●针对n分解的攻击 。侧信道攻击 。短明文 。针对RSA算法参数的攻击 32 CNR@HEU http://machunguang.hrbeu.edu.cn
RSA算法的安全性 RSA同态性质 选择密文攻击 针对n分解的攻击 侧信道攻击 短明文 针对RSA算法参数的攻击 算法参数的攻击 32