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 算法加密过程
  1. A选定一条椭圆曲线Ep（a,b），并取曲线上一点作为基点G
  2. A抉择一个私钥k，并生成公钥K=kG
  3. A将Ep（a,b）和k，G发送给B
  4. B收到后将明文编码到Ep（a,b）上一点M，并产生一个随机数r
  5. B计算点C1=M+rK，C2=rG
  6. B将C1，C2传给A
  7. A计算C1-kC2=M+rkG-krG=M
  8. A对M解码失去明文

攻击者只能失去Ep（a,b），G，K，C1，C2，没有k就无奈失去M。

ECC 算法签名验签流程
  1. A选定一条椭圆曲线Ep（a，b），并取曲线上一点作为基点G
  2. A抉择一个私钥k，并生成公钥K=kG
  3. A产生一个随机数r，计算R(x,y)=rG
  4. A计算Hash=SHA(M)，M‘=M(modp)
  5. A计算S=（Hash+M'k）/r(modp)
  6. B取得S和M'，Ep(a,b)，K，R(x,y)
  7. B计算Hash=SHA(M)，M'=M(modp)
  8. 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