[BMC][PFR] 橢圓曲線數位簽章算法 Elliptic Curve Digital Signature Algorithm (ECDSA)

Intel 目前推出的Platform Firmware Resiliency (PFR) 方案中，在secure update/boot中的sign image的部分是使用ECDSA來製作的，因此在我們開始分析PFR 使用的update image要怎麼sign 之前，必須先了解什麼是ECDSA

ECDSA 全名是 Elliptic Curve Digital Signature Algorithm，從名字我們就可以知道他是 Elliptic Curve Cryptography(ECC)和 ​Digital Signature Algorithm(DSA)的結合。

因此這篇文章分成三個部分

1. Elliptic Curve Cryptography(ECC)
2. ​Digital Signature Algorithm(DSA)
3. Elliptic Curve Digital Signature Algorithm (ECDSA)

懂了這部分再去看intel PFR 的 Authentication of Data Structure 就會發現沒這麼難

Elliptic Curve Cryptography(ECC)

ECC 是一種基於*有限域上橢圓曲線代數結構的公鑰密碼學方法。 橢圓曲線由滿足方程的點組成： 𝑦^2=𝑥^3+𝑎𝑥+𝑏，適用於密鑰協商、數字簽名、偽隨機生成器等任務。

提到有限域就要先惡補一下抽象代數，畢竟這是精隨

📂抽象代數結構 (Abstract algebraic structures)

我們從開始學數學的時候就常常將數字分組(set)，例如整數、小數、質數、或是常見的雙數、單數，那數學家就有定義如果我們對某個set裡面的數字做*的動作，且這個動作有符合以下條件，這樣我們可以把這個set視為一個group記為(G,*) ,*表示某個特定運算

例如整數做加法運算，我們可以把它視為一個group，因為他在做加法運算的時候有符合以上條件。那如果我們的(G,*)也有符合交換性的話，我們就稱之為阿貝爾群 (Abelian Group)(這個名字的由來只是要紀念阿貝爾這個數學家，他證明了五次方程沒有代數解)

那如果有個set他是一個阿貝爾群(G,*)又有符合另外一個運算(G,+)也是個阿貝爾群，並且具有分配率，這樣我們就稱之為場Field記為(F,+,*)，其中+和*表示某個特定運算 

如果這個場裡面的元素是有限的，就稱之為有限場(finite field)，又稱之伽羅瓦場(Galois field)(這也是要紀念Galois這位數學家，他是群論的創立者，用群論徹底解決了根式求解代數方程的問題)，如果我們的有限場的元素總共有256個，那我們可記為GF(256)

📂實數域上的橢圓曲線

根據Mordell-Weil定理，橢圓曲線上有理點構成的群是有限生成的。另一在Siegel定理中，橢圓曲線上的整數點只有有限多個。

我們這邊直接假設已經有個滿足以上條件的橢圓曲線(F,+,*)，其中+,*的兩個運算定義如下

+:

假設我們有兩個點P和Q，那P+Q表示兩點的連線和橢圓曲線的交點對X軸做映射所得到的點R

*:

如果P和Q都是同一點，那R 就是我們對P曲切線和橢圓曲線的交點對X軸做映射所得到的點R

因此簡單來說，如果4*P就P+P+P+P，所以在ECC中，4就是私鑰，4P求出來的結果就是我們的公鑰。

那通常我們會有個質數P，我們會將求得的點去mod P，最後能建出一個表Table of Point Additions，但因為這個牽扯到太多抽象代數的計算，這邊就不會討論計算過程。

底下的圖是我從https://www.graui.de/code/elliptic2/ 這個網站產生的

假如今天我們初始點G是(3,4)，這樣2*G就是會(3,4)+(3,4)就會是(0,4)，那3*G就會是(3,4)+(0,4) = (2,1)

📂Elliptic Curve Diffie–Hellman key exchange, ECDH

ECDH這個演算法常用在key exchange，在TLS/SSL的協定中，最後client和server會產生一組隨機金鑰，作為訊息加密用的，那ECGH就是用ECC加密法來產生這組隨機密鑰

Alice和Bob 他們的溝通建立在已知的橢圓曲線和起始點G上面

我們發現 "Bob的私鑰*Alice公鑰 = Alice的私鑰*Bob公鑰" 這樣隨機密碼就會產生

那為什麼等號會成立呢? 因為該橢圓曲線是基於finite field，有符合交換性和結合性

那現在有很多表準的橢圓模型可供使用，最常見的就是secp256r1和secp348r1這兩個，256表示p = 256bits，這樣最後我們的公鑰(x,y)就是各用256bits表示

https://neuromancer.sk/std/secg/secp256r1#

https://neuromancer.sk/std/secg/secp384r1#

Digital Signature Algorithm(DSA)

數位簽章演算法（DSA）是用於數位簽章的聯邦資訊處理標準之一，基於模算數和離散對數的複雜度。

簽署:

• 從 ${\displaystyle \{1\ldots q-1\}}$ 隨機選擇整數 ${\displaystyle k}$
• 計算 ${\displaystyle r:=\left(g^{k}{\bmod {\,}}p\right){\bmod {\,}}q}$，當出現 ${\displaystyle r=0}$ 狀況時重新選擇隨機數 ${\displaystyle k}$
• 計算 ${\displaystyle s:=\left(k^{-1}\left(H(m)+xr\right)\right){\bmod {\,}}q}$，當出現 ${\displaystyle s=0}$ 狀況時重新選擇隨機數 ${\displaystyle k}$

產生signature pair(r,s)

驗證:

收到(r,s)和訊息M

• 驗證 ${\displaystyle 0<r<q}$ 且 ${\displaystyle 0<s<q}$
• 計算 ${\displaystyle w:=s^{-1}{\bmod {\,}}q}$
• 計算 ${\displaystyle u_{1}:=H(m)\cdot w\,{\bmod {\,}}q}$
• 計算 ${\displaystyle u_{2}:=r\cdot w\,{\bmod {\,}}q}$
• 計算 ${\displaystyle v:=\left(g^{u_{1}}y^{u_{2}}{\bmod {\,}}p\right){\bmod {\,}}q}$

只有在 ${\displaystyle v=r}$ 時代表簽章是有效的

Elliptic Curve Digital Signature Algorithm (ECDSA)

這邊驗證方式在Elliptic Curve Digital Signature Algorithm講得比較仔細