公鑰密碼體制及典型算法橢圓曲線密碼體制

1、1橢圓曲線密碼體制橢圓曲線密碼體制 由由Neal Koblitz和和Victor Miller在在1985年分別提出年分別提出 安全性基于安全性基于橢圓曲線域離散對(duì)數(shù)問橢圓曲線域離散對(duì)數(shù)問題的難解性題的難解性 是目前已知公鑰密碼體制中每位提是目前已知公鑰密碼體制中每位提供加密強(qiáng)度最高的一種體制供加密強(qiáng)度最高的一種體制2ECC與與RSA和分組密碼的密鑰比較和分組密碼的密鑰比較在安全性能大致相當(dāng)?shù)那闆r下在安全性能大致相當(dāng)?shù)那闆r下 3一、橢圓曲線及其運(yùn)算一、橢圓曲線及其運(yùn)算定義定義 橢圓曲線是兩個(gè)變?cè)獧E圓曲線是兩個(gè)變?cè)獂、y滿足形如滿足形如三次方程三次方程 y2+axy+by=x3+cx2+dx+e

2、 的所有點(diǎn)的所有點(diǎn)(x,y)的集合，外加一個(gè)的集合，外加一個(gè)零點(diǎn)零點(diǎn)或或無窮遠(yuǎn)點(diǎn)無窮遠(yuǎn)點(diǎn)O。 Elliptic curves are not ellipses. They are so named because they are described by cubic equations, similar to those calculating the circumference of an ellipse. 41 1、實(shí)數(shù)域上的橢圓曲線、實(shí)數(shù)域上的橢圓曲線 實(shí)數(shù)域上的橢圓曲線實(shí)數(shù)域上的橢圓曲線E(a,b)是對(duì)于固定的是對(duì)于固定的a、b值，滿足形如三次方程值，滿足形如三次方程 y2=x3+a

3、x+b 的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無窮遠(yuǎn)點(diǎn)的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無窮遠(yuǎn)點(diǎn)O 其中其中a、b是實(shí)數(shù)，是實(shí)數(shù)，x和和y在實(shí)數(shù)域上取值在實(shí)數(shù)域上取值324270ab構(gòu)成阿貝爾群構(gòu)成阿貝爾群 5E（-1,0） E（1,1） 實(shí)數(shù)域橢圓曲線的幾何圖形實(shí)數(shù)域橢圓曲線的幾何圖形互逆點(diǎn)互逆點(diǎn)互逆點(diǎn)互逆點(diǎn)6幾何定義幾何定義 如果橢圓曲線上的三個(gè)點(diǎn)位于一條直線上，如果橢圓曲線上的三個(gè)點(diǎn)位于一條直線上，那么它們的和為那么它們的和為O。 實(shí)數(shù)域橢圓曲線的運(yùn)算規(guī)則實(shí)數(shù)域橢圓曲線的運(yùn)算規(guī)則()()PQPQO互逆點(diǎn)互逆點(diǎn)()()PQPQ點(diǎn)和點(diǎn)基本運(yùn)算為加法運(yùn)算基本運(yùn)算為加法運(yùn)算7加法單位元為加法單位元為O O，

4、滿足，滿足實(shí)數(shù)域橢圓曲線的運(yùn)算規(guī)則實(shí)數(shù)域橢圓曲線的運(yùn)算規(guī)則互逆點(diǎn)互逆點(diǎn)P、Q，滿足，滿足OOPOPPQPQO ,),),)PPQQRRP xyQ xyR xy（、（、（PQPQxxyy 且且8實(shí)數(shù)域橢圓曲線的運(yùn)算規(guī)則實(shí)數(shù)域橢圓曲線的運(yùn)算規(guī)則非互逆點(diǎn)非互逆點(diǎn)P、Q的加法規(guī)則的加法規(guī)則,),),)PPQQRRP xyQ xyR xy（、（、（,),),)PPQQRRP xyQ xyR xy（2RPQxxx()RPRPyxxyQPQPyyxx若若=，則，則R為為無窮遠(yuǎn)點(diǎn)無窮遠(yuǎn)點(diǎn)O9實(shí)數(shù)域橢圓曲線的運(yùn)算規(guī)則實(shí)數(shù)域橢圓曲線的運(yùn)算規(guī)則,),),)PPQQRRP xyQ xyR xy（、（、（,),)2,)

5、,)PPPPPPRRP xyP xyP xyR xy（22RPxx()RPRPyxxy232PPxay倍點(diǎn)規(guī)則倍點(diǎn)規(guī)則若若=，則，則R為為無窮遠(yuǎn)點(diǎn)無窮遠(yuǎn)點(diǎn)O10實(shí)數(shù)域橢圓曲線的運(yùn)算規(guī)則實(shí)數(shù)域橢圓曲線的運(yùn)算規(guī)則交換律交換律,),),)PPQQRRP xyQ xyR xy（、（、（PQQP結(jié)合律結(jié)合律PQRPQR（）（）標(biāo)量乘法標(biāo)量乘法mPPPPm m個(gè)個(gè)0 PO()()mPmP 11實(shí)數(shù)域橢圓曲線運(yùn)算舉例實(shí)數(shù)域橢圓曲線運(yùn)算舉例 例例 5 已知實(shí)數(shù)域的橢圓曲線已知實(shí)數(shù)域的橢圓曲線E(-1,0)為為 ，其上的兩個(gè)點(diǎn)分別為，其上的兩個(gè)點(diǎn)分別為 和和 。（1） 計(jì)算計(jì)算 。（2） 計(jì)算計(jì)算 。（3） 計(jì)

6、算計(jì)算 。（4） U點(diǎn)和點(diǎn)和R點(diǎn)是什么關(guān)系？點(diǎn)是什么關(guān)系？23yxx(1,0)P (2,6)Q PQR2QSPQU12實(shí)數(shù)域橢圓曲線運(yùn)算舉例實(shí)數(shù)域橢圓曲線運(yùn)算舉例 例例 5 已知實(shí)數(shù)域的橢圓曲線已知實(shí)數(shù)域的橢圓曲線E(-1,0)為為 ， 和和 。（1） 計(jì)算計(jì)算 。23yxx(1,0)P (2,6)Q PQR6062 1QPQPyyxx22( 6)123RPQxxx ()6(1 3)02 6RPRPyxxy (1,0)(2, 6)(3, 2 6)PQR13實(shí)數(shù)域橢圓曲線運(yùn)算舉例實(shí)數(shù)域橢圓曲線運(yùn)算舉例 例例 5 已知實(shí)數(shù)域的橢圓曲線已知實(shí)數(shù)域的橢圓曲線E(-1,0)為為 ， 和和 。（2） 計(jì)算

7、計(jì)算 。23yxx(1,0)P (2,6)Q 2QS2233 21112262 6QQxay2211121252()2 2424242 6SQxx 1125112335()(2)66624242882 62 6SQRQyxxy 25352 (2,6)(,6)24288QS14實(shí)數(shù)域橢圓曲線運(yùn)算舉例實(shí)數(shù)域橢圓曲線運(yùn)算舉例 例例 5 已知實(shí)數(shù)域的橢圓曲線已知實(shí)數(shù)域的橢圓曲線E(-1,0)為為 ， 和和 。（3） 計(jì)算計(jì)算 。23yxx(1,0)P (2,6)Q PQU()PQUPQ (,)(2,6)QQQxy6062 1QPQPyyxx 22(6)1 23UPQxxx ()6(1 3)02 6UP

8、UPyxxy (1,0)(2, 6)(3,2 6)PQU15實(shí)數(shù)域橢圓曲線運(yùn)算舉例實(shí)數(shù)域橢圓曲線運(yùn)算舉例 例例 5 已知實(shí)數(shù)域的橢圓曲線已知實(shí)數(shù)域的橢圓曲線E(-1,0)為為 ， 和和 。（4） U點(diǎn)和點(diǎn)和R點(diǎn)是什么關(guān)系？點(diǎn)是什么關(guān)系？23yxx(1,0)P (2,6)Q (1,0)(2, 6)(3,2 6)PQU(1,0)(2, 6)(3, 2 6)PQRURxxURyy 互逆點(diǎn)關(guān)系互逆點(diǎn)關(guān)系 結(jié)論無普遍意義！結(jié)論無普遍意義！162、素域素域GF(p)GF(p)上的橢圓曲線上的橢圓曲線 GF(p)域上的橢圓曲線域上的橢圓曲線E(a,b)是對(duì)于固定的是對(duì)于固定的a、b值，滿足形如三次方程值，滿

9、足形如三次方程y2=x3+ax+b (mod p) 的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無窮遠(yuǎn)點(diǎn)的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無窮遠(yuǎn)點(diǎn)O 其中其中a、b、x和和y在在GF(p)域上取值域上取值 這類橢圓曲線通常也用這類橢圓曲線通常也用 來表示來表示 構(gòu)成橢圓群),(mod0)274(23baEpbap( , )pEa b17HasseHasse定理定理 如果如果 是定義在是定義在GF(p)域上的橢域上的橢圓曲線，圓曲線，N是是 上的點(diǎn)的個(gè)數(shù)，上的點(diǎn)的個(gè)數(shù)，則：則： ppN2) 1( , )pEa b( , )pEa b18 圖圖 橢圓曲線上點(diǎn)的分布橢圓曲線上點(diǎn)的分布19與實(shí)數(shù)域相同，但所有的運(yùn)算都是

10、與實(shí)數(shù)域相同，但所有的運(yùn)算都是 mod p 運(yùn)算的結(jié)果。運(yùn)算的結(jié)果。分?jǐn)?shù)運(yùn)算時(shí)，既可以進(jìn)行分?jǐn)?shù)約簡(jiǎn)，分?jǐn)?shù)運(yùn)算時(shí)，既可以進(jìn)行分?jǐn)?shù)約簡(jiǎn)，也可以對(duì)分子、分母進(jìn)行模運(yùn)算，以也可以對(duì)分子、分母進(jìn)行模運(yùn)算，以便整除。便整除。 素域素域GF(p) 上橢圓曲線的運(yùn)算規(guī)則上橢圓曲線的運(yùn)算規(guī)則20素域素域GF(p) 上橢圓曲線的運(yùn)算舉例上橢圓曲線的運(yùn)算舉例 例例 6 素域素域GF(23) 上的橢圓曲線上的橢圓曲線為為 ，其上的兩個(gè)點(diǎn)分別為，其上的兩個(gè)點(diǎn)分別為 和和 。（1） 計(jì)算計(jì)算 。（2） 計(jì)算計(jì)算 。（3） 計(jì)算計(jì)算 。（4） U點(diǎn)和點(diǎn)和R點(diǎn)是否互逆點(diǎn)？點(diǎn)是否互逆點(diǎn)？231yxx(3,10)P (9,7)Q

11、 PQR2PSPQU23(1,1)E21素域素域GF(p) 上橢圓曲線的運(yùn)算舉例上橢圓曲線的運(yùn)算舉例 例例 6 素域素域GF(23) 上的橢圓曲線上的橢圓曲線為為 ， 和和 。（1） 計(jì)算計(jì)算 。231yxx(3,10)P (9,7)Q PQR23(1,1)E7 10320103311 (mod 23)936633QPQPyyxx22(11)3 9121 1210917 (mod 23)RPQxxx ()11 (3 17) 1016420 (mod 23)RPRPyxxy (3,10)(9,7)(17,20)PQR22素域素域GF(p) 上橢圓曲線的運(yùn)算舉例上橢圓曲線的運(yùn)算舉例 例例 6 素域

12、素域GF(23) 上的橢圓曲線上的橢圓曲線為為 ， 和和 。（2） 計(jì)算計(jì)算 。231yxx(3,10)P (9,7)Q 2PS23(1,1)E2233 312851246 (mod 23)22 10202044PPxay222(6)2 3366307 (mod 23)SPxx ()6 (37) 103412 (mod 23)SPRPyxxy 2 (3,10)(7,12)PS23素域素域GF(p) 上橢圓曲線的運(yùn)算舉例上橢圓曲線的運(yùn)算舉例 例例 6 素域素域GF(23) 上的橢圓曲線上的橢圓曲線為為 ， 和和 。（3） 計(jì)算計(jì)算 。231yxx(3,10)P (9,7)Q PQU23(1,1)

13、E()PQUPQ (,)(9, 7)(9,16) (mod 23)QQQxy16 1061936QPQPyyxx221391112 (mod 23)UPQxxx ()1 (3 12) 10194 (mod 23)UPUPyxxy (3,10)(9,7)(12,4)PQU24素域素域GF(p) 上橢圓曲線的運(yùn)算舉例上橢圓曲線的運(yùn)算舉例 例例 6 素域素域GF(23) 上的橢圓曲線上的橢圓曲線為為 ， 和和 。（4） U點(diǎn)和點(diǎn)和R點(diǎn)是否互逆點(diǎn)？點(diǎn)是否互逆點(diǎn)？231yxx(3,10)P (9,7)Q 23(1,1)E(3,10)(9,7)(12,4)PQU(3,10)(9,7)(17,20)PQRU

14、RxxURyy U點(diǎn)和點(diǎn)和R點(diǎn)不是互逆點(diǎn)點(diǎn)不是互逆點(diǎn)253 3、有限域、有限域GF(2GF(2n n) )上的橢圓曲線上的橢圓曲線 是對(duì)于固定的是對(duì)于固定的a、b值，滿足形如三次方程值，滿足形如三次方程 y2+xy=x3+ax2+b 的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無窮遠(yuǎn)點(diǎn)的所有點(diǎn)的集合，外加一個(gè)零點(diǎn)或無窮遠(yuǎn)點(diǎn)O 其中其中a、b、x和和y在在GF(2n)域上取值域上取值 GF(2n)域上的元素是域上的元素是n位的串，共位的串，共2n個(gè)元素個(gè)元素 常用常用 表示，表示，b0時(shí)構(gòu)成阿貝爾群時(shí)構(gòu)成阿貝爾群 實(shí)際應(yīng)用中，實(shí)際應(yīng)用中，n n必須足夠大，至少必須足夠大，至少n=160(n=160(相當(dāng)于相當(dāng)

15、于1024 bits RSA)1024 bits RSA)2( , )nEa b26例子例子 例例 7 由不可約多項(xiàng)式由不可約多項(xiàng)式 定義的定義的有限域有限域 有一個(gè)生成元有一個(gè)生成元 。（1）列出）列出 上所有的非上所有的非0元素，表明它們與元素，表明它們與生成元生成元 的關(guān)系，并驗(yàn)證的關(guān)系，并驗(yàn)證 。（2）若橢圓曲線是）若橢圓曲線是 即即 ，檢驗(yàn)，檢驗(yàn) 是否為是否為 上的點(diǎn)，并列出上的點(diǎn)，并列出 上所有非上所有非0點(diǎn)的坐標(biāo)值，畫出點(diǎn)的坐標(biāo)值，畫出 上點(diǎn)的分布圖。上點(diǎn)的分布圖。4( )1m xxx (0010)gx4(2 )GFg14(1001)g4402(,)Egg23421yxyxg x

16、913(,)gg4402(,)Egg4402(,)Egg4402(,)Egg4(2 )GF27例子例子 例例 7 由不可約多項(xiàng)式由不可約多項(xiàng)式 定義的定義的有限域有限域 有一個(gè)生成元有一個(gè)生成元 。（1）列出）列出 上所有的非上所有的非0元素，元素，表明它們與表明它們與生成元生成元 的關(guān)系，并驗(yàn)證的關(guān)系，并驗(yàn)證 。4( )1m xxx (0010)gx4(2 )GFg14(1001)gg0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111) g11=(

17、1110)g12=(1111) g13=(1101) g14=(1001) g15=(0001)4(2 )GF28例子例子 例例 7 （1）驗(yàn)證）驗(yàn)證 。4( )1m xxx (0010)gx14(1001)g1414gx14(1001)g29例子例子 例例 7 由不可約多項(xiàng)式由不可約多項(xiàng)式 定義的定義的有限域有限域 有一個(gè)生成元有一個(gè)生成元 。（2）若橢圓曲線是）若橢圓曲線是 即即 ，檢驗(yàn)檢驗(yàn) 是否為是否為 上的點(diǎn)，并列出上的點(diǎn)，并列出 上所有非上所有非0點(diǎn)的坐標(biāo)值，畫出點(diǎn)的坐標(biāo)值，畫出 上點(diǎn)的分布圖。上點(diǎn)的分布圖。4( )1m xxx (0010)gx4402(,)Egg23421yxyx

18、g x913(,)gg4402(,)Egg4402(,)Egg4402(,)Egg211ngmod (21)nxxgg213 29132622117()(1110)(1011)(0101)yxyggggggg3429349227221271()()111(1111)(1011)(0001)(0101)xg xggggggg 是是4(2 )GF30例子例子 例例 7 由不可約多項(xiàng)式由不可約多項(xiàng)式 定義的定義的有限域有限域 有一個(gè)生成元有一個(gè)生成元 。（2）若橢圓曲線是）若橢圓曲線是 即即 ，檢驗(yàn)，檢驗(yàn) 是否為是否為 上的點(diǎn)，并上的點(diǎn)，并列出列出 上所有非上所有非0點(diǎn)的點(diǎn)的坐標(biāo)值坐標(biāo)值，畫出，畫出

19、 上點(diǎn)的上點(diǎn)的分布圖分布圖。4( )1m xxx (0010)gx4402(,)Egg23421yxyxg x913(,)gg4402(,)Egg4402(,)Egg4402(,)Egg4(2 )GF3132十進(jìn)制十進(jìn)制描述描述例例 7的的坐標(biāo)值坐標(biāo)值33GF(2GF(2n n) )域上橢圓曲線的運(yùn)算規(guī)則域上橢圓曲線的運(yùn)算規(guī)則在在n次不可約多項(xiàng)式次不可約多項(xiàng)式m(x)定義的有限域中定義的有限域中進(jìn)行進(jìn)行運(yùn)算要點(diǎn)：運(yùn)算要點(diǎn)：加法：按位模加法：按位模2加加乘法、除法：使用生成元乘法、除法：使用生成元注意注意 ， mod (21)nxxgg2101ngg342( , )nEa bGF(2GF(2n

20、n) )域上橢圓曲線的運(yùn)算規(guī)則域上橢圓曲線的運(yùn)算規(guī)則,),),)PPQQRRP xyQ xyR xy（、（、（加法單位元為加法單位元為 ，滿足，滿足 OOOPOP互逆點(diǎn)互逆點(diǎn)P、Q，滿足，滿足 PQPQO PQPPQxxxyy且且352( , )nEa bGF(2GF(2n n) )域上橢圓曲線的運(yùn)算規(guī)則域上橢圓曲線的運(yùn)算規(guī)則,),),)PPQQRRP xyQ xyR xy（、（、（非互逆點(diǎn)非互逆點(diǎn) 的加法規(guī)則的加法規(guī)則PQ、,),),)PPQQRRP xyQ xyR xy（2RPQxxxa()RPRRPyxxxyQPQPyyxx若若=，則，則R為無窮遠(yuǎn)點(diǎn)為無窮遠(yuǎn)點(diǎn)O362( , )nEa b

21、GF(2GF(2n n) )域上橢圓曲線的運(yùn)算規(guī)則域上橢圓曲線的運(yùn)算規(guī)則,),),)PPQQRRP xyQ xyR xy（、（、（0)Py （倍點(diǎn)規(guī)則倍點(diǎn)規(guī)則,),)2,),)PPPPPPRRP xyP xyP xyR xy（2Rxa2(1)RPRyxx2PPPxyx若若=，則，則R為無窮遠(yuǎn)點(diǎn)為無窮遠(yuǎn)點(diǎn)O372( , )nEa bGF(2GF(2n n) )域上橢圓曲線的運(yùn)算規(guī)則域上橢圓曲線的運(yùn)算規(guī)則,),),)PPQQRRP xyQ xyR xy（、（、（0)Py （交換律交換律PQQP結(jié)合律結(jié)合律PQRPQR（）（）標(biāo)量乘法標(biāo)量乘法mPPPPm個(gè)0 PO()()mPmP 38444022(

22、,)(3,1)EggE23421yxyxg x511(,)(6,14)Pggg0=(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)4( )1m xxx (0010)2gx4(2 )GF例例 8 8614(,)(12,9)Qgg（1） 計(jì)算計(jì)算P+Q=R 。（2） 計(jì)算計(jì)算2P=S。（3） 計(jì)算計(jì)算P-Q=U。（4） 計(jì)算計(jì)算8P=V 。 4(0011)

23、ag0(0001)bg5(0110)Pxg11(1110)Pyg6(1100)Qxg14(1001)QygPQxxPQ、 是非互逆點(diǎn)39511(,)(6,14)Pggg0=(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)614(,)(12,9)Qgg4(0011)ag（1） 計(jì)算計(jì)算P+Q=R 。141110659(1001)(1110)(0111)(

24、1100)(0110)(1010)QPQPyyggggxxggg2256412(0100)(0010)(0110)(1100)(0011)(1111)RPQxxxagggggg例例 8 823421yxyxg x40511(,)(6,14)Pggg0=(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)614(,)(12,9)Qgg4(0011)ag（1）

25、 計(jì)算計(jì)算P+Q=R 。g12(1111)Rxg51212116131211()()(1100)(1101)(1111)(1110)(0000)0RPRRPyxxxyg gggggggg51161412(,)(,)(,0)P ggQ ggR g例例 8 823421yxyxg x41511(,)(6,14)Pggg0=(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

26、=(0001)614(,)(12,9)Qgg4(0011)ag（2） 計(jì)算計(jì)算2P=S。例例 8 823421yxyxg x252115695()(0110)(1100)(1010)PPPxygggggxg2929418943940()(1000)(1010)(0011)(0001)1Sxagggggggggg 42511(,)(6,14)Pggg0=(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=(1

27、101)g14=(1001)g15=(0001)614(,)(12,9)Qgg4(0011)ag（2） 計(jì)算計(jì)算2P=S。例例 8 823421yxyxg x9(1010)g0(0001)1Sxg 252901096(1)()(1)1(0111)(1010)(0001)(1100)SPSyxxgggggg51162 (,)(1,)P ggSg43511(,)(6,14)Pggg0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g

28、12=(1111)g13=(1101)g14=(1001)g15=(0001)614(,)(12,9)Qgg4(0011)ag（3） 計(jì)算計(jì)算P-Q=U。例例 8 823421yxyxg x()PQUPQ 6QQxxg6148(1100)(1001)(0101)QQQyxyggg68(,)(,)QQQxygg8117715136599(0101)(1110)(1011)(1100)(0110)(1010)QPQPyyggggggxxgggg44511(,)(6,14)Pggg0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(110

29、0)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)614(,)(12,9)Qgg4(0011)ag（3） 計(jì)算計(jì)算P-Q=U。例例 8 823421yxyxg x()PQUPQ 68(,)(,)QQQxygg13g213 213564261356411135649()(1110)(1101)(0110)(1100)(0011)(1010)UPQxxxagggggggggggggggg45511(,)(6,14)Pggg0=(0001)g1=(0010)g2=(0100

30、)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)614(,)(12,9)Qgg4(0011)ag（3） 計(jì)算計(jì)算P-Q=U。例例 8 823421yxyxg x()PQUPQ 68(,)(,)QQQxygg13g9(1010)Uxg135991118229113791110()()(1000)(1011)(1010)(1110)(0111)UPUUPyxxxygggggggggggggg51161

31、4910(,)(,)(,)P ggQ ggU gg46511(,)(6,14)Pggg0=(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)614(,)(12,9)Qgg4(0011)ag（4） 計(jì)算計(jì)算8P=V 。 例例 8 823421yxyxg x82 (2 (2 )VPP51162 (,)(1,)P ggSg82 (2 )VPS2WS2VW2 :

32、WS22661311(0001)(1100)(1101)1SSSxygggx 47511(,)(6,14)Pggg0=(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)614(,)(12,9)Qgg4(0011)ag（4） 計(jì)算計(jì)算8P=V 。 例例 8 823421yxyxg x51162 (,)(1,)P ggSg82 (2 )VPS2WS2VW2

33、:WS13(1101)g21321342613411134()(1110)(1101)(0011)(0000)0Wxaggggggggg2213(1)1(1) 01WSWyxxg62 (1,)(0,1)SgW48511(,)(6,14)Pggg0=(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)614(,)(12,9)Qgg4(0011)ag（4） 計(jì)

34、算計(jì)算8P=V 。 例例 8 823421yxyxg x51162 (,)(1,)P ggSg82 (2 )VPS2WS2VW2:VW62 (1,)(0,1)SgW22010WWWxyx 224( )Vxag 22(1)0(1)VWVyxx 2(0,1)( ,)WV VO49定義定義設(shè)設(shè)G是橢圓曲線上的一點(diǎn)，若存在最小是橢圓曲線上的一點(diǎn)，若存在最小的正整數(shù)的正整數(shù)h，使得，使得 則稱則稱h為為G點(diǎn)的階點(diǎn)的階。hGO由于由于 時(shí)，時(shí)，8VPO511(,)(6,14)Pgg因此，因此，P的階的階h=8。橢圓曲線密碼體制中，要求使用階橢圓曲線密碼體制中，要求使用階h非常非常大的點(diǎn)大的點(diǎn)G作為本原元來

35、生成橢圓曲線子作為本原元來生成橢圓曲線子群群 。這樣的點(diǎn)。這樣的點(diǎn)G稱為基點(diǎn)。稱為基點(diǎn)。 ( , )hE a b50二、橢圓曲線密碼體制二、橢圓曲線密碼體制 1、橢圓曲線離散對(duì)數(shù)問題、橢圓曲線離散對(duì)數(shù)問題 已知橢圓曲線已知橢圓曲線 和曲線上的一點(diǎn)和曲線上的一點(diǎn)G，隨機(jī)，隨機(jī)選擇一個(gè)整數(shù)選擇一個(gè)整數(shù)d，容易計(jì)算，容易計(jì)算 。( , )E a bQdG但給定但給定G和和Q，要計(jì)算，要計(jì)算d卻非常困難。卻非常困難。 dQdGGGGGd個(gè)logGdQ橢圓曲線離散對(duì)數(shù)橢圓曲線離散對(duì)數(shù)51二、橢圓曲線密碼體制二、橢圓曲線密碼體制 2、橢圓曲線密碼體制、橢圓曲線密碼體制 （1）建立系統(tǒng)）建立系統(tǒng) 選一個(gè)基域

36、選一個(gè)基域 （或（或 ），其中），其中p是素是素?cái)?shù)，數(shù)，n是正整數(shù)。是正整數(shù)。 ( )GF p(2 )nGF選一條定義在基域選一條定義在基域 （或（或 ）上的橢圓）上的橢圓曲線曲線 （或（或 ），尋找一個(gè)），尋找一個(gè)h階基點(diǎn)階基點(diǎn)G，滿，滿足以足以G為本原元生成的橢圓子群上的離散對(duì)數(shù)問題是為本原元生成的橢圓子群上的離散對(duì)數(shù)問題是難處理的。難處理的。 ( )GF p(2 )nGF( , )pEa b2( , )nEa b 公開基域、橢圓曲線、基點(diǎn)公開基域、橢圓曲線、基點(diǎn)G及階及階h 。52二、橢圓曲線密碼體制二、橢圓曲線密碼體制 2、橢圓曲線密碼體制、橢圓曲線密碼體制 （2）生成密鑰）生成密鑰

37、公鑰公鑰Q公開，私鑰公開，私鑰d保密保密 。選擇一個(gè)大整數(shù)選擇一個(gè)大整數(shù)d作為私鑰，滿足作為私鑰，滿足 1,1dh根據(jù)基點(diǎn)根據(jù)基點(diǎn)G和私鑰和私鑰d，計(jì)算公鑰，計(jì)算公鑰Q： QdG53二、橢圓曲線密碼體制二、橢圓曲線密碼體制 2、橢圓曲線密碼體制、橢圓曲線密碼體制 （3）加密算法）加密算法 查找查找BobBob的公鑰的公鑰Q QB BAliceAlice發(fā)送消息給發(fā)送消息給BobBob( )imGF p將消息劃分為域元素，滿足將消息劃分為域元素，滿足 ( )imGF p(2 )nimGF隨機(jī)選擇一個(gè)整數(shù)隨機(jī)選擇一個(gè)整數(shù)k，滿足，滿足1,1kh計(jì)算：計(jì)算： (,)RRR xykG(,)SSBS x

38、ykQiiScmx如果如果 ，則返回，則返回 重新選擇一個(gè)整數(shù)重新選擇一個(gè)整數(shù) 0Sx 將將 和密文和密文 發(fā)送給發(fā)送給Bob，R供收方解密用供收方解密用(,)RRR xyic54二、橢圓曲線密碼體制二、橢圓曲線密碼體制 2、橢圓曲線密碼體制、橢圓曲線密碼體制 （4）解密算法）解密算法 ( )imGF pBob收到收到 和密文和密文 (,)RRR xyic用用BobBob自己的私鑰自己的私鑰 ，計(jì)算，計(jì)算Bd(,)(,)SSBRRS xydR xy(,)(,)(,)(,)SSBBGGBGGBRRS xykQkdG xydkG xydR xy使用使用 中的中的 ，從密文，從密文 計(jì)算出明文計(jì)算出

39、明文 (,)SSS xySxicim1iiSmcx55g0=(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)例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（1 1）若）若BobBob選擇私鑰選擇私鑰 ，計(jì)算，計(jì)算BobBob的公鑰的公鑰51,7Bd BQ（2 2）若）若AliceAlice要發(fā)送消

40、息要發(fā)送消息m =m =（0010101000101010）給）給BobBob，給，給出出AliceAlice的加密過程的加密過程（3 3）給出）給出BobBob的解密過程的解密過程56g0=(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)4(0011)ag例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)

41、Egg（1 1）若）若BobBob選擇私鑰選擇私鑰 ，計(jì)算，計(jì)算BobBob的公鑰的公鑰51,7Bd BQ5(0110)Gxg11(1110)Gyg2(,)(,)GGPPG xyP xy252115695()(0110)(1100)(1010)GGGxygggggxg2929418943940()(1000)(1010)(0011)(0001)1Pxagggggggggg 5(,)BBGGQdGG xy 57g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=

42、(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)4(0011)ag例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（1 1）若）若BobBob選擇私鑰選擇私鑰 ，計(jì)算，計(jì)算BobBob的公鑰的公鑰51,7Bd BQ5(0110)Gxg11(1110)Gyg2(,)(,)GGPPG xyP xy9(1010)g0(0001)1Pxg 252901096(1)()(1)1(0111)(1010)(0001)(1100)PGPyxxgggggg51162(,)(1,)G ggPg58

43、g0=(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)4(0011)ag例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（1 1）若）若BobBob選擇私鑰選擇私鑰 ，計(jì)算，計(jì)算BobBob的公鑰的公鑰51,7Bd BQ5(0110)Gxg11(1110)Gyg4(,)2(,)(,)GGPPWWG

44、xyP xyW xy51162(,)(1,)G ggPg22661311(0001)(1100)(1101)1PPPxygggx 21321342613411134()(1110)(1101)(0011)(0000)0Wxaggggggggg59g0=(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)4(0011)ag例例 9 923421yxyxg x

45、8h 511(,)G gg4402(,)Egg3402(,)Egg（1 1）若）若BobBob選擇私鑰選擇私鑰 ，計(jì)算，計(jì)算BobBob的公鑰的公鑰51,7Bd BQ5(0110)Gxg11(1110)Gyg4(,)2(,)(,)GGPPWWG xyP xyW xy51162(,)(1,)G ggPg13(1101)g(0000)0Wx2213(1)1(1)01WPWyxxg62(1,)(0,1)PgW60g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(

46、0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)4(0011)ag例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（1 1）若）若BobBob選擇私鑰選擇私鑰 ，計(jì)算，計(jì)算BobBob的公鑰的公鑰51,7Bd BQ5(0110)Gxg11(1110)Gyg5(,)(,)(,)BBGGWWGGQdGG xyW xyG xy (0,1)WWGxx(,)(,)WWGGW xyG xy點(diǎn)與點(diǎn)不是互逆點(diǎn)不是互逆點(diǎn) 11127551(0001)(1110)(1111)(1011)0(0110

47、)(0110)WGWGyygggxxgg61g0=(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)4(0011)ag例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（1 1）若）若BobBob選擇私鑰選擇私鑰 ，計(jì)算，計(jì)算BobBob的公鑰的公鑰51,7Bd BQ5(0110)Gxg11(1110)

48、Gyg5(,)(,)(,)BBGGWWGGQdGG xyW xyG xy (0,1)W7(1011)g2727541475410()0(1001)(1011)(0110)(0011)(0111)QGWxxxaggggggggg62g0=(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)4(0011)ag例例 9 923421yxyxg x8h 511(,

49、)G gg4402(,)Egg3402(,)Egg（1 1）若）若BobBob選擇私鑰選擇私鑰 ，計(jì)算，計(jì)算BobBob的公鑰的公鑰51,7Bd BQ5(0110)Gxg11(1110)Gyg5(,)(,)(,)BBGGWWGGQdGG xyW xyG xy (0,1)W7(1011)g10(0111)Qxg710101710210()(0)111(0100)(0111)(0001)(0010)QWQQWyxxxygggggggg 51151151110(,)5(,)(0,1)(,)(, )BBdG ggG ggWG ggQgg 63g0=(0001)g1=(0010)g2=(0100)g3=

50、(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)例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（2 2）AliceAlice發(fā)送消息發(fā)送消息m=m=（0010101000101010）給）給BobBob的加密過程的加密過程4(0011)ag5(0110)Gxg11(1110)Gyg 查找查找BobBob的公鑰的公鑰10(, )BQgg 將消息劃分為域

51、元素將消息劃分為域元素 ，滿足，滿足 im4(2 )imGF1(0010)mg92(1010)mg 隨機(jī)選擇一個(gè)整數(shù)隨機(jī)選擇一個(gè)整數(shù)k=3k=3，滿足，滿足 1,7k 計(jì)算密文計(jì)算密文 (,)RRR xykG(,)SSBS xykQiiScmx64g0=(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)例例 9 923421yxyxg x8h 511(,

52、)G gg4402(,)Egg3402(,)Egg（2 2）AliceAlice發(fā)送消息發(fā)送消息m=m=（0010101000101010）給）給BobBob的加密過程的加密過程4(0011)ag5(0110)Gxg11(1110)Gyg 計(jì)算密文計(jì)算密文 (,)32RRR xykGGGGPG 51162(,)(1,)G ggPgP P、G G不是互逆點(diǎn)不是互逆點(diǎn) PGxx（1 1）中計(jì)算得到）中計(jì)算得到65g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=

53、(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（2 2）AliceAlice發(fā)送消息發(fā)送消息m=m=（0010101000101010）給）給BobBob的加密過程的加密過程4(0011)ag5(0110)Gxg11(1110)Gyg 計(jì)算密文計(jì)算密文 (,)RRR xykGPG51162(,)(1,)G ggPg61116651010(1100)(1110)(0010)1(0001)(0110)(0111)PGPGyygggg

54、gxxggg2626541265410()11(1111)(1100)(0001)(0110)(0011)(0111)RPGxxxaggggggggg 66g0=(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)例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（2 2）AliceAlice發(fā)送消息發(fā)送

55、消息m=m=（0010101000101010）給）給BobBob的加密過程的加密過程4(0011)ag5(0110)Gxg11(1110)Gyg 計(jì)算密文計(jì)算密文 (,)RRR xykGPG51162(,)(1,)G ggPg6g10(0111)Rxg610106616106611068()(1)(1100)(0010)(0111)(1100)(0101)RPRRPyxxxyggggggggggggg6511108(1,)(,)(,)PgG ggR gg67g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1

56、011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12=(1111)g13=(1101)g14=(1001)g15=(0001)例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（2 2）AliceAlice發(fā)送消息發(fā)送消息m=m=（0010101000101010）給）給BobBob的加密過程的加密過程4(0011)ag5(0110)Gxg11(1110)Gyg 計(jì)算密文計(jì)算密文 6511108(1,)(,)(,)PgG ggR gg(,)32SSBBBBBS xykQQQQUQ 2BQU21021161

57、010671010()(0111)(1100)(1011)BBBQQQxygggggggxgg10(, )BQgg68g0=(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)例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（2 2）AliceAlice發(fā)送消息發(fā)送消息m=m=（001010100010

58、1010）給）給BobBob的加密過程的加密過程4(0011)ag5(0110)Gxg11(1110)Gyg 計(jì)算密文計(jì)算密文 6511108(1,)(,)(,)PgG ggR gg(,)32SSBBBBBS xykQQQQUQ 7(1011)g2727414740()(1001)(1011)(0011)(0001)1Uxaggggggg 2BQU10(, )BQgg69g0=(0001)g1=(0010)g2=(0100)g3=(1000)g4=(0011)g5=(0110)g6=(1100)g7=(1011)g8=(0101)g9=(1010)g10=(0111)g11=(1110)g12

59、=(1111)g13=(1101)g14=(1001)g15=(0001)例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（2 2）AliceAlice發(fā)送消息發(fā)送消息m=m=（0010101000101010）給）給BobBob的加密過程的加密過程4(0011)ag5(0110)Gxg11(1110)Gyg 計(jì)算密文計(jì)算密文 6511108(1,)(,)(,)PgG ggR gg(,)32SSBBBBBS xykQQQQUQ 7(1011)g01Uxg 210270207576(1)()(1)11(0110)(1011)(0001)(11

60、00)BUQUyxxgggggggg 10162(,)(1,)BQggUg2BQU10(, )BQgg70g0=(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)例例 9 923421yxyxg x8h 511(,)G gg4402(,)Egg3402(,)Egg（2 2）AliceAlice發(fā)送消息發(fā)送消息m=m=（0010101000101010）給