DES算法DES算法描述01DES算法1973年，美國國家標(biāo)準(zhǔn)局（NIST）征求國家密碼標(biāo)準(zhǔn)時，IBM提供了Tuchman-Meyer方案1977年，Tuchman-Meyer方案被正式確立為數(shù)據(jù)加密標(biāo)準(zhǔn)，即DES1998年7月，電子前哨基金會（EFF）利用一臺造價不足25萬美金的特殊計算機(jī)攻破了DESNIST征集新的密碼標(biāo)準(zhǔn)替換DES，采納Rijndael算法作為新的標(biāo)準(zhǔn)算法，即AES。2001年正式推出DES是分組密碼的典型代表，也是第一個被公布出來的標(biāo)準(zhǔn)算法。分組密碼：明文分組、密文分組及密鑰分組大小均為64比特。在實(shí)際運(yùn)算中，對密鑰每隔7個比特（8,16,…,64）設(shè)置一個奇偶校驗(yàn)位，不參與運(yùn)算，實(shí)際密鑰長度只有56比特.對稱密碼：加密和解密除密鑰編排不同外，使用同一算法。采用混淆和擴(kuò)散的組合，每個組合先替代后置換，共16輪。只使用了標(biāo)準(zhǔn)的算術(shù)和邏輯運(yùn)算，易于實(shí)現(xiàn)。DES算法結(jié)構(gòu)DES加/解密算法流程

算法流程

初始置換和逆初始置換初始置換IP

初始逆置換IP-15850423426181024084816562464326052443628201243974715552363316254463830221463864614542262306456484032241683754513532161295749413325179136444125220602859514335271911335343115119592761534537292113534242105018582663554739312315733141949175725

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364初始置換和逆初始置換58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157例：明文中的第20位經(jīng)過初始置換后處于第14位，通過逆初始置換第14位換回到第20位IP輸入塊輸出塊

??函數(shù)內(nèi)部構(gòu)造??函數(shù)內(nèi)部按序可分成3個部分：E擴(kuò)展置換、S盒替換以及P盒置換，如下圖所示。

E擴(kuò)展置換產(chǎn)生與密鑰同長度的數(shù)據(jù)以進(jìn)行異或運(yùn)算；提供更長的結(jié)果，使得在S盒替代運(yùn)算時能夠進(jìn)行壓縮。

E擴(kuò)展置換32|01020304|0504|05060708|0908|09101112|1312|13141516|1716|17181920|2120|21222324|2524|25262728|2928|29303132|01E擴(kuò)展置換表數(shù)據(jù)的擴(kuò)展置換規(guī)則：中間為32位，兩邊為擴(kuò)展位，擴(kuò)展后為48位。

S盒替換S盒替換的構(gòu)造S盒的目的是對擴(kuò)展后的數(shù)據(jù)塊進(jìn)行壓縮，同時進(jìn)行一次非線性替換，替換操作由8個不同的S盒查找表完成。S盒替換的構(gòu)造如右圖所示。首先將E擴(kuò)展置換結(jié)果與輪密鑰進(jìn)行異或后的48比特數(shù)據(jù)塊分為8組，每組6比特，分別送入對應(yīng)的S盒。每個S盒有一張4行16列的查找表，由6比特輸入作為索引，輸出4比特結(jié)果。記S盒的6比特輸入為abcdef，第0比特和第5比特組合形成行號af，第1～4比特組合形成列號bcde，用于查找4比特結(jié)果。替換操作由8個不同的S盒查找表完成。最后再將8個S盒的4比特結(jié)果合并，形成32比特輸出。S盒替換S盒替換的構(gòu)造S盒的目的是對擴(kuò)展后的數(shù)據(jù)塊進(jìn)行壓縮，同時進(jìn)行一次非線性替換，替換操作由8個不同的S盒查找表完成。S盒替換的構(gòu)造如下圖所示。首先將E擴(kuò)展置換結(jié)果與輪密鑰進(jìn)行異或后的48比特數(shù)據(jù)塊分為8組，每組6比特，分別送入對應(yīng)的S盒。每個S盒有一張4行16列的查找表，由6比特輸入作為索引，輸出4比特結(jié)果。記S盒的6比特輸入為abcdef，第0比特和第5比特組合形成行號af，第1～4比特組合形成列號bcde，用于查找4比特結(jié)果。替換操作由8個不同的S盒查找表完成。最后再將8個S盒的4比特結(jié)果合并，形成32比特輸出。替換步驟S盒替換例：假設(shè)S-盒6的輸入(即異或函數(shù)的第31位到36位)為110011。（1）第1位和最后一位組合形成了11，它對應(yīng)著S-盒6的第3行。（2）中間的4位組合形成了1001，它對應(yīng)著S-盒6的第9列。（3）S-盒6的第3行第9列處的數(shù)是14，得到輸出值為1110。0

12，1，10，15，9，2，6，8，0，13，3，4，14，7，5，11，1

10，15，4，2，7，12，9，5，6，1，13，14，0，11，3，8，29，14，15，5，2，8，12，3，7，0，4，10，1，13，11，6，34，3，2，12，9，5，15，10，11，14，1，7，6，0，8，13

0123456789101112131415

S-盒6查找表P盒置換S盒替換運(yùn)算后的32位輸出依照P盒進(jìn)行置換。P盒置換將每一輸入位映射到輸出位。任一位不能被映射兩次，也不能被略去。經(jīng)過P盒置換的結(jié)果與最初64位分組的左半部分異或，然后左右兩部分交換，開始下一輪迭代。P盒置換表16，7，20，21，29，12，28，17，1，15，23，26，5，18，31，10，

2，8，24，14，32，27，3，9，19，13，30，6，22，11，4，25例：第21位移到了第4位，第4位移到了第31位。密鑰編排

DES加密算法共對明文執(zhí)行16次輪加密，需要16個輪密鑰。由初始64比特用戶密鑰生成16個48比特輪密鑰的過程稱為密鑰編排。密鑰編排算法也需進(jìn)行多輪迭代運(yùn)算，其算法流程如下：DES快速實(shí)現(xiàn)02基于AVX的DES快速實(shí)現(xiàn)：變換操作將單指令多數(shù)據(jù)流（SIMD）應(yīng)用到DES中，即多塊（Multi-Block）DES。該方法將輸入調(diào)整成適合使用SIMD指令的形式，可以高效地并行處理多條消息，但需要花費(fèi)額外的變換操作。vmovdqu(%rsi),%xmm0vmovdqu(%rdi),%xmm1vpshufd$0x4e,%xmm1,%xmm1vpblendd$0x0c,%xmm0,%xmm1,%xmm2vmovdqu(%rsi),%xmm0vmovdqu(%rdi),%xmm1vpunpcklqdq%xmm0,%xmm1,%xmm2vpunpckhqdq%xmm0,%xmm1,%xmm3vmovdqu(%rsi),%xmm0vmovdqu(%rdi),%xmm1vpunpckldq%xmm0,%xmm1,%xmm2vpunpckhdq%xmm0,%xmm1,%xmm3

基于AVX的DES快速實(shí)現(xiàn):SIMD處理SIMD核心優(yōu)化思想半塊并行處理：將32位半塊數(shù)據(jù)裝入SIMD寄存器；關(guān)鍵操作：移位、邏輯與異或技術(shù)優(yōu)勢傳統(tǒng)串行實(shí)現(xiàn)SIMD并行實(shí)現(xiàn)單指令處理1個半塊單指令處理8個半塊(AVX512)S盒串行查表寄存器預(yù)加載S盒表P盒逐位置換常量掩碼批量置換基于AVX的DES快速實(shí)現(xiàn):SIMD處理S盒替換優(yōu)化AVX512實(shí)現(xiàn)流程：將8個塊的48位輸入打包到寄存器分16次加載S盒表到寄存器使用掩碼寄存器選擇正確S盒區(qū)域合并結(jié)果寄存器P盒替換優(yōu)化SIMD常量預(yù)計算：提前生成P盒置換掩碼單條指令完成多半塊置換工作模式適配基于SIMD的DES快速實(shí)現(xiàn)ECB：直接拆分/合并半塊，指令開銷可忽略CBC：需處理塊間依賴，AVX2下性能可能劣化（僅為OpenSSL的79%）64位平臺上的DES快速實(shí)現(xiàn)：標(biāo)準(zhǔn)實(shí)現(xiàn)實(shí)現(xiàn)思路位級并行：64位處理器視為64個1位處理器。數(shù)據(jù)重組：比特分散存儲，一次加密64個字的各1位，而非一次加密一個64位字。異或操作按位計算，不受影響；P盒置換和E擴(kuò)展置換操作實(shí)現(xiàn)時只要改變寄存器的命名順序，就可以對需要的比特直接尋址。S盒比較復(fù)雜，需要從不同的字中分別提取6比特，拼湊成索引；查找到結(jié)果后再將4比特分別存放，非常低效。需要針對S盒查找進(jìn)行優(yōu)化。S盒查找優(yōu)化使用與、或、非、異或等操作表示S盒的門電路，采用優(yōu)化手段減少S盒的總門數(shù)。先計算的16種函數(shù)，再存入14個寄存器中，需要兩個求非運(yùn)算以及10個額外操作。每個S盒中該步驟只需預(yù)先做一次，之后計算輸出位時就可以直接使用這些函數(shù)，所以每行只需6個操作計算和6個操作組合計算結(jié)果。平均每個S盒只需要100個操作。效果：比64位Alpha計算機(jī)上最快的DES實(shí)現(xiàn)快了約5倍。64位平臺上的DES快速實(shí)現(xiàn)：非標(biāo)準(zhǔn)實(shí)現(xiàn)實(shí)現(xiàn)思路位級并行：64位處理器視為64個1位處理器。數(shù)據(jù)重組：整字節(jié)存儲（查表優(yōu)化），在64位處理器上，擴(kuò)展到48比特的密文右半部分可以完整地存儲在一個字中。如果將S盒輸入的6個分別存放的比特存放在一整個字節(jié)中，可以通過單字節(jié)引用直接訪問S盒表。同理，可以將查找表應(yīng)用到初始置換和逆初始置換中，對各種表查找的結(jié)果進(jìn)行異或處理。操作優(yōu)化在每輪中，將（表示為8字節(jié)，但每字節(jié)中只使用6比特）和輪密鑰（表示方法相同）進(jìn)行異或，然后用8個查找表來實(shí)現(xiàn)S盒替換，結(jié)果也要異或。此時，S盒的64比特結(jié)果中已經(jīng)包括了P盒置換和E擴(kuò)展置換操作。由于同一輪中8個S盒可以并行處理，因此流水線不會阻塞。效果：在300MHzAlpha處理器上比當(dāng)時已知的最快實(shí)現(xiàn)快了一倍。3-DES的GPU實(shí)現(xiàn)033-DES結(jié)構(gòu)設(shè)計3-DES結(jié)構(gòu)3-DES的加密可以分為三部分：（1）用密鑰1對明文進(jìn)行DES加密；（2）用密鑰2進(jìn)行DES解密；（3）用密鑰3進(jìn)行DES加密，完成整個加密操作。3-DES解密是對3-DES加密的逆向操作。3-DES結(jié)構(gòu)設(shè)計新的3-DES加密流程在CUDA編程中，實(shí)現(xiàn)3-DES的基本想法是將加密和解密操作放在GPU上，同時保留傳統(tǒng)的3-DES結(jié)構(gòu)。然而，這在CUDA編程中可能會面臨以下一些問題。并行算法構(gòu)建困難

如何利用GPU內(nèi)存優(yōu)化系統(tǒng)

3-DES加密的實(shí)現(xiàn)設(shè)計一個3-DES加密程序，要考慮各種類型的文件PowerPoint/Word:使用'\0'作為其結(jié)束符號。在這種情況下，只需要確定輸入的字是什么。流媒體數(shù)據(jù)（音樂或電影文件）：‘\0’不是結(jié)束符號，因此需要調(diào)整程序來適應(yīng)所有的文件類型。

如果一次輸入1000個字的明文，而結(jié)束符號'\0'是第1250個字，這時必須做兩次循環(huán)才能輸入所有的明文。但當(dāng)兩次循環(huán)后，卻讀到了明文的第2000個字，而該字是編譯器無法識別的空字，所以循環(huán)并不會停止。綜合上述兩個因素，Yeh等人的文獻(xiàn)中給出了偽代碼，如右邊所示Algorithm-DESEncryption(plaintext,ciphertext);Input:plaintext(64*Nbitsplaintext).Output:ciphertext(64*Nbitsciphertext).//Nmeanshowmanythreadsweuseindevice.begindeclareintegerplaintext[64*N],temptext[64*N],ciphertext[64*N];declareintegerkey1[64],key2[64],key3[64],key[192];declareintegerplaintextsize=64*N;while(notreachtheendoffile){input_EN(plaintext,temptext);//putplaintexttintotempbufferkey=key_schedule(key1,key2,key3);//generatesubkeyscopytemptextformhostmemorytodevicememory__global__3-DES_encryption(temptext,key);Copytemptextformdevicememorytohostmemoryswap(ciphertext,temptext);output_EN(ciphertext);}end3-DES加密的實(shí)現(xiàn)Algorithm-DESEncryption(plaintext,ciphertext);Input:plaintext(64*Nbitsplaintext).Output:ciphertext(64*Nbitsciphertext).//Nmeanshowmanythreadsweuseindevice.begindeclareintegerplaintext[64*N],temptext[64*N],ciphertext[64*N];declareintegerkey1[64],key2[64],key3[64],key[192];declareintegerplaintextsize=64*N;while(notreachtheendoffile){input_EN(plaintext,temptext);//putplaintexttintotempbufferkey=key_schedule(key1,key2,key3);//generatesubkeyscopytemptextformhostmemorytodevicememory__global__3-DES_encryption(temptext,key);Copytemptextformdevicememorytohostmemoryswap(ciphertext,temptext);output_EN(ciphertext);}end只有__global__3-DES_encryption函數(shù)在GPU中執(zhí)行。只有key_schedule函數(shù)可以被并行化，沿用了傳統(tǒng)3-DES的key_schedule設(shè)計，計算量很少，不值得在CUDA中執(zhí)行，其內(nèi)存訪問時間大于計算時間。代碼支持所有文件類型，設(shè)計了新的結(jié)束符號判斷方法。如果一次輸入1000個字，相當(dāng)于8000比特的明文，詳細(xì)設(shè)計如下：新的結(jié)束符號設(shè)計：特殊標(biāo)識"/nend/ab"（8字節(jié)）。添加結(jié)束符號：Yeh等人用fread()來確定是否已經(jīng)讀入所有明文，若fread()=8000，追加結(jié)束符號/nend/ab；每1000字節(jié)（8000比特）為單元，強(qiáng)制追加8字節(jié)結(jié)束符號。例[1000字節(jié)]→[1000]+/nend/ab找出明文結(jié)尾：當(dāng)fread()<8000，意味著已經(jīng)找到明文結(jié)尾。注意需要填充明文達(dá)到1008個字（包含結(jié)束符合8個），例剩余[600字節(jié)]→[600]+/nend/ab+[400個\0]

循環(huán)終止機(jī)制：fread()返回0，立即停止3-DES加密流程。3-DES解密的實(shí)現(xiàn)

3-DES解密的實(shí)現(xiàn)與3-DES加密類似，但解密需要更多的判斷操作，這意味著需要更多的CPU時間來決定何時停止操作。與加密不同，解密的輸入是全部密文，需要先對密文進(jìn)行解密，然后才能對其進(jìn)行分析。下面是實(shí)現(xiàn)的具體細(xì)節(jié)：（1）輸入1008個字并解密當(dāng)程序啟動時，將輸入1008個字的密文，并將其發(fā)送到GPU進(jìn)行解密。這個階段將一直重復(fù)下去，直到?jīng)]有密文輸入。（2）解密后的分析解密后，程序會分析明文的最后8個字。如果這8個字是"/nend/ab"，就意味著輸入文件沒有到達(dá)結(jié)尾。程序?qū)⑤敵鰶]有"/nend/ab"的結(jié)果，并返回第1階段。如果這8個字不是"/nend/ab"，就意味著輸入的文件已經(jīng)到達(dá)了結(jié)尾，程序應(yīng)該分析這1008個字以找出結(jié)束符號的位置。當(dāng)程序找到結(jié)束符號的位置時，它將把沒有"/nend/ab\0\0\0..."的結(jié)果輸出為明文。完成了所有工作之后，程序跳出循環(huán)。謝謝大家密碼學(xué)基礎(chǔ)AES算法描述01AES（AdvancedEncryptionStandard）算法背景：1997年，美國國家標(biāo)準(zhǔn)與技術(shù)研究院（NIST）開始征集高級加密標(biāo)準(zhǔn)，用以取代DES，經(jīng)過了長達(dá)5年的標(biāo)準(zhǔn)化評估，最終于2001年選定Rijndael算法。AES是分組長度為128比特的Rijindael算法。AES：高級加密標(biāo)準(zhǔn)，是一種分組密碼，要求明文和密文的分組長度都為16字節(jié)。不同的密鑰長度對應(yīng)不同的加/解密輪次。密鑰長度加密輪次解密輪次AES-12810輪10輪AES-19212輪12輪AES-25614輪14輪狀態(tài)矩陣：16字節(jié)的明文塊被排列成的矩陣AES算法—加/解密流程AES-128，加密算法流程：初始輪密鑰加：將狀態(tài)矩陣與初始密鑰矩陣進(jìn)行按位異或。一輪加密：執(zhí)行輪函數(shù)，對狀態(tài)矩陣依次執(zhí)行字節(jié)替換、行移位、列混淆及輪密鑰加等操作。重復(fù)第二步10次，得到128比特密文。注：第10輪不再進(jìn)行行列混淆操作AES-128，解密算法流程：將輪密鑰的使用順序顛倒過來，并逆序進(jìn)行加密過程中的所有操作的逆運(yùn)算。線性運(yùn)算（如行移位、列混淆等）在數(shù)學(xué)上的求逆是簡單的，只需改變操作執(zhí)行的方向或?qū)Σ僮骶仃嚽竽婕纯?。在非線性部分（S盒）中，由于S盒表是精心設(shè)計的，存在逆S盒，因此只需計算出逆S盒的常量表即可。AES算法—基本結(jié)構(gòu)AES算法基本結(jié)構(gòu)特點(diǎn):沒有采用Feistel結(jié)構(gòu)遵循替代-置換網(wǎng)絡(luò)（Substitution-PermutationNetwork）原則建立。每輪加密包括：字節(jié)替換層擴(kuò)散層密鑰加層AES算法核心部件—字節(jié)替換層字節(jié)替換層:簡單的查表操作AES定義一個S盒和一個逆S盒，將狀態(tài)矩陣中的每個元素映射為一個新元素S盒輸入輸出都是8比特字節(jié)替換操作時，字節(jié)的高4比特作為行值，低4別特作為列值，取出S盒中對應(yīng)的元素，代替原位置的字節(jié)DES使用8個不同的S盒，AES使用16個S盒完全相同AES算法中的唯一非線性層AES算法核心部件—擴(kuò)散層

AES算法核心部件—擴(kuò)散層

AES算法核心部件—擴(kuò)散層

伽羅瓦域乘法函數(shù)偽代碼實(shí)現(xiàn)AES算法核心部件—密鑰加層密鑰加層：兩個輸入是16字節(jié)的當(dāng)前狀態(tài)矩陣和密鑰編排算法生成的輪密鑰，輸出二者按位異或的結(jié)果。

AES算法核心部件—密鑰編排密鑰編排：計算的基本單位是32比特字(密鑰矩陣的一列)；輸入為原始密鑰矩陣(4×32比特),輸出一系列相同位數(shù)的輪密鑰(4×32比特)；具體分為預(yù)計算和動態(tài)生成兩種方法。

動態(tài)生成：動態(tài)生成的輪密鑰計算規(guī)則與預(yù)計算相同，區(qū)別是輪密鑰在加密和解密算法運(yùn)行過程中動態(tài)地生成，而非預(yù)先加載。在生成輪密鑰之后，密鑰編排算法將根據(jù)加/解密算法安排密鑰參與運(yùn)算的順序。若為加密算法，則輪密鑰正向參與運(yùn)算；若為解密算法，則輪密鑰反向參與運(yùn)算。SM4算法描述02SM4算法

SM4算法是一種典型的Feistel結(jié)構(gòu)算法，解密算法與加密算法結(jié)構(gòu)相同，區(qū)別僅是輪密鑰的使用順序。

SM4算法—密鑰擴(kuò)展算法

密鑰擴(kuò)展算法偽代碼AES算法高速實(shí)現(xiàn)03AES算法高效實(shí)現(xiàn)—基于資源受限平臺AES傳統(tǒng)實(shí)現(xiàn)中字節(jié)替換通常是通過256字節(jié)查找表實(shí)現(xiàn)的。除此之外，其他實(shí)現(xiàn)方法一般分為3種：T表法、向量轉(zhuǎn)置及位切片。T表法：字節(jié)替換、行移位以及列混淆經(jīng)過數(shù)學(xué)上的合并，最終形成4個1024字節(jié)的查找表，稱為T表。每個AES輪由16個掩碼(mask)、16個查找表讀取(load)、4個輪密鑰讀取(load)以及16個異或(xor)操作組成，這使得其在32位以上的平臺上的實(shí)現(xiàn)非常高效。如果花費(fèi)一個額外的旋轉(zhuǎn)操作，最終就只需要一個查找表來完成。向量轉(zhuǎn)置：T表法中的查找操作依賴于密鑰和數(shù)據(jù)，這使得對帶緩存架構(gòu)的定時攻擊變得容易。另一種方法是使用向量轉(zhuǎn)置，它避免了這種依賴于數(shù)據(jù)的查找。但并非所有的嵌入式平臺都支持該方法使用的指令，所以這種方法并不一定適用。位切片：位切片也是一種不需要查找表的方法，其核心思想是用SIMD方式并行處理多個塊，適用于具有長寄存器的架構(gòu)。對于AES而言，128比特數(shù)據(jù)通常分割到8個寄存器中，這就使得線性層非常高效。AES算法高效實(shí)現(xiàn)—基于資源受限平臺基于兩個典型的微處理器ARMCortex-M3以及Cortex-M4，介紹AES算法的快速實(shí)現(xiàn)。兩個微處理器都有16個32比特寄存器，其中3個保留給程序計數(shù)器、堆棧指針和鏈接寄存器。鏈接指針可以被推入堆棧，釋放另一個寄存器。ROM中的數(shù)據(jù)通常是通過密鑰擴(kuò)展和加/解密共享的，所以它只能在內(nèi)存中存在一次。在RAM一欄中，I/O是指函數(shù)需要用來存儲輸入和輸出的內(nèi)存。I/O數(shù)據(jù)通常通過密鑰擴(kuò)展和加/解密共享，相同的堆棧空間可以用于加/解密函數(shù)調(diào)用。

AES算法快速實(shí)現(xiàn)—基于算法優(yōu)化狀態(tài)矩陣轉(zhuǎn)置算法優(yōu)化：在輪內(nèi)部，轉(zhuǎn)換可以通過使用查找表來實(shí)現(xiàn)。選擇為查找表保留少量的空間，只將S盒和逆S盒制成表格，所有剩余的操作都是被動態(tài)計算出來的。這意味著只能通過軟件技術(shù)來進(jìn)行多次伽羅瓦域上的乘法運(yùn)算。該算法在處理狀態(tài)矩陣轉(zhuǎn)置時，必須對所有步驟進(jìn)行修改。

AES算法快速實(shí)現(xiàn)—基于算法優(yōu)化密鑰調(diào)度算法優(yōu)化：將重新規(guī)劃密鑰生成的方案，在此期間完成調(diào)整。

AES算法快速實(shí)現(xiàn)—基于算法優(yōu)化轉(zhuǎn)置密鑰調(diào)度由以下轉(zhuǎn)換組成：

AES算法快速實(shí)現(xiàn)—GPU簡介CUDA：一個GPU開發(fā)環(huán)境，程序員可以借助CUDA編寫線程程序，同時指定線程和線程塊的數(shù)量。從硬件的角度來看，GPU組裝了許多處理器和片上存儲器，而線程并行可以避免處理器處于空閑狀態(tài)，提高GPU利用率。CUDA體系結(jié)構(gòu)：GPU芯片有N個多處理器（Multi-Processor，MP），每個MP有M個標(biāo)量處理器（ScalarProcessor，SP）、16KB共享內(nèi)存、多個32比特寄存器和一個共享指令緩存，它還從指令單元中去除了控制單元部分（如條件分支組件），增加了計算單元密度。總體而言，該芯片構(gòu)成了分層SIMD體系結(jié)構(gòu)。全局內(nèi)存(VRAM)：最大內(nèi)存區(qū)，用于CPU-GPU通信，訪問延遲高共享內(nèi)存：每個MP獨(dú)享，SP高速訪問，速度接近寄存器寄存器：GPU最快速的存儲單元常量內(nèi)存：只讀存儲區(qū)，低延遲訪問AES算法快速實(shí)現(xiàn)—GPU軟件模型軟件模型：線程分組為線程塊（Block），多個線程塊組成計算任務(wù)；每個線程映射到一個SP，線程塊資源（共享內(nèi)存、寄存器）在MP上平均分配；MP中32個線程為一組同步執(zhí)行（稱為Warp）。高效利用32線程（Warp）：全局內(nèi)存聯(lián)合存取低延遲（400-600周期）避免跨步訪問，提高數(shù)據(jù)傳輸效率聯(lián)合存取由CUDA編譯器自動優(yōu)化避免共享內(nèi)存組沖突共享內(nèi)存分16個存儲組線程訪問需避免同組沖突，否則最高16倍延遲差異AES算法快速實(shí)現(xiàn)—GPU優(yōu)化技術(shù)流水線延遲隱藏內(nèi)存訪問速度慢，存在寫后讀依賴SP流水線延遲大約需要24周期，一次warp延遲是4個周期每個MP至少執(zhí)行6次warp，保證流水線一直工作，隱藏延遲01無序執(zhí)行機(jī)制遇到內(nèi)存暫停時，其他warp無序調(diào)度繼續(xù)執(zhí)行最大化活躍線程數(shù)量，有效掩蓋內(nèi)存訪問延遲示例：NVIDIAGeforceGTX285，每個線程塊最多32線程02條件分支縮減SP沒有條件分支單元，GPU使用CUDA編譯器生成類散度順序執(zhí)行條件分支指令條件執(zhí)行通過謂詞寄存器和串行處理實(shí)現(xiàn)優(yōu)化策略：重構(gòu)算法，限制條件分支數(shù)03AES算法快速實(shí)現(xiàn)—基于GPU的快速實(shí)現(xiàn)優(yōu)化方案一：多粒度并行處理方案16字節(jié)/線程每個線程獨(dú)立地處理由16字節(jié)組成的每個明文塊僅適用明文塊之間的并行操作8字節(jié)/線程兩個線程處理一個明文塊利用了明文塊中內(nèi)部明文處理之間的并行性，需要使用共享內(nèi)存4字節(jié)/線程4個線程處理一個明文塊，內(nèi)存共享和同步是必要的，單個明文塊共享的線程數(shù)不同1字節(jié)/線程雖然32比特操作比較高效，但也能夠通過線程處理1字節(jié)的數(shù)據(jù)。1字節(jié)/線程意味著16個線程以協(xié)調(diào)的方式處理明文塊，盡管該粒度性能不高，但此粒度設(shè)計可用于早期研究中和其他粒度的比較。AES算法快速實(shí)現(xiàn)—基于GPU的快速實(shí)現(xiàn)優(yōu)化方案二：內(nèi)存分配方案。AES包含3種存儲形式：明文、密文和中間數(shù)據(jù)、T表和輪密鑰。變量常量內(nèi)存共享內(nèi)存寄存器T表√√×輪密鑰√√×明文×√√（如果是16字節(jié)/線程）輪密鑰和T表共享特性，可分配到常量內(nèi)存，延遲低T表訪問隨機(jī)，存在無法提供低訪問延遲的可能性共享內(nèi)存優(yōu)點(diǎn)：低延遲問題：存儲組沖突、多份冗余復(fù)制、浪費(fèi)空間明文處理開始存于全局內(nèi)存，AES編碼開始時轉(zhuǎn)入共享內(nèi)存16字節(jié)/線程粒度：中間變量直接存儲在寄存器中，避免共享沖突AES算法快速實(shí)現(xiàn)—基于GPU的快速實(shí)現(xiàn)輪密鑰和T表、明文兩種存儲形式是使用共享內(nèi)存分配數(shù)據(jù)的，共有兩種分配方法可供選擇：結(jié)構(gòu)的數(shù)組（AoS）和數(shù)組的結(jié)構(gòu)（SoA）結(jié)構(gòu)的數(shù)組AoS：結(jié)構(gòu)是指明文塊結(jié)構(gòu)，AoS根據(jù)其性質(zhì)處理明文。下表描述了共享內(nèi)存的線程訪問模式示例，粒度為8字節(jié)/線程數(shù)組的結(jié)構(gòu)SoA：SoA將明文的每個元素分配到一個數(shù)組中，它們會產(chǎn)生不同種類的存儲組沖突。下表描述了共享內(nèi)存的線程訪問模式示例，粒度為8字節(jié)/線程AES算法快速實(shí)現(xiàn)—基于GPU的快速實(shí)現(xiàn)優(yōu)化方案三：其他優(yōu)化

T表結(jié)構(gòu)：一個32比特陣列T表和旋轉(zhuǎn)操作（保存存儲區(qū)域）。一個具有字節(jié)順序內(nèi)存訪問的64比特陣列預(yù)計算T表。預(yù)計算32比特陣列T表×4。01重疊的GPU處理和內(nèi)存復(fù)制：重疊數(shù)據(jù)傳輸（內(nèi)存復(fù)制）和處理。AES編碼過程，將明文傳輸?shù)紾PU的全局內(nèi)存（以及從GPU的AES過程傳輸密文）重疊過程被稱為數(shù)據(jù)傳輸和處理之間的管道處理，下圖描繪了將數(shù)據(jù)分為兩個塊的情況下這種重疊的示意圖：03減少線程塊的切換：與其他應(yīng)用程序不同，AES中切換線程塊的開銷往往更大且不可忽略。用少量線程加密相當(dāng)多的明文，減少在AES中切換線程塊的開銷02SM4算法高速實(shí)現(xiàn)04SM4算法高速實(shí)現(xiàn)—基于CUDA的并行實(shí)現(xiàn)與優(yōu)化CUDA（ComputeUnifiedDeviceArchitecture）：是NVIDIA于2007年推出的一種通用GPU計算設(shè)備體系結(jié)構(gòu)，為GPU并行實(shí)現(xiàn)密碼算法提供了方便的平臺。2007年，Manavski等人首次使用了CUDA來加速AES，并提出了一個T表來提高密碼的性能。2008年，Harrison等人在CUDA上實(shí)現(xiàn)了AES的CTR模式，并討論了如何在GPU上規(guī)劃分組密碼的串行/并行執(zhí)行。2013年，Xia等人針對AES的ECB模式的缺點(diǎn)，改進(jìn)了基于CUDA的實(shí)現(xiàn)。2014年，Mei等人提出了一種新的細(xì)粒度基準(zhǔn)測試方法，并將其應(yīng)用于兩種流行的GPU體系結(jié)構(gòu)：Fermi和Kepler，并且研究了庫沖突對共享內(nèi)存訪問延遲的影響。2015年，F(xiàn)ei等人在CUDA下加速AES，刷新了新的性能紀(jì)錄。2020年，Li等人使用CUDA實(shí)現(xiàn)了SM4，并探索了不同的線程塊大小和明文塊大小對性能的影響，獲得了26倍的加速。SM4算法并行優(yōu)化實(shí)現(xiàn)—CUDA簡介CUDA編程架構(gòu)：CUDA使用CPU作為主機(jī)、GPU作為設(shè)備，允許CPU調(diào)用GPU來運(yùn)行程序的計算密集型部分CUDA的6種常見的內(nèi)存結(jié)構(gòu)：寄存器：最快的存儲單元，數(shù)量很少共享內(nèi)存：每塊的公共內(nèi)存本地內(nèi)存：對每個線程是私有的常量內(nèi)存：只讀內(nèi)存紋理內(nèi)存：只讀內(nèi)存，密碼學(xué)很少使用全局內(nèi)存：GPU中最大的內(nèi)存單元，所有線程都可以訪問，速度最慢SM4算法并行優(yōu)化實(shí)現(xiàn)—SM4并行設(shè)計01每個線程處理16字節(jié)明文，提高性能線程數(shù)量分配：優(yōu)選為32的倍數(shù)，避免資源浪費(fèi)最優(yōu)配置：每個塊512線程，最大線程數(shù)為1024網(wǎng)格大小設(shè)置：輸入大小/每塊線程數(shù)/明文塊大小并行粒度、線程和網(wǎng)格分配03輪密鑰分配02明文存儲在全局內(nèi)存，適合存儲大量數(shù)據(jù)。S盒、FK和CK存儲在常量內(nèi)存，提高訪問速度。全局內(nèi)存速度較慢，但容量大，適合明文存儲。數(shù)據(jù)分配每個GPU線程使用不同的輪密鑰。多個輪密鑰：GPU生成輪密鑰并存儲在全局內(nèi)存中。單輪密鑰：CPU預(yù)計算輪密鑰，提高速度。SM4算法并行優(yōu)化實(shí)現(xiàn)—基礎(chǔ)實(shí)驗(yàn)

GPU對CPU的初步加速如下圖所示：GPU的加速比最大可達(dá)53.93小數(shù)據(jù)輸入：GPU加速效果不明顯，因數(shù)據(jù)傳輸和計算單元調(diào)度開銷大。大數(shù)據(jù)輸入：加速比迅速增大，但當(dāng)輸入達(dá)到

256KB

時，加速比趨于穩(wěn)定，最終穩(wěn)定在

50左右。結(jié)論：GPU加速并非無限增大，受到硬件和數(shù)據(jù)傳輸瓶頸的限制。SM4算法并行優(yōu)化實(shí)現(xiàn)—數(shù)據(jù)傳輸性能優(yōu)化頁鎖定內(nèi)存（固定內(nèi)存）VS可分頁內(nèi)存：默認(rèn)內(nèi)存：CPU通常分配可分頁內(nèi)存，但GPU無法直接訪問。數(shù)據(jù)傳輸過程：將數(shù)據(jù)從可分頁內(nèi)存復(fù)制到臨時頁鎖定內(nèi)存。然后將數(shù)據(jù)從頁鎖定內(nèi)存復(fù)制到GPU。優(yōu)化目標(biāo)：通過頁鎖定內(nèi)存，GPU可以直接訪問內(nèi)存，減少數(shù)據(jù)傳輸時間。頁鎖定內(nèi)存優(yōu)勢：傳輸吞吐量提升頁鎖定內(nèi)存的分配和釋放成本較高，但在大規(guī)模數(shù)據(jù)傳輸時能顯著提高吞吐量。優(yōu)化效果：輸入較?。杭铀傩Ч幻黠@，因頁鎖定內(nèi)存的初始成本較高。輸入較大：當(dāng)傳輸數(shù)據(jù)量超過64KB，初始開銷變得相對較小，優(yōu)化效果逐步顯現(xiàn)，最終優(yōu)化性能提高了40.73%。SM4算法并行優(yōu)化實(shí)現(xiàn)—并行流重疊執(zhí)行性能優(yōu)化SM4加密程序的執(zhí)行包括3個步驟：將明文和密鑰從主機(jī)復(fù)制到設(shè)備執(zhí)行加密操作將設(shè)備中的密文返回到主機(jī)重疊操作：將輸入數(shù)據(jù)分成多個子集，每個子問題在獨(dú)立的CUDA流中進(jìn)