公钥密码体制及典型算法椭圆曲线密码体制

1、1椭圆曲线密码体制椭圆曲线密码体制 由由Neal Koblitz和和Victor Miller在在1985年分别提出年分别提出 安全性基于安全性基于椭圆曲线域离散对数问椭圆曲线域离散对数问题的难解性题的难解性 是目前已知公钥密码体制中每位提是目前已知公钥密码体制中每位提供加密强度最高的一种体制供加密强度最高的一种体制2ECC与与RSA和分组密码的密钥比较和分组密码的密钥比较在安全性能大致相当的情况下在安全性能大致相当的情况下 3一、椭圆曲线及其运算一、椭圆曲线及其运算定义定义 椭圆曲线是两个变元椭圆曲线是两个变元x、y满足形如满足形如三次方程三次方程 y2+axy+by=x3+cx2+dx+e

2、 的所有点的所有点(x,y)的集合，外加一个的集合，外加一个零点零点或或无穷远点无穷远点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、实数域上的椭圆曲线、实数域上的椭圆曲线 实数域上的椭圆曲线实数域上的椭圆曲线E(a,b)是对于固定的是对于固定的a、b值，满足形如三次方程值，满足形如三次方程 y2=x3+a

3、x+b 的所有点的集合，外加一个零点或无穷远点的所有点的集合，外加一个零点或无穷远点O 其中其中a、b是实数，是实数，x和和y在实数域上取值在实数域上取值324270ab构成阿贝尔群构成阿贝尔群 5E（-1,0） E（1,1） 实数域椭圆曲线的几何图形实数域椭圆曲线的几何图形互逆点互逆点互逆点互逆点6几何定义几何定义 如果椭圆曲线上的三个点位于一条直线上，如果椭圆曲线上的三个点位于一条直线上，那么它们的和为那么它们的和为O。 实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则()()PQPQO互逆点互逆点()()PQPQ点和点基本运算为加法运算基本运算为加法运算7加法单位元为加法单位元为O O，

4、满足，满足实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则互逆点互逆点P、Q，满足，满足OOPOPPQPQO ,),),)PPQQRRP xyQ xyR xy（、（、（PQPQxxyy 且且8实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则非互逆点非互逆点P、Q的加法规则的加法规则,),),)PPQQRRP xyQ xyR xy（、（、（,),),)PPQQRRP xyQ xyR xy（2RPQxxx()RPRPyxxyQPQPyyxx若若=，则，则R为为无穷远点无穷远点O9实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则,),),)PPQQRRP xyQ xyR xy（、（、（,),)2,)

5、,)PPPPPPRRP xyP xyP xyR xy（22RPxx()RPRPyxxy232PPxay倍点规则倍点规则若若=，则，则R为为无穷远点无穷远点O10实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则交换律交换律,),),)PPQQRRP xyQ xyR xy（、（、（PQQP结合律结合律PQRPQR（）（）标量乘法标量乘法mPPPPm m个个0 PO()()mPmP 11实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例 5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0)为为 ，其上的两个点分别为，其上的两个点分别为 和和 。（1） 计算计算 。（2） 计算计算 。（3） 计

6、算计算 。（4） U点和点和R点是什么关系？点是什么关系？23yxx(1,0)P (2,6)Q PQR2QSPQU12实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例 5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0)为为 ， 和和 。（1） 计算计算 。23yxx(1,0)P (2,6)Q PQR6062 1QPQPyyxx22( 6)123RPQxxx ()6(1 3)02 6RPRPyxxy (1,0)(2, 6)(3, 2 6)PQR13实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例 5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0)为为 ， 和和 。（2） 计算

7、计算 。23yxx(1,0)P (2,6)Q 2QS2233 21112262 6QQxay2211121252()2 2424242 6SQxx 1125112335()(2)66624242882 62 6SQRQyxxy 25352 (2,6)(,6)24288QS14实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例 5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0)为为 ， 和和 。（3） 计算计算 。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实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例 5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0)为为 ， 和和 。（4） U点和点和R点是什么关系？点是什么关系？23yxx(1,0)P (2,6)Q (1,0)(2, 6)(3,2 6)PQU(1,0)(2, 6)(3, 2 6)PQRURxxURyy 互逆点关系互逆点关系 结论无普遍意义！结论无普遍意义！162、素域素域GF(p)GF(p)上的椭圆曲线上的椭圆曲线 GF(p)域上的椭圆曲线域上的椭圆曲线E(a,b)是对于固定的是对于固定的a、b值，满足形如三次方程值，满

9、足形如三次方程y2=x3+ax+b (mod p) 的所有点的集合，外加一个零点或无穷远点的所有点的集合，外加一个零点或无穷远点O 其中其中a、b、x和和y在在GF(p)域上取值域上取值 这类椭圆曲线通常也用这类椭圆曲线通常也用 来表示来表示 构成椭圆群),(mod0)274(23baEpbap( , )pEa b17HasseHasse定理定理 如果如果 是定义在是定义在GF(p)域上的椭域上的椭圆曲线，圆曲线，N是是 上的点的个数，上的点的个数，则：则： ppN2) 1( , )pEa b( , )pEa b18 图图 椭圆曲线上点的分布椭圆曲线上点的分布19与实数域相同，但所有的运算都是

10、与实数域相同，但所有的运算都是 mod p 运算的结果。运算的结果。分数运算时，既可以进行分数约简，分数运算时，既可以进行分数约简，也可以对分子、分母进行模运算，以也可以对分子、分母进行模运算，以便整除。便整除。 素域素域GF(p) 上椭圆曲线的运算规则上椭圆曲线的运算规则20素域素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例 6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线为为 ，其上的两个点分别为，其上的两个点分别为 和和 。（1） 计算计算 。（2） 计算计算 。（3） 计算计算 。（4） U点和点和R点是否互逆点？点是否互逆点？231yxx(3,10)P (9,7)Q

11、 PQR2PSPQU23(1,1)E21素域素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例 6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线为为 ， 和和 。（1） 计算计算 。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) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例 6 素域

12、素域GF(23) 上的椭圆曲线上的椭圆曲线为为 ， 和和 。（2） 计算计算 。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) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例 6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线为为 ， 和和 。（3） 计算计算 。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) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例 6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线为为 ， 和和 。（4） U点和点和R点是否互逆点？点是否互逆点？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点和点和R点不是互逆点点不是互逆点253 3、有限域、有限域GF(2GF(2n n) )上的椭圆曲线上的椭圆曲线 是对于固定的是对于固定的a、b值，满足形如三次方程值，满足形如三次方程 y2+xy=x3+ax2+b 的所有点的集合，外加一个零点或无穷远点的所有点的集合，外加一个零点或无穷远点O 其中其中a、b、x和和y在在GF(2n)域上取值域上取值 GF(2n)域上的元素是域上的元素是n位的串，共位的串，共2n个元素个元素 常用常用 表示，表示，b0时构成阿贝尔群时构成阿贝尔群 实际应用中，实际应用中，n n必须足够大，至少必须足够大，至少n=160(n=160(相当于相当

15、于1024 bits RSA)1024 bits RSA)2( , )nEa b26例子例子 例例 7 由不可约多项式由不可约多项式 定义的定义的有限域有限域 有一个生成元有一个生成元 。（1）列出）列出 上所有的非上所有的非0元素，表明它们与元素，表明它们与生成元生成元 的关系，并验证的关系，并验证 。（2）若椭圆曲线是）若椭圆曲线是 即即 ，检验，检验 是否为是否为 上的点，并列出上的点，并列出 上所有非上所有非0点的坐标值，画出点的坐标值，画出 上点的分布图。上点的分布图。4( )1m xxx (0010)gx4(2 )GFg14(1001)g4402(,)Egg23421yxyxg x

16、913(,)gg4402(,)Egg4402(,)Egg4402(,)Egg4(2 )GF27例子例子 例例 7 由不可约多项式由不可约多项式 定义的定义的有限域有限域 有一个生成元有一个生成元 。（1）列出）列出 上所有的非上所有的非0元素，元素，表明它们与表明它们与生成元生成元 的关系，并验证的关系，并验证 。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）验证）验证 。4( )1m xxx (0010)gx14(1001)g1414gx14(1001)g29例子例子 例例 7 由不可约多项式由不可约多项式 定义的定义的有限域有限域 有一个生成元有一个生成元 。（2）若椭圆曲线是）若椭圆曲线是 即即 ，检验检验 是否为是否为 上的点，并列出上的点，并列出 上所有非上所有非0点的坐标值，画出点的坐标值，画出 上点的分布图。上点的分布图。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 由不可约多项式由不可约多项式 定义的定义的有限域有限域 有一个生成元有一个生成元 。（2）若椭圆曲线是）若椭圆曲线是 即即 ，检验，检验 是否为是否为 上的点，并上的点，并列出列出 上所有非上所有非0点的点的坐标值坐标值，画出，画出

19、 上点的上点的分布图分布图。4( )1m xxx (0010)gx4402(,)Egg23421yxyxg x913(,)gg4402(,)Egg4402(,)Egg4402(,)Egg4(2 )GF3132十进制十进制描述描述例例 7的的坐标值坐标值33GF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则在在n次不可约多项式次不可约多项式m(x)定义的有限域中定义的有限域中进行进行运算要点：运算要点：加法：按位模加法：按位模2加加乘法、除法：使用生成元乘法、除法：使用生成元注意注意 ， mod (21)nxxgg2101ngg342( , )nEa bGF(2GF(2n

20、n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则,),),)PPQQRRP xyQ xyR xy（、（、（加法单位元为加法单位元为 ，满足，满足 OOOPOP互逆点互逆点P、Q，满足，满足 PQPQO PQPPQxxxyy且且352( , )nEa bGF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则,),),)PPQQRRP xyQ xyR xy（、（、（非互逆点非互逆点 的加法规则的加法规则PQ、,),),)PPQQRRP xyQ xyR xy（2RPQxxxa()RPRRPyxxxyQPQPyyxx若若=，则，则R为无穷远点为无穷远点O362( , )nEa b

21、GF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则,),),)PPQQRRP xyQ xyR xy（、（、（0)Py （倍点规则倍点规则,),)2,),)PPPPPPRRP xyP xyP xyR xy（2Rxa2(1)RPRyxx2PPPxyx若若=，则，则R为无穷远点为无穷远点O372( , )nEa bGF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则,),),)PPQQRRP xyQ xyR xy（、（、（0)Py （交换律交换律PQQP结合律结合律PQRPQR（）（）标量乘法标量乘法mPPPPm个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） 计算计算P+Q=R 。（2） 计算计算2P=S。（3） 计算计算P-Q=U。（4） 计算计算8P=V 。 4(0011)

23、ag0(0001)bg5(0110)Pxg11(1110)Pyg6(1100)Qxg14(1001)QygPQxxPQ、 是非互逆点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） 计算计算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、 计算计算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） 计算计算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） 计算计算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） 计算计算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） 计算计算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） 计算计算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） 计算计算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） 计算计算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） 计

34、算计算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定义定义设设G是椭圆曲线上的一点，若存在最小是椭圆曲线上的一点，若存在最小的正整数的正整数h，使得，使得 则称则称h为为G点的阶点的阶。hGO由于由于 时，时，8VPO511(,)(6,14)Pgg因此，因此，P的阶的阶h=8。椭圆曲线密码体制中，要求使用阶椭圆曲线密码体制中，要求使用阶h非常非常大的点大的点G作为本原元来

35、生成椭圆曲线子作为本原元来生成椭圆曲线子群群 。这样的点。这样的点G称为基点。称为基点。 ( , )hE a b50二、椭圆曲线密码体制二、椭圆曲线密码体制 1、椭圆曲线离散对数问题、椭圆曲线离散对数问题 已知椭圆曲线已知椭圆曲线 和曲线上的一点和曲线上的一点G，随机，随机选择一个整数选择一个整数d，容易计算，容易计算 。( , )E a bQdG但给定但给定G和和Q，要计算，要计算d却非常困难。却非常困难。 dQdGGGGGd个logGdQ椭圆曲线离散对数椭圆曲线离散对数51二、椭圆曲线密码体制二、椭圆曲线密码体制 2、椭圆曲线密码体制、椭圆曲线密码体制 （1）建立系统）建立系统 选一个基域

36、选一个基域 （或（或 ），其中），其中p是素是素数，数，n是正整数。是正整数。 ( )GF p(2 )nGF选一条定义在基域选一条定义在基域 （或（或 ）上的椭圆）上的椭圆曲线曲线 （或（或 ），寻找一个），寻找一个h阶基点阶基点G，满，满足以足以G为本原元生成的椭圆子群上的离散对数问题是为本原元生成的椭圆子群上的离散对数问题是难处理的。难处理的。 ( )GF p(2 )nGF( , )pEa b2( , )nEa b 公开基域、椭圆曲线、基点公开基域、椭圆曲线、基点G及阶及阶h 。52二、椭圆曲线密码体制二、椭圆曲线密码体制 2、椭圆曲线密码体制、椭圆曲线密码体制 （2）生成密钥）生成密钥

37、公钥公钥Q公开，私钥公开，私钥d保密保密 。选择一个大整数选择一个大整数d作为私钥，满足作为私钥，满足 1,1dh根据基点根据基点G和私钥和私钥d，计算公钥，计算公钥Q： QdG53二、椭圆曲线密码体制二、椭圆曲线密码体制 2、椭圆曲线密码体制、椭圆曲线密码体制 （3）加密算法）加密算法 查找查找BobBob的公钥的公钥Q QB BAliceAlice发送消息给发送消息给BobBob( )imGF p将消息划分为域元素，满足将消息划分为域元素，满足 ( )imGF p(2 )nimGF随机选择一个整数随机选择一个整数k，满足，满足1,1kh计算：计算： (,)RRR xykG(,)SSBS x

38、ykQiiScmx如果如果 ，则返回，则返回 重新选择一个整数重新选择一个整数 0Sx 将将 和密文和密文 发送给发送给Bob，R供收方解密用供收方解密用(,)RRR xyic54二、椭圆曲线密码体制二、椭圆曲线密码体制 2、椭圆曲线密码体制、椭圆曲线密码体制 （4）解密算法）解密算法 ( )imGF pBob收到收到 和密文和密文 (,)RRR xyic用用BobBob自己的私钥自己的私钥 ，计算，计算Bd(,)(,)SSBRRS xydR xy(,)(,)(,)(,)SSBBGGBGGBRRS xykQkdG xydkG xydR xy使用使用 中的中的 ，从密文，从密文 计算出明文计算出

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选择私钥选择私钥 ，计算，计算BobBob的公钥的公钥51,7Bd BQ（2 2）若）若AliceAlice要发送消

40、息要发送消息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选择私钥选择私钥 ，计算，计算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选择私钥选择私钥 ，计算，计算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选择私钥选择私钥 ，计算，计算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选择私钥选择私钥 ，计算，计算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选择私钥选择私钥 ，计算，计算BobBob的公钥的公钥51,7Bd BQ5(0110)Gxg11(1110)Gyg5(,)(,)(,)BBGGWWGGQdGG xyW xyG xy (0,1)WWGxx(,)(,)WWGGW xyG xy点与点不是互逆点不是互逆点 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选择私钥选择私钥 ，计算，计算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选择私钥选择私钥 ，计算，计算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发送消息发送消息m=m=（0010101000101010）给）给BobBob的加密过程的加密过程4(0011)ag5(0110)Gxg11(1110)Gyg 查找查找BobBob的公钥的公钥10(, )BQgg 将消息划分为域

51、元素将消息划分为域元素 ，满足，满足 im4(2 )imGF1(0010)mg92(1010)mg 随机选择一个整数随机选择一个整数k=3k=3，满足，满足 1,7k 计算密文计算密文 (,)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发送消息发送消息m=m=（0010101000101010）给）给BobBob的加密过程的加密过程4(0011)ag5(0110)Gxg11(1110)Gyg 计算密文计算密文 (,)32RRR xykGGGGPG 51162(,)(1,)G ggPgP P、G G不是互逆点不是互逆点 PGxx（1 1）中计算得到）中计算得到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发送消息发送消息m=m=（0010101000101010）给）给BobBob的加密过程的加密过程4(0011)ag5(0110)Gxg11(1110)Gyg 计算密文计算密文 (,)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发送消息发送

55、消息m=m=（0010101000101010）给）给BobBob的加密过程的加密过程4(0011)ag5(0110)Gxg11(1110)Gyg 计算密文计算密文 (,)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发送消息发送消息m=m=（0010101000101010）给）给BobBob的加密过程的加密过程4(0011)ag5(0110)Gxg11(1110)Gyg 计算密文计算密文 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发送消息发送消息m=m=（001010100010

58、1010）给）给BobBob的加密过程的加密过程4(0011)ag5(0110)Gxg11(1110)Gyg 计算密文计算密文 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发送消息发送消息m=m=（0010101000101010）给）给BobBob的加密过程的加密过程4(0011)ag5(0110)Gxg11(1110)Gyg 计算密文计算密文 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发送消息发送消息m=m=（0010101000101010）给