共计 3951 个字符，预计需要花费 10 分钟才能阅读完成。
hi，大家好，我是开发者 FTD。明天咱们来介绍一下非对称加密算法的 ECC 算法。
ECC 算法简介
ECC 是 Elliptic Curves Cryptography 的缩写，意为椭圆曲线明码编码学。和 RSA 算法一样，ECC 算法也属于公开密钥算法。最后由 Koblitz 和 Miller 两人于 1985 年提出，其数学根底是利用椭圆曲线上的有理点形成 Abel 加法群上椭圆离散对数的计算困难性。
ECC 算法的数学实践十分深奥和简单，在工程利用中比拟难于实现，但它的单位平安强度绝对较高，它的破译或求解难度基本上是指数级的，黑客很难用通常应用的暴力破解的办法来破解。RSA 算法的特点之一是数学原理绝对简略，在工程利用中比拟易于实现，但它的单位平安强度绝对较低。因而，ECC 算法的能够用较少的计算能力提供比 RSA 加密算法更高的平安强度，无效地解决了“进步平安强度必须减少密钥长度”的工程实现问题。
ECC 算法工作原理
近年来，人们对 ECC 的意识曾经不再处于钻研阶段，开始逐渐进入理论利用，如国家明码管理局颁布的 SM2 算法就是基于 ECC 算法的。上面咱们来认识一下 ECC 的工作原理。
密码学中的椭圆曲线
定义
在无限域 Fp 中定义一个椭圆曲线，罕用
$$
y^2 = x^3 + ax + b
$$
Fp 中只有 p 个元素，p 为素数
Fp 中，
$$
a+b≡c (mod \quad p)，a×b≡c (mod \quad p)，a/b≡c (mod \quad p)
$$
$$
4a^3 + 27b^2 ≠0 (mod\quad p)
$$
a，b 是小于 p 的非负整数
x，y 属于 0 到 p - 1 间的证书，曲线标记为 Ep（a，b）
阶：椭圆曲线上一点 P，存在正整数 n，使得 nP=O∞，则 n 为 P 的阶，若 n 不存在，则 P 是有限阶的，无限域上定义的椭圆曲线上所有点的阶都存在。
椭圆曲线难题
$$
K = kG
$$
其中 K,G 为 Ep（a,b）上的点，k 为小于 n 的整数，n 是点 G 的阶，给定 k 和 G，计算 K 容易，然而给定 K 和 G，求 k 就很难了！
因而，设 K 为公钥，k 为私钥，G 为基点。
ECC 算法加密过程
- A 选定一条椭圆曲线 Ep（a,b），并取曲线上一点作为基点 G
- A 抉择一个私钥 k，并生成公钥 K =kG
- A 将 Ep（a,b）和 k，G 发送给 B
- B 收到后将明文编码到 Ep（a,b）上一点 M，并产生一个随机数 r
- B 计算点 C1=M+rK，C2=rG
- B 将 C1，C2 传给 A
- A 计算 C1-kC2=M+rkG-krG=M
- A 对 M 解码失去明文
攻击者只能失去 Ep（a,b），G，K，C1，C2，没有 k 就无奈失去 M。
ECC 算法签名验签流程
- A 选定一条椭圆曲线 Ep（a，b），并取曲线上一点作为基点 G
- A 抉择一个私钥 k，并生成公钥 K =kG
- A 产生一个随机数 r，计算 R(x,y)=rG
- A 计算 Hash=SHA(M)，M‘=M(modp)
- A 计算 S =（Hash+M’k）/r(modp)
- B 取得 S 和 M ’，Ep(a,b)，K，R(x,y)
- B 计算 Hash=SHA(M)，M’=M(modp)
- B 计算 R ’=（HashG+M’K）/S=(HashG+M’kG)*r/(Hash+M’k)=rG=R（x,y），若 R ’=R，则验签胜利。
以上加解密和签名验签流程只是一个例子，具体利用时能够利用 K =kG 这一个性变幻出多种加解密形式。
ECC 算法实现
定义椭圆曲线上的点(x,y)：
class Pare {
long x;
long y;
public Pare() {super();
}
public Pare(long x, long y) {super();
this.x = x;
this.y = y;
}
// 加法
public Pare add(Pare pare) {if (this.x == Integer.MAX_VALUE) {// 为无穷大时 O +P=P
return pare;
}
Pare res = new Pare();
if (this.y == pare.y && this.x == pare.x) {// 相等时
long d = moddivision(3 * this.x * this.x + EccUtil.e.a, EccUtil.e.p, 2 * this.y);
res.x = d * d - 2 * this.x;
res.x = mod(res.x, EccUtil.e.p);
res.y = d * (this.x - res.x) - this.y;
res.y = mod(res.y, EccUtil.e.p);
} else if (pare.x - this.x != 0) {long d = moddivision(pare.y - this.y, EccUtil.e.p, pare.x - this.x);
res.x = d * d - this.x - pare.x;
res.x = mod(res.x, EccUtil.e.p);
res.y = d * (this.x - res.x) - this.y;
res.y = mod(res.y, EccUtil.e.p);
} else {//P Q 互逆, 返回无穷大
res.x = Integer.MAX_VALUE;
res.y = Integer.MAX_VALUE;
}
return res;
}
// 减法
public Pare less(Pare p) {
p.y *= -1;
return add(p);
}
// 乘法
public Pare multiply(long num) {Pare p = new Pare(this.x, this.y);
for (long i = 1; i < num; i++) {p = p.add(this);
}
return p;
}
// 求余, 解决负号问题
public long mod(long a, long b) {
a = a % b;
while (a < 0) {a += b;}
return a;
}
// 求余取商(a mod b)/c
/*public long moddivision(long a, long b, long c) {a = mod(a,b);
while(a%c != 0) {a += b;}
a = a/c;
return a;
}*/
public long moddivision(long a, long b, long c) {a = mod(a, b);
c = mod(c, b);
a = a * EccMath.exgcd(c, b);
return mod(a, b);
}
@Override
public String toString() {return EccTools.obox(EccTools.long2hexStr(this.x), 4) + " " + EccTools.obox(EccTools.long2hexStr(this.y), 4);
}
}加密：
// 加密
public Message encryption(Pare g, Pare pbk, Pare word) {pbk = g.multiply(privatekey);// 公钥
int d = new Random().nextInt(1024);// 随机数
Pare dg = g.multiply(d);
Pare dp = pbk.multiply(d);
Pare send = word.add(dp);
return new Message(dg, send);
}解密：
// 解密
public Pare decryption(Message m) {Pare pab = m.pa.multiply(this.privatekey);
Pare result = m.pb.less(pab);
return result;
}查看残缺代码请拜访：
https://github.com/ForTheDevelopers/JavaSecurity
ECC 算法劣势：
- 更适宜于挪动互联网：ECC 加密算法的密钥长度很短(256 位)，意味着占用更少的存储空间，更低的 CPU 开销和占用更少的带宽。目前手机曾经越来越遍及，随着越来越多的用户应用挪动设施来实现各种网上流动，ECC 加密算法为挪动互联网安全提供更好的客户体验。
- 更好的安全性：ECC 加密算法提供更强的爱护，比目前的其余加密算法能更好的避免攻打，使你的网站和基础设施比用传统的加密办法更平安，为挪动互联网安全提供更好的保障。
- 更好的性能：ECC 加密算法能够用较短的密钥长度来提供更好的平安。例如，256 位的 ECC 密钥加密强度等同于 3072 位 RSA 密钥的程度(目前一般应用的 RSA 密钥长度是 2048 位)。其后果是你以更低的计算能力代价失去了更高的安全性。经国外无关权威机构测试，在 Apache 和 IIS 服务器采纳 ECC 算法，Web 服务器响应工夫比 RSA 快十几倍。
- 更大的 IT 投资回报：ECC 可帮忙爱护您的基础设施的投资，提供更高的安全性，并疾速解决爆炸增长的挪动设施的平安连贯。ECC 的密钥长度减少速度比其余的加密办法都慢(个别按 128 位增长，而 RSA 则是倍数增长，如：1024 – 2048 – 4096)，将缩短您现有硬件的使用寿命，让您的投资带来更大的回报。
总结
因为 ECC 加密算法在安全性、实现代价和利用效率上较 RSA 算法都有显著的劣势，目前曾经被多家国际标准组织所承受，ECC 加密算法代替 RSA 加密算法，成为行业或组织的公钥明码规范的趋势曾经造成，并已有国家 (美国、日本、韩国和欧洲一些国家) 在国家明码规范中采纳了 ECC 算法体系。我国的国密算法 SM2 就是基于 ECC 算法的。
本文初步介绍了 ECC 算法的基本原理和实现步骤，因为自己程度无限，如有纰漏，还请斧正。
参考
1，ECC 算法介绍
2，解读 ECC 加密算法
对于作者
- GitHub：https://github.com/ForTheDevelopers
- 掘金：https://juejin.cn/user/1204720472953022/posts
- CSDN：https://blog.csdn.net/ForTheDevelopers
- segmentfault：https://segmentfault.com/u/for_the_developers
分割作者
- 微信号：ForTheDeveloper
- 公众号：ForTheDevelopers