【正文】 ?用戶 A解密： ? ? 2213:22,13 3223 ??? xxyE? ?1,11?mP13?Ae 17?Ad? ? ? ?21,141,111313 ??? mm PC? ? ? ?1,1121,141717 ??? mm CP ECDSA簽名的生成 ? 消息摘要的生成 – 計(jì)算散列值 e=H(M)160位 ? 橢圓曲線的計(jì)算 1)在區(qū)間 [1,n1]中選擇一個(gè)隨機(jī)整數(shù) k 2)計(jì)算橢圓曲線的點(diǎn) (x1,y1)=kG ? 模計(jì)算 1)轉(zhuǎn)換域元素 x1到整數(shù) 2)設(shè)置 3)如果 r= 0，則轉(zhuǎn)到橢圓曲線計(jì)算的第 1)步 4)計(jì)算 5)如果 s= 0，則轉(zhuǎn)到橢圓曲線計(jì)算的第 2)步 ? 簽名的組成 – M的簽名：（ r,s） 1xnxr mod1?ndreks m o d)(1 ??＝ ECDSA簽名的證實(shí) ? 消息摘要的生成 – 計(jì)算散列值 e’=H(M’) ? 模計(jì)算 – 如果 r’或 s’不是區(qū)間 [1, n1]內(nèi)的整數(shù)，則拒絕該簽名 – 計(jì)算 – 計(jì)算 ? 橢圓曲線計(jì)算 – 計(jì)算橢圓曲線點(diǎn) ，如果是無(wú)窮遠(yuǎn)點(diǎn)，則拒絕該簽名 ? 簽名證實(shí) – 轉(zhuǎn)換域元素 x1到整數(shù) – 計(jì)算 – 如果 r’=v: 簽名是真實(shí)的 – 如果 r’!=v: 簽名是無(wú)效的 nsc mod)( 1???nceu mod1 ?? ncru mo d2 ??QuGuyx 2111 ),( ??nxv mod1?1x例子 ?參考教材 例 6－ 15 例 6－ 16 橢圓曲線密鑰交換協(xié)議（ ECDH） ? 選擇參數(shù) ，確定橢圓曲線 ： ，選擇一個(gè)基點(diǎn) G，要求 G的階 n是一個(gè)足夠大的素?cái)?shù)。 ?對(duì)于消息 m，用戶 B加密消息為 用戶 A解密過程為： mPm?Ae AdNde AA m o d1?， Ne A ??1 Nd A ??1mAm PeC ?mmAAmAm PPdeCdP ＝?? 例子 ?橢圓曲線 ，設(shè)消息 m編碼后的信息為 : 。然后用 VerAlice檢驗(yàn)關(guān)于 x的加密簽名 y ? 一個(gè)潛在問題 ：如果 Oscar獲得了這對(duì)（ z,y)，他能用自己的簽名來(lái)替代 Alice的簽名 ? y?=SigOscar(eBob(x)) 簽名消息的加密傳遞問題 務(wù)必要先簽名后加密 ! DES和 RSA性能比較（同等強(qiáng)度） 167。 ③ 確定素?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)成。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è)試通過 ,則 拒絕數(shù)值n, 轉(zhuǎn)向步驟 1 4. 如果 n已通過足夠的測(cè)試 , 則接受 n, 否則轉(zhuǎn)向步驟 2。 為實(shí)現(xiàn)加密，需要公開 (e, n)，為實(shí)現(xiàn)解密需要 (d, n)。加密 P時(shí)，計(jì)算 C＝ Pe(mod n)，解密 C時(shí)計(jì)算 P＝ Cd(mod n)。 ?找到一個(gè) e滿足 e d＝ 1 (mod z)。 ?計(jì)算 n＝ pｘ q和 z＝ (p－ 1)(q－ 1)。 18192 181964 Q X1 X2 X3 Y1 Y2 Y3 － 1 0 2760 0 1 167 16 0 1 167 1 － 16 88 1 1 － 16 88 － 1 17 79 1 － 1 17 79 2 － 33 9 8 2 － 33 9 － 17 281 7 1 － 17 281 7 19 － 314 2 3 19 － 314 2 － 74 1223 1 用 RSA算法加密與解密的過程： 例：明文 =“RSA ALGORITHM” (1) 明文用數(shù)字表示 空白 =00， A=01, B=02, …, 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 這時(shí)加密速度一般比解密速度快 10倍以上。 為了抵抗現(xiàn)有的整數(shù)分解算法，對(duì) RSA模 n的素因子 p和 q還有如下要求： (1)|pq|很大，通常 p和 q的長(zhǎng)度相同； (2)p1 和 q1分別含有大素因子 p1和 q1 (3)gcd(p11,q11)應(yīng)該很小。建議選擇 p和 q大約是 100位的十進(jìn)制素?cái)?shù)。若分解成功使 n=pq，則可以算出 φ(n)＝（ p1)(q1)，然后由公開的 e，解出秘密的 d。 6－ 3 RSA 由 Rivest,Shamir和 Adleman在 1978年提出來(lái)的 數(shù)學(xué)基礎(chǔ) :Euler定理，并建立在大整數(shù)因子分解的困難性之上 ? 明文空間 P＝密文空間 C=Zn ? 密鑰的生成 – 選擇互異素?cái)?shù) p,q，計(jì)算 n=p*q, ? (n)=(p1)(q1), 選擇整數(shù) e使 (? (n),e)=1,1e? (n),計(jì)算 d,使 d=e1mod ? (n) – 公鑰 Pk={e,n} – 私鑰 Sk={d,n} ? 加密 (用 e,n) – 明文： Mn 密文： C=Me(mod n) ? 解密 (用 d,n) 密文： C 明文： M=Cd（ mod n)