Diffie-Hellman金鑰協商演算法探究
作者 | 魔王趙二狗
導讀
隱私計算（Privacy-preserving computation）是指在保證資料提供方不洩露原始資料的前提下，對資料進行分析計算的一系列資訊科技，保障資料在流通與融合過程中的可用不可見。而Diffie–Hellman金鑰協商是一種安全協議。它可以讓雙方在完全沒有對方任何預先資訊的條件下通過不安全通道建立起一個金鑰。這個金鑰可以在後續的通訊中作為對稱祕鑰訊內容。
全文6088字，預計閱讀時間16分鐘。
01 什麼是DH金鑰協商演算法
1.1 DH由來
DH金鑰協商是Whitefield與Martin Hellman在1976年提出了一個的金鑰交換協議。
1.2 解決什麼問題
首先我們先看一個場景：
小明要在網路上給小紅髮一篇情書，小明呢，比較害羞，不想讓其他人知道情書的內容。
那麼顯而易見，小明必須要對內容進行加密，這個時候就需要選擇加密的方式，我們知道對於非對稱加密對內容的長度是有限制的，而小明寫的情書內容又非常多，那隻好選用AES對稱加密。
我們知道，AES對稱加密和解密是需要金鑰key的，那麼我們假定小明和小紅之間需要傳遞金鑰，那麼如何保證金鑰key的安全性？這時候你可能會說，把金鑰key用RSA非對稱加密不就好了（數字信封的概念），但我們是否有其他更好的方式解決問題？
這時候，DH金鑰協商演算法就應運而生，他解決的就是對稱加密的金鑰無需進行傳輸，並使小明、小紅使用的AES金鑰是一致的，那麼這是如何實現的呢。
1.3 實現原理
DH演算法解決了金鑰在雙方不直接傳遞金鑰的情況下完成金鑰交換，這個神奇的交換原理完全由數學理論支援。
我們來看DH演算法交換金鑰的步驟。假設小明、小紅雙方需要傳遞金鑰，他們之間可以這麼做：
-
小明首選選擇一個素數$p$，例如：97，底數$g$是$p$的一個原根，例如：5，隨機數，例如：123，然後計算$A=g^a$ ，然後，小紅髮送$p=97$，$g=5$，$A=34$給小紅；
-
小紅收到後，也選擇一個隨機數$b$，例如：456，然後計算$B=g^a mod p=75$ ，小紅再同時計算$s2=A^b mod p=22$；
-
小紅把計算的$B=75$發給小明，小明計算$s1=B^a mod p=22$，計算結果與乙算出的結果一樣，都是22。
所以最終雙方協商出的金鑰$s=22$。注意到這個金鑰$s$並沒有在網路上傳輸。而通過網路傳輸的$p$,$g$，$A$和$B$是無法推算出$s$的，因為實際演算法選擇的素數是非常大的。
所以，更確切地說，DH演算法是一個金鑰協商演算法，雙方最終協商出一個共同的金鑰，而這個金鑰不會通過網路傳輸，來保障了金鑰的安全性。此時，小明和小紅都露出了開心的笑容。
02 公式推導
本著嚴謹的態度，現在我們對$s1$與$s2$是否恆等做公式推導。一般來說，書上是如下解釋：
這裡是運用了求餘的運算規則，也就是說以下等式預設是成立的：
其實當成定理記住也就OK的，但是想要證明這個公式也很簡單：將求餘運算轉換為加減乘除運算，然後利用二項式展開公式便可以得到答案。
推導過程：
令
根據①②可得
則
將③帶入上式，可得
使用二項式展開公式將展開，則
從這個表示式可以看出，前項每一項都是的整數倍，因此 運算必定為0，因此：
所以
成立。
03 應用實現
注：本示例以Java服務端作為小明，Android客戶端作為小紅，下圖為執行順序。
1.客戶端發起請求
獲取服務端的p，g，serverNum
// 獲取伺服器的p，g，serverNum
Request request = new Request.Builder()
.get()
.url("https://xxxxx/dh/getdhbasedata")
.build();
Call call = mHttpClient.newCall(request);
Response res = call.execute();
2. 服務端建立資訊
建立DHServer類
public class DHServer {
/** 用來生成大素數p */
private static final String SOURCE = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200CBBE117577A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFCE0FD108E4B82D120A93AD2CAFFFFFFFFFFFFFFFF";
/** 大素數p */
private BigInteger mP;
/** 原根g */
private BigInteger mG;
/** 服務端隨機數值 */
private int mServerNum
}
DHServer中增加初始化方法：
/**
* 初始化p g serverNum 以及計算服務端的processedServerNum
* @return HashMap<String, String> 返回初始化建立好的p g serverNum 以及計算服務端的processedServerNum
*/
public HashMap<String, String> init() {
generateBaseInfo();
HashMap<String, String> baseData = new HashMap<>();
baseData.put("p", mP.toString());
baseData.put("g", mG.toString());
baseData.put("serverNumr", mServerNum + "");
baseData.put("processedServerNum", processServerKey());
return baseData;
}
DHServer中增加建立基礎資訊方法：
/**
* 生成基礎資訊，p，g，服務端隨機數serverNum
*/
private void generateBaseInfo () {
// 第一步：根據pSource生成伺服器當前固定的p
BigInteger p = new BigInteger(SOURCE, 16);
BigInteger tempP;
BigInteger g;
BigInteger gFlag;
while (true) {
tempP = p.subtract(new BigInteger("1"));
// 取一個2-p中間的隨機數
g = getBigIntegerRandomRange(new BigInteger("2"), tempP);
gFlag = g.modPow(tempP, p);
if (gFlag.toString().equals("1")) {
break;
}
}
Random serverNumRd = new Random();
this.mServerNum = serverNumRd.nextInt(100000) + 100;
this.mG = g;
this.mP = p;
}
DHServer中計算服務端的數值processedServerNum
/**
* 返回已處理的服務端processedServerNum
* @return processedServerNum
*/
private String processServerKey() {
return mG.modPow((new BigInteger(mServerNum + "")), mP).toString();
}
3. 客戶端收到資訊後進行計算
接收服務端資料
JSONObject data = new JSONObject(res.body().string());
String p = data.getString("p");
String g = data.getString("g");
String processedServerNum = data.getString("processedServerNum");
建立DHClient類並在構造方法中生成客戶端隨機數mClientNum
public class TiDHClient {
private final int mClientNum;
private BigInteger mP;
private BigInteger mG;
private BigInteger mProcessedServerNum;
private BigInteger mProcessedClientNum;
private BigInteger mKey;
public TiDHClient() {
mClientNum = new Random().nextInt(99999 - 10000) + 10000;
}
}
DHClient增加計算方法，計算出金鑰key與客戶端計算值mProcessedClientNum
/**
* 通過服務端獲取的 p, g 和processedServerNum計算金鑰key.
* @param p 通過服務端獲取的 p
* @param g 通過服務端獲取的 g
* @param serverNum 通過服務端獲取的 server number
* @return 金鑰字串
*/
public String processKey(String p, String g, String processedServerNum) {
mP = new BigInteger(p);
mG = new BigInteger(g);
mProcessedServerNum = new BigInteger(processedServerNum);
mProcessedClientNum = mG.modPow(new BigInteger(String.valueOf(mClientNum)), mP);
// 計算金鑰key
mPublicKey = mServerNumber.modPow(new BigInteger(String.valueOf(mClientNum)), mP);
return mPublicKey.toString();
}
DHClient中新增get方法
/**
* 獲取 processedClientNum. 用於傳送給服務端.
* 如果未呼叫 processKey 將返回空字串.
* @return processedClientNum.
*/
public String getProcessedClientNum() {
if (mProcessedClientNum == null) {
return "";
}
return mProcessedClientNum.toString();
}
/**
* 返回金鑰字串.
* 如果未呼叫processKey 將返回空字串
* @return public key
*/
public String getKey() {
if (mKey == null) {
return "";
}
return mKey.toString();
}
4.客戶端將processedClientNum計算結果給服務端
// 根據processedServerNum，processedClientNum和p 計算出金鑰K
TiDHClient dhClient = new TiDHClient();
mClientKey = dhClient.processKey(p, g, serverNumber);
// 將計算過後的processedClientNum傳送給伺服器
FormBody formBody = new FormBody
.Builder()
.add("processedClientNum",dhClient.getProcessedClientNum())
.build();
request = new Request.Builder()
.post(formBody)
.url("https://xxxxxxxxxx/dh/postdhclientdata")
.build();
call = mHttpClient.newCall(request);
res = call.execute();
data = new JSONObject(res.body().string());
5.服務端計算金鑰key
DHServer中新增計算方法
/**
* 根據客戶端傳過來的processedClientNum 計算出key
* @param processedClientNum 客戶端傳過來的processedClientNum
* @param serverNum 上一次請求隨機生成的serverNum
* @param p 上一次請求的 p
* @return String 金鑰key
*/
public String computeShareKey (String processedClientNum, String serverNumber, String p) {
BigInteger BigClientNumber = new BigInteger(processedClientNum);
return BigClientNumber.modPow(new BigInteger(serverNumber + ""), new BigInteger(p)).toString();
}
怎麼樣，看到這裡是否感覺這像是握手的過程，其實HTTPS的TLS1.3版本也引入了DH的概念來保證安全性。此外，p，g的生成還可以用RSA的公鑰和私鑰，這時候就會演變成DH-RSA演算法。同時p，g的生成是放在服務端還是放在客戶端其實各有優缺點，大家可以考慮下。
學會這些，我們也可以在業務中仿寫資料傳輸的工具SDK，只要在初始化階段進行協商，那麼就能得到一個無法被抓包和破解的加密key，希望對大家的實踐有所幫助。
——END——
推薦閱讀：
- 精準水位在流批一體資料倉庫的探索和實踐
- 影片編輯場景下的文字模版技術方案
- 淺談活動場景下的圖演算法在反作弊應用
- 百度工程師帶你玩轉正則
- Serverless：基於個性化服務畫像的彈性伸縮實踐
- 百度APP iOS端記憶體優化-原理篇
- 從稀疏表徵出發、召回方向的前沿探索
- 效能平臺數據提速之路
- 採編式AIGC影片生產流程編排實踐
- 百度工程師漫談影片理解
- PGLBox 超大規模 GPU 端對端圖學習訓練框架正式釋出
- 百度工程師淺談分散式日誌
- 百度工程師帶你瞭解Module Federation
- 巧用Golang泛型，簡化程式碼編寫
- Go語言DDD實戰初級篇
- 百度工程師帶你玩轉正則
- Diffie-Hellman金鑰協商演算法探究
- 貼吧低程式碼高效能規則引擎設計
- 淺談許可權系統在多利熊業務應用
- 分散式系統關鍵路徑延遲分析實踐