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

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

2、3+cx2+dx+e 的所有点的所有点(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. 4 1 1、实数域上的椭圆曲线、实数域上的椭圆曲线 实数域上的椭圆曲线实数域上的椭圆曲线E(a,b)是对于固定的是对于固定的a、b 值，满足形如三次方程值，满足形

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

4、运算为加法运算 7 加法单位元为加法单位元为O O，满足，满足 实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则 互逆点互逆点P、Q，满足，满足 OOPOP PQPQO ,),),) PPQQRR P xyQ xyR xy（、（、（ PQPQ xxyy 且且 8 实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则 非互逆点非互逆点P、Q的加法规则的加法规则 ,),),) PPQQRR P xyQ xyR xy（、（、（ ,),),) PPQQRR P xyQ xyR xy（ 2 RPQ xxx () RPRP yxxy QP QP yy xx 若若=，则，则R为为 无穷远点无穷远点O 9 实数域

5、椭圆曲线的运算规则实数域椭圆曲线的运算规则 ,),),) PPQQRR P xyQ xyR xy（、（、（ ,),)2,),) PPPPPPRR P xyP xyP xyR xy（ 2 2 RP xx () RPRP yxxy 2 3 2 P P xa y 倍点规则倍点规则 若若=，则，则R为为 无穷远点无穷远点O 10 实数域椭圆曲线的运算规则实数域椭圆曲线的运算规则 交换律交换律 ,),),) PPQQRR P xyQ xyR xy（、（、（ PQQP 结合律结合律PQRPQR（）（） 标量乘法标量乘法 mPPPP m m个个 0 PO ()()mPmP 11 实数域椭圆曲线运算举例实数域

6、椭圆曲线运算举例 例例 5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0) 为为 ，其上的两个点分别为，其上的两个点分别为 和和 。 （1） 计算计算 。 （2） 计算计算 。 （3） 计算计算 。 （4） U点和点和R点是什么关系？点是什么关系？ 23 yxx(1,0)P (2,6)Q PQR 2QS PQU 12 实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例 5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0) 为为 ， 和和 。 （1） 计算计算 。 23 yxx (1,0)P (2,6)Q PQR 60 6 2 1 QP QP yy xx 22 ( 6)123 RP

7、Q xxx ()6(1 3)02 6 RPRP yxxy (1,0)(2, 6)(3, 2 6)PQR 13 实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例 5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0) 为为 ， 和和 。 （2） 计算计算 。 23 yxx(1,0)P (2,6)Q 2QS 2 2 3 3 2111 2262 6 Q Q xa y 22 1112125 2()2 24 24242 6 SQ xx 1125112335 ()(2)666 24242882 62 6 SQRQ yxxy 2535 2 (2,6)(,6) 24288 QS 14 实数域椭圆曲线运算

8、举例实数域椭圆曲线运算举例 例例 5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0) 为为 ， 和和 。 （3） 计算计算 。 23 yxx(1,0)P (2,6)Q PQU ()PQUPQ (,)(2,6) QQ Qxy 60 6 2 1 QP QP yy xx 22 (6)1 23 UPQ xxx ()6(1 3)02 6 UPUP yxxy (1,0)(2, 6)(3,2 6)PQU 15 实数域椭圆曲线运算举例实数域椭圆曲线运算举例 例例 5 已知实数域的椭圆曲线已知实数域的椭圆曲线E(-1,0) 为为 ， 和和 。 （4） U点和点和R点是什么关系？点是什么关系？ 23 yx

9、x(1,0)P (2,6)Q (1,0)(2, 6)(3,2 6)PQU (1,0)(2, 6)(3, 2 6)PQR UR xx UR yy 互逆点关系互逆点关系 结论无普遍意义！结论无普遍意义！ 16 2、素域素域GF(p)GF(p)上的椭圆曲线上的椭圆曲线 GF(p)域上的椭圆曲线域上的椭圆曲线E(a,b)是对于固定的是对于固定的a、 b值，满足形如三次方程值，满足形如三次方程 y2=x3+ax+b (mod p) 的所有点的集合，外加一个零点或无穷远点的所有点的集合，外加一个零点或无穷远点O 其中其中a、b、x和和y在在GF(p)域上取值域上取值 这类椭圆曲线通常也用这类椭圆曲线通常也

10、用 来表示来表示 构成椭圆群),( mod0)274( 23 baE pba p ( , ) p Ea b 17 HasseHasse定理定理 如果如果 是定义在是定义在GF(p)域上的椭域上的椭 圆曲线，圆曲线，N是是 上的点的个数，上的点的个数， 则：则： ppN2) 1( ( , ) p Ea b ( , ) p Ea b 18 图图 椭圆曲线上点的分布椭圆曲线上点的分布 19 与实数域相同，但所有的运算都是与实数域相同，但所有的运算都是 mod p 运算的结果。运算的结果。 分数运算时，既可以进行分数约简，分数运算时，既可以进行分数约简， 也可以对分子、分母进行模运算，以也可以对分子、

11、分母进行模运算，以 便整除。便整除。 素域素域GF(p) 上椭圆曲线的运算规则上椭圆曲线的运算规则 20 素域素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例 6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线 为为 ，其上的两个点分别为，其上的两个点分别为 和和 。 （1） 计算计算 。 （2） 计算计算 。 （3） 计算计算 。 （4） U点和点和R点是否互逆点？点是否互逆点？ 23 1yxx (3,10)P (9,7)Q PQR 2PS PQU 23(1,1) E 21 素域素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例 6 素域素域GF(23) 上的椭圆曲

12、线上的椭圆曲线 为为 ， 和和 。 （1） 计算计算 。 23 1yxx(3,10)P (9,7)Q PQR 23(1,1) E 7 103201033 11 (mod 23) 936633 QP QP yy xx 22 (11)3 9121 1210917 (mod 23) RPQ xxx ()11 (3 17) 1016420 (mod 23) RPRP yxxy (3,10)(9,7)(17,20)PQR 22 素域素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例 6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线 为为 ， 和和 。 （2） 计算计算 。 23 1yxx(

13、3,10)P (9,7)Q 2PS 23(1,1) E 22 33 31285124 6 (mod 23) 22 10202044 P P xa y 22 2(6)2 3366307 (mod 23) SP xx ()6 (37) 103412 (mod 23) SPRP yxxy 2 (3,10)(7,12)PS 23 素域素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例 6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线 为为 ， 和和 。 （3） 计算计算 。 23 1yxx(3,10)P (9,7)Q PQU 23(1,1) E ()PQUPQ (,)(9, 7)(9,1

14、6) (mod 23) QQ Qxy 16 106 1 936 QP QP yy xx 22 1391112 (mod 23) UPQ xxx ()1 (3 12) 10194 (mod 23) UPUP yxxy (3,10)(9,7)(12,4)PQU 24 素域素域GF(p) 上椭圆曲线的运算举例上椭圆曲线的运算举例 例例 6 素域素域GF(23) 上的椭圆曲线上的椭圆曲线 为为 ， 和和 。 （4） U点和点和R点是否互逆点？点是否互逆点？ 23 1yxx (3,10)P (9,7)Q 23(1,1) E (3,10)(9,7)(12,4)PQU (3,10)(9,7)(17,20)P

15、QR UR xx UR yy U点和点和R点不是互逆点点不是互逆点 25 3 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

16、=160(相当于相当于1024 bits RSA)1024 bits RSA) 2 ( , ) n Ea b 26 例子例子 例例 7 由不可约多项式由不可约多项式 定义的定义的 有限域有限域 有一个生成元有一个生成元 。 （1）列出）列出 上所有的非上所有的非0元素，表明它们与元素，表明它们与 生成元生成元 的关系，并验证的关系，并验证 。 （2）若椭圆曲线是）若椭圆曲线是 即即 ，检验，检验 是否为是否为 上的点，并列出上的点，并列出 上所有非上所有非0点的坐标值，画出点的坐标值，画出 上点的分布图。上点的分布图。 4 ( )1m xxx (0010)gx 4 (2 )GF g 14 (1

17、001)g 4 40 2 (,)Egg 2342 1yxyxg x 913 (,)gg 4 40 2 (,)Egg 4 40 2 (,)Egg 4 40 2 (,)Egg 4 (2 )GF 27 例子例子 例例 7 由不可约多项式由不可约多项式 定义的定义的 有限域有限域 有一个生成元有一个生成元 。 （1）列出）列出 上所有的非上所有的非0元素，元素，表明它们与表明它们与 生成元生成元 的关系，并验证的关系，并验证 。 4 ( )1m xxx (0010)gx 4 (2 )GF g 14 (1001)g g0=(0001)g1=(0010)g2=(0100)g3=(1000) g4=(001

18、1)g5=(0110)g6=(1100)g7=(1011) g8=(0101)g9=(1010)g10=(0111) g11=(1110) g12=(1111) g13=(1101) g14=(1001) g15=(0001) 4 (2 )GF 28 例子例子 例例 7 （1）验证）验证 。 4 ( )1m xxx (0010)gx 14 (1001)g 1414 gx 14 (1001)g 29 例子例子 例例 7 由不可约多项式由不可约多项式 定义的定义的 有限域有限域 有一个生成元有一个生成元 。 （2）若椭圆曲线是）若椭圆曲线是 即即 ，检验检验 是否为是否为 上的点，并列出上的点，并

19、列出 上所有非上所有非0点的坐标值，画出点的坐标值，画出 上点的分布图。上点的分布图。 4 ( )1m xxx (0010)gx 4 40 2 (,)Egg 2342 1yxyxg x 913 (,)gg4 40 2 (,)Egg 4 40 2 (,)Egg 4 40 2 (,)Egg 21 1 n g mod (21) n xx gg 213 29132622117 ()(1110)(1011)(0101)yxyggggggg 342934922722127 1()()111 (1111)(1011)(0001)(0101) xg xggggggg 是是 4 (2 )GF 30 例子例子 例

20、例 7 由不可约多项式由不可约多项式 定义的定义的 有限域有限域 有一个生成元有一个生成元 。 （2）若椭圆曲线是）若椭圆曲线是 即即 ，检验，检验 是否为是否为 上的点，并上的点，并列出列出 上所有非上所有非0点的点的坐标值坐标值，画出，画出 上点的上点的分布图分布图。 4 ( )1m xxx (0010)gx 4 40 2 (,)Egg 2342 1yxyxg x 913 (,)gg4 40 2 (,)Egg 4 40 2 (,)Egg 4 40 2 (,)Egg 4 (2 )GF 31 32 十进制十进制 描述描述 例例 7的的 坐标值坐标值 33 GF(2GF(2n n) )域上椭圆曲

21、线的运算规则域上椭圆曲线的运算规则 在在n次不可约多项式次不可约多项式m(x)定义的有限域中定义的有限域中 进行进行 运算要点：运算要点： 加法：按位模加法：按位模2加加 乘法、除法：使用生成元乘法、除法：使用生成元 注意注意 ， mod (21) n xx gg 210 1 n gg 34 2 ( , ) n Ea b GF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则 ,),),) PPQQRR P xyQ xyR xy（、（、（ 加法单位元为加法单位元为 ，满足，满足 O OOPOP 互逆点互逆点P、Q，满足，满足 PQPQO PQPPQ xxxyy且且 35 2

22、( , ) n Ea b GF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则 ,),),) PPQQRR P xyQ xyR xy（、（、（ 非互逆点非互逆点 的加法规则的加法规则PQ、 ,),),) PPQQRR P xyQ xyR xy（ 2 RPQ xxxa () RPRRP yxxxy QP QP yy xx 若若=，则，则R为无穷远点为无穷远点O 36 2 ( , ) n Ea b GF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则 ,),),) PPQQRR P xyQ xyR xy（、（、（ 0) P y （ 倍点规则倍点规则 ,),)

23、2,),) PPPPPPRR P xyP xyP xyR xy（ 2 R xa 2 (1) RPR yxx 2 PP P xy x 若若=，则，则R为无穷远点为无穷远点O 37 2 ( , ) n Ea b GF(2GF(2n n) )域上椭圆曲线的运算规则域上椭圆曲线的运算规则 ,),),) PPQQRR P xyQ xyR xy（、（、（ 0) P y （ 交换律交换律PQQP 结合律结合律PQRPQR（）（） 标量乘法标量乘法 mPPPP m个 0 PO ()()mPmP 38 44 40 22 (,)(3,1)EggE 2342 1yxyxg x 511 (,)(6,14)Pgg g0

24、=(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)2gx 4 (2 )GF例例 8 8 614 (,)(12,9)Qgg （1） 计算计算P+Q=R 。 （2） 计算计算2P=S。 （3） 计算计算P-Q=U。 （4） 计算计算8P=V 。 4 (0011)ag 0 (0001)bg 5 (0110) P x

25、g 11 (1110) P yg 6 (1100) Q xg 14 (1001) Q yg PQ xxPQ、 是非互逆点 39 511 (,)(6,14)Pgg 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) 614 (,)(12,9)Qgg 4 (0011)ag （1） 计算计算P+Q=R 。 141110 659 (1001)(111

26、0)(0111) (1100)(0110)(1010) QP QP yy ggg g xxggg 22564 12 (0100)(0010)(0110)(1100)(0011) (1111) RPQ xxxaggggg g 例例 8 8 2342 1yxyxg x 40 511 (,)(6,14)Pgg 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=

27、(0001) 614 (,)(12,9)Qgg 4 (0011)ag （1） 计算计算P+Q=R 。g 12 (1111) R xg 5121211 6131211 ()() (1100)(1101)(1111)(1110) (0000)0 RPRRP yxxxyg gggg gggg 51161412 (,)(,)(,0)P ggQ ggR g 例例 8 8 2342 1yxyxg x 41 511 (,)(6,14)Pgg g0=(0001)g1=(0010)g2=(0100)g3=(1000) g4=(0011)g5=(0110)g6=(1100)g7=(1011) g8=(0101)g

28、9=(1010)g10=(0111)g11=(1110) g12=(1111)g13=(1101)g14=(1001)g15=(0001) 614 (,)(12,9)Qgg 4 (0011)ag （2） 计算计算2P=S。 例例 8 8 2342 1yxyxg x 25211 569 5 () (0110)(1100)(1010) PP P xygg ggg xg 292941894394 0 () (1000)(1010)(0011)(0001)1 S xaggggggggg g 42 511 (,)(6,14)Pgg g0=(0001)g1=(0010)g2=(0100)g3=(1000)

29、 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)Qgg 4 (0011)ag （2） 计算计算2P=S。 例例 8 8 2342 1yxyxg x 9 (1010)g 0 (0001)1 S xg 25290109 6 (1)()(1)1 (0111)(1010)(0001)(1100) SPS yxxggggg g 5116 2 (,)(1,)P ggSg 43 511 (,)(6

30、,14)Pgg 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) 614 (,)(12,9)Qgg 4 (0011)ag （3） 计算计算P-Q=U。 例例 8 8 2342 1yxyxg x ()PQUPQ 6 QQ xxg 6148 (1100)(1001)(0101) QQQ yxyggg 68 (,)(,) QQ Qxygg 811

31、7715 13 6599 (0101)(1110)(1011) (1100)(0110)(1010) QP QP yy ggggg g xxgggg 44 511 (,)(6,14)Pgg 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) 614 (,)(12,9)Qgg 4 (0011)ag （3） 计算计算P-Q=U。 例例 8 8 2

32、342 1yxyxg x ()PQUPQ 68 (,)(,) QQ Qxygg 13 g 213 213564 26135641113564 9 () (1110)(1101)(0110)(1100)(0011) (1010) UPQ xxxaggggg gggggggggg g 45 511 (,)(6,14)Pgg 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=(1

33、001)g15=(0001) 614 (,)(12,9)Qgg 4 (0011)ag （3） 计算计算P-Q=U。 例例 8 8 2342 1yxyxg x ()PQUPQ 68 (,)(,) QQ Qxygg 13 g 9 (1010) U xg 1359911 182291137911 10 ()() (1000)(1011)(1010)(1110)(0111) UPUUP yxxxyggggg gggggggg g 511614910 (,)(,)(,)P ggQ ggU gg 46 511 (,)(6,14)Pgg g0=(0001)g1=(0010)g2=(0100)g3=(1000

34、) 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)Qgg 4 (0011)ag （4） 计算计算8P=V 。 例例 8 8 2342 1yxyxg x 82 (2 (2 )VPP 5116 2 (,)(1,)P ggSg 82 (2 )VPS 2WS2VW 2 :WS 226 613 1 1(0001)(1100)(1101) 1 SS S xyg gg x 47 511 (,)(6

35、,14)Pgg 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) 614 (,)(12,9)Qgg 4 (0011)ag （4） 计算计算8P=V 。 例例 8 8 2342 1yxyxg x 5116 2 (,)(1,)P ggSg 82 (2 )VPS 2WS2VW 2 :WS 13 (1101)g 21321342613411134

36、() (1110)(1101)(0011)(0000)0 W xaggggggggg 2213 (1)1(1) 01 WSW yxxg 6 2 (1,)(0,1)SgW 48 511 (,)(6,14)Pgg 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) 614 (,)(12,9)Qgg 4 (0011)ag （4） 计算计算8P=V

37、。 例例 8 8 2342 1yxyxg x 5116 2 (,)(1,)P ggSg 82 (2 )VPS 2WS2VW 2:VW 6 2 (1,)(0,1)SgW 22 01 0 WW W xy x 224 ( ) V xag 22 (1)0(1) VWV yxx 2(0,1)( ,)WV VO 49 定义定义 设设G是椭圆曲线上的一点，若存在最小是椭圆曲线上的一点，若存在最小 的正整数的正整数h，使得，使得 则称则称h为为G点的阶点的阶。 hGO 由于由于 时，时，8VPO 511 (,)(6,14)Pgg 因此，因此，P的阶的阶h=8。 椭圆曲线密码体制中，要求使用阶椭圆曲线密码体制中

38、，要求使用阶h非常非常 大的点大的点G作为本原元来生成椭圆曲线子作为本原元来生成椭圆曲线子 群群 。这样的点。这样的点G称为基点。称为基点。 ( , ) h E a b 50 二、椭圆曲线密码体制二、椭圆曲线密码体制 1、椭圆曲线离散对数问题、椭圆曲线离散对数问题 已知椭圆曲线已知椭圆曲线 和曲线上的一点和曲线上的一点G，随机，随机 选择一个整数选择一个整数d，容易计算，容易计算 。 ( , )E a b QdG 但给定但给定G和和Q，要计算，要计算d却非常困难。却非常困难。 d QdGGGGG d个 logGdQ 椭圆曲线离散对数椭圆曲线离散对数 51 二、椭圆曲线密码体制二、椭圆曲线密码体

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

40、。 52 二、椭圆曲线密码体制二、椭圆曲线密码体制 2、椭圆曲线密码体制、椭圆曲线密码体制 （2）生成密钥）生成密钥 公钥公钥Q公开，私钥公开，私钥d保密保密 。 选择一个大整数选择一个大整数d作为私钥，满足作为私钥，满足 1,1dh 根据基点根据基点G和私钥和私钥d，计算公钥，计算公钥Q： QdG 53 二、椭圆曲线密码体制二、椭圆曲线密码体制 2、椭圆曲线密码体制、椭圆曲线密码体制 （3）加密算法）加密算法 查找查找BobBob的公钥的公钥Q QB B AliceAlice发送消息给发送消息给BobBob ( ) i mGF p 将消息划分为域元素，满足将消息划分为域元素，满足 ( ) i

41、 mGF p (2 ) n i mGF 随机选择一个整数随机选择一个整数k，满足，满足 1,1kh 计算：计算： ( ,) RR R xykG(,) SSB S xykQ iiS cmx 如果如果 ，则返回，则返回 重新选择一个整数重新选择一个整数 0 S x 将将 和密文和密文 发送给发送给Bob，R供收方解密用供收方解密用 (,) RR R xy i c 54 二、椭圆曲线密码体制二、椭圆曲线密码体制 2、椭圆曲线密码体制、椭圆曲线密码体制 （4）解密算法）解密算法 ( ) i mGF p Bob收到收到 和密文和密文 (,) RR R xy i c 用用BobBob自己的私钥自己的私钥

42、，计算，计算 B d(,)(,) SSBRR S xydR xy (,)(,) (,)(,) SSBBGG BGGBRR S xykQkdG xy dkG xydR xy 使用使用 中的中的 ，从密文，从密文 计算出明文计算出明文 (,) SS S xy S x i c i m 1 iiS mcx 55 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=

43、(0001) 例例 9 9 2342 1yxyxg x8h 511 (,)G gg 4 40 2 (,)Egg 3 40 2 (,)Egg （1 1）若）若BobBob选择私钥选择私钥 ，计算，计算BobBob的公钥的公钥51,7 B d B Q （2 2）若）若AliceAlice要发送消息要发送消息m =m =（0010101000101010）给）给BobBob，给，给 出出AliceAlice的加密过程的加密过程 （3 3）给出）给出BobBob的解密过程的解密过程 56 g0=(0001)g1=(0010)g2=(0100)g3=(1000) g4=(0011)g5=(0110)g6

44、=(1100)g7=(1011) g8=(0101)g9=(1010)g10=(0111)g11=(1110) g12=(1111)g13=(1101)g14=(1001)g15=(0001) 4 (0011)ag 例例 9 9 2342 1yxyxg x8h 511 (,)G gg 4 40 2 (,)Egg 3 40 2 (,)Egg （1 1）若）若BobBob选择私钥选择私钥 ，计算，计算BobBob的公钥的公钥51,7 B d B Q 5 (0110) G xg 11 (1110) G yg 2(,)(,) GGPP G xyP xy 25211 569 5 () (0110)(11

45、00)(1010) GG G xygg ggg xg 292941894394 0 () (1000)(1010)(0011)(0001)1 P xaggggggggg g 5(,) BBGG QdGG xy 57 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 9 2342 1yxyxg x8h 511

46、(,)G gg 4 40 2 (,)Egg 3 40 2 (,)Egg （1 1）若）若BobBob选择私钥选择私钥 ，计算，计算BobBob的公钥的公钥51,7 B d B Q 5 (0110) G xg 11 (1110) G yg 2(,)(,) GGPP G xyP xy 9 (1010)g 0 (0001)1 P xg 25290109 6 (1)()(1)1 (0111)(1010)(0001)(1100) PGP yxxggggg g 5116 2(,)(1,)G ggPg 58 g0=(0001)g1=(0010)g2=(0100)g3=(1000) g4=(0011)g5=(

47、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 9 2342 1yxyxg x8h 511 (,)G gg 4 40 2 (,)Egg 3 40 2 (,)Egg （1 1）若）若BobBob选择私钥选择私钥 ，计算，计算BobBob的公钥的公钥51,7 B d B Q 5 (0110) G xg 11 (1110) G yg 4(,)2(,)(,) GGPPWW G xyP xyW xy 5116 2(

48、,)(1,)G ggPg 226 613 1 1(0001)(1100)(1101) 1 PP P xyg gg x 21321342613411134 () (1110)(1101)(0011)(0000)0 W xaggggggggg 59 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 9 2342

49、1yxyxg x8h 511 (,)G gg 4 40 2 (,)Egg 3 40 2 (,)Egg （1 1）若）若BobBob选择私钥选择私钥 ，计算，计算BobBob的公钥的公钥51,7 B d B Q 5 (0110) G xg 11 (1110) G yg 4(,)2(,)(,) GGPPWW G xyP xyW xy 5116 2(,)(1,)G ggPg 13 (1101)g (0000)0 W x 2213 (1)1(1)01 WPW yxxg 6 2(1,)(0,1)PgW 60 g0=(0001)g1=(0010)g2=(0100)g3=(1000) g4=(0011)g5

50、=(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 9 2342 1yxyxg x8h 511 (,)G gg 4 40 2 (,)Egg 3 40 2 (,)Egg （1 1）若）若BobBob选择私钥选择私钥 ，计算，计算BobBob的公钥的公钥51,7 B d B Q 5 (0110) G xg 11 (1110) G yg 5(,)(,)(,) BBGGWWGG QdGG xyW xyG xy (

51、0,1)W WG xx(,)(,) WWGG W xyG xy点与点不是互逆点不是互逆点 1112 7 55 1(0001)(1110)(1111) (1011) 0(0110)(0110) WG WG yygg g xxgg 61 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 9 2342 1yxyxg

52、 x8h 511 (,)G gg 4 40 2 (,)Egg 3 40 2 (,)Egg （1 1）若）若BobBob选择私钥选择私钥 ，计算，计算BobBob的公钥的公钥51,7 B d B Q 5 (0110) G xg 11 (1110) G yg 5(,)(,)(,) BBGGWWGG QdGG xyW xyG xy (0,1)W 7 (1011)g 272754 14754 10 ()0 (1001)(1011)(0110)(0011) (0111) QGW xxxagggg gggg g 62 g0=(0001)g1=(0010)g2=(0100)g3=(1000) g4=(001

53、1)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 9 2342 1yxyxg x8h 511 (,)G gg 4 40 2 (,)Egg 3 40 2 (,)Egg （1 1）若）若BobBob选择私钥选择私钥 ，计算，计算BobBob的公钥的公钥51,7 B d B Q 5 (0110) G xg 11 (1110) G yg 5(,)(,)(,) BBGGWWGG QdGG xyW xyG

54、xy (0,1)W 7 (1011)g 10 (0111) Q xg 710101710210 ()(0)111 (0100)(0111)(0001)(0010) QWQQW yxxxyggggggg g 51151151110 (,)5(,)(0,1)(,)(, ) BB dG ggG ggWG ggQgg 63 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=(100

55、1)g15=(0001) 例例 9 9 2342 1yxyxg x8h 511 (,)G gg 4 40 2 (,)Egg 3 40 2 (,)Egg （2 2）AliceAlice发送消息发送消息m=m=（0010101000101010）给）给BobBob的加密过程的加密过程 4 (0011)ag 5 (0110) G xg 11 (1110) G yg 查找查找BobBob的公钥的公钥 10 (, ) B Qgg 将消息划分为域元素将消息划分为域元素 ，满足，满足 i m 4 (2 ) i mGF 1 (0010)mg 9 2 (1010)mg 随机选择一个整数随机选择一个整数k=3k=

56、3，满足，满足 1,7k 计算密文计算密文 (,) RR R xykG(,) SSB S xykQ iiS cmx 64 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) 例例 9 9 2342 1yxyxg x8h 511 (,)G gg 4 40 2 (,)Egg 3 40 2 (,)Egg （2 2）AliceAlice发送消息发送消

57、息m=m=（0010101000101010）给）给BobBob的加密过程的加密过程 4 (0011)ag 5 (0110) G xg 11 (1110) G yg 计算密文计算密文 (,)32 RR R xykGGGGPG 5116 2(,)(1,)G ggPg P P、G G不是互逆点不是互逆点 PG xx （1 1）中计算得到）中计算得到 65 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)

58、g13=(1101)g14=(1001)g15=(0001) 例例 9 9 2342 1yxyxg x8h 511 (,)G gg 4 40 2 (,)Egg 3 40 2 (,)Egg （2 2）AliceAlice发送消息发送消息m=m=（0010101000101010）给）给BobBob的加密过程的加密过程 4 (0011)ag 5 (0110) G xg 11 (1110) G yg 计算密文计算密文 (,) RR R xykGPG 5116 2(,)(1,)G ggPg 61116 6 51010 (1100)(1110)(0010) 1(0001)(0110)(0111) PG

59、PG yygggg g xxggg 262654 12654 10 ()1 1(1111)(1100)(0001)(0110)(0011) (0111) RPG xxxagggg gggg g 66 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) 例例 9 9 2342 1yxyxg x8h 511 (,)G gg 4 40 2 (,)E

60、gg 3 40 2 (,)Egg （2 2）AliceAlice发送消息发送消息m=m=（0010101000101010）给）给BobBob的加密过程的加密过程 4 (0011)ag 5 (0110) G xg 11 (1110) G yg 计算密文计算密文 (,) RR R xykGPG 5116 2(,)(1,)G ggPg 6 g 10 (0111) R xg 610106 61610661106 8 ()(1) (1100)(0010)(0111)(1100)(0101) RPRRP yxxxygggg gggggggg g 6511108 (1,)(,)(,)PgG ggR gg