為甚麼需要協商密鑰?
對稱加密要求雙方先擁有共同秘密。若 Alice 和 Bob 從未見面,直接在公開通道上傳送秘密便失去意義。Diffie–Hellman 容許雙方只發送公開群元素,隨後各自算出同一個群元素;它本身卻不能確認對方身份。
定義 10.2.1
(Diffie–Hellman 交換)
設公開的循環群 的質數階為 ,以乘法記號表示,指數按模 計算。群、階和生成元都是公開的;Alice 和 Bob 獨立、均勻地從 選擇秘密指數 。理想化交換如下:
- Alice 發送 ,Bob 發送 。
- Alice 計算 ,Bob 計算 。
- 由 ,雙方均得到 。
這個等式證明的是正確性,不是保密性。竊聽者看到 ,必須在不知道指數的情況下計算或區分關於 的資訊。實際系統通常將群元素及具有協議含義的通訊記錄編碼交給合適的密鑰派生函數,而不是直接把群元素當成任意長度的加密密鑰。
例題 10.2.2
(模 23 的交換)
在模 的非零剩餘類中, 的階為 :,而它的階不是 。取子群 。Alice 選擇 ,發送 ;Bob 選擇 ,發送 。Alice 算得 ,Bob 算得 ;也可直接算 。這個小群便於手算,卻沒有實際安全性。
被動安全性究竟說了甚麼?
定義 10.2.3
(計算與判定 Diffie–Hellman 問題)
計算 Diffie–Hellman 問題(CDH)要求從 計算 ,其中 獨立均勻取自 。判定 Diffie–Hellman 假設(DDH)則說,有效的隨機算法不能區分以下兩個分佈:
其中 獨立均勻取自 。嚴格而言,我們討論隨安全參數增長的一族適當群:每個概率多項式時間區分器在兩個實驗中輸出同一指定結果的概率之差都是可忽略的。這不表示兩個分佈完全相同;計算能力不受限制的觀察者可以求出指數並檢驗關係。
從離散對數到 CDH
離散對數問題要求從 求出 。知道 足以求出共享元素,但誠實協議不需要 Alice 求離散對數,因為她本來就知道自己的指數。被動竊聽者則可能嘗試從公開值恢復它。
定理 10.2.4
(離散對數求解器給出 CDH 求解器)
假設群運算和求冪均可有效執行。若一個算法對均勻的 以至少 的概率求出離散對數,則可構造一個 CDH 算法,對獨立均勻的 至少以概率 成功。
證明
(由對數得到共享元素)
給定 ,對 運行離散對數算法,得到候選值 ,再輸出 。只要模 有 ,輸出就是 。因此離散對數算法成功時,CDH 算法必然成功;額外工作只需一次求冪。
常見錯誤
(離散對數困難不能推出 DDH)
這是單向歸約:有效的離散對數算法會使 CDH 容易,但我們沒有證明每個 CDH 算法都必須恢復指數。特別是,僅憑離散對數困難不能確立 DDH 假設。
例題 10.2.5
(在小群中恢復指數)
竊聽者看到模 的 、。依次列出 、、、,便得到 ,進而算出 。這個小群可以窮舉;例子展示一種攻擊,並不聲稱窮舉在每個群中都是最佳算法。
定理 10.2.6
(DDH 下原始共享元素是偽隨機的)
假設所用群族滿足 DDH,則在上述理想交換中,有效被動觀察者無法以不可忽略的優勢區分 和 ,其中 是獨立均勻的 元素。
證明
(兩個實驗的等同)
均勻的 可寫為 ,其中 均勻取自 。因此第一個實驗恰好給出 DDH 三元組,第二個恰好給出隨機三元組。任何區分這兩個實驗的算法本身就是 DDH 區分器,輸出概率之差完全相同。
證明透視
為甚麼轉發歸約毫無損失
三個假設各在一處用到。被動性表示觀察者只讀取 ,從不選擇公開值,所以一個 DDH 挑戰就包含其全部視圖;若對手以自己的值替換 ,歸約就需要一個不知道指數便無法算出的回應。指數必須恰好在 上均勻分佈(包括零),因為 DDH 三元組正是以這個分佈定義的。關鍵的一步是: 均勻時 在 中均勻,所以隨機實驗與隨機 DDH 三元組是同一個分佈,而不只是接近。
由於兩種情形下的視圖都完全一致,歸約的優勢等於觀察者的優勢,論證以逆否命題收結:一個優勢不可忽略的觀察者,就是一個優勢相同、運行時間基本相同的 DDH 區分器。若指數改為從非零剩餘中抽取,則每個實驗中的視圖至多相差 ,等式便變成下文推導的 界。
理想選擇包含指數零:若 ,則 , 也是公開的。在適當的大階群族中,這以概率 發生,雖可忽略,但刻意輸入單位元很危險。實際實現常拒絕單位元並使用非零秘密指數;將兩個指數限制為非零會改變理想實驗的分佈,對該變體的證明必須計入這個條件化。本節不是生產協議規範。
實驗、優勢與歸約
在被動實驗中,雙方誠實執行交換:觀察者不選擇或替換任何公開訊息。先獨立均勻地選取 。真實實驗向觀察者提供 ,隨機實驗則提供 。觀察者輸出一個位元;輸出 1 表示它猜測元組來自真實實驗。若兩種實驗中輸出 1 的概率分別為 和 ,這裏將區分優勢定義為 。有些教材用隨機猜測遊戲的成功概率定義優勢,數值會差一個二分之一的因子,因此需要說明約定。
歸約接收 DDH 挑戰元組 ,原樣將 交給觀察者,再原樣輸出觀察者的位元。若挑戰是真實元組,觀察者看到的恰是真實交換實驗;若挑戰是隨機元組,它看到的恰是隨機實驗。歸約不需要求出離散對數,也沒有模擬誤差。按照上述約定,歸約的優勢與觀察者的優勢完全相同。因此,對於隨安全參數增長的群族,若觀察者有不可忽略的優勢,就與該群族的 DDH 假設矛盾;這裏要求觀察者和轉發歸約都是概率多項式時間算法,並在兩種實驗中獲得相同的公開群描述。
實驗故意把第三個元素交給觀察者:問題是即使同時看到公開交換記錄,這個元素是否仍與獨立均勻元素難以區分。這不是要求協議公開真實會話密鑰。實際加密安全還依賴編碼、密鑰派生和後續使用方式。計算不可區分並不意味著統計上接近或完全獨立。考慮所有 構成的集合:真實三元組必在其中;隨機三元組在其中的概率為 ,因為前兩項固定後,符合關係的第三項只有一個。因此,即使 DDH 指出有效觀察者的優勢可忽略,計算能力不受限制的觀察者仍能以 的概率差區分。
概念視角代數
藏在指數中的秩問題
把 的指數記成域 上的矩陣:
這個組是 Diffie–Hellman 組,當且僅當該矩陣奇異,即秩為一;均勻的 使它奇異的概率為 ,正是上文所用的計數。DDH 斷言:只能在指數中看到各元素的高效觀察者,無法分辨秩一與秩二。
例題 10.2.7
(小群中可見的區分差異)
在上述 11 階群中,令觀察者恰在第三個元素為單位元時輸出 1。真實實驗中, 當且僅當模 11 有 ;其概率為 。隨機實驗中 的概率為 。因此該觀察者的優勢為 。這個簡單測試已經能區分小群中的兩個分佈;當相應差距 相對於安全參數可忽略時,它不與漸近 DDH 假設矛盾;例如安全參數為 且 時就是如此。檢查第三元素是否等於單位元即可完成這個測試。
若改為從非零剩餘類中均勻選取兩個指數,它們的聯合分佈等於原來均勻分佈在 且 條件下的分佈。被排除事件的概率為 。因此對真實或隨機實驗,條件化對任何固定觀察者事件的概率影響至多 ;由三角不等式,區分優勢的變化至多 。這是較寬鬆但明確的界,不能據此接受對手發送的單位元。
反例模式
群階不是質數時,共享元素洩漏一個位元
聲稱:DDH 可以在任何循環群中假設,例如模質數 的整個乘法群。模 時,元素 的階為 。由 Euler 判別法, 當且僅當 是平方元,而 是平方元當且僅當 為偶數。所以 是平方元,當且僅當 或 是平方元。若觀察者在第三個元素符合此規則時輸出 1,則 、,對每個這樣的 優勢都是 。例如 給出 、、,三者都不是平方元。修正在於定義中的質數階:在 階子群中每個元素都是平方元,這個檢驗得不到任何資訊。
主動攻擊者可以替換兩個訊息
假設 Eve 能截獲並替換公開訊息。Alice 發出 、Bob 發出 ,但 Eve 選取非零 ,向 Alice 發送 代替 ,向 Bob 發送 代替 。Alice 算出 ;Eve 用截獲的 和自己知道的 也能算出它。Bob 算出 ,Eve 同樣能算出。Alice 和 Bob 通常得到不同的密鑰,各自卻都與 Eve 共享。若後續通訊沒有有效認證,Eve 可以根據所用加密的性質在一側解密、另一側重新加密。
反例模式
小群中的替換
沿用模 的例子,Eve 向雙方都發送 。Alice 得到 ,Bob 得到 (均模 )。Eve 分別計算 和 。兩個替換值都是 的非單位元,因此僅檢查子群成員資格不能認證發送者。
要防止替換,需要有身份認證的協議。例如,可驗證的簽名覆蓋帶上下文的通訊記錄,其中包含雙方身份和公開值;還需要可信地將驗簽密鑰綁定到預期對方。若驗簽公鑰本身未經認證,簽名只是轉移了替換問題。完整協議還要規定角色、編碼、必要時的密鑰確認和失敗處理;這裏沒有證明完整的認證密鑰交換方案安全。
群和公開值的檢查
在某些使用未檢查共享元素的協議中,若輸入不在預期子群,回應可能洩露資訊。例如在模 的完整乘法群中, 的階為二。若實現用 中的整數表示 並計算 ,而攻擊者能辨認這個回應,便能獲知該整數的奇偶性。模奇數 的剩餘類本身沒有固有的奇偶性;輸入在 之外時,代表元的選擇會影響結果。這是小子群攻擊的示意,不是對上面被動 DDH 實驗的攻擊:後者的輸入都在 中取樣。
在本例的質數階子群中,剩餘類 屬於 當且僅當 。實際協議還須規定域元素編碼,拒絕格式錯誤或被禁止的值,並按所用群選擇正確參數和檢查。這些檢查維護群假設,不能證明發送者身份。
手算公開值檢查
例題 10.2.8
(合法子群元素與二階元素)
取 、,接收方檢查 。連續平方得到 、、,故 。又 ,所以它通過子群和非單位元檢查。但對手也能發送 ;通過檢查並不能識別發送者。
再看 。由於 是奇數,,子群檢查會拒絕它。若有缺陷的實現仍對它求冪,私有指數代表元 和 分別給出 和 。如果攻擊者能從回應或之後的可觀察行為區分這兩個結果,就能知道該代表元的奇偶性;僅發送 本身並不會自動洩露私有指數。
對模 的非零剩餘類,測試 恰好識別這個 11 階子群:由拉格朗日(Lagrange)定理,子群提供 11 個根;域上非零的 11 次多項式至多有 11 個根。測試包含 ,因此要求非單位元的協議還需要單獨檢查。不能不核對其他群的表示與協議規則,就照搬這個條件。
練習與解答
快速檢查
(在上述子群中,Alice 取 ,Bob 取 。求公開值和共同元素。)
計算 與 模 ,再作一次求冪。
解答 · 答案
,,而 ;也可用 。
快速檢查
(如果接收者接受 ,任意秘密指數會得到甚麼共享元素?這與經過認證的交換有何區別?)
把 取任意次冪。
解答 · 答案
,這是公開值。它不證明發送者身份,而已知的共享元素不能提供秘密密鑰。
快速檢查
(解釋總是正確的 CDH 求解器如何構造 DDH 區分器。若 獨立均勻且群階為 ,計算其區分概率差。)
把第三個分量與求解器的輸出比較。
解答
用求解器計算 ,當且僅當第三項等於 時輸出「真實」。若求解器總是正確,真實三元組中的輸出概率為 ,隨機三元組中為 ,差為 。不完美求解器需要另行分析成功概率。
快速檢查
(在上述攻擊中,Eve 為甚麼無需知道 就能算出 ?只替換發給 Alice 的訊息,是否必然能使 Eve 也得到 Bob 的密鑰?)
把 與 都寫成 的冪。
解答
對公開的 用已知的 求冪即可:。若只替換發給 Alice 的訊息,Bob 仍使用 Alice 原來的 計算 ,Eve 一般不能僅憑這次替換求得 Bob 的密鑰。
快速檢查
(驗證 未通過模 的子群檢查,並說明該檢查不能證明甚麼。)
利用 與 的奇偶性。
解答 · 答案
,所以 ,排除其屬於 。即使檢查通過,元素仍可能來自攻擊者,而非預期對方。
快速檢查
(在小群中,指數在 上均勻分佈時,求真實實驗與隨機實驗中單位元測試的概率。為甚麼答案說明兩種實驗的分佈並非完全相同?)
沿用單位元檢驗的計算。
解答 · 答案
概率分別為 和 ,相差 ,因此兩種分佈不相同;計算不可區分是漸近性質,不是相等。
快速檢查
(驗證 通過子群檢查,並解釋為甚麼它仍不能認證對方。)
使用反覆平方。
解答 · 答案
如上,,且 。任何人都能發送此合法值,所以成員資格不能證明身份。