ECDSA高性能硬件实现——算法详解与模块划分
ECDSA全称椭圆曲线数字签名算法，它是基于素数域的椭圆曲线对信息进行加签与验签。其核心在于对信息的加签，及对加签的信息进行验签，那么下面介绍该算法流程。
假设Alice希望对消息m进行签名，并将消息传给Bob。首先Alice要选用一条椭圆曲线，其参数组为D = ( p,S,a,b,G,n,h) ，对应的密钥对为( k , Q ) ，其中各参数解释为：
- 域的阶p;
- 种子S，用于参数随机数;
- 两个椭圆曲线系数a，b∈Fp，定义了Fp上椭圆曲线E的等式;
- 定义椭圆曲线上的一个有穷远点 ，一般称其为椭圆曲线基点;
- G的阶n,为素数域的模数;
- 余数因子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 = x2 mod 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对各模块进行建模编写，最后综合得到下图：
详细的模块化设计我会在后续模块介绍中放出。