椭圆曲线加密ECDSA 签名 验签原理



  • 椭圆曲线加密 ECDSA 原理简析

    ECDSA椭圆曲线加密算法是DSA数字签名算法的变例之一,ECDSA的基础是ECC椭圆曲线密码学,而ECC的理论基础是椭圆曲线上的点的倍积。

    一、先验知识

    1. 椭圆曲线点的倍积

    **椭圆曲线的点倍积(pointy multiplication)**指的是椭圆曲线上的一个点沿着这条曲线不断的与自身相加,最终落在曲线另一个点上的过程。

    假设起点是椭圆曲线点 P,终点是曲线上点 R,于是有下面的公式:
    R=nPR = nP
    通过上式,R 是计算不出来的,需要一些其他的准备,这里所选择的椭圆曲线的几何方程是固定的,为:
    y2=x3+ax+by^2 = x^3 + ax + b
    方程中的 a 和 b 都是普通标量参数,a 和 b 的取值对于曲线形状是有影响的。如下图中的红线为(a, b) = (-7, 6),蓝线为(a, b) = (-6, 6)

    仍然用上图为例,注意到红色曲线上的 P, Q, R 三点,P + Q = R,即两点相加得到的点 RP, Q 两点直线延长线与椭圆曲线的交点的共轭点,就是关于 X 轴的对称点。从代数上计算:
    P+Q=RP + Q = R

    (xp,yp)+(xq,yq)=(xr,yr)(x_{p}, y_{p})+(x_{q}, y_{q}) = (x_{r}, y_{r})

    由于上面给定了椭圆曲线的代数式,可以得到:
    xr=λ2xpxqx_{r} = \lambda^2 - x_{p} - x_{q}

    yr=λ(xpxr)ypy_{r} = \lambda(x_{p} - x_{r}) - y_{p}

    λ=yqyqxqxp\lambda = \dfrac{y_{q} - y_{q}}{x_{q} - x_{p}}

    如果 P, Q 是同一点呢?lambda可以有特殊取值为:
    λ=3xp2+a2yp\lambda = \dfrac{3x_{p}^2 + a}{2y_{p}}
    有了上面两个公式,就可以计算出点相加和点翻倍。

    2. 椭圆曲线密码学

    现在流行的几种密码学类型之一,通过非对称加密的形式,也就是区分公私钥来进行加密的相关操作。它是基于有限域上特定椭圆曲线进行操作的,最重要的操作是椭圆曲线的点倍积。

    通过简单地逻辑推演,我们可以发现,对于点倍积 Q = nP 而言,在已知起点 P 和 终点 Q 的时,想要计算出 n 是几乎不可能实现的,比如上图中的红色曲线中,想要在左半边通过 P, Q 来计算出 n 是不可能完成的,因为 n 增大的过程总有办法保证 Q 在这个位置不动。

    ECC的使用场景包含数字签名,安全为随机数生成等,在应用中,椭圆曲线必须用完整的参数 (p, a, b, G, n, h) 来定义,其中

    • p是一个很大的质数,用来表示曲线上所有点的范围

    • a, b 是椭圆曲线的系数

    • G 是该曲线上点倍积的基点,对于所有通过点倍积运算得到的点的集合来说,G是生成器

    • n 是基点 G 的可倍积阶数,定义为能够使点倍积 nG 不存在的最小的整数 n

    • h 是一个整数常量,它跟椭圆曲线运算中得到点的集合以及 n 有关系,一般取值为 1

    3. 椭圆曲线数字签名算法理论

    相比于RSA密码学中的DSAECDSA在计算数字签名时所需要的公钥长度可以大大缩短。比如,对于一项安全级别为80 bits的数字签名来说,ECDSA需要的公钥长度仅仅为安全级别的2倍,即160 bits,而同样安全级别要求下的RSA所需公钥长度至少为1024 bits;同时算法所生成的签名长度,不论是ECDSA还是RSA都大约是320 bits,这样一来,ECDSA相对于RSA在应用上的优势就很明显了。

    安全级别:N bits的安全级别意味着攻击者大约要经过 2^N 的运算才能获得本次加密用的私钥,安全级别所代表的的bits越长,安全性也就越好。

    二、数字签名的生成

    假设Alice给Bob发送一则经过数字签名的消息,他们需要首先定义组共同接受的椭圆曲线加密参数,表示为:
    (CURVE,G,n)(CURVE, G, n)
    CURVE 是椭圆曲线的点域和几何方程,G 就是上面提到的生成器,n 就是该曲线的可倍积阶数。n 的作用是,使得 nG = 0 ,即点倍积 nG 的结果不存在,而对于小于 n 的任何一个正整数,点倍积 nG 都可以得到一个合理的处于该椭圆曲线上的点。

    其次,Alice需要创建一对秘钥,私钥是 [1, n - 1] 内的一个随机数:
    dA=rand(1,n1)d_{A} = rand(1, n-1)
    公钥是私钥和基点的椭圆曲线点倍积:
    QA=dA×GQ_{A} = d_{A} \times G
    ok,准备工作就绪,准备开始签署数字签名:

    1. 计算 e = HASH(m)

    2. 计算 z,是 e 的二进制形式下最左边(最高位)L_n个bits,L_n是上述椭圆曲线参数中的可倍积阶数n的二进制长度,z 可能大于 n,但是长度绝对不会比 n

    3. [1, n-1] 内,随机选择一个符合加密学随机安全性的整数 k

    4. 计算椭圆曲线上点:
      (x1,y1)=k×G(x_{1},y_{1}) = k \times G

    5. 计算签名 r 值,如果 r == 0 ,返回步骤3重新计算
      r=x1modnr = x_{1}\mod n

    6. 计算签名 s 值,如果 s == 0 ,返回步骤3重新计算
      s=k1(z+rdA)modn s = k^{-1}(z + rd_{A}) \mod n

    7. 生成的数字签名就是 (r, s)

    第3步中的 k 的选择,不仅要满足加密学的随机安全性要求,要像私钥一样保护起来,并且每次生成一个新的数字签名时,这个 k 必须每次更新。否则,通过上述数字签名过程中的算式相互换算,很容易从中破译出私钥。

    三、数字签名的验证

    对于Bob来说,收到的消息不只是数字签名文件,还有一份公钥。所以验证分为两部分,首先是验证公钥,然后是验证签名文件 (r, s)

    公钥的验证:

    1. 公钥的坐标应该是有效的,不会等于一个极限值空点

    2. 通过公钥的坐标验证它必须是处于该椭圆曲线上的点

    3. 曲线的可倍积数n与公钥的点倍积不存在
      n×QA=On \times Q_{A} = O

    签名文件的验证:

    1. 验证 r , s 都处于 [1, n-1] 范围内的整型数,否则验证失败

    2. 计算 e = HASH(n),这里的HASH函数要与签名时用到的一样

    3. 计算 z

    4. 计算参数 w :
      w=s1modnw = s^{-1} \mod n

    5. 计算两个参数 u1, u2 :
      u1=zwmodn,u2=rwmodnu_{1} = zw \mod n,u_{2} = rw \mod n

    6. 计算 (x1, y1),如果该点不是同一个曲线上的点,验证失败
      (x1,y1)=u1×G+u2×QA(x_{1}, y_{1}) = u_{1} \times G + u_{2} \times Q_{A}

    7. 如果存在下面的恒等式,则验证通过,否则验证失败:
      rx1modnr \equiv x_{1} \mod n

    以上就是所有的签名以及签名验证过程。



  • 太强啦泥组长


Log in to reply
 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

Looks like your connection to Dian was lost, please wait while we try to reconnect.