椭圆曲线公钥密码体制(ECC)

基于椭圆曲线密码（ECC）的数字签名技术作者：任艳芳来源：《硅谷》2013年第12期摘要椭圆曲线密码（ECC）基于椭圆曲线离散对数问题，它是有限域上椭圆曲线有理点群的一种密码系统，既可以用于文件传输中的数据加密又可用于文件或密码的数字签名。

和其它公钥密码体制相比，它具有可用的攻击算法少、把明文转化为密文的任务小、处理速度快、密钥>=3、计算所需参数少以及带宽要求低等优点。

本文简略介绍了数字签名技术，主要内容是基于椭圆曲线的数字签名技术。

关键词椭圆曲线；数字签名；签名；验证中图分类号：TN918 文献标识码：A 文章编号：1671-7597（2013）12-0051-031 何为数字签名技术电子签名（Electronic Signature）泛指所有以电子形式存在，依附在电子文件并与其逻辑相关的一种签名，它以密码技术加密文件，辨别文件签署者身份，保证文件的完整性，并表示签署者认可电子文件所陈述事项的内容。

目前最成熟的电子签名技术就是“数字签名（Digital Signature）”，它由两种形式，一种是以公钥及密钥的”非对称型”密码技术制作的电子签名，还有一种是对称的密码技术电子签名，即只有公钥无需密钥。

由于数字签名技术采用的是单向不可逆运算方式，即文件明文用密钥加密得到的密文进行传输，如果不知道密钥，要有密文推导出明文几乎不可能。

并且传输时是以乱码的形式显示的，他人无法阅读或篡改。

因此，从某种意义上讲，使用数字签名的电子文件，甚至比使用签字盖章的书面文件安全得多。

数字签名机制应用在电子网络环境下，可提供四重的安全保证：1）完整性（integrity）：文件接收者通过数字签名核对可确保文件完整性。

2）不可否认性（non-repudiation）：只有文件发送者知道自己的密钥，而且文件具有发送者的数字签名附据，使其无法否认发送事实。

3）可鉴别（authentication）：文件接收者可确认文件发送者的身份。

椭圆曲线密码概述：椭圆曲线密码学（ECC, Elliptic curve cryptography ）是基于椭圆曲线数学的一种公钥密码的方法。

1985年，Neal Koblitz 和Victor Miller 分别独立提出了椭圆曲线密码体制(ECC)，其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。

引言：ECC 被广泛认为是在给定密钥长度的情况下，最强大的非对称算法，因此在对带宽要求十分紧的连接中会十分有用。

ECC 的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA ——提供相当的或更高等级的安全。

ECC 的另一个优势是可以定义群之间的双线性映射，基于Weil 对或是Tate 对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。

不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。

国家标准与技术局和ANSI X9已经设定了最小密钥长度的要求，RSA 和DSA 是1024位，ECC 是160位，相应的对称分组密码的密钥长度是80位。

NIST 已经公布了一列推荐的椭圆曲线用来保护5个不同的对称密钥大小(80, 112, 128, 192, 256)。

一般而言，二进制域上的ECC 需要的非对称密钥的大小是相应的对称密钥大小的两倍。

椭圆曲线密码学的许多形式有稍微的不同，所有的都依赖于被广泛承认的解决椭圆曲线离散对数问题的困难性上，对应有限域上椭圆曲线的群。

引理及有关概念：（1） 无穷远元素（无穷远点，无穷远直线）平面上任意两相异直线的位置关系有相交和平行两种。

引入无穷远点，是两种不同关系统一。

AB ⊥L1， L2∥L1，直线AP 由AB 起绕A 点依逆时针方向转动，P 为AP 与L1的交点，如图1。

Q=∠BAP →π /2则AP → L2，可设想L1上有一点P ∞，它为L2和L1的交点，称之为无穷远点。

直线L1上的无穷远点只能有一个（因为过A 点只能有一条平行于L1的直线L2，而两直线的交点只能有一个）。

椭圆曲线加密算法椭圆曲线密码学（英语：Elliptic curve cryptography，缩写为 ECC），一种建立公开密钥加密的算法，基于椭圆曲线数学。

椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别独立提出的。

ECC的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA 加密算法——提供相当的或更高等级的安全。

ECC的另一个优势是可以定义群之间的双线性映射，基于Weil对或是Tate对；双线性映射已经在密码学中发现了大量的应用，例如基于身份的加密。

不过一个缺点是加密和解密操作的实现比其他机制花费的时间长1.椭圆曲线在数学上，椭圆曲线（英语：Elliptic curve，缩写为EC）为一代数曲线，被下列式子所定义y2=x3+ax+b其是无奇点的；亦即，其图形没有尖点或自相交。

满足此条件的a b满足：4a3+27b2≠0图1在基础上需要定义一个无穷远的点，将此点作为零点：此时椭圆曲线定义为：{(x,y)∈ℝ2|y2=x3+ax+b,4a3+27b2≠0}∪{0}在椭圆曲线中的群的运算律：1. 所有的点都在椭圆曲线上2. 0点作为群上的单元点即P+0=P3. P点关于X轴的对称点为P点的逆即P+(−P)=04.对于位于同一条直线上的三个点P,Q,R.则有P+Q+R=0图2P+Q+R=0（无限远点P Q R三个点的位置是任意的，他们满足加法的结合律，因为这个群是一个阿贝尔群。

2.椭圆曲线加法当P和Q不相等时(x P≠x Q)由于是在阿贝尔群上可以将P+Q+R=0改写为P+Q=−R所以在椭圆曲线上的加法定义为P Q 两点加法为P,Q两点连线与曲线的交点R的关于X轴对称点−R图2-3P+Q=-RP Q两点的直线的斜率为：m=y P−y Q x P−x Q这条线与曲线的交点为：R=(x R,y R)x R=m2−x P−x Qy R=y P+m(x R−x P)因此(x P,y P)+(x Q,y Q)=(x R,−y R)如果在图上表示即为上述的P+Q=−R当P 和Q 不相等时(x P =x Q )( y P =−y q )因为p +(−p )=0图 3 P Q 两点相同时直线的斜率为m =3x P 2+a 2y P 经计算的m =3x P 2+a 2y P x R =m 2−x P −x Q y R =y P +m(x R −x P )图 43.椭圆曲线标量乘法通过上面的加法运算我们可以得出其标量乘法运算可以得出nP=P+P+⋯+P⏟n times从上式可以看出当我们计算nP的时候需要做n次加法，如果n有k位那么的计算时间复杂度变为O(2k),这显然不是快捷的方式。

标题:【原创】椭圆曲线加密分析：FLEXLM ECC问答[7月16日更新到第7部分]作者:readyu时间: 2012-06-25,19:00:18链接: /showthread.php?t=152615说明：我曾经写过ECCTool用于学习和研究椭圆曲线加密在软件上的应用。

椭圆曲线密码学工具 ECCTooL v1.04原帖年代久远不再更新。

v1.05版本我放在本帖3#。

FLexLM ECC是椭圆曲线签名的一个典型应用，不可不察。

我整理了一下FLEXLM ECC方面的研究心得，准备把它完全写出来。

后面会有算法描述的例子代码。

FLEXLM ECC问答 (1)readyu 2012.61. FLEXLM是个虾米东西？FLEXlm是应用广泛的License管理工具。

宣称数千家EDA工具采用它管理授权。

FLEXlm对厂商来说，它的优点是证书管理功能强大，支持平台众多。

对最终用户来说，它的缺点是不够友好，比如Windows下，经常由于某些原因，flexlm服务启动错误。

对于破解者来说，它有着为数众多的教本。

维基百科上的条目为：/wiki/FLEXlmFLEXLM本来属于GLOBEtrotter。

Macrovision曾经收购GLOBEtrotter。

2006年的时候，FLEXLM原来的开发组跑路，另起灶头，产品叫RLM。

/index.php2008年Macrovision把FLEXLM卖了。

现在叫FlexNet Publisher。

/products/flexnet-publisher.htm2. FLexLM 的ECC（椭圆曲线加密）怎么来的？早期的flexlm采用的常规加密，不安全，能被做出lic。

这样的教程是很多的。

flexlm的安全性完全得不到保障，所以，自 v8(大约2001-2002)版本引入了公钥加密算法：椭圆曲线加密。

从此，它一直是flexlm的金钟罩。

包括v9(2003-) , v10(2004-) , v11(2007-), 到最新的版本 v11.10 (2012) 。

标题:【原创】椭圆曲线加密分析：FLEXLM ECC问答[7月16日更新到第7部分]作者:readyu时间: 2012-06-25,19:00:18链接: /showthread.php?t=152615说明：我曾经写过ECCTool用于学习和研究椭圆曲线加密在软件上的应用。

椭圆曲线密码学工具 ECCTooL v1.04原帖年代久远不再更新。

v1.05版本我放在本帖3#。

FLexLM ECC是椭圆曲线签名的一个典型应用，不可不察。

我整理了一下FLEXLM ECC方面的研究心得，准备把它完全写出来。

后面会有算法描述的例子代码。

FLEXLM ECC问答 (1)readyu 2012.61. FLEXLM是个虾米东西？FLEXlm是应用广泛的License管理工具。

宣称数千家EDA工具采用它管理授权。

FLEXlm对厂商来说，它的优点是证书管理功能强大，支持平台众多。

对最终用户来说，它的缺点是不够友好，比如Windows下，经常由于某些原因，flexlm服务启动错误。

对于破解者来说，它有着为数众多的教本。

维基百科上的条目为：/wiki/FLEXlmFLEXLM本来属于GLOBEtrotter。

Macrovision曾经收购GLOBEtrotter。

2006年的时候，FLEXLM原来的开发组跑路，另起灶头，产品叫RLM。

/index.php2008年Macrovision把FLEXLM卖了。

现在叫FlexNet Publisher。

/products/flexnet-publisher.htm2. FLexLM 的ECC（椭圆曲线加密）怎么来的？早期的flexlm采用的常规加密，不安全，能被做出lic。

这样的教程是很多的。

flexlm的安全性完全得不到保障，所以，自 v8(大约2001-2002)版本引入了公钥加密算法：椭圆曲线加密。

从此，它一直是flexlm的金钟罩。

包括v9(2003-) , v10(2004-) , v11(2007-), 到最新的版本 v11.10 (2012) 。

椭圆曲线密码算法（ECC）是一种非对称加密算法，它通过椭圆曲线上的点来实现密钥的生成与交换。

ECC的安全性与RSA等传统非对称加密算法相当，但它所需的密钥长度较短，使得它在移动设备等资源受限环境下具有明显的优势。

而椭圆曲线密钥生成算法就是ECC中用来生成密钥对的重要算法之一。

椭圆曲线密码算法的安全性建立在椭圆曲线离散对数问题的困难性上。

也就是说，在已知一个点P和整数kP的情况下，要很难计算出整数k。

这一性质使得椭圆曲线密码算法成为一种非常有前景的加密算法，因为相较于RSA等算法，可以用更短的密钥长度实现同等级的安全性。

椭圆曲线密钥生成算法的过程可以分为如下几个步骤：1. 选择椭圆曲线参数首先需要选择一个合适的椭圆曲线来作为公开参数。

这个椭圆曲线的选择直接影响到了密钥对的生成过程以及算法的安全性。

一般来说，椭圆曲线的安全性和性能是一对矛盾体，需要在其中寻找一个平衡点。

2. 生成私钥选择一个随机数作为私钥，私钥的大小通常是根据椭圆曲线的位数来确定的。

在ECC中，私钥通常是一个整数，它是生成公钥的重要参数。

3. 计算公钥利用椭圆曲线参数和私钥，可以通过一系列计算得到对应的公钥。

公钥通常是一个椭圆曲线上的点，它将被用于加密和数字签名等操作中。

4. 密钥对生成完成私钥和公钥组成了一个完整的密钥对，可以用于加密通信和身份认证等操作。

椭圆曲线密钥生成算法的实现涉及到大量数论和代数运算，其中包括模运算、点乘、椭圆曲线点加等复杂运算。

如何高效地实现这些运算对于算法的性能和安全性都有很大的影响。

椭圆曲线密钥生成算法是一种重要的非对称加密算法，它在移动设备、物联网设备等资源受限环境下具有明显的优势。

加之它在相同安全级别下所需的密钥长度较短，因此在当前信息安全领域有着广泛的应用前景。

椭圆曲线密钥生成算法（ECC）是当今信息安全领域中备受瞩目的一种加密算法。

其独特的数学原理和高效的计算性能使得它成为了许多安全通信协议和应用中不可或缺的一部分。

ECC （Elliptic Curves Cryptography ）加密算法是一种公钥加密算法，与主流的RSA 算法相比，ECC 算法可以使用较短的密钥达到相同的安全程度。

近年来，人们对ECC 的认识已经不再处于研究阶段，开始逐步进入实际应用，如国家密码管理局颁布的SM2算法就是基于ECC 算法的。

下面我们来认识一下ECC 的工作原理。

椭圆曲线定义在引入椭圆曲线之前，不得不提到一种新的坐标系-------射影平面坐标系，它是对笛卡尔直角坐标系的扩展，增加了无穷远点的概念。

在此坐标系下，两条平行的直线是有交点的，而交点就是无穷远点。

两者的变换关系为：笛卡尔坐标系中的点a （x,y ），令x=X/Z ，y=Y/Z ，则射影平面坐标系下的点a 的坐标为（X,Y,Z)，如点（2,3）就转换为（2Z,3Z,Z ）。

椭圆曲线定义：一条椭圆曲线在射影平面上满足方程：Y 2Z+a 1XYZ+a 3YZ 2=X 3+a 2X 2Z+a 4XZ 2+a 6Z 3的所有点的集合，且曲线上每个点都是非奇异的。

该方程有名维尔维斯特拉斯方程，椭圆曲线的形状不是椭圆，只是因为其描述的方程类似于计算一个椭圆周长的方程。

转换到笛卡尔坐标系下的方程为：y 2+a 1xy+a 3y = x 3+a 2x 2+a 4x+a 6 加法法则运算法则：任意取椭圆曲线上两点P 、Q （若P 、Q 两点重合，则做P 点的切线）做直线交于椭圆曲线的另一点R’，过R’做y 轴的平行线交于R 。

我们规定P+Q=R 。

（如图）●此处+不是简单的实数相加，是抽象出来的 ●O∞+P=P ，O∞为零元 ● 曲线上三个点A,B,C 处于一条直线上，则A+B+C=O∞下面，我们利用P 、Q 点的坐标(x 1,y 1)，(x 2,y 2)，求出R=P+Q 的坐标(x 4,y 4)。

P,Q,R'共线，设为y=kx+b ，若P≠Q ，k=(y 1-y 2)/(x 1-x 2)若P=Q ，k=(3x 2+2a 2x+a 4 -a 1y) /(2y+a 1x+a 3)解方程组得到：x 4=k 2+ka 1-a 2-x 1-x 2;y 4=k(x 1-x 4)-y 1-a 1x 4-a 3;密码学中的椭圆曲线定义在有限域Fp 中定义一个椭圆曲线，常用y 2=x 3+ax+b1.Fp 中只有p 个元素，p 为素数 2.Fp 中，a+b≡c (mod p)，a×b≡c (mod p)，a/b≡c (mod p) 3.4a 3+27b 2≠0 (mod p) a ，b 是小于p 的非负整数 4. x ，y 属于0到p-1间的证书，曲线标记为Ep （a ，b ） 阶：椭圆曲线上一点P ，存在正整数n ，使得nP=O∞，则n 为P 的阶，若n 不存在，则P 是无限阶的，有限域上定义的椭圆曲线上所有点的阶都存在。