【正文】 定義： 橢圓曲線是一個具有兩個變元 x和 y的三次方程，它是滿足： Y2+aXY+bY=X3+cX2+dX+e 的所有點 (X,Y)的集合，外加一個零點或無窮遠點 O 實數(shù)域上的橢圓曲線 ?實數(shù)域上的橢圓曲線是對于固定的 a、 b值，滿足形如方程： Y2=X3+aX+b 的所有點的集合，外加一個零點或無窮遠點 ?其中 a、 b是實數(shù)， X和 Y在實數(shù)域上取值 有限域 GF(p)上的橢圓曲線 ? GF(p)域上的橢圓曲線是對于固定的 a、 b值，滿足形如方程： Y2=X3+aX+b mod(p) 的所有點的集合，外加一個零點或無窮遠點 ?其中 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 的所有點的集合，外加一個零點或無窮遠點 ?其中 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，計算點 :(x2,y2)=d (x1,y1) – 計算 ，恢復(fù)出消息 m 12??? xcmA、 ECELG－橢圓曲線 ElGamal密碼體制 ?任務(wù)： B－＞ A： m ?用戶 A選取隨機數(shù)（私鑰） dA，產(chǎn)生公開密鑰 :PA=dA*G ?用戶 B選取隨機數(shù)（私鑰） dB，并計算公鑰： PB=dB*G ? B計算并向 A發(fā)送： (PB， m+dB*PA) ?用戶 A解密： (m+dB*PA)－ dA*PB＝ m 例子 ? 橢圓曲線 ? 設(shè)用戶 A的私鑰為 7，則公鑰為： 1)設(shè)用戶 B的消息 m編碼后為 ，且選取了隨機數(shù) 2)用戶 B計算： ， 3） B向 A發(fā)送消息： 4)用戶 A計算： 5)用戶 A計算： ? ? 2213:22,13 3223 ??? xxyE ? ?5,10?G? ?21,177 ?GP A＝? ?1,11?mP13＝Bd? ? ? ?5,165,1013 ??Gd B ? ? ? ?18,2021,1713 ??AB Pd? ? ? ? ? ?19,1818,201,11 ???? ABm PdP? ? ? ?? ?19,18,5,16? ? ? ?18,205,167 ?? ? ? ? ? ? ? ? ? ?1,1119,2022,1818,2022,18 ?????B、 ECMO－橢圓曲線 MasseyOmura密碼體制 ?設(shè) E是有限域 GF(p)上的橢圓曲線， N為橢圓曲線的階， 是明文空間到橢圓曲線群的嵌入 ?用戶 A選取一個公鑰 ，私鑰 ，滿足。由于模運算的對稱性，可以證明， 在確定的范圍內(nèi)，加密和解密函數(shù)是互逆的。 模 n的長度要求至少是 512比特。 （ 6）