《第6章RSA密码信息理论密码加密演算法邓安文》由会员分享，可在线阅读，更多相关《第6章RSA密码信息理论密码加密演算法邓安文（31页珍藏版）》请在装配图网上搜索。
1、1.2 20061.3 20061.4 20061.5 2006BobBobD(E(m)mBobE( ) BobD() BobE( ) BobD( ) BobE( ) BobD( ) BobBobE(D(m)mBobE( ) 1.6 20061.7 2006(n)(p1)(q1)ed1 (mod (n)ecE(m)m(mod n)dmD(c)c(mod n)1.8 2006(n)(p1)(q1)2403107440011de10333097(mod 74400)1.9 200626mrsa(17,18,0)21726182611960(n,e)(74951,1033)103e10331022
2、2 22 2 2221cm1196011960(11960 ) )(11960 ) )119606330247290 1196051922 (mod 74951) 次平方。1.10 2006111043d30971110222 2 22 2 222 2 22 2 222221mc5192251922(51922 ) )(51922 ) )(51922 ) )(51922 ) )5192258071 4573249264739775192211960 (mod 74951) 次平方次平方,26m11960(17,18,0)rsa 1.11 2006(n)a1 (mod n)p 1a1 (mod
3、p)1.12 2006ed1 (mod (p1)(q1)eE(m)m(mod n)dD(c)c(mod n)D(E(m)m(mod n)E(D(m)m(mod n)1.13 2006(n)lcm(p1,q1)ecE(m)m(mod n)d1mD (c)c(mod n)1de(mod(n)pdd(mod p1)qdd(mod q1)1qxq(mod p)pqq(n,d,d ,d ,x )pqCRTddqqmD(c)x q(cmod p)(1x q) (cmod q)(mod n)。1.14 2006CRTD(E(m)m(mod n)CRTE(D(m)m(mod n)pqddeeCRTqqD(E(
4、m)x q(m )mod p)(1x q) (m )mod q)(mod n)pedm(mod q)1e(d k (q 1)m(mod q)1ek (q 1)1 k lcm(p 1,q 1)mmm (mod q) CRTD(E(m)0m (mod q)CRTD(E(m)m(mod p)pqpppddeeCRTqqededpppqedD(E(m)x q(m )mod p)(1x q) (m )mod q)(mod n) (1-x p)mx pm (gcd(p,q)=1, x p+x q=1) m (mod p)2e(d+k p) m (modp) 2ek p1 k1cm(p 1,q 1)mmm
5、(modp) (某整数K2）) 1.15 2006mbob cracked rsa 1.16 2006(n,e,d)(24206811682801236799169 ,31,19521622324306440686971);npq(p622354832383, q38895514943)11de(mod (n)(p1)(q1)31(mod 24206811682139986451844)19521622324306440686971。1.17 20062727lognlog24206811682801236799169152714 1312109876542bob cracked rsa (2
6、, 15, 2, 0, 3, 18, 1, 3, 11, 5, 4, 0, 18, 19, 1)227+ 1527 + 227 + 327+1827 + 1 27 + 327 + 11 27+527 + 427 + 1827 + 1927 + 1279927250081200479782m ,BobD( ) d19521622324306440686971sm(mod n)279927250081200479782(mod 24206811682801236799169)17083178691394655337512s170831786913946553375121.18 2006e31ms(
7、mod n)17083178691394655337512(mod 24206811682801236799169)27992725008120047978227=(2, 15, 2, 0, 3, 18, 1, 3, 11, 5, 4, 0, 18, 19, 1) bob cracked rsa ,1.19 20061.20 20062626log n = log782741 = 4(n)(p1)(q1)1d7mod (n)dm144310mod (782741)1.21 2006 782741884782741/863 = 907 = q(n)(p1)(q1)862906780972(n)(
8、p1)(q1)8629067809721d = 7223135 (mod (n)780972)223135144310 126037 (mod 782741) 12603726126037 = 4847 26 + 15= (186 26 + 11) 26 + 15= (7 26 + 4) 26 + 11) 26 + 15= (7, 4, 11, 15)。1.22 2006年份十进制的位数备注19642019744519836922511用二次筛法1989106用二次筛法1994129RSA-129用二次筛法1996130RSA-130用代数数体筛法1999155RSA-155用代数数体筛法1.
9、23 20061.24 2006 (n,e,d)(291999619490932896138040207735768920167,273353824517871327944626733911805527157,60102512763177539335068764336403641333)。x60541520037091837230139960944836511430gcd(x,n)1（2）计算1ed1s28214625863474377432813546698865260701799025836995560747647339280085209590140 ,11syx(mod n)11.25
10、20062ed1s44107312931737188716406773349432630350899512918497780373823669640042604795070 ,22syx(mod n)162916502317468198293896370228560679357 ,（4）因此其中一个因数为2pgcd(y1,n)17623662805242429011而另一个因数为qn/p165686113447468551971.26 2006 6.9 RSA密码系统使用的注意事项BCgcd(e ,e )1BCe se t1CBBCe s e teeststB CBCc c(m) (m)mm(
11、mod n)1.27 2006 112233(n ,e)(443929, 3), C217560(n ,e)(346781, 3), C51086(n ,e)(779917, 3), C363662123121323 123x n n1 mod nx n n1 mod nx n n1 mod n123(x ,x ,x )(217560, 51086, 363662)1 12322133312123c c x n n + c x n n + c x n n (mod n n n ) 2002138753532653326m2002138753532653126037(7,4,11,15)help
12、。1.28 2006循环攻击，Cycling Attackke ee ekee(e ) )c 次此时k1emeuegcd(n,cc)11.29 2006u 绝对不可泄漏RSA密码系统的任何参数：p、q、 一个，这与公开自己的私钥无异。u使用RSA数字签名，建议先使用Hash函数，以防止利用其乘法代数性质伪造数字签名。u绝对不要使用相同的RSA模数犯下相同模数协议的错误。u加密密钥的长度不得少于RSA模数长度的1/4 u另外因为数论家在因数分解上的进展，为防止n被质因数分解，也应考虑以下建议：(n)gcd(p1,q1)1.30 2006 6.10 Wiener低幂次d攻击cdgcd(c,d)12c1xd2d令RSA密码系统中各参数满足下列条件：npqqp2qed1 (mod (n)(p1)(q1)41dn3则存在多项式时间算法可因数分解RSA模数n。1.31 2006 6.11 Rabin密码pq3 (mod 4)2cm(mod n)pmm (mod p)qmm (mod q)p 12q 12mmc(mod p)mmc(mod q)p 1p 124q 1q 124mmc(mod p)mmc(mod q) p 1q 144maq( c)bq( c) (mod n)aqbq1
第6章RSA密码信息理论密码加密演算法邓安文
