北京大學(xué)網(wǎng)絡(luò)信息安全課件-消息驗(yàn)證與數(shù)字簽名-資料下載頁(yè)
2024-10-19 12:29本頁(yè)面
【正文】 ? 證明 : x2 ? 1 mod p ?p|(x21) ?p|(x+1)(x1) ?p|(x+1),或者 p|(x1) ?x+1=kp,或者 x1=jp, k,j是整數(shù) ?x=kp1,或者 x=jp+1 ?x ? 1 mod p, 或者 x ? 1 mod p ? 若方程 x2 ? 1 mod p存在的解不是 x ? ?1 ，則 P不是素?cái)?shù)。 (2)目前還沒(méi)有一個(gè)高效的辦法，實(shí)際中應(yīng)用最多 Miller and Rabin, WITNESS算法 WITNESS(a,n) 判定 n 是否為素?cái)?shù)， a是某些小于 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) (3)通常的辦法是隨機(jī)選取一個(gè)大的奇數(shù)，然后進(jìn)行素性檢驗(yàn) 1. 隨機(jī)選一個(gè)奇數(shù) n (如 : 可使用偽隨機(jī)數(shù)發(fā)生器 ) 2. 隨機(jī)選擇一個(gè)整數(shù) a n 3. 執(zhí)行概率素?cái)?shù)判定測(cè)試 (如 :用 WITNESS(a,n)),如果 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) （ sieve擴(kuò)展的歐拉算法） 經(jīng)典例子 ? DiffieHellman密鑰交換算法 ? 背包算法 ? RSA算法 ? EIGamal算法 ? 橢圓曲線密碼算法 ECC ElGamal加密算法 ?選擇 : 一個(gè)素?cái)?shù) p,p的一個(gè)原根 r,一個(gè)整數(shù) a,令 s=ra,公開(kāi) {p,r,s},保密 a. ?對(duì)于明文信息 x, 加密 : 秘密選擇隨機(jī)數(shù) k, 計(jì)算 (rk mod p,xsk mod p)作為密文 解密 : (xsk)((rk)a)1 ? xrak?rak ? x mod p ?信息有擴(kuò)張 經(jīng)典例子 ? DiffieHellman密鑰交換算法 ? 背包算法 ? RSA算法 ? EIGamal算法 ? 橢圓曲線密碼算法 ECC 橢圓曲線密碼介紹 ? 1985年 Miller,Koblitz 獨(dú)立提出 y2+axy+by=x3+cx2+dx+e ? 曲線上的點(diǎn)連同無(wú)窮遠(yuǎn)點(diǎn) O的集合 ? 運(yùn)算定義： – 若曲線三點(diǎn)在一條直線上 ,則其和為 O – O用作加法的單位： O = O。 P+O = P – 一條豎直線交 X軸兩點(diǎn) P P2，則 P1+P2+O=O，于是 P1 = P2 – 如果兩個(gè)點(diǎn) Q和 R的 X軸不同，則畫一連線，得到第三點(diǎn)P1，則 Q+R+P1=O，即 Q+R=P1 – 2倍，一個(gè)點(diǎn) Q的兩倍是，找到它的切線與曲線的另一個(gè)交點(diǎn) S，于是 Q+Q=2Q=S 橢圓曲線密碼示意圖 有限域上橢圓曲線 ? 有限域上橢圓曲線 y2?x3+ax+b mod p p是奇素?cái)?shù) ,且 4a3+27b2?0 mod p – 針對(duì)所有的 0= x p，可以求出有效的 y，得到曲線上的點(diǎn) (x,y)，其中 x,y p。記為 Ep(a,b) – Ep(a,b)中也包括 O ? 加法公式 : – P+O=P – 如果 P=(x,y)，則 P+(x,y)=O， (x,y)點(diǎn)是 P的負(fù)點(diǎn)，記為 P。而且 (x,y)也在 Ep(a,b)中 – 如果 P=(x1,y1)， Q=(x2,y2)，則 P+Q=(x3,y3)為 x3=?2x1x2 (mod p) y3=?(x1x3)y1 (mod p) 其中， 如果 P?Q，則 ? = (y2y1)/(x2x1) 如果 P=Q，則 ? = (3x12+a)/(2y1) 橢圓曲線用于加密 ? 找到一個(gè)難題： – 考慮等式 Q=kP，其中 Q、 P屬于 Ep(a,b)， kp – 已知 k和 P，計(jì)算 Q，是容易的 – 已知 Q和 P， 計(jì)算 k，是困難的 ? 選擇 Ep(a,b)的元素 G,使得 G的階 n是一個(gè)大素?cái)?shù) – G的階是指滿足 nG=O的最小 n值 ? 秘密選擇整數(shù) r，計(jì)算 P=rG，然后 – 公開(kāi) (p,a,b,G,P)， P為公鑰 – 保密 r ? 加密 M：先把消息 M變換成為 Ep(a,b)中一個(gè)點(diǎn) Pm – 然后，選擇隨機(jī)數(shù) k，計(jì)算密文 Cm={kG,Pm+kP) – 如果 k使得 kG或者 kP為 O，則要重新選擇 k. ? 解密 Cm: (Pm+kP)r(kG)=Pm+krGrkG=Pm ? 加密信息有擴(kuò)張 橢圓曲線密碼的安全性 ? 難點(diǎn) : 從 P和 kP獲得 k ? 對(duì)橢圓曲線研究的時(shí)間短 ? 橢圓曲線要求密鑰長(zhǎng)度短 ,速度快 ? 對(duì)比 : ECC RSA *Pollard rho分析方法 Key size MIPSYrs 150 ?1010 205 ?1018 234 ?1028 512 3?104 768 2?108 1024 3?1011 1280 1?1014 1536 3?1016 2048 3?1020 ECC密鑰長(zhǎng)度 m RSA密鑰長(zhǎng)度 MIPS年 160 1024 1012 320 5120 1036 600 21000 1078 1200 120210 10168 ECC和 RSA性能比較 DES密鑰長(zhǎng)度 (bit) RSA密鑰長(zhǎng)度 (bit) 56 384 64 512 112 1792 128 2304 DES和 RSA性能比較 (同等強(qiáng)度） 公開(kāi)密鑰密碼總結(jié) ?三類算法 : RSA, ElGamal, ECC ?RSA –基礎(chǔ) : IFP(Integer Factorization Problem) –加 /解密 、 密鑰交換 、 數(shù)字簽名 –使用最廣泛 ?ElGamal –基礎(chǔ) : DLP(Discrete Logarithm Problem) –加 /解密 、 密鑰交換 、 數(shù)字簽名 公開(kāi)密鑰密碼總結(jié) ?ECC –基礎(chǔ) : ECDLP(Elliptic Curve Discrete Logarithm Problem) –加 /解密 、 密鑰交換 、 數(shù)字簽名 –密鑰短 ,速度快 –正在開(kāi)始廣泛應(yīng)用 ?公鑰算法加密解密速度慢 ?誤區(qū) :?公開(kāi)密鑰密碼算法更安全 ?公開(kāi)密鑰密碼使對(duì)稱密鑰密碼過(guò)時(shí)了 ?公鑰的分發(fā)是簡(jiǎn)單和一目了然的 Reference ? 書 – William Stallings, Cryptography and work security: principles and practice, Second Edition. – Bruce Shneier, Applied cryptography: protocols, algorithms, and sourcecode in C, Second Edition. ? 文章 – 密碼學(xué)的新方向 ? Web站點(diǎn) –
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1