contributed by < laochanlam
>, < etc276
>, < jack81306
>, < peterting
>
laochanlam
etc276
延伸 B04: clz 要求,探討 carryless multiplication 演算法和實作 (需要考慮到 Intel 延伸指令集),介紹密碼學的應用
選用適當的數學結構可保證計算上的正確性,以及利用其數學性質將運算加速
有限體 (Finite Field 或 Galois Field)
是包含有限個數元素的體。有限體最常見的例子是當 p 為質數時,整數對 p 取模。
以 GF(5) 為例
GF(5) = {0, 1, 2, 3, 4}
2 + 4 = 1 (mod 5),亦即 2 的加法反元素是 4
2 * 3 = 1 (mod 5),亦即 2 的乘法反元素是 3
p 為質數時,能保證集合中的所有的元素都有加法和乘法反元素 (0除外)
另一種常見的有限體 GF(pn)
以 GF(28) 為例
使用 m(x) = x8 + x4 + x3 + x2 + 1 作為質多項式
取模的概念是,將到達上界的值替換掉
以 2 * 6 (mod 10) 為例,就是計算 2 * 6 = 12 之後,將 10 替換為 0 ,得到 2
所以這邊就是將所有的 x8 替換成 x4 + x3 + x2 + 1 (正負號相同)
GF(28) | a的多項式表達 | D7D6D5D4D3D2D1D0 | 推導過程 |
---|---|---|---|
0 | 0 | 0 0 0 0 0 0 0 0 | |
a0 | a0 | 0 0 0 0 0 0 0 1 | |
a1 | a1 | 0 0 0 0 0 0 1 0 | |
a2 | a2 | 0 0 0 0 0 1 0 0 | |
a3 | a3 | 0 0 0 0 1 0 0 0 | |
a4 | a4 | 0 0 0 1 0 0 0 0 | |
a5 | a5 | 0 0 1 0 0 0 0 0 | |
a6 | a6 | 0 1 0 0 0 0 0 0 | |
a7 | a7 | 1 0 0 0 0 0 0 0 | |
a8 | a4+a3+a2+a0 | 0 0 0 1 1 1 0 1 | P(a) = a8 + a4 + a3 + a2 + a0 |
a9 | a5+a4+a3+a1 | 0 0 1 1 1 0 1 0 | a8*a = (a4+a3+a2+a0)*a = a5+a4+a3+a1 |
a10 | a6+a5+a4+a2 | 0 1 1 1 0 1 0 0 | a9*a = (a5+a4+a3+a1)*a = a6+a5+a4+a2 |
a11 | a7+a6+a5+a3 | 1 1 1 0 1 0 0 0 | a10*a = (a6+a5+a4+a2)*a = a7+a6+a5+a3 |
a12 | a7+a6+a3+a2+a0 | 1 1 0 0 1 1 0 1 | a11*a = (a7+a6+a5+a3)*a = a7+a6+a3+a2+a0 |
a13 | a7+a2+a1+a0 | 1 0 0 0 0 1 1 1 | a12*a = (a7+a6+a3+a2+a0)*a = a8+a7+a4+a3+a1 = (a4+a3+a2+a0) + a7+a4+a3+a1 = a7+a2+a1+a0 |
在 GF(pn)的情況下,必須找一個 n 次方的質多項式 (不被集合內的元素整除),以確保封閉性
如同上面所說,把超過上界(pn)的部分進行替換,且因為沒有進位的概念,不會替換完又超過 pn,就可以確保所有運算均具有封閉性
以數字表示
以多項式表示
3 * 3
= (x+1)(x+1)
= x2 + 2x + 1 = 9(10) (進位)
= x2 + 1 = 5(10) (無進位)
無進位乘法在密碼學上的應用
資訊安全 Galois Fields C++ 軟體實作體驗
伽罗华域(Galois Field,GF,有限域)乘法运算
在尋找 Intel 有關加密的延伸指令集時,找到了 AES-NI 的指令集,而在官方的文件中看到了以下一段:
PCLMULQDQ – Performs carry-less multiplication of two 64-bit data into a 128-bit result.
Carry-less multiplication of two 128-bit data into a 256-bit result can use PCLMULQDQ as building blocks.
Carry-less multiplication is an important piece of implementing Galois Counter Mode (GCM) operation of block ciphers.
GCM operation can be used in conjunction with AES algorithms to add an authentication capability.
GCM usage models also include IPsec, storage standard, and security protocols over fiber channel. Additionally, PCLMULQDQ can be used in
calculations of hash functions and CRC using arbitrary polynomials.
有提及到該指令集中有一個指令 PCLMULQDQ
,可輸入兩個 64-bit 的 data 作 Carry-less multiplication 輸出 128-bit 的 data。
而此處亦有提及到 Carry-less muliplication 是 GCM 加密應用的重要一環,所以先來研究一下 GCM (Galois/Counter Mode)。
GCM (Galois/Counter Mode) 的介紹在這裡。
隨後找到了 PCLMULQDQ
instruction 的官方文件,先來把文件讀完,隨後進行實作!
PCLMULQDQ
instruction 官方文件導讀進階加密指令集和安全金鑰構成 Intel® 資料保護技術 (Intel® Data Protection Technology)
INTRODUCTION TO INTEL® AES-NI AND INTEL® SECURE KEY INSTRUCTIONS
CPUIDFIELD:CPUID字段的统一编号、读取方案。范例:检查SSE4A、 AES、PCLMULQDQ指令
Intel® Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode
AES指令集 Wiki
這是 GCM 加密的流程圖:
問:那麼,到底 GCM 和 AES 之間有什麼關係,以致 GCM 裡面所用到的無進位乘法要放在 AES-NI 的指令集裡呢?
ECC 是一種建立公開金鑰加密的演算法,基於橢圓曲線數學的離散對數難題而成立
簡易的 ECC 說明
橢圓曲線(連續) 藉由 GF 的性質而離散化
以 GF(5) 的 y2 = x^3 + x + 1 為例
離散對數難題
其他細節
Montgomery Ladder
ECC 的優點是在相同安全度下,所需的密鑰長度較短,但缺點就是計算較慢,所以利用 PCLMULQDQ 來加速,參考資料 [2] 中提到這樣可以提升 10% 的速度
Intel Polynomial Multiplication Instruction and its Usage for Elliptic Curve Cryptography
Software implementation of binary elliptic curves:impact of the carry-less multiplier on scalar multiplication
近代加密 快速冪次計算
橢圓曲線密碼系統
[x]設計實驗測試 Intel 延伸指令集的優化程度
[x]設計 Intel 延伸指令集的數值分佈實驗
首先這個 AES-NI 是一個 Instruction set 嘛,所以我來找找怎麼把他放到 c code 裡面。
這個表格不錯,先把他記下來。
後來在參考完這裡之後,得知若要用 C 寫 Instruction Set 有以下兩種方法:
雖然後者的可讀性比較高,可是還是要經過 Compiler 的產生,不同的 Compiler 有可能會對效能有不同的影響。
接下來要開始去找 AES-NI 的 intrinsics 了!
先是從 Intel® Advanced Encryption Standard Instructions (AES-NI) 看到這一段
Compiler | Description | Version supporting AES-NI |
---|---|---|
Gcc/g++ | Open source GNU compiler for C/C++ | 4.4 or later |
Intel® C/C++ compiler | Intel compiler tools for C/C+ | 11.1 or later |
Microsoft* Visual C++ | C/C++ compiler tools for Windows* operating systems | 2008 SP1 or later |
意思呢,大概就是說可以用 intrinsics 實現 AES-NI 的 Instruction Set。
之後就找到了 wmmintrin.h
( intrinsics of AES-NI ) 的 Document,來看看 Source Code:
有我們一直在找的 clmul
,然後依照他給的的文件進行實作。
_mm_clmulepi64_si128
這個指令
only looks at the least significant bit of each
example code :
在執行時我們遇到一個問題,將 a, b 宣告成 __m128i 但是卻得到錯誤訊息,
然後發現我不小心把 .c 檔打成 .cpp (眼神死)。
改回 .c 檔出現以下錯誤訊息,
查了一下發現 gcc 會直接把 __m128i 當成 long[2],所以不支援.m128i_i64[1]
這類的 function ,所以手動改成 a[1] = 2
。
又得到以下錯誤,
補上編譯選項之後,
砍掉 -m32 的編譯選項後,
將 product 從 int 改成 int8_t 仍不能解決問題, 最後將第三個參數直接放 0x00
才可以跑。
以下是最後可以跑的版本
為了得知 _mm_clmulepi64_si128
在效能上的提升,我們設計了以下實驗:
我們把以上兩個版本分別進行 100 次的運算,計算出來平均值的繪圖如下:
可見有使用 Instruction Set ( AES-NI ) 實作的 clmul 比原來的程式效能提升有超過十倍之多。
在實驗的準確性方面,我們使用了 assert
來進行驗證。
我們對 _mm_clmulepi64_si128
的四種情況各進行了驗證,以確定實驗得出的答案一致。
可是我們遇到了一個問題,就是
_mm_clmulepi64_si128
會返回 128-bit,但我們實作的 cl_mul 只能做到返回 64-bit,若改為用數組作儲存方式的話時間會大大增加,所以我們只有作_mm_clmulepi64_si128
的後 64-bit 直接與 cl_mul 的 64-bit 作比對。
laochanlam
接下來為了實驗指令 _mm_clmulepi64_si128(a, b, product)
是否在效能上達到 const time ,設計了以下實驗:
因為無進位乘法需要的參數有 a, b 兩個,所以以下分成幾個狀況
laochanlam
程式碼:
由以上實驗可得出結論 _mm_clmulepi64_si128
的指令為 Const Time。
ECC
Galois Fields
carryless multiplication
AES-NI
AES-NI
_mm_clmulepi64_si128
指令