從公開冪次達成協商
公鑰加密與密鑰協商解決相關但不同的問題:此處兩名參與者利用公開訊息計算共同值,而非直接加密訊息。我們先證明兩人的計算結果相同,再問這項計算能和不能證明甚麼。
定義 10.1.1
(剩餘類的階與交換過程)
令 為質數, 為模 的非零剩餘類。其階 是滿足 的最小正整數。由於非零剩餘類構成有限乘法群, 存在。公開參數為 。Alice 選私人指數 ,Bob 在同一集合中選 ;兩人分別公開
Alice 計算 ,Bob 計算 。此指數範圍只定義數學實驗,並非安全密鑰生成的完整規格。
定理 10.1.2
(協商一致)
若雙方收到對方未經修改的公開值,其計算結果相同:
證明
(誠實交付下的指數法則)
模冪的恆等式來自乘法結合律和 。指數模 化簡不改變 的冪,因為在域中 。此等式證明誠實交付時的正確性,並未證明觀察者不能計算結果。
例題 10.1.3
(模 23 的小型計算)
取 、、、。 的階為 :費馬(Fermat)定理給出 ,而 、;因此階不能是 的任何真因數。公開值為 和 。雙方均算得
這些極小參數只用來展示運算,並不安全。
觀察者看到甚麼
觀察者看到 。離散對數問題要求:給定 及其生成子群中的 ,找出滿足 的指數 。若觀察者找到這樣的指數,便可計算 。此推論不證明逆命題:計算共同值和找回指數是不同問題。
概念視角結構
同一交換在另一種表示中
映射 是由加法群 到 所生成子群的同構,所以這個交換就是把指數之積 搬到該子群中。在 中以生成元 進行完全相同的交換,公開 和 (模 )。取 得 ;由於 ,觀察者算出 。抽象而言兩個群相同;若有任何困難性,它來自以模 剩餘表示這個群的方式。
定理 10.1.4
(找回指數即可得到共同值)
若觀察者找到任意整數 使 ,則 。
證明
( 的任何對數都足夠)
由於 ,有 。指數 不必等於 : 的任何解都與 模 同餘,而 的冪只取決於指數模 的值。
例題 10.1.5
(用冪次表破解小例子中的交換)
在例子中,列出冪次便可發現 ;用 和公開的 就得到共同值 。因此,僅稱指數為私人數據並不能推出安全。這個有限玩具群可行地列出完整表格,而運算能力無限的觀察者總能窮舉有限指數範圍。實際安全性是依賴指定群、實現及攻擊者假設的計算性主張,不是協商恆等式證明的資訊論保密性。
例題 10.1.6
(退化的指數與小的階)
若 Alice 的指數為 ,則 ,不論 Bob 怎樣選擇,共同值都是 ;觀察者直接由 讀出結果。階很小同樣有害。模 時,剩餘類 的階為 ,所以每個公開值和每個共同值都屬於 。取 、,雙方都公開 ,並算得 。觀察者完全知道規則:共同值為 當且僅當 ,即兩個指數都是奇數。兩種情形下協商仍然一致;改變的是 所生成的群的大小。
常見錯誤
(正確性不等於保密性)
即使群小得足以讓觀察者列舉所有指數,誠實雙方的計算仍然相等。保密主張需要威脅模型及額外假設。
為何需要認證
反例模式
替換公開值
假設主動攻擊者能替換訊息,並選取指數 。攻擊者把 傳給 Alice,代替 Bob 的 ;把 傳給 Bob,代替 Alice 的 。Alice 計算 ,攻擊者也可由 算出;Bob 計算 ,攻擊者也可由 算出。攻擊者因此能分別建立兩個共同值。雙方沒有認證正在與誰分享,其值也未必相同。例如在模 的例子中,攻擊者取 ,向雙方都發送 。Alice 算得 ,Bob 算得 ,而攻擊者算得 及 。這並不與協商一致定理矛盾:失效的正是「公開值未被修改」這個假設。
認證必須把交換值與預期參與者和協議上下文綁定。真正的密鑰建立協議還要規定安全參數、公開值檢查、隨機性、密鑰導出函數及在需要時的密鑰確認。本玩具計算不是協議或實現建議。
習題
快速檢查
(在模 23 的例子中,驗證 、 和共同值。)
用模 的反覆平方。
解答 · 答案
重複平方得到公開值 、; 和 模 都化為 。
快速檢查
(若 的階為 ,為何指數 與 給出相同公開值?)
利用 。
解答 · 答案
在域中 。
快速檢查
(觀察者由公開值 得知 ,如何利用 計算共同值?)
應用找回指數的定理。
解答 · 答案
計算公開值 的 次方:。
快速檢查
(單靠 能否阻止上述公開值替換?解釋。)
檢查協商一致定理的假設。
解答 · 答案
不能。等式假設預期的公開值被送達;替換值讓攻擊者分別與每位參與者分享一個值。
延伸閱讀
Diffie 與 Hellman,〈New Directions in Cryptography〉(1976) 提出公開密鑰分發。NIST SP 800-56A Rev. 3 討論離散對數密鑰建立方案,並註明計劃更新。