密碼學(xué)基礎(chǔ)SHA256算法描述01SHA256算法背景：MD5和SHA1標準分別于1992年和1995年由密碼學(xué)家RonaldLinnRivest和美國國家安全局提出，SHA2標準作為SHA1的后繼標準被提出。根據(jù)不同的循環(huán)次數(shù)與哈希值長度，SHA2標準可再分為6個不同的算法，包括SHA224、SHA256、SHA384、SHA512、SHA512/224和SHA512/256。本節(jié)主要對SHA256進行描述。

SHA256算法—核心部件核心部件一：常量初始化SHA256算法中使用到的64個哈希常量如下偽代碼所示。這些常量對應(yīng)自然數(shù)的前64個質(zhì)數(shù)的立方根的前32比特小數(shù)部分（u32是C語言中的無符號32比特數(shù)據(jù)類型）。

SHA256算法—核心部件

比特填充例子：消息“enc”中e、n、c的ASCII碼分別是101、110、99，則輸入消息的二進制編碼如下:01100101

01101110

01100011

//共24比特補“1”后為01100101

01101110

01100011

1

//共25比特補423比特的“0”，湊齊448比特的數(shù)據(jù)，用十六進制數(shù)表示為656E6380

00000000

00000000

0000000000000000

00000000

00000000

0000000000000000

00000000

00000000

0000000000000000

00000000

//共448比特填充長度值信息：“enc”占用24比特，填充64比特長度信息后的十六進制數(shù)表示為656E6380

00000000

00000000

0000000000000000

00000000

00000000

0000000000000000

00000000

00000000

0000000000000000

00000000

00000000

00000018

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

SM3算法描述02SM3算法背景：SM3是由我國國家密碼管理局于2010年發(fā)布的哈希算法標準。SM3算法的設(shè)計是公開的，是在SHA256基礎(chǔ)上進行改進的一種算法。

SM3算法—核心部件核心部件一：常量初始化SM3中使用到8個哈希初值核心部件二：填充SM3的填充方式與SHA256大致相同，本節(jié)不再贅述

SM3算法—核心部件

SHA256算法高速實現(xiàn)03SHA256算法高速實現(xiàn)—樹哈希

SHA256算法高速實現(xiàn)—區(qū)塊鏈中的SHA256Fan等人于2021年利用區(qū)塊鏈的特性以及數(shù)據(jù)級并行（Data-LevelParallelism）和線程級并行（Thread-LevelParallelism）兩種并行機制來提高區(qū)塊鏈中最常用的SHA256的計算速度，并提供了3點優(yōu)化方法。優(yōu)化方法一：預(yù)處理填充模塊填充模塊的工作是對需要哈希的消息進行填充，確保其長度為512的倍數(shù)。在填充模塊，對于任意的輸入消息，都需要填充一個“1”位、若干位的“0”和64比特的長度值信息。Fan等人對區(qū)塊鏈中SHA256的運算模式進行分析，并提出了預(yù)處理填充模塊技術(shù)。該技術(shù)通過對消息塊進行預(yù)處理，使消息長度為512的整數(shù)倍，從而跳過了填充模塊和信息分割與擴展模塊的需要，提高了SHA256的計算速度。預(yù)處理填充模塊的SHA256和一般SHA256的性能對比如右圖所示。SHA256算法高速實現(xiàn)—區(qū)塊鏈中的SHA256

對上圖（a）與上圖（b）進行觀察可發(fā)現(xiàn)，IMV-MS可以充分利用SIMD資源，避免了資源浪費。SHA256算法高速實現(xiàn)—區(qū)塊鏈中的SHA256優(yōu)化方法三：多核SIMD實現(xiàn)IMV-MS在SIMD架構(gòu)中能對單個消息進行并行化調(diào)度，而在需要同時對多個（個）獨立消息進行哈希運算的情況下，F(xiàn)an等人提出結(jié)合線程級并行和數(shù)據(jù)級并行架構(gòu)加速SHA256。他們提出了區(qū)塊鏈中SHA256消息塊的運算方式，即使用IMV-MS進行消息調(diào)度，使用標量指令壓縮表達式。AVX2架構(gòu)中共有8個數(shù)據(jù)通路，一次計算4個子塊，并將它們視為一個組，如下圖所示。該工作流程仍然存在串行操作，不能充分利用多核線程級并行（TLP）和數(shù)據(jù)級并行（DLP）架構(gòu)。因此，F(xiàn)an等人將IMV-MS引入SHA256的消息調(diào)度和壓縮階段，將一個CPU視為一個單元，同時處理條消息（對于核處理器，可以同時處理條個消息），如表5-1所示。Scalar實現(xiàn)SIMD實現(xiàn)壓縮輪次(0≤t≤15)消息調(diào)度Wt(16≤t≤31)壓縮輪次(16≤t≤31)消息調(diào)度Wt(32≤t≤47)壓縮輪次(32≤t≤47)消息調(diào)度Wt(48≤t≤63)壓縮輪次(48≤t≤63)—SM3算法優(yōu)化實現(xiàn)04SM3算法優(yōu)化實現(xiàn)—CUDA框架CUDA允許多個kernel使用不同的流復(fù)制數(shù)據(jù)，能夠在GPU設(shè)備上并發(fā)執(zhí)行。每個設(shè)備中kernel數(shù)量取決于設(shè)備本身，如GTX1080為32個。此外，當(dāng)前的GPU設(shè)備通常有多個數(shù)據(jù)復(fù)制引擎，能夠并行地進行數(shù)據(jù)傳輸與計算。CUDA：一個支持并行運算的計算框架和編程模型，CUDA中的并行程序由線程執(zhí)行；多個線程能夠組成一個block，同一個block中的線程可以進行同步，也可以通過共享內(nèi)存進行通信；多個block可以組成grid。CUDA允許開發(fā)人員使用他們熟悉的高級編程語言在GPU設(shè)備上處理任務(wù)，如C/C++、Python。它還提供了一個線程并行執(zhí)行（PTX）指令，使在CUDA上進行的優(yōu)化更加靈活。CUDA中針對GPU的編程模型與針對CPU的編程模型有所不同，GPU設(shè)備作為主機的協(xié)處理器，按照異構(gòu)編程的方式，通過調(diào)用異步和可配置的kernel函數(shù)，將煩瑣的計算外包到GPU上，而其余的串行代碼則在主機端（CPU端）執(zhí)行。從硬件方面來看，GPU建立在SM（StreamingMultiProcessor）上，每個SM都以SIMT（單指令多線程）的方式同時運行數(shù)千個線程，其中的調(diào)度單元是warp（線程束），它是一個包含32個并行線程的基本執(zhí)行單元；從軟件方面來看，kernel由多個grid組成，每個grid中的block數(shù)量和每個block中的線程數(shù)量都受到硬件的嚴格限制。SM3算法優(yōu)化技術(shù)—優(yōu)化數(shù)據(jù)通道流水線執(zhí)行方案優(yōu)化存在的問題：GPU運算時CPU處于等待狀態(tài)，導(dǎo)致資源浪費新消息需等待前一個處理完成

，導(dǎo)致

延遲高改進方案（Sun等人提出）：利用GPUkernel的異步調(diào)用特性GPU處理當(dāng)前消息的同時，CPU準備下一條消息提高并發(fā)性，減少等待時間效果：CPU、GPU協(xié)同最大化資源利用降低延遲，提高處理吞吐量線程表構(gòu)建優(yōu)化存在的問題：輸入消息大小不一，導(dǎo)致頻繁創(chuàng)建/銷毀線程消耗CPU資源，影響性能穩(wěn)定性改進方案：使用

OpenMP構(gòu)建線程表在線程填充階段一次性創(chuàng)建，復(fù)用線程運算結(jié)束后統(tǒng)一銷毀線程表效果：減少線程開銷與失敗檢測平滑線程管理，提高整體執(zhí)行效率SM3算法優(yōu)化技術(shù)—優(yōu)化SM3運算循環(huán)展開SM3壓縮函數(shù)和迭代模塊含大量循環(huán)運算手動完成或編譯器自動執(zhí)行，能夠消除SM3中大量循環(huán)運算帶來的資源以及性能開銷，并減少寄存器的使用量，同時幫助編譯器進行分支測試該技術(shù)能夠加快內(nèi)存訪問和計算速度，寄存器壓力可能增加，從而導(dǎo)致性能不穩(wěn)定。

在GPU平臺上的原有SM3實現(xiàn)會浪費計算資源并降低算法整體的性能表現(xiàn)。Sun等人提出了一些通用的和特用于硬件的優(yōu)化方法，對GPU平臺上的SM3實現(xiàn)進行改進。

SM3算法優(yōu)化技術(shù)—優(yōu)化SM3運算內(nèi)聯(lián)PTX組件CUDA框架支持直接嵌入PTX指令。在迭代模塊和壓縮函數(shù)模塊中，PTX指令能夠直接進行位操作。例如，指令xor.b32、and.b32、or.b32和not.b32分別用于異或、與、或和非運算。左循環(huán)移位操作較為復(fù)雜，需要shl.b32、shr.b32和or.b32這3條指令完成。可以利用prmt指令交換32比特整數(shù)或64比特整數(shù)的字節(jié)順序。內(nèi)聯(lián)函數(shù)或宏調(diào)用函數(shù)會帶來額外的開銷，例如，將寄存器保存到堆棧、跳轉(zhuǎn)到被調(diào)用函數(shù)地址等操作，使用內(nèi)聯(lián)函數(shù)或宏能夠減少此類損失。對于CUDA編程，編譯器NVCC將自行決定合適的內(nèi)聯(lián)設(shè)備函數(shù)。同時，編譯指示forceinline能夠強制編譯器內(nèi)聯(lián)設(shè)備函數(shù)。合并訪問SM3算法中存在很多全局內(nèi)存訪問操作，延遲高。緩存技術(shù)存放中間數(shù)據(jù)，如消息塊和中間哈希值等?？蓽p少對全局內(nèi)存的訪問，提高訪問速度和效率。采用預(yù)取技術(shù)，提前加載所需數(shù)據(jù)，降低等待時間。如下圖（a），以行優(yōu)先的方式存儲哈希值，需要進行32次緩存轉(zhuǎn)換。如下圖（b），列優(yōu)先的方式進行存儲，那么只需要進行1次緩存轉(zhuǎn)換。因此，當(dāng)輸入消息的長度相同時，應(yīng)采用列優(yōu)先的方式進行存儲；當(dāng)輸入消息的長度不相同時，應(yīng)采用行優(yōu)先的方式進行存儲。SM3算法優(yōu)化技術(shù)—優(yōu)化數(shù)據(jù)傳輸并行執(zhí)行數(shù)據(jù)復(fù)制與計算構(gòu)建多個數(shù)據(jù)流來并行傳輸數(shù)據(jù)。不同數(shù)據(jù)流中的操作可以交錯地進行執(zhí)行，并可以在某些情況下并行執(zhí)行，以隱藏主機和設(shè)備之間傳輸?shù)臄?shù)據(jù)。使用PCI總線在CPU和GPU之間進行數(shù)據(jù)傳輸，會使算法的延遲增加，可以通過如下優(yōu)化技術(shù)對此過程進行改進。具體步驟如下：首先創(chuàng)建多個數(shù)據(jù)流，并對輸入的消息進行分割；消息的每個部分都通過不同的數(shù)據(jù)流異步地從主機復(fù)制到設(shè)備，并使用SM3算法對其進行哈希運算；在處理完所有的消息后，將輸出的哈希值再通過數(shù)據(jù)流異步地從設(shè)備復(fù)制回主機，計算策略如右圖所示。固定內(nèi)存使用固定大小的內(nèi)存空間能夠提高內(nèi)存?zhèn)鬏攷挕Ｓ葾PI中的cudaHostAlloc函數(shù)分配在主機端并鎖定一個特定的內(nèi)存空間，用于CPU和GPU之間的數(shù)據(jù)交換。通過進行上述的兩項優(yōu)化后，CPU和GPU之間的吞吐量在GTX1080上達到95.2Gbps。SM3算法優(yōu)化實現(xiàn)—性能評估數(shù)據(jù)大小/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.7021139

SM3算法優(yōu)化實現(xiàn)—性能評估NGTX1080TITANXp延遲/ms吞吐量/Mbps延遲/ms吞吐量/Mbps327341.572818651.28238644210.364894518.814561282327.928852461.898372561390.9314811515.631359512734.192806827.2524901024416.544946527.1639082048320.576427480.1242914096310.996625402.9951128192306.506722378.26544716384298.456903312.87658532768307.946690314.466552

任意長度的數(shù)據(jù)：在消息長度不固定的情況下，Sun等人選取兩個8核平臺進行測試。在數(shù)據(jù)長度任意的情況下，性能測試結(jié)果如右表所示，也能獲得很高的吞吐量，但無法與固定長度數(shù)據(jù)的情況相比。造成這種性能下降的主要原因有以下兩個。輸入的消息無法進行合并訪問操作，導(dǎo)致時鐘周期數(shù)增加。輸入的消息長度不統(tǒng)一，導(dǎo)致每個線程的計算不均勻，GPU計算資源被浪費。謝謝大家密碼學(xué)基礎(chǔ)算法描述01RSA算法概述1978年，RonaldRivest、AdiShamir和LeonardAdleman提出了一種基于有限域的公鑰密碼實現(xiàn)方案：RSA，算法的名稱是他們?nèi)齻€人首字母的縮寫。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近三十年，經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。原理：大整數(shù)分解困難問題。

應(yīng)用場景：（1）小片段數(shù)據(jù)的加密，如密鑰傳輸。（2）數(shù)字簽名，如互聯(lián)網(wǎng)上的數(shù)字證書。RSA公司的三位創(chuàng)始人RSA加密

算法描述示例RSA簽名

算法描述示例算法原理02解密算法的正確性推導(dǎo)

基礎(chǔ)實現(xiàn)03大整數(shù)運算:大整數(shù)加減法

0102大整數(shù)加法的代碼表示大整數(shù)減法的代碼表示大整數(shù)加法大整數(shù)減法大整數(shù)運算：大整數(shù)模加

大整數(shù)模加的代碼表示大整數(shù)模加03大整數(shù)運算：大整數(shù)模減大整數(shù)模減的代碼表示大整數(shù)模減

04

基于費馬小定理的大整數(shù)求逆:

基于二進制擴展歐幾里得(BEEA)算法的大整數(shù)求逆:大整數(shù)運算：大整數(shù)求逆基于BEEA的大整數(shù)求逆05大整數(shù)求逆費馬小定理模逆BEEA模逆基本原理通過模冪運算求逆元保持等式，通過不斷移位和減法求逆元計算特點調(diào)用模乘、模平方操作，算法結(jié)構(gòu)簡單大量使用移位代替除法，速度快效率稍慢一些（取決于冪大?。a短小、結(jié)構(gòu)穩(wěn)定計算效率高，特別適合大數(shù)運算代碼量小，容易集成，適合資源受限場景稍復(fù)雜，需要維護多組變量和狀態(tài)安全性較高，能防止通過功耗信息泄露秘密數(shù)據(jù)，能抵抗SPA、組合攻擊有安全隱患，2017年Aldaya指出：容易通過功耗分析（SPA）泄露底數(shù)的比特位應(yīng)用場景安全性要求高、資源受限（如嵌入式、智能卡）對計算速度要求極高，但安全性可控的環(huán)境費馬小定理模逆

VSBEEA模逆蒙哥馬利模乘只用乘法和移位操作實現(xiàn)模乘，極大減少除法開銷時間恒定，避免定時攻擊特點:將數(shù)轉(zhuǎn)換到蒙哥馬利域（即變換成特殊形式）定義蒙哥馬利乘積通過蒙哥馬利約減快速計算結(jié)果核心思想:RSA算法的核心運算是模冪運算，模乘是模冪的基礎(chǔ)1985年，Montgomery提出蒙哥馬利模乘（MontgomeryMultiplication）算法起源:蒙哥馬利模乘算法蒙哥馬利模乘MonPro有5種實現(xiàn)方法：SOS（SeparatedOperandScanning）CIOS（CoarselyIntegratedOperandScanning）CIHS（CoarselyIntegratedHybridScanning）其中CIOS是最快速的實現(xiàn)方法。蒙哥馬利模乘算法-CIOS表6-2

不同方法實現(xiàn)MonPro算法的性能對比（時間/ms）表6-1

不同方法實現(xiàn)MonPro計算復(fù)雜度對比（s為操作數(shù)字長）FIOS（FinelyIntegratedOperandScanning）FIPS（FinelyIntegratedProductScanning）冪指數(shù)運算：二進制掃描法

算法描述示例表6-3

for循環(huán)執(zhí)行冪指數(shù)運算：固定窗口算法

算法描述示例表6-4固定窗口算法示例計算過程冪指數(shù)運算：滑動窗口算法

算法描述示例優(yōu)化實現(xiàn)04預(yù)備知識：基于RNS的運算

描述:

注意事項:對于大整數(shù)運算，不處理它本身，而是同時處理它在一組小整數(shù)模數(shù)下的余數(shù)，各個模數(shù)之間互不相關(guān)，可以并行計算，借此來提升效率。原理:全稱:ResidueNumberSystem。

缺點:需要多次小模數(shù)運算和最后CRT重