本发明涉及哈希算法加速领域，具体是存储受限型哈希算法的加速装置及方法。
背景技术：
随着互联网的发展，数据安全和隐私保护受到人们极度重视。口令作为一种常见且简单的用户认证方式，被广为使用。口令恢复是在忘记口令的情况下，恢复正确口令的过程。口令恢复中，简单直接的办法是遍历口令空间，以得到正确的口令。
哈希算法作为口令加密算法，其在口令恢复研究中占有主要地位。能够快速地计算哈希算法，缩小遍历口令空间时间，是口令恢复的主要研究方向之一。目前哈希算法的设计主要包含两种：(1)计算密集型哈希算法，该类算法在计算过程中，通过对散列函数的循环迭代计算来增加算法的时间复杂度，从而保证哈希算法的强度；(2)存储受限型哈希算法，该类算法在计算过程中，需要足够内存来存储中间过程值，不断地更新内存中的数据，来保证算法的时间复杂度，校验值需要根据迭代更新后的内存数据来生成。存储需求提升算法的空间复杂度，该类算法比计算密集型具有更高的强度。
在口令恢复时，针对计算密集型哈希算法，可以通过图形处理器(graphicsprocessingunit，gpu)、专用集成电路(applicationspecificintegratedcircuit，asic)等硬件提升哈希算法的计算效率，从而提高口令恢复的效率。但是，存储受限型哈希算法不同于计算密集型加密算法：内存需求使得目前高性能硬件系统难以满足存储需求，如gpu的局部存储；不同参数的设置，导致对存储的需求也不同，使得专用集成电路这种硬件平台无法满足更多的应用算法；最为困难的是频繁的数据访问增加了算法计算的时间，从而降低了加密算法的计算效率。
因此，为了满足存储受限型哈希算法的存储需求，解决访存带来的计算效率下降问题，本发明提出一种存储受限型哈希算法加速装置及方法。
技术实现要素：
本发明要解决的技术问题提供一种存储受限型哈希算法的加速装置及方法，用以高效地实现存储受限型哈希算法。
为了解决上述技术问题，本发明提供一种存储受限型哈希算法的加速装置，包括通用处理单元、加速单元和存储单元；通用处理单元和加速单元之间信号连接，通用处理单元与存储单元之间为双向高速访问的信号连接；
所述加速单元包括a个计算单元，a为自然数，每个计算单元含有至少4k字节的局部存储且计算单元之间为并行运行，每个计算单元采用直接内存访问(directmemoryaccess，dma)的方式对局部存储和存储单元进行数据传输，直接内存访问和计算单元的运行是相互独立且并行运行。
作为本发明的存储受限型哈希算法的加速装置的改进：
所述存储单元提供至少8g字节的独立存储空间供通用处理单元访问。
本发明还同时提供了利用所述的存储受限型哈希算法的加速装置进行的加速方法，包括初始化、循环计算和哈希值生成，所述初始化包括在存储单元中申请建立
所述通用处理单元用以所述初始化和哈希值生成；
所述加速单元用以所述循环计算：四个切片按从左到右的顺序，循环迭代更新计算t次，其中t为迭代次数，在加速单元内，更新计算以一个切片为单位运行；在每个切片内，每个计算单元对应于处理一行数据，利用压缩函数g从左至右的顺序对每个数据块b[l][n]依次进行更新计算，a个计算单元同步对a行数据进行并行的更新计算，前一个切片每行的最后一个数据块b作为后一个切片对应行的第一个数据块b的输入，每行的最后一个数据块b[0][n-1]、b[1][n-1]、……、b[p-1][n-1]作为下一轮更新计算的一个输入；
所述计算单元对数据块b[l][n]更新计算的同时从存储单元读取索引数据块d[i][j]作为数据块b[l][n 1]更新计算的一个输入，每个切片的计算所需时间为第一个数据块b的两次从存储单元读入加速单元的dma操作时长、最后一个数据块b从加速单元写入存储单元的一次dma操作时长，以及压缩函数g的
作为本发明的加速方法的改进，所述计算单元利用压缩函数g依次对每个数据块b[l][n]进行更新计算为：
b[l][n]＝g(b[l][n-1]，d[i][j])，
计算单元从存储单元读取索引数据块d[i][j]作为更新计算的一个输入，其中i、j为索引计算得到的索引值，数据块b[l][n-1]直接作为更新计算的另一个输入；然后将数据块b[l][n-1])和索引数据块d[i][j])中的数据按位异或并将结果分组为个64单元r0、r1、……、r63，将64个单元设置为8*8的数据矩阵r，再依次对数据矩阵r的每行进行变换操作后得到8*8的数据矩阵q，然后再依次对数据矩阵q的每列进行变换操作后得到8*8的数据矩阵z，最后将数据矩阵z和数据矩阵r按位异或得到输出的数据块output，将数据块output同步更新到局部存储和存储单元中的数据块b[l][n]。
作为本发明的加速方法的进一步改进：
所述变换操作包括：将8*8矩阵的每一行或每一列分成16个基本块，将16个基本块设置为4*4的单元矩阵x，每次变化操作的输入为单元矩阵x中的4个基本块，一个单元矩阵x共需执行8次变化操作：前四次变化操作分别按单元矩阵x的每一行中的4个基本块进行分组处理，后四次变化操作分别按单元矩阵x的对角线的4个基本块进行分组处理，输出为一个新的8*8矩阵。
作为本发明的加速方法的进一步改进：
所述初始化还包括初始化存储受限型哈希算法的参数：版本号v、算法种类y、关联数据k、关联数据x、并行度p、算法输出长度t、需要的存储空间m、迭代次数t、输入数据p和盐值s；然后将参数级联后获得：(p,t,m，t，v,y,<p>,p,<s>,s,<k>,k,<x>,x)并利用blake2b算法进行初步处理，其中，<p>为输入数据p的长度，<s>为盐值s的长度，<k>为关联数据k的长度，<x>为关联数据x的长度；然后将初步处理的结果依次填充所述mk字节的存储空间中第一个切片每一行的前两个数据块b作为所述循环计算的初始输入。
作为本发明的加速方法的进一步改进：
所述哈希值生成包括通用处理单元将所述更新计算所得的每行的最后一个数据块b[0][n-1]、b[1][n-1]、……、b[p-1][n-1]分别依次按位异或计算，然后再各自经过blake2b算法后，根据所述输出长度t进行拼接或截断得到哈希函数散列输出值。
本发明与现有技术相比的有益效果主要体现在：
1、本发明将初始化阶段和哈希值生成阶段置于通用处理单元运行，将循环计算阶段置于加速单元运行，从而充分利用了多个加速单元对哈希函数的循环计算的并行运行的效率；
2、本发明将一个切片的更新放入加速单元内处理，由多个计算单元并行处理一个切片内多行数据的更新计算，从而提高了更新计算的效率；
3、本发明在数据块连续的更新计算时，可以将上一次的计算结果直接用来下一次更新计算的输入，而不用再次去访问主存，且计算单元在计算的同时只需通过dma方式从存储单元访问获取索引数据块，实现访存和计算解耦、并行操作实现来提升算法的计算效率。
附图说明
下面结合附图对本发明的具体实施方式作进一步详细说明。
图1为本发明的存储受限型哈希算法加速装置结构示意图；
图2为本发明的实施例1中存储受限型哈希算法argon2i流程示意图；
图3为本发明的实施例1中存储受限型哈希算法argon2i基于国产处理器的加速方法示意图；
图4为本发明的实施例1中存储受限型哈希算法argon2i的压缩函数g更新计算的流程示意图。
具体实施方式
下面结合具体实施例对本发明进行进一步描述，但本发明的保护范围并不仅限于此：
实施例1、存储受限型哈希算法的加速装置，如图1所示，国产处理器(申威sw26010)是一种异构架构的处理器，本实例中的存储受限型哈希算法的加速装置使用国产处理器实现，每个国产处理器包含4个核组和存储单元20，每个核组含有一个通用处理单元10(即主核)和一个加速单元30(即从核阵列)，一个核组用以实现一条哈希值的计算，主核作为运算控制核心(managementprocessingelement，mpe)可以处理复杂的逻辑操作，实现对存储受限型哈希算法的预处理操作，对算法的数据参数进行处理，初始化存储空间，主核与主存之间互为双向高速访问的信号连接，主核可以快速访问主存，实现存储受限型哈希算法的初始化和哈希值生成计算；主存提供8g字节的独立的存储空间供主核访问，满足存储受限哈希算法存储参数最大为8g字节的要求；每个加速单元30含有a个计算单元31(a为自然数，申威sw26010为64个从核)，即申威sw26010的从核阵列可以并发运行64个从核，每个从核含有64k字节的局部存储32，可以实现单指令多数据流的计算方式，提升从核的计算效率和吞吐率，计算单元31可以高速地访存局部存储32；
从核阵列与主存之间为互为双向访问的信号连接；从核采用直接内存访问(directmemoryaccess，dma的方式实现对局部存储32和主存的数据传输，从核计算时，可以高效访问局部存储32，访问延迟为4个节拍，且dma的访存和从核的计算是相互独立的，可以并行执行，利用dma实现双缓冲的数据访问机制，在从核计算的同时，写回上一次的计算结果和读入下一次计算的输入；
主核与从核之间为信号连接，多个从核并发由主核athread编程实现，从核内部支持单指令多数据流的实现方式，可以提升从核的计算效率。
利用存储受限型哈希算法的加速装置进行存储受限型哈希算法argon2i的加速方法如图2-图4所示，过程如下：
argon2i是存储受限型哈希算法argon2的一种，算法含有10个参数，参数默认为四个字节表示：
p为并行度，取值范围[1,224-1]，默认值为1；
t为算法输出长度，以字节为单位，取值范围[4,232-1]，默认输出32字节；
m为需要的存储空间大小，以1024字节为单位(kilobytes，kb)，取值范围[8p,232-1]，实际的计算情况是向上取整到4p的整数倍，默认为4m字节；
t为迭代次数，表明循环阶段，需要更新内存的次数，取值范围[1,232-1]，默认值为3；
v表示版本号，为固定值0x13，用一个字节表示；
y为算法种类，argon2i为1，用一个字节；
p为输入数据，数据长度范围为[0,232-1]字节；
s为盐值，盐值长度范围为[8,232-1]字节；
k和x为关联数据，数据长度范围[0,232-1]字节；
1、初始化
1.1、参数设置
对argon2i算法的10个参数进行初始化设置：版本号v、算法种类y为固定值；关联数据k和x为字符数据，可以根据实际应用选择是否需要；并行度p、算法输出长度t、需要的存储空间m、迭代次数t根据需要设置对应值，数值大小用4个字节表示；输入数据p和盐值s进行初始化；
1.2、参数处理及初步运算
此步骤的运算主要以逻辑运算为主，包括参数处理、存储空间申请以及初步运算，逻辑处理复杂，在主核中实现，首先采用以下顺序对各个初始化后的参数进行级联获得级联后的参数：(p，t，m，t，v，y，<p>，p，<s>，s，<k>，k，<x>,x)，其中，<>符号表示对应数据长度，如<p>为输入数据p的长度，<s>为盐值s的长度，<k>为关联数据k的长度，<x>为关联数据x的长度；
然后根据步骤1.1中设置的参数m，在主存中申请建立
将级联后的参数(p，t，m，t，v，y，<p>，p，<s>，s，<k>，k，<x>，x)作为输入数据，利用blake2b算法h进行初步运算，结果填充申请的mk字节的存储空间一行的前两个数据块b，即数据块b[0][0]和b[0][1]、数据块b[1][0]和b[1][1]、……、数据块b[p-1][0]和b[p-1][1]，作为步骤2的输入；
2、循环处理
2.1、一个数据块的更新
对当前所需更新的数据块b[l][n]进行一次数据块更新时，将前一个数据块b[l][n-1](其中l，n分别为数据块b所在的行和列，
1)、获取索引数据块d[i][j]
由索引计算得到索引值i和j，再根据索引值i和j在主存内查找并定位索引数据块d[i][j]，利用dma的数据传输方式从主存将索引数据块d[i][j]读入到局部存储32，需要一次dma数据传输，共1k字节的数据大小；
2)、获取前一个数据块b[l][n-1]
压缩函数g的更新计算从每行每个切片第1个数据块b时，利用dma的数据传输方式从主存读入到局部存储32；
压缩函数g的更新计算切片内第2个至
3)、压缩函数g的更新计算
压缩函数g的更新计算过程如图4所示：将一个输入的数据块b[l][n-1])和另一个输入的索引数据块d[i][j])中的数据按位异或并将结果分组为64个单元(即r0、r1、……、r63)，每个单元为16字节，将64个单元设置为8*8的矩阵从而得到数据矩阵r，再依次对数据矩阵r的每行进行变换操作得到8*8矩阵形式的数据矩阵q，然后再依次对数据矩阵q的每列进行变换操作后得到8*8矩阵形式的数据矩阵z，最后将数据矩阵z和数据矩阵r按位异或得到数据块output，即压缩函数g的的输出为数据块output，将数据块output从局部存储32利用dma的方式传输到主存，同步更新局部存储32和主存中的数据块b[l][n]作为下一个数据块b[l][n 1]的一个输入，从而实现了一个数据块的更新；
数据矩阵r到数据矩阵q的变换操作具体为：将数据矩阵r的每行(128字节)分成16个基本块(即x0、x1、……、x15)，每个基本块为8个字节，将16个基本块设置为4*4的单元矩阵x，即数据矩阵r的每一行对应地设置为一个4*4的单元矩阵x，一个单元矩阵x共需执行八次blake2b算法中的迭代计算，其中，前四次分别按单元矩阵x的每一行中的4个基本块(如图4中虚线①、②、③、④所示的行中的4个基本块)对数据分组进行迭代计算，后四次分别按单元矩阵x的对角线的4个基本块(如图4中虚线⑤、⑥、⑦、⑧所示的行中的4个基本块)对数据分组进行迭代计算，每次迭代计算后更新该4个基本块的值；一个数据矩阵r共设置成8个单元矩阵x，因此一个数据矩阵r共需变换操作64次，获得更新后的64个基本块，从而对应地输出q0、q1、……、q63，并设置为8*8的数据矩阵q；
在对4*4的单元矩阵x的变换操作中，前四次计算的输入数据彼此不存在相关性，后四次计算同样如此，因此在从核阵列中，可以采用并发计算的方式提升性能，从核支持256位(32字节)单指令多数据流的计算，恰好对应四次变换操作，因此在从核中针对一个单元矩阵x的8次变换操作可以采用单指令多数据流的计算方式，两次计算可以实现原来的8次变换操作的计算，从而实现了用单指令多数据流的并行进行数据处理，提升计算效率；
对于数据矩阵q到数据矩阵z的变化操作过程与数据矩阵r到数据矩阵q的变换操作过程类似，以数据矩阵q每列128字节的数据，作为变换操作的输入，同样地利用变换操作得到数据矩阵z；
在上述一个数据块b[l][n]的更新过程中，压缩函数g计算之前，从核需要将两个数据块从主存读入到局部存储32，压缩函数g计算后，从核要将一个数据块从局部存储32写回到主存，一个数据块b[l][n]的更新过程需要三个数据块的读写操作。
2.2、一个切片的更新
一个切片包含p行数据，每行包括
同一个切片内的数据块b更新时，压缩函数g计算是在从核中实现，其中一个输入是压缩函数g的输出的前一个数据块b[l][n-1]，可以直接在从核中获得，另一个输入是利用dma操作从主存中读入的索引数据块d[i][j]，利用该方式一次压缩函数g的计算可以只需一次dma操作时间；压缩函数g计算时，采用该双缓冲的数据访存方式：写回压缩函数g的计算结果的同时，同步读入下一个压缩函数g的索引数据块d[i][j]，可以隐藏掉数据从主存读入局部存储32以及计算后的数据从局部存储32写回主存的时间；因此整个切片的计算时间为第一个数据块b的两次读操作、最后一个数据块b的写操作以及
2.3循环迭代更新
采用步骤2.2的一个切片的更新方式，对主存内的四个切片slices按从左到右的顺序，以一个切片为单位对每个切片中的数据块b依次进行更新计算(第二、三、四个切片每一行的第一个数据块b的输入为前一个切片对应行的最后一个数据块b)，每行最后一个数据块b[0][n-1]、b[1][n-1]、……、b[p-1][n-1]，其中
3、哈希值生成阶段
经过步骤2.3，即在从核阵列循环迭代更新t次主核申请的mk字节存储空间数据后，主核对最后一个数据块b[0][n-1]、b[1][n-1]、……、b[p-1][n-1]，分别依次按位异或计算然后再各自经过blake2b算法计算后，根据步骤1.1中设置的输出长度t进行拼接或截断得到最后输出，即argon2i哈希函数散列输出值，该部分计算简单，在主核中计算即可。
实验1：
分别搭建三个实验环境验证本发明的有效性：
1)国产处理器sw26010上仅使用主核实现argon2i存储受限哈希算法；
2)国产处理器sw26010上使用主核加从核的方式采用本实施例1实现argon2i存储受限哈希算法；
3)intel(r)core(tm)i7-8700cpu@3.20ghz3.19ghz处理器上实现argon2i存储受限哈希算法。
首先，在从核实现压缩函数g时，利用国产处理器软件统计计算的时钟周期，单指令多数据流的实现方式，计算一次需要10323个时钟周期，非单指令流多数据流的实现方式，计算一次需要41084个时钟周期，计算效率提升41084/10323≈3.98倍。
argon2i哈希函数计算时，实验环境1)和实验环境2)采用默认参数设置，即迭代次数3，内存参数4m字节，并行度p为1，输入数据p为7个字符长度，盐值为8个字符长度，k和x不设置，其他参数为默认值，在两种平台上实现argon2i算法，并利用软件统计计算时间。在实验环境1)上实现argon2i算法，计算一次argon2i哈希值时间需要0.16秒；在实验环境2)上采用国产处理器主核加从核，并采用实施例1的加速方法，64个从核同时运行，计算一次argon2i哈希值时间需要0.1秒，单个核组(1个主核 64个从核)相比于一个主核计算一次argon2i哈希值，计算效率提升为
实验环境2)和实验环境3)参数设置为迭代参数10，并行度4，内存参数4m字节输入数据p为7个字符长度，盐值为8个字符长度，在两种平台实现argon2i算法，在实验环境3)上计算一次argon2i哈希值时间为0.0078秒，在实验环境2)上计算一次argon2i哈希值时间为0.0013秒，计算效率提升0.0078/0.0013＝6倍，因此本发明有效地提升了存储受限型哈希算法的效率，达到了发明目的。
最后，还需要注意的是，以上列举的仅是本发明的若干个具体实施例。显然，本发明不限于以上实施例，还可以有许多变形。本领域的普通技术人员能从本发明公开的内容直接导出或联想到的所有变形，均应认为是本发明的保护范围。
1.存储受限型哈希算法的加速装置，其特征在于：包括通用处理单元(10)、加速单元(30)和存储单元(20)；通用处理单元(10)和加速单元(30)之间信号连接，通用处理单元(10)与存储单元(20)之间为双向高速访问的信号连接；
所述加速单元(30)包括a个计算单元(31)，a为自然数，每个计算单元(31)含有至少4k字节的局部存储(32)且计算单元(31)之间为并行运行，每个计算单元(31)采用直接内存访问的方式对局部存储(32)和存储单元(20)进行数据传输，直接内存访问和计算单元(31)的运行是相互独立且并行运行。
2.根据权利要求1所述的存储受限型哈希算法的加速装置，其特征在于：
所述存储单元(20)提供至少8g字节的独立存储空间供通用处理单元(10)访问。
3.利用如权利要求1-2任一所述的存储受限型哈希算法的加速装置进行的加速方法，包括初始化、循环计算和哈希值生成，所述初始化包括在存储单元(20)中申请建立
所述通用处理单元(10)用以所述初始化和哈希值生成；
所述加速单元(30)用以所述循环计算：四个切片按从左到右的顺序，循环迭代更新计算t次，其中t为迭代次数，在加速单元(30)内，更新计算以一个切片为单位运行；在每个切片内，每个计算单元(31)对应于处理一行数据，利用压缩函数g从左至右的顺序对每个数据块b[l][n]依次进行更新计算，a个计算单元(31)同步对a行数据进行并行的更新计算，前一个切片每行的最后一个数据块b作为后一个切片对应行的第一个数据块b的输入，每行的最后一个数据块b[0][n-1]、b[1][n-1]、……、b[p-1][n-1]作为下一轮更新计算的一个输入；
所述计算单元(31)对数据块b[l][n]更新计算的同时从存储单元(20)读取索引数据块d[i][j]作为数据块b[l][n 1]更新计算的一个输入，每个切片的计算所需时间为第一个数据块b的两次从存储单元(20)读入加速单元(30)的dma操作时长、最后一个数据块b的从加速单元(30)写入存储单元(20)的一次dma操作时长以及压缩函数g的
4.根据权利要求3所述的加速方法，其特征在于，所述计算单元(31)利用压缩函数g依次对每个数据块b[l][n]进行更新计算为：
b[l][n]＝g(b[l][n-1]，d[i][j])，
计算单元(31)从存储单元(20)读取索引数据块d[i][j]作为更新计算的一个输入，其中i、j为索引计算得到的索引值，数据块b[l][n-1]直接作为更新计算的另一个输入；然后将数据块b[l][n-1])和索引数据块d[i][j])中的数据按位异或并将结果分组为64个单元r0、r1、……、r63，将64个单元设置为8*8的数据矩阵r，再依次对数据矩阵r的每行进行变换操作后得到8*8的数据矩阵q，然后再依次对数据矩阵q的每列进行变换操作后得到8*8的数据矩阵z，最后将数据矩阵z和数据矩阵r按位异或得到输出的数据块output，将数据块output同步更新到局部存储(32)和存储单元(20)中的数据块数据块b[l][n]。
5.根据权利要求4所述的加速方法，其特征在于：
所述变换操作包括：将8*8矩阵的每一行或每一列分成16个基本块，将16个基本块设置为4*4的单元矩阵x，每次变化操作的输入为单元矩阵x中的4个基本块，一个单元矩阵x共需执行8次变化操作：前四次变化操作分别按单元矩阵x的每一行中的4个基本块进行分组处理，后四次变化操作分别按单元矩阵x的对角线的4个基本块进行分组处理，输出为一个新的8*8矩阵。
6.根据权利要求5所述的加速方法，其特征在于：
所述初始化还包括初始化存储受限型哈希算法的参数：版本号v、算法种类y、关联数据k、关联数据x、并行度p、算法输出长度t、需要的存储空间m、迭代次数t、输入数据p和盐值s；然后将参数级联后获得：(p,t,m,t,v,y,<p>,p,<s>,s,<k>,k,<x>,x)并利用blake2b算法进行初步处理，其中，<p>为输入数据p的长度，<s>为盐值s的长度，<k>为关联数据k的长度，<x>为关联数据x的长度；然后将初步处理的结果依次填充所述mk字节的存储空间中第一个切片每一行的前两个数据块b作为所述循环计算的初始输入。
7.根据权利要求6所述的加速方法，其特征在于：
所述哈希值生成包括通用处理单元(10)将所述更新计算所得的每行的最后一个数据块b[0][n-1]、b[1][n-1]、……、b[p-1][n-1]分别依次按位异或计算，然后再各自经过blake2b算法后，根据所述输出长度t进行拼接或截断得到哈希函数散列输出值。
技术总结