1.引言

之前在《全国高校密码数学挑战赛》中接触到关于椭圆曲线密码的题目，通过复习大一下学期的《离散数学》和相关文献，将其进行如下总结。

如下4篇文章讲解的很清楚。

Elliptic Curve Cryptography: a gentle introduction - Andrea Corbellini

Elliptic Curve Cryptography: finite fields and discrete logarithms - Andrea Corbellini

Elliptic Curve Cryptography: ECDH and ECDSA - Andrea Corbellini

Elliptic Curve Cryptography: breaking security and a comparison with RSA - Andrea Corbellini

2.数学概念

2.1 同余式

数学上，同余（英语：congruence modulo，符号：≡）是数论中的一种等价关系。当两个整数除以同一个正整数，若得相同余数，则二整数同余。同余是抽象代数中的同余关系的原型。

两个整数a,b,若它们除以正整数m所得到的余数相等，则称a,b对于模m同余，记作a≡b (mod m)。读作a与b关于模m同余。（例 26≡14(mod 12)）。

2.2 有限循环群

现代密码学算法和协议中，消息是作为有限空间中的数字或元素来处理的。加密和解密的各种操作必须在消息之间进行变换，以使变换服从有限消息空间内部的封闭性。然而，数的一般运算诸如加减乘除并不满足有限空间内部的封闭性。所以密码算法通常运行于具有某些保持封闭性的代数结构的空间中，这种代数结构就是有限循环群。在数学中，群是一种代数结构，由一个集合以及一个二元运算组成。群必须满足以下四个条件：封闭性，结合律，存在单位元和存在逆元。 
最常见的群之一是整数集Z以及加法操作。 

有限循环群在群的基础上满足两个额外条件：群元素个数有限以及交换律。循环群由单个元素（产生元）的叠加操作生成，最常见的有限循环群为模拟时钟。 

2.3椭圆曲线定义

在数学上，椭圆曲线群的元素为椭圆曲线上的点，群操作为”+”,”+”的定义为，给定曲线两点P，Q，P+Q等于P和Q两点的连线与曲线交点沿X轴的对称点，如果P=Q，则P+P等于P在曲线上的切线与曲线交点沿X轴的对称点。该群的单位元为无穷远零点记作O=(0,0)，有P+O=P，点P的逆元为其沿X轴的对称点，记作−P。

2.4椭圆曲线有限循环群

基于加密算法的可实现性，密码学上使用基于整数的模加运算产生椭圆曲线循环群，有如下特点：

• 运算速度快
• 精确的运算结果
• 产生有限循环

假如考虑y2=x3−7x+10(mod 19)的集合，该集合中所有的元素如下图所示。模运算把发散的椭圆曲线映射到19*19的正方形空间中，并且保持了原有曲线的上下对称特性。 
 
下图展示了y2=x3−7x+10(mod 19)集合中的元素和椭圆曲线的关系。 
点Q′映射到点Q，点P的对称点也由点−P′映射到点−P。 
 
如果取一个更大的质数p进行模运算，集合中的元素点也会相应地增多。下图展示了利用同一个曲线方程进行不同模运算的结果。在实际的椭圆曲线加密算法中，使用长度为192-256位的质数p进行模运算。

现在我们基于y2=x3−7x+10(mod 19)，利用产生元P=(2,2)来生成ECC有限循环群。如下图所示。

知识来了 | ECC椭圆曲线密码学简介

2.5 椭圆曲线的阶

椭圆曲线定义在有限域上，这也意味着，椭圆曲线上的点也是有限的。所以引出了一个问题：一个椭圆曲线到底有多少个点？

定义“椭圆曲线上点的个数”为 椭圆曲线的阶。

2.6 子群的阶

首先，我们已经定义了阶就是群中点的个数。在子群中也是这样的，但是我们可以换一种表达方式：子群的阶是最小能够使得nP=0的n。
子群的阶和群的阶是有关系的。拉格朗日定理说明了，子群的阶是群的阶的因子。即如果N是群的阶，则其子群的阶n，则n是N的因子（n is a diviser of N）。
找到子群的阶的方法（根据上面讲述的定义和性质就能得出下面的方法）： 
（1）计算群的阶N 
（2）找出所有N的因子 
（3）每个N的因子n，然后乘以P 
（4）在3中，找出最小的n，使得满足nP=0。则n是子群的阶。

2.7 如何找一个基点

在ECC算法种，我们希望找到一个阶数较大的子群。 
通常我们会选择一个椭圆曲线，然后计算它的阶N，选择一个较大的因子n，然后找一个合适的基点。也就是说，我们不是首先找一个基点，然后计算它的阶，而是相反，我们先找到一个合适的阶，然后找以这个数为阶的子群的生成元。

首先，拉格朗日揭示，h=N/n是一个整数（当然，n是N的因子），h有一个自己的名字：cofactor of the subgroup（协因子）。

其次，每个椭圆曲线上的点P，NP=0，因为N是P的阶n的倍数。 
我们可以写成这样 n(hP)=0。 
假设n是一个素数，我们令G=hP，则G就是子群的生成元。 
n必须是素数，若非如此，则nP=0不一定表示n是P的阶，因为P的阶可能是n的一个因子。 
总结如下： 
1. 计算椭圆曲线的阶N。 
2. 选择一个数n当成子群的阶。n应该是N的素因数 
3. 计算h=N/n 
4. 随机选择一个点P 
5. 计算G=hP 
6. 如果G是0，到第4步。否则，我们找到了这个基点。

3、算法优点

1. 短的密钥长度，意味着小的带宽和存储要求。
2. 所有的用户可以选择同一基域上的不同的椭圆曲线，可使所有的用户使用同样的操作完成域运算。

4、椭圆曲线定义