【信息系統(tǒng)】lecture06_公鑰密碼體制-文庫(kù)吧
2025-07-17 16:17 本頁(yè)面
【正文】 , …, Z=26 ( 兩位十進(jìn)制數(shù)表示 ) 1819 0100 0112 0715 1809 2022 1300 (2) 利用加密變換公式 C=mPK mod r, 即 C = 18191223 mod 2867=2756 PK=1223=10011000111 =210+27+26+22+21+20 =1024+128+64+4+2+1 C=18191223 (mod 2867) =18191024 1819128 181964 18194 18192 18191(mod 2867) =2756 2756 2022 0542 0669 2347 0408 1815 選擇兩個(gè)大素?cái)?shù) p和 q，通常要求每個(gè)均大于 10100。 ?計(jì)算 n＝ pｘ q和 z＝ (p－ 1)(q－ 1)。 ?選擇一與 z互素的數(shù)、令其為 d 。 ?找到一個(gè) e滿足 e d＝ 1 (mod z)。 選好這些參數(shù)后，將明文劃分成塊，使得每個(gè)明文報(bào)文P長(zhǎng)度 m滿足 0mn。加密 P時(shí)，計(jì)算 C＝ Pe(mod n)，解密 C時(shí)計(jì)算 P＝ Cd(mod n)。由于模運(yùn)算的對(duì)稱性，可以證明， 在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。 為實(shí)現(xiàn)加密，需要公開 (e, n)，為實(shí)現(xiàn)解密需要 (d, n)。 RSA算法歸納 如何計(jì)算 ab mod n？ 如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？ 如何找到足夠大的素?cái)?shù) p和 q ? 問(wèn)題 …… 要點(diǎn) 1： (a x b) mod n = [(a mod n) x (b mod n)] mod n] 要點(diǎn) 2： a16=aaaaaaaaaaaaaaaa =a2, a4,a8, a16 更一般性的問(wèn)題： am m的二進(jìn)制表示為 bkbk1…b 0, 則 計(jì)算 am mod n am mod n = [? a(2i)] mod n = ?[ a(2i) mod n] bi?0 bi?0 ikiibm 20???如何計(jì)算 ab mod n？ 快速取模指數(shù)算法計(jì)算 abmodn c 0。d 1 for i k downto 0 do c 2 c d (d d)mod n if bi=1 then c c+1 d (d a)mod n return d 快速取模指數(shù)算法：例子 i 9 8 7 6 5 4 3 2 1 0 bi 1 0 0 0 1 1 0 0 0 0 c=0 1 2 4 8 17 35 70 140 280 560 d=1 7 49 157 526 160 241 298 166 67 1 7560mod561=1 Miller and Rabin, WITNESS算法 WITNESS(a,n) 判定 n 是否為素?cái)?shù)， a是某 個(gè) 小于 n的整數(shù) 1. 令 bkbk1…b 0 為 (n1)的二進(jìn)制表示， 2. d ? 1 3. for i ? k downto 0 4. do x ?d 5. d ? (d ? d) mod n 6. if d = 1 and x ? 1 and x ? n1 7. then return TRUE 8. if bi = 1 9. then d ? (d ? a) mod n 10. if d ? 1 11. then return TRUE 12. return FALSE 返回值： TRUE: n一定 不是素?cái)?shù) FALSE: n可能是素?cái)?shù) 應(yīng)用： 隨機(jī)選擇 a n, 計(jì)算 s次， 如果每次都返回 FALSE， 則這時(shí) n是素?cái)?shù)的概率為 (1 1/2s) 如何判定一個(gè)給定的整數(shù)是素?cái)?shù)？ 1. 隨機(jī)選一個(gè)奇數(shù) n (偽隨機(jī)數(shù)發(fā)生器 ) 2. 隨機(jī)選擇一個(gè)整數(shù) a n 3. 執(zhí)行概率素?cái)?shù)判定測(cè)試 ,如果 n 未測(cè)試通過(guò) ,則 拒絕數(shù)值n, 轉(zhuǎn)向步驟 1 4. 如果 n已通過(guò)足夠的測(cè)試 , 則接受 n, 否則轉(zhuǎn)向步驟 2。 說(shuō)明：① 隨機(jī)選取大約用 ln(N)/2的次數(shù)，如 ln(2200)/2=70 ② 好在生成密鑰對(duì)時(shí)才用到，慢一點(diǎn)還可忍受。 ③ 確定素?cái)?shù) p和 q以后，只需選取 e, 滿足gcd(e,?(n))=1, 計(jì)算 d = e1 mod ?(n) （擴(kuò)展的歐拉算法） 如何找到足夠大的素?cái)?shù) p和 q ? ?p和 q在長(zhǎng)度上應(yīng)僅差幾個(gè)數(shù)位，即 p和 q應(yīng)是 1075 到10100 ?（ p1）和（ q1）都應(yīng)包含一個(gè)較大的素?cái)?shù)因子 ?gcd(p1, q1)應(yīng)比較小 ?如果 en 且 dn1/4,則 d可以很容易確定 建 議－ 數(shù)字簽名 方案：一個(gè)簽名方案是由簽署算法與驗(yàn)證算法兩部分構(gòu)成?？捎晌逶P(guān)系組（ M,A,K,S,V）來(lái)描述： (1)M是由一切可能 消息 所構(gòu)成的有限集合； (2)A是一切可能的簽名的有限集合； (3)K為有限密鑰空間，是一些可能密鑰的有限集合； (4)任意 k ∈ K，有簽署算法 Sigk ∈ S且有對(duì)應(yīng)的驗(yàn)證算法 Verk∈ V,對(duì)每一個(gè) Sigk和 Verk滿足條件：任意一個(gè)簽名： Ver(x,y)= ｛ RSA的數(shù)字簽名應(yīng)用 真 若 y=sig(x) 假 若 y?Sig(x) ? 選取整數(shù) n=pq, M=A=Zn ? 定義密鑰集合 K={(n,e,p,q,d)}|n=pq,d*e?1(mod ?(n))} ? n和 e為公鑰； p,q,d為保密的（私鑰） ? 對(duì) x∈ M, Bob要對(duì) x簽名，取 k∈ K： ? Sigk(x)? xd(mod n)?y(mod n) ? Verk(x,y)=真 x?ye(mod n) RSA的數(shù)字簽名方案 ? 假設(shè) Alice想把簽了名的消息加密送給 Bob：對(duì)明文 x， Alice計(jì)算對(duì) x的簽名 y=SigAlice(x)，然后用 Bob的公鑰加密函數(shù) eBob,算出z=eBob(x,y) ,Alice 將 z傳給 Bob ? Bob收到 z后，先解密： dBob(z)=dBobeBob(x,y)=(x,y) ? 后檢驗(yàn)： ? VerAlice(x,y)= 真？ ? 問(wèn)題：若 Alice首先對(duì)消息 x進(jìn)行加密 ,z=eBob(x),然后再簽名， y=SigAlice(eBob(x)),結(jié)果如何呢？ ? Alice 將（ z,y)傳給 Bob， Bob先將 z解密，獲取 x。然后用 VerAlice檢驗(yàn)關(guān)于 x的加密簽名 y ? 一個(gè)潛在問(wèn)題 ：如果 Oscar獲得了這對(duì)（ z,y)，他能用自己的簽名來(lái)替代 Alice的簽名 ? y?=SigOscar(eBob(x)) 簽名消息的加密傳遞問(wèn)題 務(wù)必要先簽名后加密 ! DES和 RSA性能比較（同等強(qiáng)度） 167。 6－ 4 橢圓曲線密碼體制 ECC ?橢圓曲線密碼體制以高效性著稱 ?由 Neal Koblitz和 Victor Miller在 1985年分別提出 ? ECC的安全性基于橢圓曲線離散對(duì)數(shù)問(wèn)題的難解性 ?密鑰長(zhǎng)度大大地減小 ?是目前已知公鑰密碼體制中每位提供加密強(qiáng)度最高的一種體制 橢圓曲線的概念和分類 定義： 橢圓曲線是一個(gè)具有兩個(gè)變?cè)?x和 y的三次方程，它是滿足： Y2+aXY+bY=X3+cX2+dX+e 的所有點(diǎn) (X,Y)的集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn) O 實(shí)數(shù)域上的橢圓曲線 ?實(shí)數(shù)域上的橢圓曲線是對(duì)于固定的 a、 b值，滿足形如方程： Y2=X3+aX+b 的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無(wú)窮遠(yuǎn)點(diǎn) ?其中 a、 b是實(shí)數(shù)， X和 Y在實(shí)數(shù)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1