【正文】 署算法 Sigk ∈ S且有對應(yīng)的驗證算法 Verk∈ V,對每一個 Sigk和 Verk滿足條件：任意一個簽名： 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為保密的（私鑰） ? 對 x∈ M, Bob要對 x簽名，取 k∈ K： ? Sigk(x)? xd(mod n)?y(mod n) ? Verk(x,y)=真 x?ye(mod n) RSA的數(shù)字簽名方案 ? 假設(shè) Alice想把簽了名的消息加密送給 Bob：對明文 x， Alice計算對 x的簽名 y=SigAlice(x)，然后用 Bob的公鑰加密函數(shù) eBob,算出z=eBob(x,y) ,Alice 將 z傳給 Bob ? Bob收到 z后，先解密： dBob(z)=dBobeBob(x,y)=(x,y) ? 后檢驗： ? VerAlice(x,y)= 真？ ? 問題：若 Alice首先對消息 x進(jìn)行加密 ,z=eBob(x),然后再簽名， y=SigAlice(eBob(x)),結(jié)果如何呢？ ? Alice 將（ z,y)傳給 Bob， Bob先將 z解密，獲取 x。 6－ 4 橢圓曲線密碼體制 ECC ?橢圓曲線密碼體制以高效性著稱 ?由 Neal Koblitz和 Victor Miller在 1985年分別提出 ? ECC的安全性基于橢圓曲線離散對數(shù)問題的難解性 ?密鑰長度大大地減小 ?是目前已知公鑰密碼體制中每位提供加密強度最高的一種體制 橢圓曲線的概念和分類 定義： 橢圓曲線是一個具有兩個變元 x和 y的三次方程，它是滿足： Y2+aXY+bY=X3+cX2+dX+e 的所有點 (X,Y)的集合，外加一個零點或無窮遠(yuǎn)點 O 實數(shù)域上的橢圓曲線 ?實數(shù)域上的橢圓曲線是對于固定的 a、 b值，滿足形如方程： Y2=X3+aX+b 的所有點的集合，外加一個零點或無窮遠(yuǎn)點 ?其中 a、 b是實數(shù)， X和 Y在實數(shù)域上取值 有限域 GF(p)上的橢圓曲線 ? GF(p)域上的橢圓曲線是對于固定的 a、 b值，滿足形如方程： Y2=X3+aX+b mod(p) 的所有點的集合，外加一個零點或無窮遠(yuǎn)點 ?其中 a、 b， X和 Y在 GF(p)域上取值 Hasse定理 ?如果 E是定義在 GF(p)域上的橢圓曲線， N是 E上的點的個數(shù)，則： ppN 2)1( ???例子 有限域 GF(2m)上的橢圓曲線 ?是對于固定的 a、 b值，滿足形如方程： Y2+XY=X3+aX2+b 的所有點的集合，外加一個零點或無窮遠(yuǎn)點 ?其中 a、 b， X和 Y在 GF(2m)域上取值 ? GF(2m)域上的元素是 m位的串 例子 ?由多項式 定義的域 GF（ 24） ?基元為 g=(0010)， g的各冪分別是 1)( 4 ??? xxxfg0=(0001) g1=(0010) g2=(0100) g3=(1000) g4=(0011) g5=(0110) g6=(1100) g7=(1011) g8=(0101) g9=(1010) g10=(0111) g11=(1110) g12=(1111) g13=(1101) g14=(1001) g15=(0001) 例子（續(xù)） ? 考慮橢圓曲線： ? 點 (g5, g3)滿足該方程 ? ∵ (g3)2 + g5 g3 = (g5) 3 + g4 (g5) 2 + 1 g6 + g8 = g15 +g14 + 1 (1100) + (0101) = (0001) + (1001) + (0001) (1001) = (1001) 12432 ???? xgxxyy滿足該方程的點集 橢圓曲線的加法規(guī)則 ? Abel群 ： ? 加法規(guī)則 1： ? 加法規(guī)則 2： ? 加法規(guī)則 3：互逆點 ? 加法規(guī)則 4：加法交換律 ? 加法規(guī)則 5：加法結(jié)合律 ? 加法規(guī)則 6： ? 加法規(guī)則 7 ： 0)( m o d274 23 ?? pbaOOO ??POP ??OQP ??PP ???RQPRQP ????? )()(? ? ? ? ? ?332211 , yxSyxQyxP ?＋2123 xxx ???? 1313 )( yxxy ??? ? 12 12 xx yy ????? ? ),(),(2),(, 33111111 yxQyxPyxPyxP ???123 2xx ??? 1313 )( yxxy ??? ?12123 y ax ???橢圓曲線的加法規(guī)則（續(xù)） ? GF（ 2m)域 ?加法規(guī)則 3 ′ ： 如果 ，則 ?加法規(guī)則 6′ ： ?加法規(guī)則 7′ ： ? ? ? ? ? ?332211 , yxSyxQyxP ?＋axxx ????? 2123 ??13313 )( yxxxy ???? ? 1212xxyy????? ? ),(),(2),(, 33111111 yxQyxPyxPyxP ???3213 *)1( xxy ??? ?ax ??? ?? 231121xyx ???? ?,P x y? ? ?,P x x y? ? ?加法規(guī)則的幾何描述 兩個定義 ?標(biāo)量乘 ?階 – P是橢圓曲線 E上的一點，若存在最小的正整數(shù) n，使得 nP=O，則稱 n是點 P的階 ?? ??? ?? ?mPPPmP ????例子 ? GF（ 23）上橢圓曲線 ： ? 設(shè)： ? 求 P1＋ P2和 2P1 132 ??? xxy? ?10,31 ?P ? ?7,92 ?P112 )23mod1()23( mo d2139 1071212 ??????????? xx yy?1723m o d1099311 22123 ??????? －xxx ?2023m o d1 4 410)173(11)( 1313 ???????? yxxy ?64244 23m od123m od20502 23m od28102 1)3(323 2121 ???????? ＋＝y(tǒng)ax?723m o d3032)6(2 2123 ??????? xx ?1223m o d3410)73(6)( 1313 ??????? －－yxxy ?橢圓曲線密碼體制 ?橢圓曲線離散對數(shù)問題 – 已知橢圓曲線 E和點 P，隨機生成一個整數(shù) d，容易計算 :Q=d*P，但給定 Q和 P,計算 d就相對困難 系統(tǒng)的建立 ?選取 : – 一個基域 GF(p) – 定義在該基域上的橢圓曲線 Ep(a,b) – E上的一個擁有素數(shù)階 n的點 P ?其中有限域 GF(p) ，橢圓曲線參數(shù) a,b，點 P和階 n都是公開信息 密鑰的生成 ? 在區(qū)間 [1,n1]中隨機選取一個整數(shù) d ? 計算 :Q=d*P ? 實體的 – 公開密鑰 :點 Q – 實體的私鑰 :整數(shù) d 加密過程 ? 待發(fā)送消息： A－＞ B： M 1. 查找 B的公開密鑰： Q 2. 將消息 M表示成一個域元素 :m 3. 在區(qū)間 [1, n1]中隨機選取一個整數(shù) k 4. 計算點 :(x1,y1)=kP 5. 計算點 :(x2,y2)=kQ，如果 x2=0，則返回第 (3)步 6. 計算 :c=mx2 7. 傳送加密數(shù)據(jù) (x1,y1,c)給 B 解密過程 ?當(dāng)實體 B解密從 A收到的密文 (x1,y1,c)時，執(zhí)行步驟： – 使用私鑰 d