密码工程- 课件 第五章 SHA256SM3算法

密码学基础之江实验室SHA256算法描述01SHA256算法背景：MD5和SHA1标准分别于1992年和1995年由密码学家RonaldLinnRivest和美国国家安全局提出，SHA2标准作为SHA1的后继标准被提出。根据不同的循环次数与哈希值长度，SHA2标准可再分为6个不同的算法，包括SHA224、SHA256、SHA384、SHA512、SHA512/224和SHA512/256。本节主要对SHA256进行描述。

SHA256算法—核心部件核心部件一：常量初始化SHA256算法中使用到的64个哈希常量如下伪代码所示。这些常量对应自然数的前64个质数的立方根的前32比特小数部分（u32是C语言中的无符号32比特数据类型）。

SHA256算法—核心部件

比特填充例子：消息“enc”中e、n、c的ASCII码分别是101、110、99，则输入消息的二进制编码如下:01100101

01101110

01100011

//共24比特补“1”后为01100101

01101110

01100011

1

//共25比特补423比特的“0”，凑齐448比特的数据，用十六进制数表示为656E6380

00000000

00000000

0000000000000000

00000000

00000000

0000000000000000

00000000

00000000

0000000000000000

00000000

//共448比特填充长度值信息：“enc”占用24比特，填充64比特长度信息后的十六进制数表示为656E6380

00000000

00000000

0000000000000000

00000000

00000000

0000000000000000

00000000

00000000

0000000000000000

00000000

00000000

00000018

//共512比特SHA256算法—核心部件

SM3算法描述02SM3算法背景：SM3是由我国国家密码管理局于2010年发布的哈希算法标准。SM3算法的设计是公开的，是在SHA256基础上进行改进的一种算法。

SM3算法—核心部件核心部件一：常量初始化SM3中使用到8个哈希初值核心部件二：填充SM3的填充方式与SHA256大致相同，本节不再赘述

SM3算法—核心部件

SHA256算法高速实现03SHA256算法高速实现—树哈希

SHA256算法高速实现—区块链中的SHA256Fan等人于2021年利用区块链的特性以及数据级并行（Data-LevelParallelism）和线程级并行（Thread-LevelParallelism）两种并行机制来提高区块链中最常用的SHA256的计算速度，并提供了3点优化方法。优化方法一：预处理填充模块填充模块的工作是对需要哈希的消息进行填充，确保其长度为512的倍数。在填充模块，对于任意的输入消息，都需要填充一个“1”位、若干位的“0”和64比特的长度值信息。Fan等人对区块链中SHA256的运算模式进行分析，并提出了预处理填充模块技术。该技术通过对消息块进行预处理，使消息长度为512的整数倍，从而跳过了填充模块和信息分割与扩展模块的需要，提高了SHA256的计算速度。预处理填充模块的SHA256和一般SHA256的性能对比如右图所示。SHA256算法高速实现—区块链中的SHA256

对上图（a）与上图（b）进行观察可发现，IMV-MS可以充分利用SIMD资源，避免了资源浪费。SHA256算法高速实现—区块链中的SHA256优化方法三：多核SIMD实现IMV-MS在SIMD架构中能对单个消息进行并行化调度，而在需要同时对多个（个）独立消息进行哈希运算的情况下，Fan等人提出结合线程级并行和数据级并行架构加速SHA256。他们提出了区块链中SHA256消息块的运算方式，即使用IMV-MS进行消息调度，使用标量指令压缩表达式。AVX2架构中共有8个数据通路，一次计算4个子块，并将它们视为一个组，如下图所示。该工作流程仍然存在串行操作，不能充分利用多核线程级并行（TLP）和数据级并行（DLP）架构。因此，Fan等人将IMV-MS引入SHA256的消息调度和压缩阶段，将一个CPU视为一个单元，同时处理条消息（对于核处理器，可以同时处理条个消息），如表5-1所示。Scalar实现SIMD实现压缩轮次(0≤t≤15)消息调度Wt(16≤t≤31)压缩轮次(16≤t≤31)消息调度Wt(32≤t≤47)压缩轮次(32≤t≤47)消息调度Wt(48≤t≤63)压缩轮次(48≤t≤63)—SM3算法优化实现04SM3算法优化实现—CUDA框架CUDA允许多个kernel使用不同的流复制数据，能够在GPU设备上并发执行。每个设备中kernel数量取决于设备本身，如GTX1080为32个。此外，当前的GPU设备通常有多个数据复制引擎，能够并行地进行数据传输与计算。CUDA：一个支持并行运算的计算框架和编程模型，CUDA中的并行程序由线程执行；多个线程能够组成一个block，同一个block中的线程可以进行同步，也可以通过共享内存进行通信；多个block可以组成grid。CUDA允许开发人员使用他们熟悉的高级编程语言在GPU设备上处理任务，如C/C++、Python。它还提供了一个线程并行执行（PTX）指令，使在CUDA上进行的优化更加灵活。CUDA中针对GPU的编程模型与针对CPU的编程模型有所不同，GPU设备作为主机的协处理器，按照异构编程的方式，通过调用异步和可配置的kernel函数，将烦琐的计算外包到GPU上，而其余的串行代码则在主机端（CPU端）执行。从硬件方面来看，GPU建立在SM（StreamingMultiProcessor）上，每个SM都以SIMT（单指令多线程）的方式同时运行数千个线程，其中的调度单元是warp（线程束），它是一个包含32个并行线程的基本执行单元；从软件方面来看，kernel由多个grid组成，每个grid中的block数量和每个block中的线程数量都受到硬件的严格限制。SM3算法优化技术—优化数据通道流水线执行方案优化存在的问题：GPU运算时CPU处于等待状态，导致资源浪费新消息需等待前一个处理完成

，导致

延迟高改进方案（Sun等人提出）：利用GPUkernel的异步调用特性GPU处理当前消息的同时，CPU准备下一条消息提高并发性，减少等待时间效果：CPU、GPU协同最大化资源利用降低延迟，提高处理吞吐量线程表构建优化存在的问题：输入消息大小不一，导致频繁创建/销毁线程消耗CPU资源，影响性能稳定性改进方案：使用

OpenMP构建线程表在线程填充阶段一次性创建，复用线程运算结束后统一销毁线程表效果：减少线程开销与失败检测平滑线程管理，提高整体执行效率SM3算法优化技术—优化SM3运算循环展开SM3压缩函数和迭代模块含大量循环运算手动完成或编译器自动执行，能够消除SM3中大量循环运算带来的资源以及性能开销，并减少寄存器的使用量，同时帮助编译器进行分支测试该技术能够加快内存访问和计算速度，寄存器压力可能增加，从而导致性能不稳定。

在GPU平台上的原有SM3实现会浪费计算资源并降低算法整体的性能表现。Sun等人提出了一些通用的和特用于硬件的优化方法，对GPU平台上的SM3实现进行改进。

SM3算法优化技术—优化SM3运算内联PTX组件CUDA框架支持直接嵌入PTX指令。在迭代模块和压缩函数模块中，PTX指令能够直接进行位操作。例如，指令xor.b32、and.b32、or.b32和not.b32分别用于异或、与、或和非运算。左循环移位操作较为复杂，需要shl.b32、shr.b32和or.b32这3条指令完成。可以利用prmt指令交换32比特整数或64比特整数的字节顺序。内联函数或宏调用函数会带来额外的开销，例如，将寄存器保存到堆栈、跳转到被调用函数地址等操作，使用内联函数或宏能够减少此类损失。对于CUDA编程，编译器NVCC将自行决定合适的内联设备函数。同时，编译指示forceinline能够强制编译器内联设备函数。合并访问SM3算法中存在很多全局内存访问操作，延迟高。缓存技术存放中间数据，如消息块和中间哈希值等。可减少对全局内存的访问，提高访问速度和效率。采用预取技术，提前加载所需数据，降低等待时间。如下图（a），以行优先的方式存储哈希值，需要进行32次缓存转换。如下图（b），列优先的方式进行存储，那么只需要进行1次缓存转换。因此，当输入消息的长度相同时，应采用列优先的方式进行存储；当输入消息的长度不相同时，应采用行优先的方式进行存储。SM3算法优化技术—优化数据传输并行执行数据复制与计算构建多个数据流来并行传输数据。不同数据流中的操作可以交错地进行执行，并可以在某些情况下并行执行，以隐藏主机和设备之间传输的数据。使用PCI总线在CPU和GPU之间进行数据传输，会使算法的延迟增加，可以通过如下优化技术对此过程进行改进。具体步骤如下：首先创建多个数据流，并对输入的消息进行分割；消息的每个部分都通过不同的数据流异步地从主机复制到设备，并使用SM3算法对其进行哈希运算；在处理完所有的消息后，将输出的哈希值再通过数据流异步地从设备复制回主机，计算策略如右图所示。固定内存使用固定大小的内存空间能够提高内存传输带宽。由API中的cudaHostAlloc函数分配在主机端并锁定一个特定的内存空间，用于CPU和GPU之间的数据交换。通过进行上述的两项优化后，CPU和GPU之间的吞吐量在GTX1080上达到95.2Gbps。SM3算法优化实现—性能评估数据大小/KBGTX1080TITANXp最佳N延迟/ms吞吐量/Mbps最佳N延迟/ms吞吐量/Mbps126214427.0979272655367.73694532524288103.4583035524288116.69736134524288201.2785357262144106.38807488524288398.1886292524288418.818204116262144395.95867781638427.877705432131072395.5986857262144838.20819856432768199.2486227131072832.178257912832768397.948634465536902.26761642568192200.178582616384428.96801005128192400.03858934096225.747610510244096414.64828668192851.788067720482048483.44710734096972.427066940961024615.27558451024723.35475018192512915.4537533256812.70