作者 | 魔王趙二狗

導(dǎo)讀

【資料圖】

隱私計算（Privacy-preserving computation）是指在保證數(shù)據(jù)提供方不泄露原始數(shù)據(jù)的前提下，對數(shù)據(jù)進(jìn)行分析計算的一系列信息技術(shù)，保障數(shù)據(jù)在流通與融合過程中的可用不可見。而Diffie–Hellman密鑰協(xié)商是一種安全協(xié)議。它可以讓雙方在完全沒有對方任何預(yù)先信息的條件下通過不安全信道創(chuàng)建起一個密鑰。這個密鑰可以在后續(xù)的通訊中作為對稱秘鑰訊內(nèi)容。

全文6088字，預(yù)計閱讀時間16分鐘。

01 什么是DH密鑰協(xié)商算法

1.1 DH由來

DH密鑰協(xié)商是Whitefield與Martin Hellman在1976年提出了一個的密鑰交換協(xié)議。

1.2 解決什么問題

首先我們先看一個場景：

小明要在網(wǎng)絡(luò)上給小紅發(fā)一篇情書，小明呢，比較害羞，不想讓其他人知道情書的內(nèi)容。

那么顯而易見，小明必須要對內(nèi)容進(jìn)行加密，這個時候就需要選擇加密的方式，我們知道對于非對稱加密對內(nèi)容的長度是有限制的，而小明寫的情書內(nèi)容又非常多，那只好選用AES對稱加密。

我們知道，AES對稱加密和解密是需要密鑰key的，那么我們假定小明和小紅之間需要傳遞密鑰，那么如何保證密鑰key的安全性？這時候你可能會說，把密鑰key用RSA非對稱加密不就好了（數(shù)字信封的概念），但我們是否有其他更好的方式解決問題？

這時候，DH密鑰協(xié)商算法就應(yīng)運而生，他解決的就是對稱加密的密鑰無需進(jìn)行傳輸，并使小明、小紅使用的AES密鑰是一致的，那么這是如何實現(xiàn)的呢。

1.3 實現(xiàn)原理

DH算法解決了密鑰在雙方不直接傳遞密鑰的情況下完成密鑰交換，這個神奇的交換原理完全由數(shù)學(xué)理論支持。

我們來看DH算法交換密鑰的步驟。假設(shè)小明、小紅雙方需要傳遞密鑰，他們之間可以這么做：

小明首選選擇一個素數(shù)，例如：97，底數(shù)是的一個原根，例如：5，隨機(jī)數(shù)，例如：123，然后計算 ，然后，小紅發(fā)送，，給小紅；小紅收到后，也選擇一個隨機(jī)數(shù)，例如：456，然后計算 ，小紅再同時計算；小紅把計算的發(fā)給小明，小明計算，計算結(jié)果與乙算出的結(jié)果一樣，都是22。

所以最終雙方協(xié)商出的密鑰。注意到這個密鑰并沒有在網(wǎng)絡(luò)上傳輸。而通過網(wǎng)絡(luò)傳輸?shù)?，和是無法推算出的，因為實際算法選擇的素數(shù)是非常大的。

所以，更確切地說，DH算法是一個密鑰協(xié)商算法，雙方最終協(xié)商出一個共同的密鑰，而這個密鑰不會通過網(wǎng)絡(luò)傳輸，來保障了密鑰的安全性。此時，小明和小紅都露出了開心的笑容。

02 公式推導(dǎo)

本著嚴(yán)謹(jǐn)?shù)膽B(tài)度，現(xiàn)在我們對與是否恒等做公式推導(dǎo)。一般來說，書上是如下解釋：

這里是運用了求余的運算規(guī)則，也就是說以下等式默認(rèn)是成立的：

其實當(dāng)成定理記住也就OK的，但是想要證明這個公式也很簡單：將求余運算轉(zhuǎn)換為加減乘除運算，然后利用二項式展開公式便可以得到答案。

推導(dǎo)過程：

令

根據(jù)①②可得

則

將③帶入上式，可得

使用二項式展開公式將展開，則

從這個表達(dá)式可以看出，前項每一項都是的整數(shù)倍，因此 運算必定為0，因此：

所以

成立。

03 應(yīng)用實現(xiàn)

注：本示例以Java服務(wù)端作為小明，Android客戶端作為小紅，下圖為執(zhí)行順序。

1.客戶端發(fā)起請求

獲取服務(wù)端的p，g，serverNum

// 獲取服務(wù)器的p，g，serverNumRequest request = new Request.Builder()        .get()        .url("https://xxxxx/dh/getdhbasedata")        .build();Call call = mHttpClient.newCall(request);Response res = call.execute();

2. 服務(wù)端創(chuàng)建信息

創(chuàng)建DHServer類

public class DHServer {    /** 用來生成大素數(shù)p */    private static final String SOURCE = "FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA051015728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64ECFB850458DBEF0A8AEA71575D060C7DB3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3D2261AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200CBBE117577A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFCE0FD108E4B82D120A93AD2CAFFFFFFFFFFFFFFFF";    /** 大素數(shù)p */    private BigInteger mP;    /** 原根g */    private BigInteger mG;    /** 服務(wù)端隨機(jī)數(shù)值 */    private int mServerNum}

DHServer中增加初始化方法：

/** * 初始化p g serverNum 以及計算服務(wù)端的processedServerNum * @return HashMap 返回初始化創(chuàng)建好的p g serverNum 以及計算服務(wù)端的processedServerNum */public HashMap init() {    generateBaseInfo();    HashMap baseData = new HashMap<>();    baseData.put("p", mP.toString());    baseData.put("g", mG.toString());    baseData.put("serverNumr", mServerNum + "");    baseData.put("processedServerNum", processServerKey());    return baseData;}

DHServer中增加創(chuàng)建基礎(chǔ)信息方法：

/** * 生成基礎(chǔ)信息，p，g，服務(wù)端隨機(jī)數(shù)serverNum */private void generateBaseInfo () {    // 第一步：根據(jù)pSource生成服務(wù)器當(dāng)前固定的p    BigInteger p = new BigInteger(SOURCE, 16);    BigInteger tempP;    BigInteger g;    BigInteger gFlag;    while (true) {        tempP = p.subtract(new BigInteger("1"));        // 取一個2-p中間的隨機(jī)數(shù)        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中計算服務(wù)端的數(shù)值processedServerNum

/** * 返回已處理的服務(wù)端processedServerNum * @return processedServerNum */private String processServerKey() {    return mG.modPow((new BigInteger(mServerNum + "")), mP).toString();}

3. 客戶端收到信息后進(jìn)行計算

接收服務(wù)端數(shù)據(jù)

JSONObject data = new JSONObject(res.body().string());String p = data.getString("p");String g = data.getString("g");String processedServerNum = data.getString("processedServerNum");

創(chuàng)建DHClient類并在構(gòu)造方法中生成客戶端隨機(jī)數(shù)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

/** * 通過服務(wù)端獲取的 p, g 和processedServerNum計算密鑰key. * @param p 通過服務(wù)端獲取的 p * @param g 通過服務(wù)端獲取的 g * @param serverNum 通過服務(wù)端獲取的 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. 用于發(fā)送給服務(wù)端. * 如果未調(diào)用 processKey 將返回空字符串. * @return processedClientNum. */public String getProcessedClientNum() {    if (mProcessedClientNum == null) {        return "";    }    return  mProcessedClientNum.toString();}/** * 返回密鑰字符串. * 如果未調(diào)用processKey 將返回空字符串 * @return public key */public String getKey() {    if (mKey == null) {        return "";    }    return mKey.toString();}

4.客戶端將processedClientNum計算結(jié)果給服務(wù)端

// 根據(jù)processedServerNum，processedClientNum和p 計算出密鑰KTiDHClient dhClient = new TiDHClient();mClientKey = dhClient.processKey(p, g, serverNumber);// 將計算過后的processedClientNum發(fā)送給服務(wù)器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.服務(wù)端計算密鑰key

DHServer中添加計算方法

/** * 根據(jù)客戶端傳過來的processedClientNum 計算出key * @param processedClientNum 客戶端傳過來的processedClientNum * @param serverNum 上一次請求隨機(jī)生成的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的生成是放在服務(wù)端還是放在客戶端其實各有優(yōu)缺點，大家可以考慮下。

學(xué)會這些，我們也可以在業(yè)務(wù)中仿寫數(shù)據(jù)傳輸?shù)墓ぞ逽DK，只要在初始化階段進(jìn)行協(xié)商，那么就能得到一個無法被抓包和破解的加密key，希望對大家的實踐有所幫助。

——END——

推薦閱讀：

??貼吧低代碼高性能規(guī)則引擎設(shè)計??

??淺談權(quán)限系統(tǒng)在多利熊業(yè)務(wù)應(yīng)用??

??分布式系統(tǒng)關(guān)鍵路徑延遲分析實踐??

??百度工程師教你玩轉(zhuǎn)設(shè)計模式（裝飾器模式）??

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

??揭秘百度智能測試在測試定位領(lǐng)域?qū)嵺`??