L 记事本

ECC生成元之 Schoof 算法

   #ECC 

对于比特币使用的 secp256k1曲线

P = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
G = 02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

确定这些是参数,(有限域, 生成元,子群的阶) 比较难(数字太大)

前面写到,
ECC椭圆曲线加密

寻找$G$

但是对于如何找到 生成元G, 下面给出一个算法

  1. 确定有限域素数 p
  2. 根据 Schoof 算法,找到椭圆曲线上点的个数,即椭圆曲线对于的群的阶 n
  3. 由于 西罗定理

    设G是以阶为$n = mp^{i}$的有限群，r>=1，p是素数，（p,m）=1，对每个($0<i<=r$)，G中有 $p^i$阶的子群，并且G中每个$p^i$阶的子群是某个$p^{i+1}$阶子群的正规子群。

  4. 从1开始,设计一个最大陪集H个数 Hmax,分解${n}, 得到一个子群G的阶。一般 Hmax 是 很小的数字 ，secp256k1 的曲线h=1;
    • 如果找不到 h,和 Order,那么跳转到步骤1
     for h in [1, Hmax]
   if h * p = n and p is Prime number
      return p as Order , and h ;
  5. 随机选取曲线上一个点$P_0$, 计算 $G = h \cdot P_0$ ,如果 $G = \infty$,那么重新运行5
    可以验证, \(Order \cdot G = \infty\) 那么 $G$ ,$Order$ ,和 $p$ 就是椭圆曲线的参数。

上面过程可以用 $(Z_{26},+)$ 群来简单验证。

Schoof 算法

先埋坑. // TODO