椭圆曲线点群总结


0X00. 椭圆曲线好在哪里

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

  • 功能性
  • 安全性
  • 性能

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

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

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

0X01. 椭圆曲线上的一些问题

0X01-1. 椭圆曲线上的DL问题–ECDLP

定义:对于定义在某有限域上的曲线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的难解并没有数学上的证明,它只是一个假设

0X01-2. 椭圆曲线上的 Diffie-Hellman 问题–ECDHP

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

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

0X01-3. 椭圆曲线上的判定性 Diffie-Hellman 问题–ECDDHP

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

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

0X02. 椭圆曲线上的签名方案

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

0X02-1 ECDSA

  • 签名的生成
    [P为曲线上一基点,n为P在曲线上的阶,m为消息,H()为输出长度不超过n比特的密码杂凑函数,d为私钥]

    • 在[1, n-1]中选择随机k
    • 计算kP=(x1, y1)
    • 计算r=x1 mod n 若r=0,则跳回第一步
    • 计算e=H(m)
    • 计算s=k^(-1)(e+dr) mod n 若s=0,则跳回第一步
    • 返回(r, s)
  • 签名的验证
    [Q为公钥,有Q=dP]

    • 计算e=H(m)
    • 计算w=s^(-1) mod n
    • 计算u1=ew mod n
    • 计算u2=rw mod n
    • 计算X=u1P+u2Q=(x, y)
    • 若x=r,则签名通过验证

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

ECDSA基于的问题是ECDLP

0X03. 椭圆曲线上的加密方案

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

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

  • 加密

    • 在[0, n-1]选择随机r
    • 计算R=rP,Z=rQ=(xz, yz),若Z=无穷远点,返回第一步
    • ke||kM = KDF(xz, R)
    • c = E(ke, m)
    • t = MAC(kM, c)
    • 返回 R||c||t
  • 解密

    • 计算Z=dR=(xz, yz)
    • 计算ke||kM = KDF(xz, R)
    • 计算m=E(ke, m)
    • 校验 t = MAC(kM, c)

算法基于的问题是ECDHP

0X04. 椭圆曲线上的密钥交换

0X04-1. ECDH

  • 密钥交换
    [双方确定一个曲线G;A的公钥为Qa,B的公钥为Qb;A的私钥为da,B的私钥为db;]
    • A->B:Qa
    • B->A:Qb
    • A计算K=daQb
    • B计算K=dbQa
    • 双方得到同一个点K

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

同样地,ECDH基于ECDHP