第10章 椭圆曲线和密码学

椭圆曲线加密算法椭圆曲线密码学（英语：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),这显然不是快捷的方式。

内容安全研究室朱潜报告的主要内容⏹群和域的相关概念⏹椭圆曲线的定义和运算法则⏹椭圆曲线离散对数问题⏹椭圆曲线密码体制⏹椭圆曲线密码的优势⏹曲线密码体制的应用为什么要在有限域上研究椭圆曲线密码？密码学常在有限域的基础上研究椭圆密码曲线，在有限域的椭圆m基础上。

基于有限域Fp，而不是使用实数域、曲线主要是基于Fp和F2是因为实数计算时会产生截段误差，无法满足密码算法的精确性，而m是由于可以在计算机处理时大大提且实数运算的速度很慢。

基于F2高处理速度。

群和域的相关概念定义1：任意给定一个非空集合F和其上的二元运算“*”，如果满足（1）封闭性：对任意a,b∈F,存在c ∈F,使得c=a*b ∈F;（2）结合律：对于任意a,b∈F,都有(a*b)*c=a*b*c;（3）单位元e存在：即存在e ∈F,对于任意a ∈F,都有a*e=e*a;（4）逆元存在：对于任意a ∈F,存在b ∈F,使得a*b=b*a=e;则称集合F关于二元运算“*”构成群，记为（F，*）。

在群（F，*）中，如果对于任意a ,b∈F,都有a*b=b*a,则称群（F，*）是交换群，也称为阿贝尔（Abel）群。

定义2：设“+”，“*”是G上的二元运算，如果满足：（1）（G，+）是一个交换群，其单位元记为0；（2）（G-{0}，*）是交换群，其单位元记为1；（3）运算“*”对“+”可分配，即对任意a ,b,c∈G,都有a*(b+c)=a*b+a*c(a+b)*c=a*c+b*c则称（G,+,*）是域。

群和域的相关概念定义3：有限域，如果域F中的元素个数有限，则称F为有限域或伽罗华域，其中F中的元素个数称为有限域F的阶，记为∣F ∣。

对有限域而言，其元素的个数必为一素数的方幂。

即存在一个q阶有限域F，当且仅当q是一个素数的幂，即q=p m,其中，p是一个素数，并称为域F的特征，m是一个正整数。

若m=1,则域F就称为素域。

定义4：设p是一个素数，以p为模，则模p的全体余数的集合{0，1，2，……，p-1}关于模p的加法和乘法构成一个p阶有限域，简称素域，并且用符号Fp表示。

密码学是研究保护信息安全的科学，其中的一个分支是椭圆曲线密码学。

椭圆曲线密码学通过利用椭圆曲线上的离散对数问题，实现了高强度的加解密算法。

而贝尔曲线则是椭圆曲线密码学的重要组成部分。

贝尔曲线是以Elwyn R. Berlekamp的名字命名的，他是一位在代数编码理论领域有显著成就的科学家。

贝尔曲线之所以成为椭圆曲线密码学的关键要素，是因为它具有良好的性质，可在加解密算法中得到应用。

在椭圆曲线密码学中，贝尔曲线被用作椭圆曲线上的一个点的生成器。

通过选择适当的贝尔曲线方程和椭圆曲线上的基点，我们可以构建出一个加密强度很高的密码体系。

与其他加密算法相比，椭圆曲线密码学具有许多优势。

首先，它使用的曲线方程相对简单，计算效率较高，能够在有限的资源下完成加解密操作。

其次，椭圆曲线密码学还具有极高的安全性。

由于椭圆曲线上的离散对数问题在目前的计算能力下非常难以解决，因此攻击者很难通过破解椭圆曲线密码系统来获取加密信息。

椭圆曲线密码学在现代密码学中的应用非常广泛。

它被用于互联网安全传输协议（SSL/TLS）、数字签名、密钥交换等领域。

比特币等大型数字货币系统也广泛使用椭圆曲线密码学来保护交易的安全性。

尽管椭圆曲线密码学具有许多优势，但它也存在一些挑战和限制。

首先，生成适合用于密码学的椭圆曲线需要高度的数学和计算技术。

其次，在处理大量数据时，椭圆曲线计算的效率较低。

此外，椭圆曲线密码学也受到量子计算的威胁。

一旦量子计算机问世，它们可能能够更有效地解决椭圆曲线上的离散对数问题，从而破解现有的椭圆曲线密码系统。

为了应对这些挑战，研究人员正在努力开发新的密码学算法，以防止量子计算机对椭圆曲线密码学的攻击。

其中一种方法是使用更高强度的曲线，以增加安全性。

另一种方法是开发基于其他数学问题的密码学算法，能够抵御量子计算的攻击。

总结而言，贝尔曲线与椭圆曲线密码学是现代密码学中不可或缺的部分。

它们通过利用椭圆曲线上的离散对数问题，提供了高强度的加解密算法。

椭圆曲线加密算法（⼀）椭圆曲线加密和签名算法简述椭圆曲线密码学，简称ECC。

是⼀种建⽴公开加密的算法，也就是⾮对称加密。

和RSA类似。

被公认在给定密钥长度下最安全的加密算法。

应⽤范围很⼴，主要的三个技术TLS、PGP、SSH都在使⽤它，特别是以BTC为代表的数字货币。

椭圆曲线椭圆曲线并不是我们⾼中时学习的椭圆形状，其名字的由来是应为椭圆曲线的描述⽅程，类似于计算⼀个椭圆周长的⽅程。

这⾥⽤来加密的椭圆曲线的定义是⼀个特殊情况。

椭圆曲线暂时可以简单的理解为：其中：a和b决定了曲线在坐标系的不同形状。

举个例⼦：当b=1,a的取值从2到-3时，曲线的形状如下：特殊曲线：当a=b=0时(左)，或a=-3,b=2时(右)，这两条都不是符合标准的曲线。

阿贝尔群数学上，群是指定义了⼆元操作运算并且⽤符号“+”表⽰的⼀个集合。

则必须满⾜以下要求：封闭性：如果a和b都是群成员，那么a+b也是群成员。

组合性：(a+b)+c=a+(b+c)单位元：存在确切的⼀个值可以保证 a+0=0+a=a成⽴，我们称之为单位元逆元：每个成员都有⼀个相反数：对于任意值a必定存在b使得a+b=0这样的群我们称之为阿贝尔群。

另外阿贝尔群还应该满⾜交换律a+b=b+a我们所熟知的在整数范围内的加法运算(Z,+)就是阿贝尔群封闭性：a、b属于整数，a+b也属于整数组合性：(a+b)+c=a+(b+c)单位元：0值就是单位元逆元：a的逆元就是-a所以(Z,+)是⼀个阿贝尔群。

椭圆曲线的加法假设我们有这样⼀条椭圆曲线y2=x3-x,曲线上有两点P、Q，过P和Q做⼀条直线，交椭圆曲线于R'点，再过R'点做垂直于X轴的直线，交椭圆曲线于另⼀点R，我们定义P+Q=R。

当P=Q时候，则是过P点的切线交于椭圆曲线于R'，此时R=2P，如图所⽰：当有k个相同的点P相加时，记做kP，如：P+P+P=2P+P=3P，如图：椭圆曲线密码利⽤上述“运算”中的“椭圆曲线上的离散多数问题”，就像RSA利⽤“⼤数质因数分解”⼀样。

10.３椭圆曲线算术椭圆曲线理论是一个古老而深奥的数学分支，已有100多年的历史，一直作为一门纯理论学科被少数数学家掌握。

它被广大科技工作者了解要归功于20世纪80年代的两件重要的工作。

第一，Weil应用椭圆曲线理论证明了著名的费尔玛大定理。

第二，Neal Koblitz和ler把椭圆曲线群引入公钥密码理论中，提出了基于椭圆曲线的公钥密码体制ECC（Elliptic Curves Cryptosystem），取得了公钥密码理论和应用的突破性进展。

20世纪90年代，最通用的公钥密码体制是RSA公钥密码体制和DH公钥密码交换算法。

其密钥长度一般为512比特。

1999年8月22日RSA-512被攻破，所以，这些公钥不得不被加长。

为了达到对称密钥128比特的安全水平，NIST推荐使用3072比特的RSA密钥。

显然这种密钥长度的增长，对本来计算速度缓慢的RSA来说，无疑是雪上加霜。

ECC的提出改变了这种状况，实现了密钥效率的重大突破。

大有以强大的短密钥优势取代RSA成为新一代公钥标准（事实标准）之势。

ECC的安全性和优势得到了业界的认可和广泛的应用：（1）1998年ECDSA（椭圆曲线数字签名算法）被确定为ISO/IEC数学签名标准ISO14888-3;（2）1999年2月ECDSA被ANSI确定为数字签名标准ANSI X9.62-1998，ECDH（椭圆曲线Diffie-Hellman）被确定为ANSI X9.63;（3）2000年2月ECDSA被确定为IEEE标准IEEE1363-2000，同期，NIST确定其为联邦数字签名标准FIPS186-2。

1.椭圆曲线椭圆曲线并非椭圆，之所以称为椭圆曲线是因为它的曲线方程与计算椭圆周长的方程类似，一般来计，椭圆曲线的曲线方程是以下形式的三次方程：y2+axy+by=x3+cx2+dx+e (1)其中a,b,c,d,e是满足某些简单条件的实数。

其中包括称为无穷远点的元素。