Assignment

在实验室算法库（部分）的基础上实现

  • 椭圆曲线标量乘（方法选的Sliding window，但固定基点标量乘也需要用到w-NAF，就也实现了w-NAF）
  • 上层SM2模块（数字签名+公钥加密）

Record

fp

有限域模块均采用Montgomery表示，即$x\rightarrow x\cdot R\ (mod\ N)$，输出时（调用fp_wt_bin）再做Mont约简

本科毕设写的格密码库就基于Montgomery做了模约简，同时实现了AVX2的并行优化，但参照的是NFLlib的技术路线，不涉及多精度（Multiprecision Montgomery）

阅读bn_mont_mul_low函数的逻辑后，梳理如下：

ecp

点加/倍点

椭圆曲线模块下的点加基于雅可比坐标（为了避免仿射坐标下的求逆运算；无穷远点即$Z=0$）

仿射坐标下：

转化为雅可比坐标：$(X,Y)\rightarrow(X,Y,1)$，则点加运算过程如下：

倍点的推导类似，算法库提供的接口均已实现

标量乘

翻出了大二买的《椭圆与超椭圆曲线公钥密码的理论与实现》…（吃灰

  • Sliding Window

    Input: 椭圆曲线上的点P, 整数$k=\sum_{j=0}^{l-1}k_j2^j$

    Output: Q=[k]P

    窗口上限=r（模数256-bit下，暂设r=5）

    $k_j=1$时，可以在处理完$h_j$那段后，直接再做$t-(j-r+1)$次倍点运算，共计跳过二进制长度=r的窗口

  • w-NAF

    设整数k为l比特长，则可将k写作SD表达式（binary signed digit representation）$\sum_{j=0}^{l}s_j2^j,\ s_j\in\{-1,0,1\}$

    其中，若要求SD表达式是稀疏的（无任何两个非零值相邻），即为NAF表达式

    在k的所有SD表达式中，NAF表达式的重量最小，且具备唯一性

    将整数k转换为NAF表达式的实现如下（算法1）：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    static int ecp_to_wnaf(const ecp_ctx* group, int8_t* R, const dig_t* k) {
        // default NAF_2(k), i.e. w = 2
        int N_dig = group->N->digs;
        dig_t k_copy[MAX_BN_DIGS];
        bn_copy(k_copy, k, N_dig);
        int j = 0;
        while (!bn_is_zero(k_copy, N_dig)) {
            if (k_copy[0] & 1) {
                if (k_copy[0] & 0x02) {
                    R[j++] = -1;
                    bn_add_dig(k_copy, k_copy, 1, N_dig);
                } else {
                    R[j++] = 1;
                }
            } else {
                R[j++] = 0;
            }
            bn_rsh_low(k_copy, k_copy, 1, N_dig);
        }
        return j;
    }

    当k_copy % 4 = 3时，令R[j]=-1；k_copy % 4 = 1时，令R[j]=1；否则令R[j]=0

    迭代令k_copy = (k_copy - R[j]) >> 1（由于k_copy为奇时，减去R[j]使得其%4=0，因此下一次的k_copy必为偶，保证了NAF的稀疏性），最后输出的R[j]即为NAF表达式的$s_j$

    IEEE P1363标准中还有另一种隐式转化为NAF的方法（算法2）：

    对于算法2生成的NAF表达式正确性证明如下（即证明$d_j=s_j$）：

    测试后发现基于算法2的w-NAF标量乘要略快于算法1（w=2），而且滑动窗口法也比w-NAF要略快

  • 固定基点G

    设基点G的阶有n-bit，则预计算所有的$[2]P,[2^2]P,…,[2^{n}P]$

    调用标量乘时，再将k转换为NAF表示，在每个不为0的位上进行单次点加即可

sm2

略