基本概念简介
椭圆曲线密码学（英语：Elliptic Curve Cryptography，缩写：ECC）是一种基于椭圆曲线数学的公开密钥加密算法。与传统的基于大质数因子分解困难性的加密方法不同，ECC 依赖于解决椭圆曲线离散对数问题的困难性。它的优势主要在于相对于其它方法，它可以在使用较短密钥长度的同时保持相同的密码强度。目前椭圆曲线主要采用的有限域有以素数为模的整数域 GF(p)和特征为2的伽罗华域 GF(2^m)

椭圆曲线
椭圆曲线的定义式：$y^2+axy+by=x^3+cx^2+dx+e$
一般方程：$y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6$

最常用方程（维尔斯特拉斯标准形式）
$y^2=x^3+ax+b$，判别式$ Δ=−16(4a^3+27b^2)≠0$
椭圆曲线的定义也要求曲线是非奇异的。几何上来说，这意味着图像里面没有尖点、自相交或孤立点。代数上来说，这成立当且仅当判别式 Δ≠0。

还需要一个无穷远点作为曲线的一部分，用O表示。

椭圆曲线阿贝尔群
O为零元，相反数 P为关于X轴对称的另一边的点，加法规则为直线三点 P+Q+R=0。

几何加法：
普通相交三点：P+Q+R=0
普通相交两点：P+P+Q=0;P+Q+Q=0(有切点)
垂直相交两点：P+Q+0=0(垂直x轴)
垂直相交一点P+P+0=0(垂直x轴+一点相切)

代数加法：
去掉特殊情况：
P=(xp,yp),Q=(xq,yq)
P,Q不同即xp!=xq直线斜率k=(yp-yq)/(xp-xq)
P,Q相同即xp=xq 直线斜率k=3(xp^2+a) / 2yp
这条直线和椭圆曲线的交点 R=(xR,yR)，则：
$$
xR=k2−xP−xQ,yR=yP+k(xR−xP)=yQ+k(xR−xQ)
$$
于是：$P+Q=(xP,yP)+(xQ,yQ)=−R=(xR,−yR)$

$ Q = nP = P + P + \cdots + P = \sum_{i=0}^{n-1} (b_i \cdot 2^i)P, \quad b_i = {0, 1}, \ b_i \text{ 为 } n \text{ 的各比特位值。} $
Q=nP,已知P,Q->求n

曲线的阶
找一个最小的s满足s=|k-j|,kP=jP
点的阶
椭圆曲线上一点P，存在最小的正整数n使得数乘nP=O，n称为P的阶；如果n不存在，则P是无线阶的。

加密原理:
Diffie-Hellman密钥交换算法:
1、
取一个大素数p和两个参数a,b,生成椭圆曲线
$E_p(a,b)$。
K,G都是椭圆曲线上的点，n为G的阶(nG=O)
2、
Alice选择一个私钥n_A，计算公钥
$P_A=n_A\cdot G$
Bob选择一个私钥n_B，计算公钥
$P_B=n_B\cdot G$
3、
密钥交换

$K=n_A\cdot P_B=n_B\cdot P_A$
得到K容易反过来求解nA,nB困难

通信EIGamal算法

  1. 用户A选择$E_P(a,b)$,并选定椭圆曲线上一点作为基点G
  2. 选择$n_A$作为密钥$P_A=n_AG$作为公钥
  3. A公开$E_P(a,b)$和$P_A$，G
  4. B将明文编码到$E_P(a,b)$上的一点$P_m$
  5. 随机k->对应密文$C_m$={kG,$P_m$+k$P_A$}并发给A
  6. M=$P_m+kP_A-kn_AG$