ECC

椭圆曲线密码学（英语：Elliptic Curve Cryptography，缩写：ECC）是一种基于椭圆曲线数学的公开密钥加密演算法。

ECC的主要优势是它相比RSA加密演算法使用较小的密钥长度并提供相当等级的安全性。

安全性高

• 有研究表示160位的椭圆密钥与1024位的RSA密钥安全性相同。

处理速度快

• 在私钥的加密解密速度上，ecc算法比RSA、DSA速度更快。
• 存储空间占用小。
• 带宽要求低。

image.png

ECC被广泛认为是在给定密钥长度的情况下，最强大的非对称算法，因此在对带宽要求十分紧的连接中会十分有用。

基于这个秘密值，用来对Alice和Bob之间的报文进行加密的实际方法是适应以前的，最初是在其他组中描述使用的离散对数密码系统。这些系统包括：

• Diffie-Hellman 椭圆曲线迪菲-赫尔曼密钥交换 —ECDH
• MQV（英语：Menezes–Qu–Vanstone）—ECMQV
• ElGamal discrete log cryptosystem ElGamal离散对数密码体制— ECElGamal
• 数字签名算法—ECDSA

ECDSA

每个人可能都听说过ECDSA算法。当我提到数字签名的时候，有些人能够很好地识别出它，有些人却不知道我说的是什么。

我曾经试图去理解ECDSA是如何工作的，但是大部分的在线参考资料都是有缺失的，不足以让我能够很好地理解它。他们要么太基础了──只是解释算法的基础然后留给你“它是如何工作的？”的疑问──要么就是太高阶了，完全略过那些你本该知道但它却假设你已经知道的基础知识。因此，我始终在“它是如何工作的”和“我们如何才能够理解它的工作原理之间”徘徊。

概念

椭圆曲线数字签名算法（ECDSA）是使用椭圆曲线密码（ECC）对数字签名算法（DSA）的模拟。

ECDSA的全名是Elliptic Curve DSA，即椭圆曲线DSA。它是Digital Signature Algorithm (DSA)应用了椭圆曲线加密算法的变种。椭圆曲线算法的原理很复杂，但是具有很好的公开密钥算法特性，通过公钥无法逆向获得私钥。

主要用于对数据（比如一个文件）创建数字签名，以便于你在不破坏它的安全性的前提下对它的真实性进行验证。可以将它想象成一个实际的签名，你可以识别部分人的签名，但是你无法在别人不知道的情况下伪造它。而ECDSA签名和真实签名的区别在于，伪造ECDSA签名是根本不可能的。

你不应该将ECDSA与用来对数据进行加密的AES（高级加密标准）相混淆。ECDSA不会对数据进行加密、或阻止别人看到或访问你的数据，它可以防止的是确保数据没有被篡改。

ECDSA当中有两个词需要注意：Curve（曲线）和Algorithm（算法），这意味着ECDSA基本上是基于数学的。

基础支撑

原理非常简单，有一个数学方程，在图上画了一条曲线，然后你在这条曲线上面随机选取了一个点作为你的原点(point of origin)。接着你产生了一个随机数，作为你的私钥(Private key)，最后你用上面的随机数和原点通过一些复杂的魔法数学方程得到该条曲线上面的第二个点，这是你的公钥(Public key)。

当你想要对一个文件进行签名的时候，你会用这个私钥（随机数）和文件的哈希（一串独一无二的代表该文件的数）组成一个魔法数学方程，这将给出你的签名。签名本身将被分成两部分，称为R和S。为了验证签名的正确性，你只需要公钥（用私钥在曲线上面产生的点）并将公钥和签名的一部分S一起代入另外一个方程，如果这个签名是由私钥正确签名过的数字签名，那么它将给出签名的另外一部分R。简单来说，一个数字签名包含两个数字，R和S，然后你使用一个私钥来产生R和S，如果将公钥和S代入被选定的魔法数学方程给出R的话，这个签名就是有效的。仅仅知道公钥是无法知道私钥或者创建出数字签名。

ECDSA只使用整数数学，没有浮点数，这意味着可能的数值是1，2，3，1.5，2.5则是不被允许的，并且，整数的范围由签名当中所采用的位数决定，更多的位数意味着更大的数字范围，更高的安全性能，因为这使得“猜”到方程当中所采用的具体数字变得更难。正如大家所应该知道的，计算机采用比特来表示数据，一个比特是二进制当中的一位，八个比特表示一个字节。每次你增加一个比特，可表示的最大整数就可以翻一倍，使用4个比特，你可以表示0~15，一共16个数字，6个比特，可以表示64个数字。一个字节，可以表示256个数字，32比特，可以表示4294967296个数字。通常ECDSA会总共使用160比特，它可以表示相当大的数，可以由49个数字在里面。

用途

除了显而易见的“我需要对一份文件/合同进行签名”，还有一个非常流行的应用场景：让我们以一个不想自己的数据被用户修改或者破坏的应用程序为例，比如一个只允许你载入官方地图和不可修改的模块的游戏，或者一部只允许你安装官方应用程序的手机或其它设备。

在这些案例当中，相关文件（应用程序、游戏地图、数据等）会用ECDSA进行签名，公钥会随应用程序/游戏/设备一起捆绑并用来验证签名来确保数据没有被修改，而私钥在本地一个私密的地方进行保存。由于你可以用公钥对签名进行验证，但是不能用它创建或者伪造新的签名，你可以无所顾忌地将公钥随应用程序/游戏/设备一起分发。

这与AES相比，区别是显而易见的。AES加密系统允许你对数据进行加密，但是你需要用密钥来解密，这就要求你将密钥与应用程序一起捆绑，破坏了对数据进行保护防止数据被用户修改的目的。

ECDSA签名过程

大家知道加密算法可以分为对称加密和非对称加密两大类，对称加密就是说加密和解密用的是同一个秘钥（所以秘钥不能公开），非对称加密就是用公钥加密，只有私钥能解密（注意，跟数字签名相反，数字签名是用私钥签，用公钥验证）。

非对称加密算法的其中一种就是用椭圆曲线，就是说我们先规定一条曲线，它大致长这样（不同的曲线可以有不同的参数）：

image.png

这条曲线上，每个点就可以用(x, y)坐标来表示。我们规定x和y是固定大小的整数（通常是256位的整数，32字节）。这条曲线上的点就可以用两个256位的整数来表示。

重点来了：椭圆曲线上的一个点可以乘以一个整数来得到曲线上的另一个点（相当于移动点然后取模），这个乘的操作非常快，而反过来要把两个点相除反推出这个乘数就非常慢，被认为是不可行。所以我们就可以选一个秘密的整数作为私钥，去乘以曲线上的一个固定的“生成点“来得到公钥（曲线上的另一个点），这样一来其他人是无法从公钥算出我们私钥的。

再说一遍，私钥是一个整数，公钥是曲线上的一个点。

由于公钥是一个点，有两个坐标x, y，每个坐标256位，这样总共是64字节，但是我们可以把公钥压缩到33字节，具体方法是取出y的正负号加上2形成一字节，然后照抄x的32字节。因为从x可以推出y的绝对值，所以可以这样压缩。

我们有了私钥，我们就可以去生成签名。我们先把需要签的信息（可以是一次转账内容，或者是证书）哈希一下，得到哈希值。如果是用ECDSA-SHA256那么哈希值就是32字节。

这里需要注意，一般情况下ECDSA生成的签名带有随机性，也就是说我同一个私钥，签同一份信息，签很多次会得到很多份不同的签名，但每一份都是有效的，可验证的。这个随机性来自于，生成签名的时候，你可以给ECDSA一个随机数k。ECDSA先用k乘以生成点G得到一个随机点R，它的x坐标就是签名的第一部分r。签名的第二部分s，是用 （哈希值 + r*私钥）/ k算出来。r和s拼在一起就是数字签名。

那你可能要问了，如果我不希望我的签名带有随机性，比如说我想做测试，需要每次测试得到一样的结果，怎么办呢？rfc6979 规定，在需要deterministic ECDSA的时候，可以把哈希值和私钥拼接在一起用作hmac-drbg的种子，生成一个伪随机数来作为k。因为种子是确定的，所以k, R, s都是确定的。

验证签名的时候，需要先用信息哈希值、s和签发者的公钥来算出R，如果R的x坐标确实是签名里的r，就说明签名确实是签发者的私钥生成的。

小工具：https://javacardos.com/tools/ecdsa-sign-verify

JDK中对于ECDSA的实现

特别注意的是：ECDSA签名算法，只是在JDK1.7之后才有实现，最常见的场景是在微软的产品的安装的产品密钥的设计

1、KeyPairGenerator

KeyPairGenerator 类用于生成公钥和私钥对。密钥对生成器是使用 getInstance 工厂方法（返回一个给定类的实例的静态方法）构造的。

特定算法的密钥对生成器可以创建能够与此算法一起使用的公钥/私钥对。它还可以将特定于算法的参数与每个生成的密钥关联。

有两种生成密钥对的方式：与算法无关的方式和特定于算法的方式。

下面我们将按照指定ECDSA算法去生成秘钥KeyPairGenerator.getInstance("EC");

2、ECDSAPublicKey

ECDSA公用密钥的接口

3、ECDSAPublicKey

ECDSA 专用密钥的接口

4、PKCS8EncodedKeySpec

PKCS8EncodedKeySpec类继承EncodedKeySpec类，以编码格式来表示私钥。

PKCS8EncodedKeySpec类使用PKCS#8标准作为密钥规范管理的编码格式

5、Signature

Signature 类用来为应用程序提供数字签名算法功能。数字签名用于确保数字数据的验证和完整性。

在所有算法当中，数字签名可以是 NIST 标准的 ECDSA，它使用 ECDSA 和 SHA-1。可以将使用 SHA-1 消息摘要算法的 ECDSA 算法指定为SHA1withECDSA。

其他摘要算法和比较如下图：


在Java中，签名和校验，都是通过： Signature 类来实现的。

该类的主要方法如下：

getInstance(String algorithm)
工厂方法，获取Signature实例，而参数：algorithm就是签名算法的名称，这里我们使用的是：SHA256withECDSA

更具体的参数，请浏览：https://docs.oracle.com/javase/7/docs/technotes/guides/security/StandardNames.html#Signature

• initSign(PrivateKey privateKey)

• initVerify(PublicKey publicKey)
  初始化成签名或者校验，Signature类的实例，在同一个阶段只能完成签名或者校验之一的任务，因此调用initSign或者initVeify让Signature进入相应的状态。

• update(byte[] data)
  无论是计算签名，还是校验数据，都需要传入被签名或者被校验的数据，调用该方法进行计算。注意，该方法可以调用多次，通常数据都可能非常大，不可能一次性读入内存（从磁盘上或者网络），因此我们可以对数据进行分块，一次性一KB或者合适的块进行多次调用

• sign()
  获取签名，当所有的数据都调用update计算后，就可以获取签名了，返回的签名是一个byte数组

• verify(byte[] signature)
  校验签名，当所有的数据都调用update计算之后，调用该方法，传递签名数据，如果签名正确，那么返回true，否则返回false，说明数据可能被篡改、伪造，或者对应的私钥不正确。

···
public static byte[] signData(String algorithm, byte[] data, PrivateKey key) throws Exception {
Signature signer = Signature.getInstance(algorithm);
signer.initSign(key);
signer.update(data);
return (signer.sign());
}

public static boolean verifySign(String algorithm, byte[] data, PublicKey key, byte[] sig) throws Exception {
    Signature signer = Signature.getInstance(algorithm);
    signer.initVerify(key);
    signer.update(data);
    return (signer.verify(sig));
}

@Test
public void testSignVerify() throws Exception {
    // 需要签名的数据
    byte[] data = new byte[1000];
    for (int i=0; i<data.length; i++)
        data[i] = 0xa;

    // 生成秘钥，在实际业务中，应该加载秘钥
    KeyPair keyPair = KeyUtil.createKeyPairGenerator("secp256k1");
    PublicKey publicKey1 = keyPair.getPublic();
    PrivateKey privateKey1 = keyPair.getPrivate();

    // 生成第二对秘钥，用于测试
    keyPair = KeyUtil.createKeyPairGenerator("secp256k1");
    PublicKey publicKey2 = keyPair.getPublic();
    PrivateKey privateKey2 = keyPair.getPrivate();

    // 计算签名
    byte[] sign1 = signData("SHA256withECDSA", data, privateKey1);
    byte[] sign2 = signData("SHA256withECDSA", data, privateKey1);

    // sign1和sign2的内容不同，因为ECDSA在计算的时候，加入了随机数k，因此每次的值不一样
    // 随机数k需要保密，并且每次不同


    // 用对应的公钥验证签名，必须返回true
    Assert.assertTrue(verifySign("SHA256withECDSA", data, publicKey1, sign1));
    // 数据被篡改，返回false
    data[1] = 0xb;
    Assert.assertFalse(verifySign("SHA256withECDSA", data, publicKey1, sign1));
    data[1] = 0xa;
    
    Assert.assertTrue(verifySign("SHA256withECDSA", data, publicKey1, sign1));
    // 签名被篡改，返回false
    // 签名为DER格式，前三个字节是标识和数据长度，如果修改了这三个会抛出异常，无效签名格式
    sign1[20] = (byte)~sign1[20];
    Assert.assertFalse(verifySign("SHA256withECDSA", data, publicKey1, sign1));

    // 使用其他公钥验证，返回false
    Assert.assertFalse(verifySign("SHA256withECDSA", data, publicKey2, sign1));
}

···
我们在测试用例中可以看到，只要是数据、签名被修改，或者不正确的私钥都会引发签名验证失败.

参考

https://www.pediy.com/kssd/pediy06/pediy6014.htm