密碼學(xué) 第8章 公鑰密碼.ppt

《密碼學(xué) 第8章 公鑰密碼.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫(kù)。

1、第8章公鑰密碼數(shù)論簡(jiǎn)介公鑰密碼體制的基本概念RSA算法背包密碼體制Rabin密碼體制橢圓曲線密碼體制數(shù)論簡(jiǎn)介回顧歐拉函數(shù)的求值公式：1970=1×1066+904,gcd(1066,904)1066=1×904+162,gcd(904,162)904=5×162+94,gcd(162,94)162=1×94+68,gcd(94,68)94=1×68+26,gcd(68,26)68=2×26+16,gcd(26,16)26=1×16+10,gcd(16,10)16=1×10+6,gcd(10,6)10=1×6+4,gcd(6,4

2、)6=1×4+2,gcd(4,2)4=2×2+0,gcd(2,0)因此gcd(1970,1066)=2。例:求gcd(1970,1066)。求乘法逆元如果gcd(a,b)=1，則b在moda下有乘法逆元（不妨設(shè)b

3、算法ExtendedEuclid(f,d)中，X3等于前一輪循環(huán)中的Y3，Y3等于前一輪循環(huán)中的X3-QY3，由于Q是Y3除X3的商，因此Y3是前一輪循環(huán)中的Y3除X3的余數(shù)，即X3modY3，可見ExtendedEuclid(f,d)中的X3、Y3與Euclid(f,d)中的X、Y作用相同，因此可正確產(chǎn)生gcd(f,d)。如果gcd(f,d)=1，則在最后一輪循環(huán)中Y3=0，X3=1，因此在前一輪循環(huán)中Y3=1。因?yàn)閒Y1+dY2=Y3成立，即fY1+dY2=1，所以dY2=1+(-Y1)×f，dY2≡1modf，即Y2≡d

4、-1modf。例：求gcd(7,5)。例：求gcd(17,283)。公鑰密碼體制的基本概念公鑰體制加密的框圖其中d是中間結(jié)果，d的終值即為所求結(jié)果。c在這里的作用是表示指數(shù)的部分結(jié)果，其終值即為指數(shù)m，c對(duì)計(jì)算結(jié)果無(wú)任何貢獻(xiàn)，算法中完全可將之去掉。橢圓曲線的兩個(gè)例子