ECC | AutoSecure

ECC

椭圆曲线密码学（Elliptic Curve Cryptography, ECC）是一类基于椭圆曲线数学理论的密码学技术总称。作为公钥密码体系的一个分支，ECC属于非对称密码学范畴。然而，在实际应用中，ECC通常不直接用于大量数据的加密。相反，它主要用于以下几个方面：

密钥交换协议（如 ECDH, Elliptic Curve Diffie-Hellman）：用于在不安全的通信渠道上安全地建立共享密钥。详情请见：
数字签名算法（如 ECDSA, Elliptic Curve Digital Signature Algorithm）：用于验证消息的完整性和来源。
公钥加密方案（如 ECIES, Elliptic Curve Integrated Encryption Scheme）：通常结合对称加密算法，用于小规模数据的加密。（上文算法）

椭圆曲线示例

椭圆曲线（Elliptic Curve, EC）这个名字很容易让人联想到 “椭圆形”，但实际上椭圆曲线的图像并不是椭圆形的。而之所以叫楠圆曲线，是有历史原因的，即椭圆曲线源自于求椭圆弧长的椭圆积分的反函数。

一般情况下，椭圆曲线可用下列方程式来表示。

例如，当 a = l，b = 0，c =-2，d = 4 时，所得到的椭圆曲线为：

该椭圆曲线 E1，的图像如下图所示，可以看出根本就不是椭圆形。

椭圆曲线运算

首先是加法，请看下图。过曲线上两点 A 画一条直线，找到直线与椭圆曲线的交点，我们将该交点关于 x 轴对称位置的点定义为 A + B。在这里，由两个点 A，B 按上述过程求得的点，就被定义为椭圆曲线上的点 A + B。这样的运算称为“椭圆曲线上的加法运算”。

当两点重合时，“过两点的直线”就应该是“曲线在点 A 的切线”，然后找到该切线与椭圆曲线的交点，将该交点关于 x 轴对称位置的点定义为 A + A，也就是 2A。这样的运算称为“椭圆曲线上的二倍运算”。

此外，我们将点 4 关于 x 轴对称位置的点定义为 -A。这样的运算称为“椭圆曲线上的正负取反运算”。过 A 和 -A 的直线与椭圆曲线之间只有 A 和 -A 这两个交点，于是我们认为这条直线与椭圆曲线在“无限远点” 的位置相交。这个无限远点在图像上画不出来，我们将其记作 O。可以发现，无限远点 O 的作用和数字 0 相近，A + (-A) = 0 是永远成立的。

基于上述“运算” 规则，给定椭圆曲线上的某一点 G，我们就可以求出 2G，3G，…等点的坐标。2G 相当于 G 的二倍，而 3G 则相当于 G + 2G。也就是说，当给定点 G 时，“已知数 x 求点 xG 的问题”并不困难。但反过来，“已知点 xG 求数 x 的问题”则非常困难。这就是椭圆曲线密码中所利用的“椭圆曲线上的离散对数问题”。

有限域上的椭圆曲线上运算

椭圆曲线的图像要形成一条光滑的曲线。其坐标 x，y 必须都是实数。即“实数域 R 上的椭圆曲线”。

椭圆曲线密码所使用的椭圆曲线并非在实数域 R 上，而是在有限域 F_p 上。有限域 F_p 是指对于某个给定的质数P，由 0,1，…，p-1 共 p 个元素所组成的整数集合中定义的加减乘除运算。

来看一个具体的例子：

当这个椭圆曲线 E₂ 位于实数域 R 上时，其图像如下图所示，是一条光滑的曲线。

同样是这条椭圆曲线 E₂，当位于有限域 F₂₃ 上时写作：

即等号左侧 y² 与右侧 x³ + x + 1 的结果除以 23 的余数相等。在有限域 F₂₃ 上的椭圆曲线图像如下图所示，x,y 都只能取 0 到 23 之间的整数，因此图像并不是一条曲线，而是一些不连续的点。其中每一个点的坐标（x,y）都满足“y² 除以 23 的余数”等于“x³ + x + 1 除以 23 的余数”。

如果以椭圆曲线 E₂ 上的点 G=(0,1)为基点，按照椭圆曲线”运算“的规则计算 2G,3G,4G,5G,...，结果如下图。

在这里我们所使用的 p=23 是一个很小的数，因此这个问题还不难解，但当 P 非常大时，要解这个问题是非常困难的。以 NIST 推荐的一种椭圆曲线 Curve P-521 为例，其质数 p 是下面这个长达 157 位的数。

主要需要记住以下两点：

椭圆曲线上的离散对数问题就是已知 G 和 xG 求 x
解橢圆曲线上的离散对数问题是非常闲难的

曲线类型

p192 (NIST P-192)： 192位素数域椭圆曲线，由美国国家标准与技术研究院(NIST)推荐，安全性较低，不推荐用于新系统。
p224 (NIST P-224)： 224位素数域椭圆曲线，NIST推荐，安全性比P-192高。
p256 (NIST P-256)： 256位素数域椭圆曲线，NIST推荐，广泛应用于TLS等协议，提供良好的安全性和性能平衡。
p384 (NIST P-384)： 384位素数域椭圆曲线，NIST推荐，提供更高安全性。
p521 (NIST P-521)： 521位素数域椭圆曲线，NIST推荐的最高安全级别曲线，计算开销较大。
curve25519 (X25519)： 设计用于高效的密钥交换，广泛应用于现代加密协议，提供良好的性能和安全性，在这里也可用于 ECIES。
secp256k1 (Bitcoin curve)： 256位Koblitz曲线，比特币和其他加密货币使用，非NIST标准，但在区块链领域广泛应用。

密钥格式

PKCS#8： 更通用，支持多种算法（如RSA、DSA、EC等），结构更灵活，可以包含额外信息。
RAM： 原始的非对称密钥格式，通常是直接的密钥数据，没有额外的封装或格式化，可能更加紧凑，但缺乏额外的元数据信息，在一些特定的应用场景中使用，但不如标准格式普遍。
DEM： 不是一种密钥格式，而是一种加密机制，通常用于混合加密系统中，使用对称加密来加密实际数据，然后用非对称加密来保护对称密钥，结合了对称加密的效率和非对称加密的安全性。

使用随机填充

在 RSA 的实际使用中，通常会在加密前会向明文中添加一些随机数据,使得每次加密的输入都不同，从而产生不同的密文。目的是增加加密的安全性,防止各种潜在的攻击,如重放攻击、选择明文攻击等。虽然每次加密结果看起来不同，但使用相同的私钥仍然可以正确解密。但在某些特定情境下我们又需要不做随机的填充，因此在勾选上“使用随机填充”后会在加密过程中添加随机数，反之亦然。