ECC/ECDSA深入浅出原理和实际应用步骤_ecc 点乘

一些基础概念

点加

“点加”是ECC计算中最基本和原始的概念，它描述群当中的两个元素（点）之间的操作，而实际运算中大量使用的是“点乘”。

但是不要被“点乘”这个名字所迷惑，其实它描述的是：对同一个点进行多次操作时的规则，很多常见的写法例如$\kappa$G ，很容易误导初学者–其实比较正规的写法应该是$\kappa$ $⨀$G，描述的是：针对点G进行“k-1”次点加操作所得到的结果。这不是一个简单的算数乘法。

阿贝尔群

在数学中，群是一种代数结构，由一个集合以及一个二元运算所组成。已知集合和运算(G,*)如果是群则必须满足如下要求。

封闭性： ∀a,b∈G，ab ∈ G
结合性： ∀a,b,c∈G ，有 (ab)c = a (b*c)
单位元： ョe∈G， ∀a ∈G，有ea = ae = a
逆元： ∀a ∈G ，ョb∈G 使得 ab = ba = e
交换性: ∀a,b∈G，ab = ba

椭圆曲线

椭圆曲线是域上亏格为1的光滑射影曲线。对于特征不等于2的域，它的仿射方程可以写成：y^2 =x^2 +ax^2+bx+c。复数域上的椭圆曲线为亏格为1的黎曼面。Mordell证明了整体域上的椭圆曲线是有限生成交换群，这是著名的BSD猜想的前提条件。阿贝尔簇是椭圆曲线的高维推广。

椭圆曲线是连续的，并不适合用于加密；所以，我们必须把椭圆曲线变成离散的点，我们要把椭圆曲线定义在有限域上。我们给出一个有限域Fp

• Fp中有p（p为质数）个元素0,1,2,…, p-2,p-1
• Fp的加法是a + b ≡ c ( m o d p ) a+b $\equiv$ c $(\mathrm{mod}p)$a+b≡c(modp)
• Fp的乘法是a × b ≡ c ( m o d p ) a×b $\equiv$ c $(\mathrm{mod}p)$a×b≡c(modp)
• Fp的除法是a ÷ b ≡ c ( m o d p ) ， 即 a × b − 1 ≡ c ( m o d p ) ， b − 1 也 是
  一 个 0 到 p − 1 之 间 的 整 数 ， 但 满 足 b × b − 1 ≡ 1 ( m o d p ) a÷b
  $\equiv$ c $(\mathrm{mod}p)$，即 a×b^{-1} $\equiv$ c $(\mathrm{mod}p)$，b^{-1}
  也是一个0到p-1之间的整数，但满足b×b^{-1}$\equiv$ 1 $(\mathrm{mod}p)$ a÷b≡c(modp)
• Fp的单位元是1，零元是 0
• Fp域内运算满足交换律、结合律、分配律
• 椭圆曲线Ep(a,b)，p为质数，x,y∈[0,p-1]

为了避免出现曲线上任意点有两条或以上的切线，需满足4a^3+27b $\ne$ 0， O是曲线的唯一的无穷远点。

椭圆曲线算法

椭圆曲线通常用下面的方程式来表示:

如果 a 和 b 取的值不同，那么对应的曲线形状也会不一样：
假设现在有这样一条椭圆曲线。画一条直线，与曲线相交于 3 个点，分别是 P,Q,R ，根据点加法运算的定义，可以得到 P+Q+R=0 ，那么 P+Q=−R ， −R 的定义是关于 x 轴对称所得到的一个点，如下图所示，这就是点加法的几何表达。

我们移动这条直线，让 P,Q 两点重合：

根据上面的点加法规则，可以得到 2P 点，以此类推，不断去连接 P 点和 nP 点，就可以得到 3P,4P… (n+1)P 点。点乘就定义为 kP ，表示 P 点的 k 次相加。

上面说完了椭圆曲线的定义和运算，最后来说一下椭圆曲线的安全性，对于非对称加密来说，关键点就是无法从加密的数据中和公钥中去推算私钥，这里怎么实现的呢？在上面我们得到了点乘的定义，任意一点 R 可以通过这个点乘公式 R=kP 计算得到。这里的关键在于即使知道了 P 和 R 点，我们也无法计算得到 k ，在椭圆曲线算法中没有减法或者除法这种逆向操作。 这是椭圆曲线算法安全性的基础，这个特性也称之为单向陷门函数。这个整数 k 通常就是算法中的私钥，而 R 对应的就是公钥。

椭圆曲线签名具体步骤

1. Alice选定一条椭圆曲线E，并取椭圆曲线上一点作为基点G 假设选定E29(4,20)，基点G(13,23) , 基点G的阶数n=37
2. Alice选择一个私有密钥k（k<n）比如25，并生成公开密钥K=kG = 25G = (14,6）
3. Alice将E和点K、G传给Bob
4. Bob收到椭圆曲线E，选定的基点，公钥后，将待传输的明文编码到E上的一点M，并产生一个随机整数k1（k1<n,n为G的阶数） 假设r=6 要加密的信息为3,因为M也要在E29(4,20) 上，所以M=(3,28)
5. Bob计算点C1 C2
   
6. Alice收到信息后，计算C1 − k C2=M

​