椭圆曲线密码学知识简介.ppt

第七章椭圆曲线密码学 1有关的基本概念 1 无穷远元素 无穷远点 无穷远直线 平面上任意两相异直线的位置关系有相交和平行两种 引入无穷远点 是两种不同关系统一 AB L1 L2 L1 直线AP由AB起绕A点依逆时针方向转动 P为AP与L1的交点 L2 L1 P B A P Q Q BAP 2AP L2可设想L1上有一点P 它为L2和L1的交点 称之为无穷远点 直线L1上的无穷远点只能有一个 因为过A点只能有一条平行于L1的直线L2 而两直线的交点只能有一个 结论 1 平面上一组相互平行的直线 有公共的无穷远点 为与无穷远点相区别 把原来平面上的点叫做平常点 2 平面上任何相交的两直线L1 L2有不同的无穷远点 原因 若否 则L1和L2有公共的无穷远点P 则过两相异点A和P 有相异两直线 与公理相矛盾 3 全体无穷远点构成一条无穷远直线 注 欧式平面添加上无穷远点和无穷远直线 自然构成射影平面 2 齐次坐标解析几何中引入坐标系 用代数的方法研究欧氏空间 这样的坐标法也可推广至摄影平面上 建立平面摄影坐标系 平面上两相异直线L1 L2 其方程分别为 L1 a1x b1y c1 0L2 a2x b2y c2 0 A L1 L2 P 其中a1 b1不同时为0 a2 b2也不同时为0 设D a1b1Dx b1c1Dy c1a1a2b2b2c2c2a2若D 0 则两直线L1 L2相交于一平常点P x y 其坐标为x Dx D y Dy D 这组解可表为 x Dx y Dy 1 D 约定 分母Dx Dy有为0时 对应的分子也要为0 上述表示可抽象为 Dx Dy D 若D 0 则L1 L2 此时L1和L2交于一个无穷远点P 这个点P 可用过原点O且平行于L2的一条直线L来指出他的方向 而这条直线L的方程就是 a2x b2y 0 为把平常点和无穷远点的坐标统一起来 把点的坐标用 X Y Z 表示 X Y Z不能同时为0 且对平常点 x y 来说 有Z 0 x X Z y Y Z 于是有 i e X Dx Y Dy Z D 有更好的坐标抽象 X Y Z 这样对于无穷远点则有Z 0 也成立 注 a 若实数p 0 则 pX pY pZ 与 X Y Z 表示同一个点 实质上用 X Y Z 表示 3个分量中 只有两个是独立的 具有这种特征的坐标就叫齐次坐标 i e b 设有欧氏直线L 它在平面直角坐标系Oxy上的方程为 ax by c 0则L上任一平常点 x y 的齐次坐标为 X Y Z Z 0 代入得 aX bY cZ 0给L添加的无穷远点的坐标 X Y Z 应满足aX bY 0 Z 0 平面上无穷远直线方程自然为 Z 0 3 任意域上的椭圆曲线K为域 K上的摄影平面P2 K 是一些等价类的集合 X Y Z 考虑下面的Weierstrass方程 次数为3的齐次方程 Y2Z a1XYZ a3YZ2 X3 a2X2z a4XZ2 a6Z3 其中系数ai K 或ai K为K的代数闭域 Weierstrass方程被称为光滑的或非奇异的是指对所有适合以下方程的射影点P X Y Z P2 K 来说 F X Y Z Y2Z a1XYZ a3YZ2 X3 a2X2Z a4XZ2 a6Z3 0在P点的三个偏导数之中至少有一个不为0若否称这个方程为奇异的 椭圆曲线E的定义 椭圆曲线E是一个光滑的Weierstrass方程在P2 K 中的全部解集合 Y2Z a1XYZ a3YZ2 X3 a2X2Z a4XZ2 a6Z3注 a 在椭圆曲线E上恰有一个点 称之为无穷远点 即 0 1 0 用 表示 b 可用非齐次坐标的形式来表示椭圆曲线的Weierstrass方程 设x X Z y Y Z 于是原方程转化为 y2 a1xy a3y x3 a2x2 a4x a6 1 此时 椭圆曲线E就是方程 1 在射影平面P2 K 上的全部平常点解 外加一个无穷远点 组成的集合 c 若a1 a2 a2 a4 a6 K 此时椭圆曲线E被称为定义在K上 用E K表示 如果E能被限定在K上 那么E的K 有理点集合表示为E K 它为E中的全体有理坐标点的集合外加无穷远点 4 实域R上的椭圆曲线设K R 此时的椭圆曲线可表为平面上的通常曲线上的点 外加无穷远点 实域R上椭圆曲线的点的加法运算法则 设L P2 R 为一条直线 因为E的方程是三次的 所以L可与E在P2 R 恰有三个交点 记为P Q R 注意 如果L与E相切 那么P Q R可以不是相异的 按下述方式定义E上运算 设P Q E L为联接P Q的直线 若P Q 则L取过P点的切线 设R为L与E的另一个交点 再取连接R与无穷远点的直线L 则L 与E的另一个交点定义为P Q P Q P Q L L L L P Q R T T P Q R P Q P Q R R T 上页的实际图像为椭圆曲线y2 x3 x的一般化 来自对具体曲线的抽象 对运算更具体一些 设P x1 y1 Q x2 y2 P Q x3 y3 由P Q的定义 设y x 为通过P Q两点直线L的方程 可算出 y2 y1 x2 x1 y1 x1易见 直线L上的一个点 x x 是在椭圆曲线E上 当且仅当 x 2 x3 x P Q x1 y1 x2 y2 x3 y3 x3 x3 其中 x3 2 x1 x2 y2 y1 x2 x1 2 x1 x2 y3 y1 y2 y1 x2 x1 x1 x3 当P Q时 P Q x3 y3 算得 x3 3x12 1 2y1 2 2x1 y3 y1 3x12 1 2y1 x1 x3 注 a 如果直线L与E相交与三点P Q R 不一定相异 那么 P Q R 从图中可见 b 任给P E P P 此时设Q 易见L L c 任给P Q E有 P Q Q Pd 设P E 那么可以找到 P E使P P e 任给P Q R E 有 P Q R P Q R 综上所述 知E对 运算形成一个Abel群 f 上述规则可开拓到任意域上 特别是有限域上 假定椭圆曲线是定义在有限域Fq上 q pm 那么E Fq x y Fq Fq y2 a1xy a3y x3 a2x2 a4x a6 它对 形成一个群 为Abel群 2有限域上椭圆曲线的 运算 令Fq表示q个元素的有限域 用E Fq 表示定义在Fq上的一个椭圆曲线E 定理1 Hass定理 E Fq 的点数用 E Fq 表示 则 E Fq q 1 2q1 2 1 Fp 素域 p为素数 上椭圆曲线令p 3 a b Fp 满足4a3 27b2 0 由参数a和b定义的Fp上的一个椭圆曲线方程为 y2 x3 ax b 2 它的所有解 x y x Fp y Fp 连同一个称为 无穷远点 记为 的元素组成的集合记为E Fp 由Hass定理 知 p 1 2p1 2 E Fp p 1 2p1 2集合E Fp 对应下面的加法规则 且对加法 形成一个Abel群 i 单位元素 ii x y x y 任给 x y E Fp iii x y x y 任给 x y E Fp 即点 x y 的逆元为 x y iv 令 x1 y1 x2 y2 为E Fp 中非互逆元 则 x1 y1 x2 y2 x3 y3 其中x3 2 2x1 y3 x1 x3 y1且 y2 y1 x2 x1 3 v 倍点运算规则 设 x1 y1 E Fp y1 0 则2 x1 y1 x3 y3 其中 x3 2 2x1 y3 x1 x3 y1这里 3x12 a 2y1 4 注 若 E Fp p 1 曲线E Fp 称为超奇异的 否则称为非超奇异的 例子 F23上的一个椭圆曲线令y2 x3 x 1是F23上的一个方程 a b 1 则该椭圆曲线方程在F23上的解为 y2 x3 x 1的点 0 1 0 22 1 7 1 16 3 10 3 13 4 0 5 4 5 19 6 4 6 19 7 11 7 12 9 7 9 16 11 3 11 20 12 4 12 19 13 7 13 16 17 3 17 20 18 3 18 20 19 5 19 18 群E F23 有28个点 包括无穷远点 2 F2m上的椭圆曲线 F2m上由参数a b F2m b 0定义的一个非超奇异椭圆曲线E F2m 是方程y2 xy x3 ax2 b 5 的解集合 x y 其中x y F2m 连同 E F2m 的加法规则如下 i ii 任给 x y E F2m 则 x y x y iii 任给 x y E F2m 则 x y x x y 即点 x y 的逆为 x x y iv 两个相异且不互逆的点的加法规则 令 x1 y1 x2 y2 E F2m 且有x1 x2则 x1 y1 x2 y2 x3 y3 其中x3 2 x1 x2 a y3 x1 x3 x3 y1 其中 y2 y1 x2 x1 v 倍点规则令 x1 y1 E F2m 其中x1 0 则2 x1 y1 x3 y3 其中x3 2 a y3 x12 1 x3 这里 x1 y1 x1 易见 群E F2m 为Abel群 例 F24上的一个椭圆曲线f x x4 x 1为F2上的一个不可约多项式 易见 F24 F2 x f x k0 k1 k2 k3 k0 k1 k2 k3 k0 k1 k2 2 k3 3 为f x 的零点 ki F2 假定F24上的非超奇异椭圆曲线有下述方程定义 y2 xy x3 4x2 1 注意f 0 方程应表为 1000 y2 1000 xy 1000 x3 1100 x2 1000 3椭圆曲线密码体制 1985年 N Koblitz和V Miller分别独立提出了椭圆曲线密码体制 ECC 其依据就是定义在椭圆曲线点群上的离散对数问题的难解性 1 知E Fq 对点的 运算形成一个Abel群设p E Fq 若p的周期很大 即使p p p 共有t个p相加 成立的最小正整数t 希望t很大 t p的周期 表示为 p t 并且对Q E Fq 定有某个正整数m使Q m p p p 共有t个p相加 定义m pQ m为以p为底Q的对数 椭圆曲线上的点形成的群E Fq 相关它的离散对数问题是难处理的 2 建立椭圆曲线密码体制选取基域Fq Fq的椭圆曲线具体给定为确定的形式 在E Fq 中选一个周期很大的点 如选了一个点P xp yp 它的周期为一个大的素数n 记 P n 素数 注意 在这个密码体制中 具体的曲线及点P和它的n都是公开信息 密码体制的形式采用EIGamal体制 是完全类比过来 a 密钥的生成Bob 使用者 执行了下列计算 i 在区间 1 n 1 中随机选取一个整数d ii 计算点Q dP d个P相 iii Bob公开自己的公开密钥 E Fq p n Q iv Bob的私钥为整数d Alice要发送消息m给Bob Alice执行 i 查找Bob的公钥 E Fq p n Q ii 将m表示成一个域元素m Fq iii 在区间 1 n 1 内选取一个随机数k iv 依据Bob的公钥计算点 x1 y1 kP k个P相 v 计算点 x2 y2 kQ 如果x2 0 则回到第iii 步 计算C m x2 传送加密数据 x1 y1 C 给Bobb Bob的解密过程Bob收到Alice的密文 x1 y1 C 后 执行i 使用私钥d 计算点 x2 y2 d x1 y1 再计算Fq中x2 1 Ii 通过计算m C x2 1 恢复出明文数据m