【正文】 其中Kb＝ kG為 Bob公鑰， Kb?＝ k為 Bob私鑰 ? Step 2：將消息 m編碼為 xy形式的點(diǎn) Pm 148 ECC加密 /解密實(shí)現(xiàn) ? Step 3： Alice隨機(jī)選擇一個(gè)正整數(shù) r，對(duì) Pm產(chǎn)生密文 Cm＝ {rG， Pm＋ rKb} ? Step 4： Bob解密 ? CmKb?(rG) ? =Pm+rKbkrG ? =Pm+r(kG)rkG=Pm 149 ECC加密 /解密實(shí)現(xiàn) ? AliceBob(示例） ? Step 1： Bob選擇 E88331(3， 45)， G＝(4,11), Bob私鑰 Kb?＝ K=3, Bob公布公鑰 Kb＝ (413,1808) ? Step 2： Pm=(5,1734) ? Step 3： Alice隨機(jī)選擇一個(gè)正整數(shù) r=8，對(duì) Pm產(chǎn)生密文 : ? Cm＝ {rG， Pm＋ rKb} ={(5415,6321),(6626,3576)} 150 ECC加密 /解密實(shí)現(xiàn) ? Step 4： Bob解密 ? Kb?(rG)=3(5415,6321)=(673,146) ? Cm Kb?(rG)=(6626,3576)(673,146)=(5,1734) 151 密碼學(xué)與安全性總結(jié) 第一階段 80年代 第二階段 90年代 第三階段 90年代后期 信息保密 信息保護(hù) 信息保障 密碼學(xué) 保密學(xué) 加解密技術(shù) 數(shù)據(jù)完整性 數(shù)據(jù)可用性 數(shù)據(jù)可控性 可信環(huán)境 可信計(jì)算 可信存儲(chǔ) 抗抵賴性 + + + + 密碼學(xué) 152 密碼學(xué)與安全性總結(jié)（續(xù)） 密碼學(xué) （數(shù)學(xué)基礎(chǔ)） 編碼學(xué) 分析學(xué) 相輔相成 對(duì)立統(tǒng)一 機(jī)密性、完整性、可鑒別性、抗抵賴性 信息源目標(biāo)服務(wù) 密碼學(xué) 153 密碼實(shí)現(xiàn) 數(shù)學(xué)發(fā)現(xiàn) 密碼算法 算法論證 復(fù)雜性 密鑰配置 算法實(shí)現(xiàn) 密碼協(xié)議 加密解密 破譯技術(shù) 密鑰技術(shù) 密碼應(yīng)用 領(lǐng)域應(yīng)用 密碼系統(tǒng) 密碼管理 密鑰管理 交叉融合 基礎(chǔ) 過(guò)程 結(jié)果 密碼學(xué)與安全性總結(jié)（續(xù)） 154 計(jì)算復(fù)雜性 單向函數(shù) 代數(shù)結(jié)構(gòu) 密碼 分析 古典密碼 公鑰密碼 簽名模式 私鑰密碼 散列 函數(shù) 密碼學(xué)協(xié)議 密鑰管理 操作式 抗抵賴 機(jī)密性 密碼系統(tǒng)的整體設(shè)計(jì)與分析 完整性 鑒別性 密碼學(xué)與安全性總結(jié)（續(xù)） 。對(duì)于給定的 k和 P，計(jì)算 Q比較容易，而對(duì)于給定的 P和 Q，計(jì)算 k比較困難 146 ECC ? 例如： 方程 y2=(x3+9x+17) mod 23所定義的群 E23(9,17)。 PQR = ( P + Q ) R = P + QP + Q136 橢圓曲線密碼學(xué) ? 有限域上橢圓曲線 ?y2?x3+ax+b mod p p是奇素?cái)?shù) ,且 4a3+27b2?0 mod p （構(gòu)成Abel群的條件，證明過(guò)程略） ?y2+xy?x3+ax2+b mod 2m(Galois 域的橢圓曲線） ? 有限域上橢圓曲線 ?y2?x3+ax+b mod p （ 3）加法公式 : P=(xp,yp), Q=(xQ,yQ) 若 xP=xQ且 yP=yQ則 P+Q=O， 否則 P+Q=(xR,yR) xR=?2xPxQ yR=?(xPxR)yP 其中 ?=(yQyP)/(xQxP), 如果 P?Q ?=(3xP2+a)/（ 2yP）， 如果 P=Q （ 1） P+O=P （ 2） P=(x,y)， P＋ (x,y)=O， 其中（ x,y)是 P的負(fù)元－ P (4)重復(fù)相加： nP=P+… +P 按照上述定義構(gòu)成了一個(gè)橢圓曲線上的 Abel群。其中 R是直線 PQ與橢圓曲線的第三個(gè)交點(diǎn)。 綜上， n, +n是群。 （ 3） 幺元 ： ?x∈ n，顯然有 0 +n x = x +n 0， 因此， 0是幺元。 證明 （ 1） 封閉性 ： ?x, y∈ n，令 k = x + y (mod n)，則 0≤k＜ n ? 1，即 k∈ n， 所以封閉性成立。 ? 橢圓曲線并非橢圓 64223312 axaxaxyaxyay ??????ia129 密碼學(xué) ECC ? 群： ? 對(duì)于非空集合 G，其上的一個(gè)二元運(yùn)算（ .）滿足：封閉性、結(jié)合 律 、單位元和可逆性 ? 環(huán)：對(duì)于 R上的兩個(gè)二元運(yùn)算（ +， x）滿足： ? 關(guān)于＋是一個(gè)交換群（群的條件＋交換律） ? 對(duì)于乘法 x滿足： ? 封閉性＋結(jié)合律＋分配律 ? 域：對(duì)于 F上的兩個(gè)運(yùn)算（ +， x）滿足 ? F是一個(gè) 整環(huán)：交換環(huán)＋乘法逆元＋無(wú)零因子 ? 乘法逆元存在 2022/1/4 例：證明 n, +n是群，其中 n是正整數(shù)。 126 密碼學(xué) ECC ? 為什么要提出 ECC？ 同等安全強(qiáng)度下各算法的密鑰長(zhǎng)度 ? RSA 主要問(wèn)題之一： ? 為了保證必要的安全強(qiáng)度，其密鑰必須很長(zhǎng) ? ECC的優(yōu)勢(shì)： ? 在同等安全強(qiáng)度下， ECC所需密鑰比 RSA短 128 密碼學(xué) ECC ? 橢圓曲線指的是由韋爾斯特拉斯（ Weierstrass）方程所確定的平面曲線 。 c2=m yr mod p ? 密文為（ c1， c2 ） 125 解密程序 ? 1）計(jì)算 w=(c1x)1 mod p。 設(shè)整數(shù) m0,(g,m)=1, 如果整數(shù) g對(duì) m的指數(shù)為 ?(m) ，則 g叫做 m的一個(gè) 本原根 . eg: 3是模 7的 本原根 因?yàn)?3 ?(7) ≡ 36 ≡1(mod 7) 一般說(shuō)來(lái)，當(dāng) p為素?cái)?shù)時(shí)，模 p本原根是一個(gè)數(shù)，它的冪 構(gòu)成模 p的同余類 ,比如 3(mod7)的冪運(yùn)算： 31 ≡3,32 ≡2,33 ≡6,34 ≡4,35 ≡5,36 ≡1. 存在 ?(p1)個(gè)模 p的本原根 . 本原根 123 加密和解密 ? （ 1）密鑰生成 ? 1）任選一個(gè)大素?cái)?shù) p，使得 p1有大的素因子； ? 2）任選一個(gè) mod p的 本原根 g ? 3）公布 p和 g。 本原根 由歐拉定理知道：如果 (g,m)＝ 1， m1，則 g?(n) ≡1(mod m) 也就是說(shuō)，如果 (g,m)＝ 1， m1，則存在一個(gè)整數(shù) γ 滿足 gγ ≡1(mod m)。 ? ElGamal可以用于加解密，數(shù)字簽名 ? 其安全性建立在離散對(duì)數(shù)問(wèn)題上。 ? 目前，德國(guó)、日本、法國(guó)、美國(guó)、加拿大等許多西方國(guó)家的密碼學(xué)研究小組和公司已經(jīng) 實(shí)現(xiàn) 了橢圓曲線密碼體制。 ? 已經(jīng)開(kāi)發(fā)出的橢圓曲線標(biāo)準(zhǔn)的文檔有： IEEE P1363 P1363a、 ANSI 、 ISO/IEC14888等 。 RSA：例 2 ? Bob已知 p和 q的值，他用擴(kuò)展歐幾里德算法計(jì)算 d： de ≡1(mod(p 1)(q1))， 得到 d=116402471153538991 然后 Bob計(jì)算： cd ≡ 113535859035722866116402471153538991 ≡30120(mod n) 由此他可以得到最初的信息。 令 a=01 c=03 t=20，則 cat=030120=30120。 其中 e=7 115 RSA: 例 1 5. 計(jì)算 d: de=1 mod 160 且 d 160 ，則 d=23 （因?yàn)?23 7=161= 10 160+1） 6. 公布公鑰 KU={7,187} 7. 保存私鑰 KR={23,17,11} 116 ? 如果待加密的消息 M = 88 (注意： 88187) ? 加密： C = 887 mod 187 = 11 ? 解密 :M = 1123 mod 187 = 88 RSA：例 1 RSA：例 2 ? Bob選擇 p=885320693， q=238855417， 則可以計(jì)算 n=p*q=211463707796206571， 設(shè)加密系數(shù)為 e=9007，將 n和 e發(fā)送給 Alice。 q=11 2. 計(jì)算 n = pq =17 11=187 3. 計(jì)算 248。 113 RSA ? 算法概要： 1. Bob選擇保密的素?cái)?shù) p和 q，并計(jì)算 n=pq； 2. Bob通過(guò) gcd(e,(p1)(q1))=1來(lái)選擇 e； 3. Bob通過(guò) de≡1(mod(p 1)(q1))來(lái)計(jì)算 d； 4. Bob將 n和 e設(shè)為公開(kāi)的， p、 q、 d設(shè)為秘密的； 5. Alice將 m加密為 c ≡m e(mod n)，并將 c發(fā)送給Bob； 6. Bob通過(guò)計(jì)算 m ≡c d(mod n)解密。 ? 其安全性是建立在因式分解的困難性上。 ? 1998年， Vaudenay提出了一種有效的破譯方法破譯了這種體制。 111 Merkle－ Hellman背包公鑰算法 ? 1988年， Chor與 Rivest利用有限域上的算術(shù)性質(zhì)設(shè)計(jì)了一個(gè)背包公鑰密碼體制，稱為 ChorRivest體制。12c .. . nm m m（ 3 ） 從 密 文 求 明 文 等 價(jià) 于 背 包 問(wèn) 題100 Merkle－ Hellman背包公鑰算法 12明 文 ： m ＝ 10110110 ， m ＝ 110010011 2 3 45 6 7 828 32a a aa a a a例 如 ：已 知 : a ＝ ， ＝ ， ＝ 11 ， ＝ 08 ＝ 71 ， ＝ 51 ， ＝ 43 ， ＝ 6712分 別 加 密 得 到 密 文 ： c ＝ 28+11+8+51+43 ＝ 141 c ＝ 28+32+71+47=198101 Merkle－ Hellman背包公鑰算法 ? 問(wèn)題： ? 如何解密？ 102 Merkle－ Hellman背包公鑰算法 ? MH背包公鑰算法是由超遞增序列進(jìn)行變換得到得： 3 1 ( m o d )mm? ? ? ?（ ） 和 互 素 ， 滿 足 ＝11( 2 , 3 , ..., )ijjb b i n?????1 2 ni（ 1 ） 設(shè) 序 列 b ,b ,.. .,b 是 超 遞 增 序 列 ：H( m o d ) , 1 , 2 , . . . ,kkM e r k le e llm a na b m k n????(4) 做 變 換 （ 變 化 ） ：2 nmb ?（ 2 ） 選 取 作 為 模 數(shù)103 Merkle－ Hellman背包公鑰算法 ? MH背包公鑰算法的公鑰和私鑰 ? ?i（ 1 ） 得 到 的 新 序 列 a 作 為 公 鑰1 ( m o d )m? ? ?（ 2 ） 滿 足 ＝ 的 作 為 私 鑰104 Merkle－ Hellman背包公鑰算法 ......b b b? ? ? ?? ? ? ?? ? ? ? ?1 1 2 2 3 3 n n1 1 2 2 3 3 n na m a m a m a mb m m m m1 2 1 2..... . , , .. .,01nncc m m m m m m mnc?? ? ? ? ???1 1 2 2 3 3 n n(5) 假 設(shè) 已 知 ：a m a m a m a m為 的 密 文 ， 其 中 是位 ， 符 號(hào) 串 ， 則 ：這 是 超 遞 增 序 列 的 背 包 問(wèn) 題 ?，F(xiàn)在反過(guò)來(lái)問(wèn)：究竟是哪些物品？ 95 背包問(wèn)題數(shù)學(xué)描述