一种ECDSA算法执行系统及方法与流程

一种ecdsa算法执行系统及方法
技术领域
1.本发明涉及计算机体系结构技术领域，具体涉及一种ecdsa算法执行系统及方法。


背景技术：

2.非对称加密算法包括公开密钥和私有密钥，明文通过公开密钥加密信息得到密文，密文通过私有密钥解密信息得到明文信息。而在数字货币交易等加密通信领域中，除了使用公开密钥和私有密钥加密信息之外，还需要数字签名来保证信息的真实性，此时通过私有密钥加密信息得到数字签名，通过公开密钥验证信息来源的真实性。这种非对称加密的应用为数字签名，常用的加密通信和数字签名算法包括rsa算法、dh算法和ecc算法。
3.随着计算机性能提升，基于大数因式分解的1024位rsa加密算法已经可以被破解，2048位的rsa加密算法也会随着技术发展被逐渐破解，因此采用更为安全的加密算法已经成为加密通信的必由之路。相比于rsa算法，ecc算法利用离散对数问题实现加密，是一种在正向计算中非常简单，而在逆向计算时的解决方法没有亚指数级时间复杂度算法的加密算法。因此，现在越来越多的数字签名应用采用ecc算法作为其加密算法。
4.椭圆曲线数字签名算法(elliptic curve digital signature algorithm，简称ecdsa)是一种具有代表性的复杂算法，使用椭圆曲线密码(ecc)对数字签名算法(digital signature algorithm，简称dsa)进行模拟。ecdsa于1999年成为ansi标准，并于2000年成为ieee和nist标准。与普通的离散对数问题(discrete logarithm problem，简称dlp)和大数分解问题(integer factorization problem，简称ifp)不同，椭圆曲线离散对数问题(elliptic curve discrete logarithm problem，简称ecdlp)没有亚指数时间的解决方法。因此椭圆曲线密码的单位比特强度要高于其他公钥体制。
5.ecdsa算法本身计算流程较长，需要反复的生成椭圆曲线所需的参数值，因此在传统的冯诺依曼结构中，运算器需要反复从存储器中获取信息进行计算，由此存在较多的访存指令和访存时间，增加了生成公开密钥和私有密钥的时间延迟。


技术实现要素：

6.为解决上述现有技术中存在的问题，提供一种ecdsa算法执行系统，包括：发送端和接收端，
7.所述发送端包括第一设备和第一数据流芯片，所述第一设备用于生成私钥，所述第一数据流芯片用于根据所述私钥生成公钥以及利用私钥对消息进行签名；所述接收端包括第二设备和第二数据流芯片，所述第二数据流芯片用于根据接收的公钥和消息签名获取验证结果，所述第二设备用于接收所述验证结果。
8.优选的，所述第一数据流芯片和/或第二数据流芯片的每个pe基于指令的分支转移历史表转发运算结果。
9.优选的，所述分支转移历史表包括指令id、转发标志以及转发目的，所述指令id记录分支指令的序号，所述转发标志用于标记转发记录的有效性，所述转发目的用于记录所
述分支指令的结果数据的转发目的。
10.优选的，所述转发目的为数据转发方向，所述数据转发方向为上、下、左、右其中之一。
11.优选的，在指令译码阶段，将分支指令的id写入分支转移历史表。
12.优选的，在首次执行分支指令时，根据分支指令的id将分支指令的转发目的写入所述分支转移历史表，以及将对应的转发标志置为有效。
13.优选的，在执行分支指令时，判断所述分支指令的结果转发目的与所述分支指令历史记录表中对应的转发目的，当不相同时，将转发标志置为无效，以及在所述分支指令执行完毕时，更新所述分支指令的转发目的。
14.本发明提供一种基于上述系统的ecdsa算法执行方法，包括：
15.发送端的第一数据流芯片根据发送端的第一设备生成的私钥生成公钥；
16.所述第一数据流芯片基于私钥和消息获取消息签名；
17.所述发送端将所述公钥和消息签名发送到接收端；
18.所述接收端的第二数据流芯片根据接收的所述公钥和消息签名获取验证结果；
19.所述接收端的第二设备接收所述验证结果。
20.优选的，上述执行方法包括：将ecdsa算法中的蒙哥马利大数乘法基于分支预测机制映射到所述第一数据流芯片和第二数据流芯片。
21.优选的，所述分支预测机制通过分支转移历史表预测pe的数据发送方向。
22.本发明具有如下特点和有益效果：本发明相比于现有技术，通过将ecdsa算法移植到数据流架构芯片上，类比ecdsa算法的执行过程，利用了数据流架构芯片低访存需求的特点，加快了ecdsa算法的运算过程，加速了密钥的生成过程。本发明将ecdsa算法移植到了数据流架构芯片上，考虑到ecdsa算法的广泛应用，此实现增加了数据流芯片的通用性。
附图说明
23.图1示出了根据本发明一个实施例的系统架构图。
24.图2示出了根据本发明一个实施例的发送端生成私钥和公钥的运算过程图。
25.图3示出了根据本发明一个实施例的通过公钥和私钥生成签名的运算过程图。
26.图4示出了根据本发明一个实施例的签名验证运算过程图。
27.图5示出了现有技术的蒙哥马利大数乘法循环程序示意图。
28.图6示出了根据本发明一个实施例的数据流芯片架构图。
29.图7示出了根据本发明一个实施例的分支预测机制对应的分支转移历史表。
30.图8示出了现有技术的蒙哥马利大数乘法的循环程序代码。
31.图9示出了根据本发明一个实施例的蒙哥马利大数乘法的数据流图。
32.图10示出了根据本发明一个实施例的蒙哥马利大数乘法的数据流图映射到pe阵列的情况。
具体实施方式
33.下面结合附图和具体实施例对本发明加以说明。应当理解，此处所描述的具体实施例仅用以解释本发明，并不用于限定本发明。
34.传统的冯诺依曼结构计算机由存储器、运算器、控制器、输入输出设备组成，采用存储程序的思想，运算器从存储器中取出数据，进行运算，再将结果写回存储器，并且计算机中的指令按照其在存储器中的顺序依次执行。存储程序和指令驱动执行的方式使得冯诺依曼结构计算机能够处理绝大多数任务，但是对于神经网络、计算科学等专用的应用需求，冯诺依曼结构计算机的顺序执行特征在执行专用任务时频繁的访问内存，且大型任务中的并行特征没有被很好的利用，导致冯诺依曼结构的计算机在处理神经网络等专用任务时的性能较低，且顺序执行的特征阻碍了专用任务的优化，因此处理专用的计算任务，需要考虑不同于冯诺依曼结构的计算机。
35.数据流结构不同于冯诺依曼结构，数据流结构通过粗粒度表示提高数据的并行度，其编译器可以同时调度多个顺序循环和功能，实现更高的吞吐量和更低的延迟，因此数据流结构在处理神经网络、科学计算等较高数据并行度的应用时，具有访存需求少、同步开销低的优点。然而由于数据流结构的专用性，导致其不能适应广泛的应用场景，并且现今还未开发出广泛接受的数据流结构的软件栈，复杂的程序移植到数据流结构的计算机，需要专门的技术人员进行设计与优化。
36.本发明的目的是解决上述现有技术ecdsa算法的访存需求高、密钥生成时间长、pe(process element，处理单元)阵列部件利用率低等问题，本发明意图通过将ecdsa算法移植到数据流架构芯片上，并对其运算过程进行加速，增加数据流架构芯片的通用性。
37.发明人在进行ecdsa算法研究时认识到，通过以下几个方面的技术改进可以解决现有技术中的问题。
38.首先，ecdsa算法本身计算流程较长，需要反复的生成椭圆曲线所需的参数值，因此在传统的冯诺依曼结构中运算器需要反复从存储器中获取信息进行计算，由此存在较多的访存指令和访存时间，增加了生成公开密钥和私有密钥的时间延迟。基于以上发现，发明人认为通过减少生成公开密钥和私有密钥的访存时间可以有效地降低生成公开密钥和私有密钥的时间。
39.第二，现有的ecdsa算法在生成密钥时需要用到蒙哥马利大数乘法，而在顺序执行的冯诺依曼结构中，蒙哥马利大数乘法存在循环程序执行的情况，类似的，需要进行重复的多次访存操作，增加了密钥生成过程中的时间延迟，因此，发明人认为可以利用数据流结构的低访存性加速密钥生成过程。
40.第三，由于蒙哥马利大数乘法中存在的循环程序，对循环的预测将有效的减少判断循环跳转的冗余指令，加快大数乘法的计算时间。因此发明人提出了一种基于数据流结构的分支预测机制，对循环的下一步执行指令和数据发送传递进行预测，加速了程序循环的执行时间。
41.第四，ecdsa算法作为加密算法被广泛应用，在通用芯片中采用ecdsa算法加密时增加了通用芯片的处理和计算负担，为了加速密钥生成的时间和减少生成时的访存需求，将生成密钥所需的数据放到专用的粗粒度的数据流结构中，可以有效的加快ecdsa算法生成密钥的时间，并且降低生成过程中的访存需求，充分利用数据流芯片的低访存需求的特点，有效地加速ecdsa算法的执行过程。
42.基于以上研究分析，本发明提供一种基于数据流结构的ecdsa算法执行系统，其架构如图1所示，包括：发送端和接收端，发送端用于生成私钥和公钥，以及根据私钥和消息生
成消息签名并发送到接收端；接收端用于根据接收的私钥和消息签名获取验证结果；发送端包括第一设备和第一数据流芯片，第一设备用于生成私钥，第一数据流芯片用于根据私钥生成公钥以及利用私钥对消息进行签名；接收端包括第二设备和第二数据流芯片，第二数据流芯片用于根据接收的私钥和消息签名获取验证结果，第二设备用于接收验证结果。
43.图2示出了根据本发明一个实施例的发送端生成私钥和公钥的函数ecc_make_key的运算过程图。函数ecc_make_key的注释如下：
44.函数名：ecc_make_key
45.函数功能：生成私钥和公钥
46.参数：p_publickkey[]：48 1字节(48字节为公钥的x坐标值，1字节为校验位)
[0047]
p_privatekey：48字节，384位
[0048]
函数返回：生成成功返回1，否则返回0
[0049]
函数ecc_make_key生成私钥和公钥的具体过程如下：
[0050]
(1)选择一个随机整数l_private作为私钥；
[0051]
(2)判断l_private是否为0，如果为0，返回步骤(1)；
[0052]
(3)判断l_private是否小于n，如果大于n，则将l_private赋值为l_private
‑
n，执行步骤(4)；
[0053]
(4)调用eccpoint_mult函数计算公钥，如果公钥为0，返回步骤(1)；其中，eccpoint_mult函数可通过现有技术实现，例如，github中的nano
‑
ecc或micro
‑
ecc；
[0054]
(5)公钥q、私钥l_private生成，程序执行结束。
[0055]
其中(1)
‑
(3)在host完成，执行完毕后生成计算签名所需的公钥和私钥。
[0056]
在生成私钥和公钥后，即可利用私钥对消息进行签名。ecdsa算法是现有技术，使用椭圆曲线密码(ecc)对数字签名算法进行模拟，其签名由一对整数(r，s)组成，该签名由公钥和私钥计算得到。
[0057]
假设椭圆曲线的参数为d＝(p，a，b，g，n，h)，其中，
[0058]
p为素数，用于确定有限域的范围；
[0059]
a，b为椭圆曲线方程中的参数；
[0060]
g表示用于生成子群的基点；
[0061]
n为子群的阶；
[0062]
h为子群的辅助因子h。
[0063]
对应的密钥对为(l_private，q)，其中，l_private为私钥，q为公钥。签名的具体步骤为：随机选择一个整数k，通过eccpoint_mult函数计算点p的值，并得到点p的x坐标为r，将私钥l_private通过格式变化得到d，计算s＝(e r*d)/k，其中，e为待签名数据的哈希值。计算过程中要求r和s均不为0，如果有一个0则需要重新选择整数k的值。其中，用于实现签名算法的eccpoint_mult函数采用现有技术实现，例如github中的nano
‑
ecc或micro
‑
ecc。
[0064]
图3示出了根据本发明一个实施例的通过公钥和私钥生成签名的运算过程图，生成签名的流程图如图3所示，计算消息x的签名的步骤如下：
[0065]
(1)选择一个随机整数k，且0<k<n；
[0066]
(2)调用eccpoint_mult函数计算p(p＝k*g，p的x坐标x1用于计算r)；
[0067]
(3)r＝x1(mod n)，其含义为：如果x1小于n，则r＝x1，否则，x1取模，使得最终结果
r满足0<r<n；
[0068]
(4)如果r为0，返回步骤(1)；
[0069]
(5)由私钥l_private通过ecc_native2bytes函数经过格式变化得到d，计算s＝(e r*d)/k，其中e为待签名的数据的哈希值；其中，用于格式变化的ecc_native2bytes函数用于变换字节顺序，可采用现有技术实现，例如github中的nano
‑
ecc或micro
‑
ecc；
[0070]
(6)(r，s)即为签名，程序结束。
[0071]
上述过程执行完毕后已经生成了消息x的签名，此时发送端将消息x的签名通过网络传输到接收端，接收端通过数据流芯片进行ecdsa算法的验证部分，并将验证结果发送给接收端的host，得到加密传输的消息内容。
[0072]
接收方验证ecdsa算法的验证过程是根据提供的公钥q、待验证的数据的哈希值h(x)以及签名(r，s)得到的。签名的验证步骤为：根据签名(r，s)和消息的哈希值h(x)计算辅助值u1和u2，再根据公钥q、基点g和辅助值计算出点x，点x的横坐标x1满足以下公式：
[0073]
x1 mod p＝r mod p。
[0074]
图4示出了根据本发明一个实施例的签名验证函数ecdsa_verify的运算过程图，函数ecdsa_verify的注释如下：
[0075]
函数名：ecdsa_verify
[0076]
函数功能：根据公钥以及数据判断数据是否被修改
[0077]
参数：p_signature[]：48*2字节(签名)
[0078]
p_publickey[]：48字节(384)位
[0079]
p_hash[]：48字节(384)位，待签名数据的hash
[0080]
函数返回：验证成功返回1，否则返回0
[0081]
函数ecdsa_verify执行的验证步骤如下：
[0082]
(1)判断签名(r，s)是否大于0小于n，如果不满足，程序结束
[0083]
(2)计算辅助值u1＝(h(x)/s)mod n
[0084]
(3)计算辅助值u2＝(h(x)/r)mod n
[0085]
(5)计算rx＝u1*g u2*q
[0086]
(6)比较rx和公钥(r，s)中的r，如果rx＝r mod q，则签名有效，否则无效
[0087]
此时已经完成了数据从发送端加密后通过网络传输到接收端，接收端通过验证消息的正确性和可靠性后获得消息内容的过程，在数据流芯片上实现了ecdsa算法。
[0088]
发明人在研究中发现，在密钥生成阶段，蒙哥马利大数乘法的实现方式包括循环程序嵌套多路分支的情况，以下具体说明蒙哥马利大数乘法。
[0089]
在加密算法中，公钥算法实现通常需要计算模乘(例如a
·
b(mod n)，其中a，b，n均为几千位的大整数)，而模乘的运算中包含除法。对于计算机来说，除法计算需要循环计算，实现困难，且计算时间较长。因此希望有其他算法能够加速模乘运算。蒙哥马利大数乘法是数学家蒙哥马利提出的一种加速计算模乘的方法，这种算法不需要计算除法，极大的方便了模乘运算。
[0090]
蒙哥马利大数乘法的原理如下：
[0091]
对于a
·
b(mod n)来讲，假设将n用r进制表示，且n用r进制表示时的位数为k。然后同样将a表示为r进制，得到然后考虑表达式a
·
b
·
r
‑
k
(mod n)，有
[0092][0093]
由上式可知，对于c而言，计算机程序中可以将每个i的内容累加求和再取模得到c的值。每个需要累加的部分为a
i
·
b/r
k
‑
i
，因此有如下的例子：
[0094][0095]
然而上面的程序中存在问题，c/＝r这一步丢失了余数，解决丢失的余数需要让c加上某个值后是r的倍数，为了保证最终结果不变，补充的值同样是n的倍数，得到的循环为，
[0096][0097]
考虑到c的累加特性，则q需要满足的条件是使得(c a[i]*b q*n)(mod r)＝0，即(c0 a[i]*b0 q*n0)(mod r)＝0，其中c0、b0和n0为c、b和n以r进制表示时的个位数的值，等价于分别对r取模。则q的一个解为(c0 a[i]*b0)*(
‑
n0‑1)(mod r)，将q值代入后得到循环程序为，
[0098][0099]
在上述循环中，可以看到，原本的大数乘法再取模的运算化简为一系列的加减法和移位运算。特别的，通常情况下r的选取为2的幂，这样对r取模就可以变为移位操作，进一步消除了运算的复杂性。
[0100]
以上解释了如何计算a
·
b
·
r
‑
k
(mod n)的化简，记为mont_prod(a,b)，如果计算a
·
b(mod n)，计算如下四个算数式即可，
[0101][0102][0103][0104][0105]
前两步称为进入蒙哥马利域，最后一步称为退出蒙哥马利域，最终的结果c就是(a
·
b)(mod n)的值。
[0106]
蒙哥马利算法的优点：
[0107]
在运算时间上，蒙哥马利算法消除了模乘运算中的取模运算，由此节约了计算机执行过程中的除法执行时间；蒙哥马利算法中的循环可以修改r的大小减少循环的次数，从而调整循环计算所用的时间；蒙哥马利算法中可以提前计算好其中的b0和n0，循环中只需要计算c0的值，因此并没有因为额外的开销增加运算时间。
[0108]
在运算空间上，传统的模乘运算需要先计算乘法，大位数的乘法需要占用相比原数多一倍的内存空间，影响了计算机的内存空间使用，并且对乘法结果的取模进一步占用了更多的内存空间；通过移位实现的模乘运算同样因为每次移动一位而影响计算效率；而蒙哥马利算法则通过r的变化改变了循环的执行次数，节省了循环执行所需要的内存空间。
[0109]
实际实现蒙哥马利大数乘法时，考虑到结果c的累加特性，还可以优化循环过程，将计算过程并行化处理，进一步加速模乘运算。
[0110]
蒙哥马利算法的代码实现示例如下：
[0111]
[0112]
[0113][0114]
程序中从taga到tagb的代码是主要计算部分，其结构是while循环中嵌套4个分支，对应于图5所示出的现有技术的蒙哥马利大数乘法循环程序示意图，其中，展示了循环程序的嵌套多路分支。
[0115]
图6示出了根据本发明一个实施例的数据流芯片架构图。考虑到多路分支的传递性和依赖性，图5所示的循环程序和图6所示的常见的数据流架构芯片结构高度匹配。因此，在数据流架构中通过历史记录进行分支预测，通过历史记录得到下游的pe编号或者是数据的发送方向，能够提高数据流芯片中的模块部件利用率，加快密钥的生成时间。
[0116]
根据本发明的一个实施例，本发明提供一种基于数据流结构的分支预测机制，该方法将ecdsa算法中的蒙哥马利大数乘法步骤分解为循环程序，并根据该循环程序的执行特征提出了数据流架构中的分支预测机制。该分支预测机制通过历史记录预测下游的数据发送方向，减少了循环程序的跳转指令时间，减少了数据依赖而带来的pe等待时间，提高了pe阵列的部件利用率。
[0117]
根据本发明的一个实施例，所述分支预测机制包括：每个pe内部维护一个指令的分支转移历史表；图7示出了根据本发明一个实施例的分支预测机制对应的分支转移历史表，表中包括指令id、转发标志和转发目的。其中指令id记录分支指令的序号，指令经过译码阶段，如果是分支指令，则将该指令的id加入分支历史表。pe在发射指令时，如果发射的指令id存在分支历史表中，且其转发标志g为确认转发时，则将分支历史表中的数据转发目的信息给链接pe的路由，将运算结果根据转发目的转发至相应的pe。
[0118]
其中，转发标志的目的是标志此条转发记录是否有效，第一次执行一条分支指令时，根据此条指令的转发目的，将转发目的填入表格中，并将转发标志记为true。如果对于某次执行，实际的程序执行的结果转发目的与表格中的转发目的不同，则将转发标志置位false，表示上次预测错误，该条指令执行结束之后需要根据实际的转发目的更新目的。
[0119]
其中转发目的并非传统的分支记录机制中记录下一条指令的地址，此处记录此条指令的结果数据的转发目的。由于数据流架构的程序是由数据流图表示，实际在执行过程中是由数据的流动所完成，所以将数据流动的目的或者转发方向作为需要预测的内容。根据本发明的一个实施例，采用用数据转发方向：上、下、左、右。
[0120]
具体来说，图8示出了现有技术的蒙哥马利大数乘法的循环程序代码，其中的代码段标出了序号，标号1表示while主循环，标号2、3、4、5分别表示while循环中的4个分支的判断语句，6、7、8、9分别对应于4个分支的代码段。图8的代码对应于图9的蒙哥马利大数乘法的数据流图。图9中的结点编号与图8中的代码段编号相对应。图10示出了图9的数据流图映射到pe阵列的一个示例，其中，在pe101中映射了编号为1、2、3、4、5的数据流图结点，该
pe101相邻的四个pe分别映射了数据流图的6、7、8、9四个结点。pe101中的分支转移历史表记录了分支指令的id、转发目的、转发标志，pe101在发射指令时，根据分支转移历史表的分支指令的id、转发目的和转发标志，将运算结果转发至相邻的四个pe之一。
[0121]
根据本发明的一个实施例，本发明提供一种基于上述系统的ecdsa执行方法，该方法包括以下步骤：发送端和接收端设备都由host和数据流芯片组成，发送端的host生成满足要求的密钥，将密钥发送至发送端设备的数据流芯片上，数据流芯片根据私钥生成公钥，并将公钥返回给发送端的host。然后数据流芯片根据生成的私钥对将要发送的数据进行签名计算，签名计算完成后，即可将签名信息和公钥通过网络传输至接收端。接收端的数据流芯片对签名进行验证，将验证结果发送到接收端的host，完成ecdsa算法的整个过程。
[0122]
应该注意到并理解，在不脱离后附的权利要求所要求的本发明的精神和范围的情况下，能够对上述详细描述的本发明做出各种修改和改进。因此，要求保护的技术方案的范围不受所给出的任何特定示范教导的限制。