現(xiàn)代密碼技術(shù)-資料下載頁
2025-08-15 22:43本頁面
【正文】 n不互素，則公因子必是 p(或者 q) 事實(shí)上，此時(shí) mkφ(n)+1≡m mod p （因?yàn)?m是 p的倍數(shù)） mkφ(n)+1≡m mod q （根據(jù) Fermat小定理） mkφ(n)+1≡m mod pq （由以上兩式） Fermat小定理 ? 若 p是素?cái)?shù)， gcd(a, p) = 1，則 ap1 ≡ 1 mod p，或即 ap ≡ a mod p ? 舉例 251 ≡ 1 mod 5 4111≡ 1 mod 11 ? 證明 ?見備注 RSA實(shí)例 ? 選 p＝ 7， q＝ 17 則 n＝ pq＝ 119 且 φ(n)＝ (p1)(q1)＝ 6 16＝ 96 ? 取 e＝ 5 則 d＝ 77 (5 77＝ 385＝ 4 96＋ 1≡1 mod 96) ? 公鑰（ 5， 119），私鑰（ 77， 119） ? 加密 m＝ 19 則 c＝ me mod n= 195 mod 119 = 66 mod 119 ? 解密 c＝ 66 m＝ cd mod n = 6677mod 119＝ 19 mod 119 RSA考慮 ? 素?cái)?shù) ?必須夠大，否則對手可能很快分解 n ?判定，試除法不可行 ?判定，采用 MillerRabin概率測試方法 ?強(qiáng)素?cái)?shù) ? (p1)/2和 (q1)/2應(yīng)是素?cái)?shù) ? 選取較小的 e（較大的 d） ?e： 65537 ? 快速計(jì)算 X^Y%Z RSA中基本計(jì)算的復(fù)雜度 ? 大數(shù)的加、減計(jì)算復(fù)雜度 ?O(k), O(k) {字加法 } ? K是大數(shù)的字寬度 ? 大數(shù)的乘、除 (逆元 )計(jì)算復(fù)雜度 ?O(k2), O(k2logk) {字乘法 } ? 大數(shù)指數(shù)運(yùn)算 xc mod n ?O(k2logc) {字乘法 } ? 注：都是在 mod n下 模冪乘舉例 ? 97221 % 2022 （都在模 2022意義下） 97221 ＝ 97128+64+16+8+4+1 ＝ 97128 9764 9716 978 974 971 ? 依次計(jì)算 97 97 97 97 9716… 97 128 ?一直平方下去即可，并保持模 2022 ? 如果某次方在 1式出現(xiàn)，則累乘 ?累積開始是 1 * 乘法次數(shù) O(log2Y) 模冪乘算法實(shí)現(xiàn) ? 計(jì)算 W=X^Y mod Z ? W=1 ? For each bit of Y=Y1Y2…Y k ? W=W*W % Z ? if Yi=1 then ? W=W*X % Z ? End for 分解里程碑 十 /二進(jìn)制 日期 MIPS年 方法 ? 69/ 1983 二次篩法 ? 106/ 1989 ? 100/332 April 1991 7 quadratic sieve ? 110/365 April 1992 75 quadratic sieve ? 120/398 June 1993 830 quadratic sieve ? 129/428 April 1994 5000 quadratic sieve ? 130/431 April 1996 5000 generalized number field sieve ? 140 Feb 1999 ? 155 Aug 1999 8400 ? 160 1Apr 2022 ? 174/576 Dec 3,2022 ? 200/663 9 May2022 ↓ 安全性 RSA的安全性取決于模 n的大整數(shù)分解的困難性。因?yàn)槿?p、 q已知，則 φ (n)便可算出，從而可方便的計(jì)算出 d。目前，因子分解的時(shí)間復(fù)雜度為： exp(sqrt(ln(n)lnln(n)))。 由于分解大整數(shù)的能力日益增強(qiáng)，所以對 RSA的安全帶來了一定的威脅。有一些算法已經(jīng)能有效的攻擊 RSA密碼體系，如前向搜索攻擊、公共模攻擊、循環(huán)攻擊、低加密指數(shù)攻擊和定時(shí)攻擊等。目前 768比特長的密鑰已不安全。一般建議使用 1024比特長的密鑰，預(yù)計(jì)要保證20年的安全就要選擇 1280比特的密鑰，增大密鑰帶來了實(shí)現(xiàn)上的難度。而基于離散對數(shù)問題的公鑰密碼在目前技術(shù)下 512比特模長就能夠保證其安全性。特別是橢圓曲線上的離散對數(shù)的計(jì)算要比有限域上的離散對數(shù)的計(jì)算更困難，目前技術(shù)下只需要 160比特模長即可，適合于智能卡的實(shí)現(xiàn)，因而受到國內(nèi)外學(xué)者的廣泛關(guān)注。 對 RSA的主要支持和批評 ? 形式簡單，易于理解，研究深入，支持廣泛 ? 既能用來加密，又可簽名 ? 安全性的模糊（疑為等價(jià)于因子分解的難度） ? 隨機(jī)素?cái)?shù)產(chǎn)生并不容易 ? 運(yùn)算量大，速度受局限，尤其在嵌入式設(shè)備中 使用公鑰傳遞會(huì)話密鑰 ? 公鑰算法太慢 ?對稱算法一般幾十兆字節(jié) /秒 ?1024位 RSA解密約 100多次 /秒 (加密快 10倍以上 ) ? 用 OpenSSL演示速度 ? 只用來傳遞會(huì)話密鑰 ? (假設(shè) A已經(jīng)有 B的公鑰 KeB) ?A發(fā)起和 B的通信 ?A產(chǎn)生會(huì)話密鑰 Ks，并用 KeB加密后傳給 B ?B能用自己的私鑰 KdB解開 ?他人不會(huì)知道 Ks 對稱算法 vs. 公鑰算法 ? 安全性 ? 速度 ?典型相差 1000倍 ? 密鑰管理 ?對稱算法需要額外安全信道 ?公鑰：證書中心 CA ? 混合密碼體制 ?公鑰算法用于簽名和認(rèn)證 ?用公鑰算法傳輸會(huì)話密鑰 ?用會(huì)話密鑰 /對稱算法加密批量 (bulk)數(shù)據(jù) 謝謝！
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號-1