@iPhan 2017-07-18T01:13:49.000000Z 字数 1974 阅读 880

椭圆曲线加密与签名

密码学 椭圆曲线

0X00. 椭圆曲线好在哪里

对公钥密码体制进行评测时，一般要考虑三个方面：

对于给定的安全级别， ECC 比 RSA ， DL 只需要更小的参数；对于更高的安全性级别，参数大小的差异会更加明显。这意味着 ECC 会拥有占用空间更小的密钥、安全证书，以及更快的运行速度。

实际上， ECC 的私钥运算比 RSA 、 DL 快很多倍。在公钥运算中， ECC的运算速度比 DL 快很多倍；当 RSA 选用了一个小的加密指数e（如65535）时，rsa的公钥运算会比ecc快一些。

综合这些情况，在一些性能受限的场合， ECC 的这些优点是很有意义的。

定义：对于定义在某有限域上的曲线E，设一阶为n的基点P，及P生成出来的某点Q，在[0, n-1]间寻找一个数字l，使得Q=lP。

对于ECDLP问题，已知最好的算法是将 Pohlig-Hellman 算法和 Pollard's rho 算法相结合该方法的运行时间是为完全指数时间 O(P^(1/2)) 其中P为基点阶数n的最大素因子。所以在参数选择上，要求n含有较大的素因子，以使该算法的计算量不可能实现。

ECDLP的难解并没有数学上的证明，它只是一个假设

定义：对于定义在某有限域上的曲线E，设一基点P。提供 A=aP、B=bP、P；求出C=abP。

这个问题不比ECDLP困难。已经证明在某些情况下，ECDHP与ECDLP是等价的。

定义：对于定义在某有限域上的曲线E，设一基点P。提供 A=aP、B=bP、P；区分C=abP与P生成的点群上的任意一点Q。

这个问题不比ECDLP困难。在一般的素数阶n中ECDDHP困难性下界为n^(1/2)。

对椭圆曲线上的签名的定义——由四个部分组成：
    1. 生成一组用以定义椭圆曲线及基点的参数
    2. 生成一组公私钥对
    3. 根据输入的参数组，私钥和消息生成一个签名
    4. 根据输入的参数组，公钥，消息和签名来验证这一签名

将ECDSA与DSA对比，很容易发现，本质上他们是相同的算法。只不过ECDSA中将DSA的实数域上的指数运算改成了椭圆曲线点群上的数乘运算。

ECDSA基于的问题是ECDLP

对椭圆曲线上加密的定义——由四部分组成：
    1. 生成一组用以定义椭圆曲线及基点的参数
    2. 生成一组公私钥对
    3. 根据输入的参数组，公钥，明文，生成一个密文
    4. 根据输入的参数组，私钥，密文，拒绝一个密文为非法密文或得到合法密文对应的明文。

[P为曲线上一基点，n为P在曲线上的阶，Q为公钥，且Q=dP，某对称加密算法E()，某密钥导出函数KDF()，明文m]

算法基于的问题是ECDHP

本质上， ECDH 和 Diffie-Hellman 密钥交换协议是相同的。只不过把实数域的指数运算换成了椭圆曲线点群上的数乘运算

同样地，ECDH基于ECDHP