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

第5章 非对称密码体制与典型算法 椭圆曲线密码体制 由Neal Koblitz和Victor Miller在1985年分别提出 安全性基于椭圆曲线域离散对数问题的难解性 是目前已知公钥密码体制中每位提供加密强度最高的一种体制 ECC与RSA和分组密码的密钥比较 一、椭圆曲线及其运算 定义 椭圆曲线是两个变元x、y满足形如三次方程 y2+axy+by=x3+cx2+dx+e 的所有点(x,y)的集合，外加一个零点或无穷远点O。 1、实数域上的椭圆曲线 实数域上的椭圆曲线E(a,b)是对于固定的a、b值，满足形如三次方程 y2=x3+ax+b　　　　　　 的所有点的集合，外加一个零点或无穷远点O 其中a、b是实数，x和y在实数域上取值 实数域椭圆曲线的几何图形 实数域椭圆曲线的运算规则 实数域椭圆曲线的运算规则 实数域椭圆曲线的运算规则 实数域椭圆曲线的运算规则 实数域椭圆曲线的运算规则 实数域椭圆曲线运算举例 实数域椭圆曲线运算举例 实数域椭圆曲线运算举例 实数域椭圆曲线运算举例 实数域椭圆曲线运算举例 2、素域GF(p)上的椭圆曲线 GF(p)域上的椭圆曲线E(a,b)是对于固定的a、b值，满足形如三次方程 　　　　y2=x3+ax+b (mod p)　　　　 的所有点的集合，外加一个零点或无穷远点O 其中a、b、x和y在GF(p)域上取值 这类椭圆曲线通常也用 来表示 Hasse定理 如果 是定义在GF(p)域上的椭圆曲线，N是 上的点的个数，则： 素域GF(p) 上椭圆曲线的运算规则 素域GF(p) 上椭圆曲线的运算举例 素域GF(p) 上椭圆曲线的运算举例 素域GF(p) 上椭圆曲线的运算举例 素域GF(p) 上椭圆曲线的运算举例 素域GF(p) 上椭圆曲线的运算举例 3、有限域GF(2n)上的椭圆曲线 是对于固定的a、b值，满足形如三次方程 　　　　 y2+xy=x3+ax2+b　　　　　 的所有点的集合，外加一个零点或无穷远点O 其中a、b、x和y在GF(2n)域上取值 GF(2n)域上的元素是n位的串，共2n个元素 常用 表示，b≠0时构成阿贝尔群 例子 例 7 由不可约多项式 定义的有限域 有一个生成元 。 （1）列出 上所有的非0元素，表明它们与生成元 的关系，并验证 。 （2）若椭圆曲线是 即 ，检验 是否为 上的点，并列出 上所有非0点的坐标值，画出 上点的分布图。 例子 例 7 由不可约多项式 定义的有限域 有一个生成元 。 （1）列出 上所有的非0元素，表明它们与生成元 的关系，并验证 。 例子 例 7 （1）验证 。 例子 例 7 由不可约多项式 定义的有限域 有一个生成元 。 （2）若椭圆曲线是 即 ，检验 是否为 上的点，并列出 上所有非0点的坐标值，画出 上点的分布图。 例子 例 7 由不可约多项式 定义的有限域 有一个生成元 。 （2）若椭圆曲线是 即 ，检验 是否为 上的点，并列出