ECDSA高性能硬件实现——算法详解与模块划分

  ECDSA全称椭圆曲线数字签名算法,它是基于素数域的椭圆曲线对信息进行加签与验签。其核心在于对信息的加签,及对加签的信息进行验签,那么下面介绍该算法流程。

  假设Alice希望对消息m进行签名,并将消息传给Bob。首先Alice要选用一条椭圆曲线,其参数组为D = ( p,S,a,b,G,n,h) ,对应的密钥对为( k , Q ) ,其中各参数解释为:

  1. 域的阶p;
  2. 种子S,用于参数随机数;
  3. 两个椭圆曲线系数a,b∈Fp,定义了Fp上椭圆曲线E的等式; 
  4. 定义椭圆曲线上的一个有穷远点 ,一般称其为椭圆曲线基点;
  5. G的阶n,为素数域的模数;
  6. 余数因子h。

   密钥中记k为私钥,Q为公钥。其中Q=kG;

Alice将按如下步骤进行签名:
  1.利用种子S产生一个随机数d,d∈(0,n);

  2.计算dG=(x1,y1);

  3.计算r=x1 mod n,若r=0,则返回第一步;

  4.计算d-1 mod n;

  5.计算哈希值e = H(m),    //此步骤可在信息到来时便开始进行;

  6.计算s=d-1(e+kr)mod n。 若s = 0,则返回步骤1;

  7.(r,s)即为对消息m的签名,最后Alice将(D,r,s,m,Q)传输给Bob。

Bob收到(D,r,s,m,Q)后,要对消息进行验签,检验消息m是否被篡改。

Bob将按以下步骤进行验签:

  1.计算哈希值e = H(m);

  2.计算w = s-1 mod n;

  3.计算u1=ew mod n 及u2=rw mod n;

  4.计算X=u1G+u2G=(x2,y2);

  5.若X = 0,则验签失败,输出invalid_verify;否则计算v = xmod n;

  6.若v = r,则验签成功,输出valid_verfy。

注:上述计算都是基于整数,因为是基于数字椭圆曲线加密,曲线的点选取也是整数,所有一系列计算都是整数,如果出现小数。

下面来将上述算法模块化,具体化:

  注意到我们使用过的模块,

  加签步骤1:随机数产生模块,要求输出一个随机数种子S,输出一个(0,n)的随机数d。

  加签步骤2:点乘模块,也成为标量乘模块,随机数d为一个标量,G为椭圆曲线上的一个点。标量乘表示多个点相加,比如5G = 2G+2G+G;为啥不能是4G+G或者直接5G,算法不允许呀,因为这不是最简的点运算形式。

    2G及2G+G才是最简的点运算形式,其中2G称为倍点,2G+G称为点加(注意2G运算后为一个新的点P,也落在椭圆曲线上)。

  加签步骤3:模乘模块,两个标量相乘并取模。

  加签步骤4:模逆模块,定义d*d-1=1(mod n),即d*d-1 = kn(k=1,2,3…)。素数域上的取逆元操作。

  加签步骤5:哈希模块,输入消息m,输出哈希值H;

  加签步骤6:其中kr和d-1(e+kr)都是模乘模块,e+kr 为模加模块。

验签部分也是依靠上述几个算法模块,那么得到下面这张图:

                      

 

标量乘调用点加和倍点,但是如果标量为1,2这种情况就直接调用点加和倍点模块,而点加和倍点根据椭圆曲线规则,需要调用模运算模块,这个我单独出一篇文章来讲各个模块的具体实现,这里就不详细介绍。

因为要在硬件上实现ECDSA算法,所有博主采用了verilog对各模块进行建模编写,最后综合得到下图:

                                                     

详细的模块化设计我会在后续模块介绍中放出。