Diffie-Hellman密鑰協商算法探究

語言: CN / TW / HK

作者 | 魔王趙二狗

導讀

隱私計算(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算法交換密鑰的步驟。假設小明、小紅雙方需要傳遞密鑰,他們之間可以這麼做:

圖片

  1. 小明首選選擇一個素數$p$,例如:97,底數$g$是$p$的一個原根,例如:5,隨機數,例如:123,然後計算$A=g^a$ ,然後,小紅髮送$p=97$,$g=5$,$A=34$給小紅;

  2. 小紅收到後,也選擇一個隨機數$b$,例如:456,然後計算$B=g^a mod p=75$ ,小紅再同時計算$s2=A^b mod p=22$;

  3. 小紅把計算的$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——

推薦閲讀:

貼吧低代碼高性能規則引擎設計

淺談權限系統在多利熊業務應用

分佈式系統關鍵路徑延遲分析實踐

百度工程師教你玩轉設計模式(裝飾器模式)

百度工程師帶你體驗引擎中的nodejs

揭祕百度智能測試在測試定位領域實踐