我的電子情人夢(28) ：終極密碼戰 – 橢圓的數學之美
在密碼學史上，二次大戰神出鬼沒德國U型潛艇使用的Enigma密碼機，很有名氣。以Enigma為背景的電影也不少，好比說，《獵殺U-571》、《攔截密碼戰》、《模仿遊戲》都是很好看的影片。
戰爭‧日常網路生活，尤其，疫情帶來”遠距工作”的新型態，都與密碼脫離不了關係。而”密碼學”領域相關的知識，又與”數學”知識息息相關。不喜歡數學的人，難免有催眠的作用。
手機真是方便易用，凡間眾生幾乎天天需要它。可是，有一個疑問存在，手機的安全性真的安枕無慮嗎？
手機內部處理器晶片的霸主高通(Qualcomm)，使用率很高。而安全性專業公司Check Point卻給出了一項資訊，喚起眾人的留意；指出高通的系統晶片平台Snapdragon，發現到400多個脆弱性(漏洞)。這些漏洞來自於擔當音頻、視訊以及充電的數位處理器。
攻撃者可以利用這些漏洞即可獵取照片、視訊、通話記錄、即時麥克風資訊、GPS和位置數據。也可以使的所有儲存的資料永久不可用，或完全隱藏惡意軟體和惡意程式碼，使其無法刪除。
提醒閣下，安全性的議題，如同小心匪諜、人人有責。
而當前的主力密碼學 – “橢圓曲線密碼學”。
由於”數位資產”的重要性越來越高，密碼學的知識有朝一日，會像藍芽、Wi-Fi、USB、HDMI等技術名詞逐步轉化為普通名詞。
區塊鏈的運作底蘊是”分散式網路”，特色在於”去中心化”、”公開帳本共同維護”、”具有時間戳(timestamp)”、”防止竄改”、”自行解決交易衝突”等特徵。若是應用面向與這些特色沒有迎合，區塊鏈就不會是一個解決問題的好方案。加密貨幣的需求與區塊鏈屬性完全匹配，所以，比特幣就成為第一個落地應用。
世紀藏鏡人「中本聰(Satoshi Nakamoto)」巧妙結合密碼學、資訊技術、貨幣學和網路結構，設計了比特幣。區塊鏈讓加密貨幣交易不可竄改，可以被信任的機制出現，就能夠實現價值交換。
區塊鏈再怎麼厲害不過是一個解決問題的好工具，卻不是包山包海的萬靈丹。很多有世上現實解的問題，無須殺雞用牛刀。天下事不是樣樣可以去中心化。最怕的是無良商人借題藉機的炒作甚至欺詐，對社會毫無助益。技術不是問題，問題在人性；天主教七宗罪 - 傲慢、貪婪、色慾、嫉妒、暴食、憤怒及怠惰，在Internet上似乎可以印證。
區塊鏈一言以蔽之，就是「以哈希函數( hash function) 串接資料」。而哈希函數是基礎密碼演算法。所以說，區塊鏈運作基礎正是”密碼學”。 不知道密碼學，焉能理解區塊鏈呢？
而當代密碼學橢圓曲線加密演算法ECC(Elliptic Curve Cryptography)，係基於橢圓曲線數學理論來實現的一種”非對稱加密”演算法。 以下嘗試對資料通信的密碼學，從古典加密到當代加密交代出一個完整又明確的梗概。
密碼學(Cryptography)，可以說是網路社會現代公民的必要知識。依據美國金融犯罪調查局的資訊，加密犯罪激增，再度說明了加密知識認知上的重要。
在地球上再怎麼厲害的加密方法之數學演算式，總有更厲害的絕頂高手會竄出來。許多專家擔心，當代密碼學開端的RSA和Diffie-Hellman背後的數學演算法很有可能會在幾年內被駭客所破解，而目前看來，橢圓曲線加密演算法ECC是當前唯一合理的最佳選擇。
所有當代的瀏覽器(browser)均支援橢圓曲線加密，大多數認證機構也都提供了橢圓曲線加密證書。歐盟網路和資訊保安局就非常小心密碼學的發展。
在密碼學領域，往往會看見一些很特異的名詞與觀念，這是踏向密碼學的基礎功夫。
密碼學，簡單扼要來說，有三個普遍的領域：
. 串流密碼(Stream Ciphers)。
. 區塊密碼(Block Ciphers)。
. 公鑰密碼學(Public Key Cryptography)。
先從”密語‧密碼(Ciphers)”來說起。密碼，乃是密碼學的基石。密碼，是對訊息執行加密或解密的一組演算法。
加密演算法(E)取得密鑰(k)和訊息(m)，並產生密文(c)。反之，解密演算法(D)採用密鑰(k)和先前得到的密文(c)來求得訊息。 簡單表示如下：
E(k,m) = c ：加密。
D(k,c) = m ：解密。
換句話說；
D(k, E(k,m)) = m
這意味著，如果您使用密鑰k加密訊息，也可以透過使用k的解密來獲得完全相同的訊息。
凱撒密碼是最古老、最簡單的密碼之一，這是一種替換加密的技術，明文中的字母都會向後(或向前)按照一個固定數目進行偏移，替換成密文。比如說：
明文字母表：ABCDEFGHIJKLMNOPQRSTUVWXYZ
密文字母表：DEFGHIJKLMNOPQRSTUVWXYZABC
當偏移量是左移3的時候，解密時的密鑰就是3。若是透過了以下的數學式就可以導出：
En(k,m) = m + k MOD 26
Dn(k,c) = c – k MOD 26
若是再深入一點更安全的加密演算法，可討論”XOR”(互斥或)的運算符。數學上有幾個重要的屬性可適用於XOR。
a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c
a ⊕ a = 0
a ⊕ 0 = a
由此，可以推導出a ⊕ b ⊕ a = b。
請留意，這種方式僅適用於1和0，因此必須首先將不同基數的數字轉換為二進制。比如說：
87 ⊕ 73 = 1010111b ⊕ 1001001b = 0011110b = 30
現在來探討第一個安全密碼 - 一次性密碼本(one-time pad)。這是古典密碼學中的一種加密演算法，在1882年由Frank Miller所提出。動作原理是對訊息和私鑰執行XOR的動作，然後對私鑰和密文使用XOR重新獲得訊息。
這是基於上述 a ⊕ b ⊕ a = b屬性來完成此操作的。定義一次性密碼本的一對演算法可以表示如下：
c = E(k,m) = k ⊕ m
D(k,c) = k ⊕ c
這對密碼的一致性方程式，可以容易地證明如下：
D(k, E(k,m))
= D(k, k ⊕ m)
= k ⊕( k ⊕ m)
= (k ⊕ k) ⊕ m
= 0 ⊕ m
= m
一次性密碼本有效且易於使用，但它們也有許多缺點。比如說，假設有兩個訊息m1和m2，我們都將使用相同的密鑰k對其進行加密。兩個密文最終會XOR在一起。
c1 = m1 ⊕ k
c2 = m2 ⊕ k
c1 ⊕ c2 = m1 ⊕ k ⊕ m2 ⊕ k = (k ⊕ k) ⊕ m1 ⊕ m2 = 0 ⊕ m1 ⊕ m2
= m1 ⊕ m2
如此一來，攻擊者可以對結果文本(明文)進行各種形式的分析，例如統計分析，頻率分析，模式匹配或使用自然語言方法等來破解。
其次，來談”串流密碼”(Stream Ciphers)。
一次性密碼的密鑰長度必須等於或大於本文長度，縱然完全保密，實用性卻是受到限制。串流密碼背後的關鍵概念是用“偽隨機”密鑰替換一次性密碼簿中的“隨機”密鑰，這意味著訊息將與由加密安全偽隨機數字生成器CSPRNG產生的密鑰進行XOR。
注：CSPRNG = Cryptographically Secure Pseudo-random number generator。
CSPRNG僅是產生大量數字序列的演算法(或函數)，近似隨機數的性質。由於很難產生隨機數，因此CSPRNG依靠種子(seed)來確定起始狀態以及將來產生的隨機數。它允許從相對較小的起始種子來產生不成比例的大量隨機數；比如說，128位元種子，產生了千兆位元組的隨機資料。
CSPRNG是確定性的。因此，產生數字的隨機性限制取決於起始種子的隨機性。它的數學式呈現是將k用G(K)來表示：
c = E(k,m) = k ⊕ g(k)
D(k,c) = c ⊕ g(k)
串流密碼由於訊息加密的密鑰長度較短，實用性提高。不過，它也有其脆弱性。比如說，兩個最為典型的案例：
案例一：無線網路802.11b WEP：
WEP是用於WiFi加密數據的演算法，稱為RC4的串流密碼。由於同一密鑰不能在流密碼中多次使用，長期密鑰與初始向量值“ IV”(initialization vector)連接，該值每次都會變更。但是，“ IV”只有24位元長，這意味著在對5000條訊息進行加密之後，將有50％的機會使用相同的密鑰。
案例二：CSS( Content Scramble System)：
CSS使用於加密DVD，CSS使用了一個40位元的密鑰，由於系統的密鑰空間較小，因此可以相對較快地進行暴力式破解。儘管密鑰是40位元長度，由於CSPRNG的特性，僅產生17位元組合之後，系統便可能被破解。
其次，來談”區塊密碼”(Block Ciphers)。
區塊密碼，係由兩種演算法E加密和D解密所組成，它們均採用密鑰K。
區塊密碼的要點是輸入文本(明文)的長度和結果密文始終是相等的固定量。此數量稱為“區塊大小”，取決於所使用的區塊密碼。密鑰長度也是固定量，稱為” 密鑰大小”。
兩種常見的代表性區塊密碼是：
*. 3DES(Data Encryption Standard)：64位元區塊和168位元密鑰。DES於1970年代IBM所開發，爾後由三重資料加密演算法3DES所取代。
*. AES(Advanced Encryption Standard)：128位元區塊和128、192或256位元密鑰。
注：DES(Data Encryption Standard)，在1976年被確定為聯邦標準，它基於使用56位金鑰的對稱演算法。DES往往被稱為對加密演算法的非軍用研究和發展的開始。後來被AES所取代。
AES和大多數其他區塊密碼透過迭代或說反覆(iteration)方式來動作，其中輸入文本(明文)將使用一系列密鑰進行迭代加密。
第一步驟是將私鑰K作為輸入，通常為128、192或256位元；在此以128位元為例來擴展為一系列用於加密訊息的”回合密鑰”(Round Keys)。
採用128位元(16位元組)輸入密鑰K，透過密鑰擴展功能為”11”個獨立的16位元組密鑰。AES使用這些密鑰將訊息通過10個單獨的回合函數R(kₙ, m)加密10次；回合函數使用kₙ和訊息m作為輸入。
由於AES動作於128位元區塊，可以將輸入訊息m表示為一個1位元組單元的4x4矩陣。每個回合密鑰(Round Key)也表示為4x4矩陣，如此可以與訊息狀態的單元進行XOR運算。
首先，輸入訊息與第一個回合密鑰進行XOR運算，然後將結果訊息通過了 ”ByteSub”， ”ShiftRows”和”MixColumns”函數傳遞，以更新訊息的狀態。然後，將這些步驟重複10次，而最後一回沒有MixColumn步驟。最終狀態與第十回密鑰XOR產生輸出。
這裡有”ByteSub”， ”ShiftRows”和”MixColumns”函數，需要解釋。
先來解釋”ByteSub”。也就是依照替換盒(Substitution-box；簡稱S-box)或稱S盒，將訊息狀態矩陣中的每個位元組都被其對應的位元組所替換。
AES的S盒如下圖：
比如說，位元組9a將替換為b8。
而”ShiftRows” 是說每一列移動一定量。第一列不移位，第二列向左移一次，第三列左移兩次，第四列左移三次。解釋如下圖：
”MixColumns”，對於訊息狀態矩陣的每一行進行線性轉換；如下圖：
至此，相信閣下可以看出AES加密的限制；它不能一次加密超過128位元的訊息。若要加密超越16位元組，就要引入一種稱為操作模式的概念。有很多種方式，最為簡易的該是”電子密碼本ECB(Electronic Codebook)”。
ECB將訊息分為16位元組區塊，並使用私鑰分別對每個區塊進行加密。為了使文本(明文)與16位元組邊界對齊，可能必須填充明文。比如說，一個28位元組文本就要添加四個位元組，來構成兩個16位元組區塊。當訊息劃分為多個區塊之後，每個區塊都使用密鑰分別進行加密。
EOB有個明顯的缺點，相同的明文區塊將會產生出相同的密文區塊，一致性資訊領域加密後仍然會相同，那麼，模式很容易被看出來。比如：以下是以ECB模式加密的影像；很輕易可以推斷出原始影像，沒有發揮加密的效用。
於是，再介紹與ECB的工作原理非常相似的CBC(Cipher Block Chaining)方式。在加密每個明文區塊之前，先將其與區塊前面的密文進行XOR，使每個明文區塊具有唯一性，對於第一個區塊，則是將明文與隨機產生的初始向量(Initialisation Vector)進行XOR。
注：在密碼學領域，初始向量(initialization vector)就是初始變數，簡稱IV；係一個固定長度的輸入值。一般的使用上會採用隨機數。
以下是以CBC模式加密的影像，結果就是發揮了加密的效用。
基礎的密碼學就談到這兒，下一段將進入當代最為重要的”公鑰加密”(Public Key Cryptography)的領域。
傳說有人戲稱”公鑰加密”，乃是網際網路的三大發明呢。
大致上，基本密碼學，有兩類加解密方式：
1. 對稱式加密(Symmetric Encryption) 。比如，DES (Data Encryption Standard) ；AES (Advanced Encryption Standard)。
2. 非對稱式加密(Asymmetric Encryption)。比如，RSA (Rivest – Shamir – Adleman 1977)；ECC (Elliptic Curve Cryptosystem)橢圓曲線密碼系統。
對稱式加密，意思是說傳送方與接收方的加密與解密都是使用了同一密鑰，運作的原理如下圖所示：
上面所討論加密方式多是歸屬於對稱式加密。
非對稱式加密，每個使用者都會擁有一對金鑰：公開金鑰(Public key)以及私密金鑰(Private key)。
通常是公鑰加密、私鑰解密。
公鑰密碼通常用於加密伺服器或機器之間的通信，送收電子郵件和網路瀏覽。運作原理如下圖所示：
非對稱式加密技術解決了部分竊聽者問題，示意圖如下：
請注意，這裡還存在著一個問題。由於公開金鑰能夠被發佈與流傳，私密金鑰則須要妥善保存。因此，接收方要如何來確認訊息真的是由傳送方所傳來的呢？攻擊者可能會偷取某一方的公鑰而送出私自的公鑰，造成了假訊息脆弱性的風險。如下圖所示：
所以，才會需要”數位簽章”(Digital Signature)或是”證書頒發機構”(Certificate Authorities)的方式。
”數位簽章”(Digital Signature)的二次確認方式，會加入了簽章(sign)以及驗章(verify)的流程。
為了能夠更清楚了解數位簽章，下圖範例該是可以給出更為詳細的流程解釋：
密碼學家將這個領域區劃分為”古典加密”以及”當代加密”兩大流派，而其中的轉折點就在於1977/1978年代推出的”RSA演算法”和”Diffie-Hellman密鑰交換演算法”。無妨說也就是兩大流派的分水嶺。
注：RSA加密算法是很常用的非對稱加密算法；以三個發明者Ron Rivest、Adi Shamir、Leonard Adleman的名字命名。RSA的安全性，係基於大數分解的難度。
注：Diffie-Hellman key exchange (exponential key exchange)，簡稱為D-H；1976發表。係用於金鑰的交換，並非用於加密解密。主要目的是讓未曾見面的雙方，可以經由模指數(modulo)運算，使得雙方可以獲得相同的對談金鑰(session key)。
使用很廣泛的系統之一，該是RSA。無論是認識D-H金鑰交換還是RSA演算法會涉及到很深很廣的數學知識。比如說，要清楚甚麼是”質數”？甚麼是”互質數”？
質數(prime)，只能被 1或自己整除的數。好比說，介於1~ 100之間的質數有：
“2, 3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97”
一個大於 1的整數，除了 1和它自己以外，還有別的因數時，就稱為「合數(composite number)」。
而大於1的任意數，可以被分解成多個質數的乘積。好比說：
3600 = 24×32×52 (2的四次方乘上3的 二次方 乘上5的二次方)
gcd(a, b)，表示了 a 和 b 的最大公因素。如果gcd(a b) =1，表示a與b 互質(co-prime)。
「互質數」，是指兩個或多個數之間的關係。質數之間肯定是互質數，而合數之間也可能是互質數(比如說，4與9)。
先來解釋”Diffie-Hellman密鑰交換演算法”。請參照下圖：
步驟1：質數p、g可以用明文傳送，是公開的；就算被第三方知道了也沒關係。
步驟2：使用者A產生成一個隨機數Xa。這個隨機數不能讓任何人知道，連使用者B也不必知道。
步驟3：使用者B產生成一個隨機數Xb。這個隨機數不能讓任何人知道，連使用者A也不必知道。
步驟4：使用者A將gXa(mod p)傳給使用者B。
步驟5：使用者B將gXb(mod p)傳給使用者A。
使用者A現在有p,g,Xa, gXb(mod p) 這四個值
使用者B現在有p,g,Xb, gXa(mod p) 這四個值
步驟6：使用者A將 (gXb mod p)Xa mod p的值計算出來。
(gXb mod p)Xa mod p 可以簡化為 (gXbXa mod p)
步驟7：使用者B將(gXa mod p)Xb mod p的值計算出來。
(gXa mod p)Xb mod p 可以簡化為 (gXaXb mod p)
相信閣下可以發現，使用者A與使用者B所計算出來的值，其實都是一樣的。這也就是兩者之間所產出出來用於加密對話的”對稱式金鑰”是也。
以下就嚐試來解釋”RSA演算法”。
步驟1：選兩個大質數 p 和 q ，令 N = p • q
步驟2：再計算Ø(N)=(p-1)(q-1)，並選一個與Ø(N)互質數 e。
Ø(N)為Euler’s Totient函數，其意為與N互質之個數。
步驟3：(e,N) 即為”公開金鑰”。
加密法為 C = Me mod N
步驟4：選一個數 d，滿足 e • d mod Ø(N) = 1
步驟5：d 即為”私密金鑰”。
解密法為 M = Cd mod N
根據上述，RSA演算的安全性，就取決於”質因數分解之困難度”。要將很大的N因數分解成P跟Q的乘積，是非常困難的。
注：費瑪(Fermat)定理：若p為質數且(a,p)互質，則 ap-1 mod p = 1。
注：Euler定理：若a，n互質，則 aØ(n) mod n = 1。
注：尤拉函數：Ø(P) = P-1 若P為質數；Ø(N) = Ø(PQ)= Ø(P)Ø(Q)= (P-1)(Q-1)。
以下是”RSA演算法”的一個範例。
1. 接收方選 p = 3，q = 11 ; N = p • q = 33。
2. 找出一個與(p-1) x( q-1) = (3-1)(11-1) = 2 x 10 = 20互質數 e = 3。
3. (e, N) = (3,33)，為接收方的公開金鑰。
4. 接收方選一個數 d = 7 作為解密金鑰，
滿足 e • d mod 20 =1 ( 7 x 3 mod 20 = 1 )
那麼，令明文 M = 19
加密 : C = Me mod N = 193 mod 33 = 28
解密 : M = Cd mod N = 287 mod 33 = 19
那要如何來驗證RSA密碼系統的正確性呢？
C = E(M) = Me mod n M = D(C) = Cd mod n
Cd = (Me)d = Med mod n ； 因 ed = 1 mod (p-1)(q-1)
故 Med = Ma(p-1)(q-1)+1 = MMa(p-1)(q-1) = MMaφ(n) mod n
根據尤拉定理，得到
M × 1 = M
注：暗門函數(Trapdoor Function)，是說，易在一個方向上計算，但是很難在相反的方向上計算。廣泛用於密碼學。
RSA隨著可用於解密數字的資源增加，密鑰的大小需要更快地增長。對於運算能力有限的移動和低功率裝置來說，這就不算是很好的方案了。
理想的暗門函數，相對於所討論數字的大小，簡單方法和困難方法以相同的速度變得越來越困難。隨著時代的需求，我們需要基於更好暗門函數的公鑰系統。
於是乎研究者接著下來，探索”橢圓曲線加密演算法” - ECC(Elliptic Curve Cryptography)。
ECC，係基於橢圓曲線數學理論來實現的一種非對稱加密演算法。相比於RSA，ECC的優勢是可以使用更短的金鑰，來實現安全性相當或是更高的安全性。依據研究，228位ECC加密安全性就相當於2380位RSA加密呢。也就是說，在同等位的加密情況下，橢圓曲線密碼系統更難破解。
況且，RSA加密在未來幾年，被破解的機率還不小呢。
也許要先從橢圓曲線的數學性質來說起了。
話說，數學家研究橢圓曲線豐富而深入的理論超過150多年了。直到了1985年，基於數學的一個深奧分支橢圓曲線提出了密碼算法。
橢圓曲線是滿足兩個變數方程式的一組點，變數之一為二次方，另一個變數為三次方。
比如說：
y2 = x3 + ax + b (y的二次方, x的三次方)
其圖形如下(可以看出就不像橢圓形喔)：
橢圓曲線不單是漂亮的圖形， 它還具有一些很有趣的屬性，使其能成為加密的良好設定。
若是來仔細觀察橢圓曲線，可發現它具有幾個有趣的屬性 – 『奇異的對稱性』。
其中之一的特性，就是”水平對稱”， 曲線上的任何點都可以在x軸上反射並保持相同的曲線。如下圖：
另一個更有趣的特性是，任何非垂直線最多將在三個地方與曲線相交。
橢圓曲線加密現在已用於多種應用中，比如說：美國政府使用來保護內部通訊、Tor項目使用它來確保匿名性、用於證明比特幣的所有權、在Apple的iMessage服務中提供簽名、DNSCurve加密DNS訊息、SSL / TLS進行安全Web瀏覽的身份驗證的首選方法等。
接著下來，先來看一看橢圓曲線的運算規則。
*. 加法運算
透過曲線上的兩點A、B來畫一條直線，找到直線與橢圓曲線的交點。將交點對稱於x軸位置的點，定義為A+ B，這就是加法運算。如下圖：
當A=B時，呈現切線，就是以下的二倍運算。
*. 二倍運算
當兩點重合的情況下，將橢圓曲線在A點的切線，與橢圓曲線的交點，將交點對稱於x軸位置的點，定義為2A，也就是二倍運算。如下圖：
注：請留意以下兩個用詞的差異：相同點相加(point doubling)；相異點相加(point addition)。
*. 正負取反運算
若是將A點對稱於x軸位置的點定義為 -A，這就是橢圓曲線的正負取反運算。如果將A與 -A相加，通過A與 -A的直線會平行於y軸，可以認為直線與橢圓曲線相交於無窮遠點處。如下圖所示：
有了以上這些定義的運算概念之後，當給定橢圓曲線的某一點G，可以求出2G、3G、4G……。換句話說，當給定G點時，已知x，求xG點並不是困難。反之，若已知xG點，要反向求x就非常困難了。
這就是橢圓曲線加密演算法的基礎數學原理。
更精確地說，這是橢圓曲線密碼中所利用的“橢圓曲線上的離散對數問題”。
再來，另一個很重要的觀念。橢圓曲線加密演算法，並非使用了”實數域”，而是使用『有限域(finite field)』。
有限域GF(p)，是指定了某個質數p，由0、1、2……p-1共p個元素所組成的集合中定義之加減乘除運算。這個運算使用的是”取模運算”。
注：取模運算(modulo或是也稱為modulus)，得到的是一個數除以另一個數的餘數。比如說，有兩個正整數，被除數 a 和除數 n，a modulo n可以寫為 a mod n。得到的是 a/n 的餘數。
比如說，假設橢圓曲線為y² = x³+ x + 1，在實數域上它是一條曲線，但是在有限域GF(23)上時，則是寫為：
y² ≡ x³+ x + 1(mod 23)
這是表示”左側與右側的結果除以23的餘數是相等的”。
注：同餘運算概念，當兩個整數除以同一個正整數，若得相同餘數，則這二整數稱為”同餘”( congruence modulo)。
於是乎，在有限域GF(23)上它的影象並不是一條光滑的數學曲線，而是一些離散的點；也就是一些不連續的點。如下圖所示：
以點(1,7)為例，7² ≡ 1³+ 1+ 1 (mod 23) = 3。
請留意還有以下這些點，而且是呈現對稱於x軸：
(0,1) (0,22)
(1,7) (1,16)
(3,10) (3,13)
(4,0)
(5,4) (5,19)
(6,4) (6,19)
(7,11) (7,12)
(9,7) (9,16)
(11,3) (11,20)
這說明了若P(x,y)為橢圓曲線上的點，則 -P，亦即(x,-y)也是橢圓曲線上的點。比如說，點P(0,1)，-P = (0,-1) = (0,22)，也是橢圓曲線上的點。
接著，來談計算xG的方法。當然，必須有一個相關的公式。
有限域GF(p)上的橢圓曲線y² = x³ + ax + b，若P(Xp, Yp), Q(Xq, Yq)，而且P≠-Q，則R(Xr,Yr) = P + Q 係由以下的規則來確定：
Xr = (λ²–Xp–Xq) mod p
Yr = (λ(Xp–Xr)–Yp) mod p
其中
λ = (Yq – Yp)/(Xq – Xp) mod p（若P≠Q）,
λ = (3Xp² + a)/2Yp mod p（若P = Q）
也就是說，當P ≠ Q時，兩點縱坐標相減的值與橫坐標相減的值就是直線的斜率。當P = Q時，計算通過P(Q)點切線的斜率，亦即橢圓曲線公式兩邊求導數然後相除。
因此，仍然以上述有限域GF(23)上的橢圓曲線y² ≡ x³ + x + 1 (mod 23)為例，假設以(0,1)為G點，那麼計算2G、3G、4G...xG的方法如下：
*. 計算2G(G + G)：
因為P = Q，所以：
λ = (3x0² + 1)/2x1 mod 23 = (1/2) mod 23 = 12 ；分數取模運算。
Xr = (12² - 0 - 0) mod 23 = 6
Yr = (12(0 - 6) - 1) mod 23 = 19 ；負數取模運算。
因此，2G為點(6,19)。
這裡有兩道難題喔，就是分數與負數的取模運算。
分數取模運算，怎麼辦呢？ 比如， 1/m mod n = ？ 的解題有兩個步驟：
之一，找到一整數p，使1/m + p = (1+pm)/m，(1+pm) mod n =0，也就是(1+pm)是n的倍數。
之二，轉化問題。1/m ≡ -p mod n ≡ (n-p) mod n
1/m mod n = (n –p)
以(1/2) mod 23為例來說， (1/2 + x) =(1 +2x)/2；當x=11時， (1 +2x) mod 23 = 0
轉化問題 1/2 ≡ -11 mod 23 ≡ (23-11) mod 23 = 12 mod 23
1/2 mod 23 =12
還有一個負數的取模運算的問題呢？
-73 mod 23
- -73 mod 23 = -4
- -73 mod 23 = -14 +23 =19
*. 計算3G：(G + 2G) 就是(0,1) + (6,19)
因為P ≠ Q，所以：
λ = (19 - 1)/(6 - 0) mod 23 = 3
* Xr = (3² - 0 - 6) mod 23 = 3
* Yr = (3(0 - 3) - 1) mod 23 = 13
即3G為點(3, 13)
只要依據上述同樣的原理，就可以計算出4G、5G…xG的分佈圖了；如下圖：
談到此處，我們就可以切入橢圓曲線加解密的演算法原理。
若要建立基於橢圓曲線加密機制，就需要找到有如上述RSA質因子分解的難題
。而橢圓曲線加密則是離散對數問題。
上面已經提到，橢圓曲線上已知G點和xG，若是要求得x是極為困難的，這就是橢圓曲線上的的離散對數問題。
請留意；此處x乃為私鑰，xG則為公鑰。
接下來，來探索橢圓曲線的加密演算法原理。
假定私鑰、公鑰分別為k、K，即K = kG，其中G就是G點。
公鑰加密：
選擇隨機數r，將要傳送的訊息M產生為加密文C，加密文乃是一個點對，亦即：
C = {rG, M rK}，其中K為公鑰
私鑰解密：
M rK –k(rG) = M r(kG) –k(rG) = M
其中k為私鑰、K為公鑰。
橢圓曲線簽章演算法，稱之為ECDSA(Elliptic Curve Digital Signature Algorithm)。這也是比特幣、以太坊區塊鏈所使用的。讓貨幣持有者透過私鑰對資訊進行簽章，而讓所有人使用公鑰來進行驗證。
注：ECDSA成為ANSI標準，也後續成為IEEE和NIST標準。
注：NIST = National Institute of Standards and Technology 。
ECDSA 使用了特殊規範的橢圓曲線，總是可以同時找到 P、Q、R 三個點，並且這三個點又符合阿貝爾群(Abelian group)；這是可交換群，滿足其元素的運算不依賴於它們的次序。
注：阿貝爾群(Abelian group)，也稱之爲可交換群(commutative group)，它是滿足其元素的運算，不會依賴於它們的次序關係。
ECDSA 演算法當中，會產生一次性使用的臨時簽名變數/臨時密鑰(Ephemeral Key)；如果每次在進行簽章時都使用了相同的值，一旦這個值遭到洩漏，私鑰有機會被回推計算出來。這就是為何” RFC6979 提案”有較佳的值選法。昔日Sony PS3就是每次都使用了相同的值，導致遊戲機被高手所破解。
與RSA相比，ECDSA數位簽章有一個缺點，因為它需要良好的”熵(entropy)”源。任何一套加密系統需要一組金鑰以及一組輸入的資料流。用以編排密碼的、「或多或少隨機」的位元流，被稱做是Entropy (熵)輸入。
如果沒有適當的隨機性，則可能會洩露私鑰。安卓(Android)上的隨機數產生器就存在著漏洞，駭客在2013年初就找到用於保護幾個人的比特幣錢包的ECDSA私鑰。PS3的情形也是如此。
因此，進行簽章的機器上需要有一個很好的”隨機數產生源”。
ECDSA 演算法。
假定私鑰、公鑰分別為k、K，即K = kG的特性，其中G就是G點。
透過橢圓曲線、私鑰來進行簽章：
1、選擇隨機數r以及基點G，求出點rG(x, y)。
2、根據隨機數r、要傳送訊息的哈希Hash(M) = h、私鑰k，計算s = (h + kx)/r。
3、將訊息M、和簽章{rG, s}傳送給接收方。
透過橢圓曲線、公鑰來進行驗章：
1、接收方收到訊息M、以及簽章 {rG = (x,y), s} (也就是點 rG 和 s)。
2、根據訊息求得哈希h。
3、使用傳送方公鑰K計算：hG/s + xK/s，並與rG比較，如果相等就是驗章成功；否則說明是錯誤的數位簽章。。
原理的驗證如下：
hG/s + xK/s = hG/s + x(kG)/s = (h + xk)G/s = r(h + xk)G / (h+ kx) = rG
私鑰，非常重要 ! 非常重要 ! 私鑰，必須具有徹底的“保密性”與保證的“唯一性”。
底下，就再次以比特幣交易圖，來強調出私鑰的重要性。
總之，要確保私鑰不會遭人破解，那麼一定要選用符合 RFC6979 提案的值選定。
那麼，接下來就得來談甚麼又是” RFC6979提案”？
RFC6979提案要面對的是密碼學，不單是比特幣而已，而是需要考慮到更多的曲線、更多的參數、更多演算法等。
注：RFC是” Request for Comments”的縮寫，係由開放性標準組織IETF(Internet Engineering Task Force)所發佈的一系列備忘錄。
在原始的ECDSA概念中，每個簽章需要256位元的隨機資訊。這樣會帶來了一個問題，因為當您使用相同的隨機輸入對兩條不同的訊息(比如說，比特幣交易)進行簽章時，可能會洩漏了您至關重要的私鑰。
所以，RFC6979提案建議使用”HMAC-SHA256(私鑰，訊息)”的輸出來代替隨機資訊，從而消除了這種風險。
以下先來看一個相對簡單的式子：
r = SHA256(k + HASH(m)) ；其中，k是私鑰，m是訊息。
一般會對訊息進行哈希。
請留意，這個簡單公式參數裡有私鑰k，這就保證了“保密性”。再加上了訊息m的哈希，則是保證了“唯一性”。
這就是隸屬於“確定性”的演算法，只要SHA256是安全的，演算法就安全。所以，RFC6979提案的原文主題是：
“Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA)。”
請留意，這段文字裡強調的”確定性”使用法。
那甚麼又是HMAC - SHA256 加密方式呢？
HMAC ，乃是”Hash-based message authentication code”的簡稱，無妨翻譯為密鑰哈希訊息鑑別碼。
HMAC - SHA256簡單說，就是是一種密鑰哈希演算法的類型。它是從 SHA-256 哈希函式所建立，並作為哈希型的訊息驗證碼HMAC來使用。
HMAC 的處理會將秘鑰與訊息資料相混合，使用哈希函式來得出結果；再混用該哈希值與密鑰，然後再套用哈希函式一次。輸出哈希的長度為256位元。
最後，作個扼要的整理。
橢圓曲線密碼ECC，它隸屬於公鑰密碼體制，可以提供與RSA密碼體制相同的功能，它的安全性基礎是建立在橢圓曲線離散對數問題的困難性之上。RSA密碼則是基於大整數因子分解困難性之上。
其實，在國際上研究且公認比較安全的公鑰密碼，也要提一下1985年提出的ElGamal加密演算法，係基於Diffie-Hellman密鑰交換的非對稱加密算法。ElGamal加密，通常應用在混合性加密系統中。比說，用對稱加密來加密訊息，然後，利用ElGamal加密演算法來傳遞密鑰。
行文至此，該來說點結語了。
區塊鏈成為信任機制，基礎在於「不可竄改之性質」。而區塊鏈邁向攜帶式裝置的應用時，ECC似乎提供了更好的權衡：使用”短而快速”的密鑰提供高安全性。
區塊鏈終究是解決問題的一種工具，但絕非是包山包海的萬靈丹。品德與才華，基本上是不相關的。”幣圈”的黑暗史何其的多，2019/12發現名為StrandHogg的危險Android漏洞，可讓駭客竊取加密錢包資訊。也就是說，數位資產的安全性大有疑慮。
比如說，名為維卡幣( OneCoin) 的加密貨幣，打著響亮稱號、高學歷白領階級參與，以多層次傳銷手法包裝，乃標準的『龐氏騙局』。2019/11以太坊研究科學家Virgil Griffith被控涉嫌協助北韓用加密貨幣規避制裁，在美遭逮捕。人性並不善。
密碼學畢竟是中性的技術，若是落在壞蛋的手裡，就會造出惡意的傷害。比如說，勒索軟體”LooCipher”透過了Microsoft Word的檔案(DOC形式)來將中毒者電腦的所有檔案加密，並勒索被害者得支付比特幣。
密碼學歷史上還有一種稱之為”中間相遇攻擊”(meet-in-the-middle attack)；這是一種以空間換取時間的攻擊；於1977年提出來。
網路犯罪分子和安全性分析師之間的貓捉老鼠遊戲永遠不會停止，也部會永久消失。網路犯罪分子試圖隱藏他們的惡意軟體，並逃脫避免專門設計的安全性機制。通常，壞蛋會利用安全軟體的固有漏洞來如此做或是建立掩蓋真實惡意程式碼的長攻擊鏈。在這場不斷輪迴的遊戲中，每個惡意軟體的更高功力提升都會督促來提高安全性，反之亦然。因此，除了要不停地更新自己腦袋的知識與網上行為的謹慎，我實在想不出來有甚麼一刀永逸的方法。
在這裡也不提不提到一件影響到密碼學的新技術，那就是量子電腦。量子運算始終是科技產業熱議話題，與AI人工智慧(AI)都被視為新世代科技改革的重要關鍵，全球的科技巨頭都在進行卡位戰，比如，IBM、谷歌、微軟、富士通、NEC等在爭奪所謂的”量子霸權”(quantum supremacy)。
注：量子電腦的動作原理，大致上分為“量子閘”(quantum gate)以及” “量子退火”(quantum annealing)的方法。富士通就開發模擬量子運算的數位退火(digital annealing)晶片 – DAU(Digital Annealing Unit)。
注：量子退火方式，係1998年由東京工業大學的西森秀敏教授和當時的研究生門脇正史所提出的，利用”量子漲落”(quantum fluctuation)的性質，從膨大的眾多選擇中探索出最佳選擇。簡單說，就是一種解決所謂組合優化問題的技術。
你或許會問，那量子電腦與密碼學又有何關係？1982 年提出量子電腦的概念，約1994年數學家建立了演算法。最可怕的是傳統的高階電腦的運算速度在量子電腦面前是超級小兒科，也就是說在極短的時間之內，就有機會破解當代現有的密鑰系統。於是乎，出現了一門新科學，那就是”量子抗性密碼學” (quantum-resistant crypto)。美國國家安全局 NSA 也正在進行開發。IBM則成功地展示了其開發的量子驗證加密方法。
人性永遠不會變好，僅能誠心期待與盼願在安全性上的密碼學技術能夠越來越好。
分享至
成為作者繼續創作的動力吧！
© 2024 vocus All rights reserved.