关于算法:奇妙的安全旅行之ECC算法

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