Post

ECC Study

Posted Updated
By sfeng
7 min read
ECC Study

Preface

The Elliptic Curve Cryptography (ECC) is modern family of public-key cryptosystems, which is based on the algebraic structures of the elliptic curves over finite fields and on the difficulty of the Elliptic Curve Discrete Logarithm Problem (ECDLP). The ECC cryptography is considered a natural modern successor of the RSA cryptosystem, because ECC uses smaller keys and signatures than RSA for the same level of security and provides very fast key generation, fast key agreement and fast signatures.

  本篇主要目的是对ECC建立一个基本概念，由于里面涉及到很多算法知识，博主也从理解它的实现和用法着手，描绘ECC算法的一个概貌。

Elliptic Curves

  在密码学中选用了Elliptic Curves一种简单的形式：y2 = x3 + ax + b。其中不同的a和b的值会得到不同的ECC曲线。例如用于bitcoin加密的ECC曲线为：
y2 = x3 + 7 (secp256k1)
  当然定义在有限域上的椭圆曲线方程还需要取模。

  这里要提示下，并非所有的ECC曲线都有足够的安全性来做加解密或者签名。这里列出了一些ECC曲线是否安全。

  还有几个概念需要了解。

  1. EC point 就是椭圆曲线上的点。
  2. Order
    The order of the curve is the total number of all EC points on the curve.当定义在有限域上时，椭圆曲线上的点是有限的，点的个数就是order。
  3. Multiplication of EC Points 拿到ECC曲线上的一对或者一个点，可以对它（们）进行加减和乘，当然这不是平常代数意义上的加减乘，具体可以看Elliptic_curve_point_multiplication。
  4. Cofactor
    Cofactor是在#3的计算下，可以从某个点开始导出在该ECC曲线上部分或者所有点的集合。有的曲线只存在一个这样的集合，而也可能有多个这样的集合。Cofactor就是集合的个数。例如：
    secp256k1 cofactor = 1
    Curve25519 cofactor = 8
    Curve448 cofactor = 4
    这些子集要求互相不重复，它们共同组成了整个曲线上order个EC points。
  5. Generator Point
    上面说子集不重合，并非所有的EC point都可以做到，上述子集中任取一个点做Multiplication操作得到的很可能是该子集的子集，那得到的集合恰恰是这个子集的就叫这个subgroup的generator point。
    一般情况下Generator point会有很多个，当选用该ECC Curve并设计算法时，要谨慎选取这个点以得到更好性能。这个点一般叫做“G”。
  6. Private Key
    在RSA中首先要找到一对大素数来生成私钥公钥，ECC中的私钥则是一个随机数。唯一要求就是要小于order，当然考虑安全性，位数要足够多，比如256 bits。
  7. Public Key
    Public Key是对G做private key次加生成，表示为 P = (private key) * G。

  OK，这些基本元素齐了，总结下（摘抄下，嘿嘿），一个ECC算法包含下面几个元素：

  • Еlliptic curve (EC) over finite field 𝔽p
    • cofactor
    • n order
    • p mod
    • a rom_lib_ecc_verify of x
    • b constant
  • G == generator point (fixed constant, a base point on the EC)
  • k == private key (integer) 随机生成
  • P == public key (point) P = k * G（由于ECDLP，很难由P倒推出k）

  说到很难推出k，涉及到Curve Security Strength。这里可以简单的认为它就是k的长度的一半。也就是key为256 bits时，它的Security Strength大约为128 bits。

How to Sign and Verify

  这个过程就抄了，哈哈。

Generate Signature

  1. 生成一个随机数 k1，它也是小于order就好
  2. 利用 P1 = k1 * G 计算出点 P1
  3. P1 点的 x 坐标定义为R
  4. 对需要签名的数据计算hash，记为 H
  5. 计算S = k1-1 (H + k0 * R) mod p ，这个p是上文提到的模运算的底

  最终的签名为R（20字节）+ S（20字节），总共40字节。

Verify Signature

  验签用下面的公式：
P2 = S-1 * H * G + S-1 * R * P (其中P是公钥， S和R共同组成签名，G是generator pointer，H是数据hash)

  如果P2的横坐标等于R，则验签成功。

ECDH，ECDSA，EdDSA and ElGamal

  这几个概念经常搞混，列在这里以备后查。

  • ECDH (Elliptic Curve Diffie-Hellman)
    用在两个机构之间通过非安全的通道做key的交换，这里的key一般是对称密钥。下面这个例子很容易理解啊，就直接抄过来了。
    1. Alice generates a random ECC key pair: {alicePrivKey, alicePubKey = alicePrivKey * G}
    2. Bob generates a random ECC key pair: {bobPrivKey, bobPubKey = bobPrivKey * G}
    3. Alice and Bob exchange their public keys through the insecure channel (e.g. over internet)
    4. Alice calculates sharedKey = bobPubKey * alicePrivKey
    5. Bob calculates sharedKey = alicePubKey * bobPrivKey
    6. Now both Alice and Bob have the same sharedKey == bobPubKey * alicePrivKey == alicePubKey * bobPrivKey
  • ECDSA (Elliptic Curve Digital Signature Algorithm)
    ECDSA则用来做数字签名，以保证数据的真实性和完整性（authenticity and integrity）。与RSA比较，在达到相同level的security的同时，key的长度比RSA要小的多，所以签名和验签的速度会快很多。
    最典型的应用之一是用于bitcoin的secp256k1.
  • EdDSA (Edwards-curve Digital Signature Algorithm) 同ECDSA类似，不过在安全性和性能上有些优势。比如Ed25519和Ed448。
  • ElGAmal 既可以用来做key exchange，也可以用来做签名。不过相比ECDH和ECDSA不是很常用。

  关于ECC，就先总结这么多吧。

Reference

Elliptic Curve Cryptography
ECC-zhihu
ECC-wiki
Online Elliptic Curve Visualization Tool
Multiplication of EC Points
ECDH Key Exchange

Security
ECC
This post is licensed under CC BY 4.0 by the author.