Diffie-Hellman 密钥协商算法探究

2023-01-10
上海
本文字数：4357 字
阅读完需：约 14 分钟

作者 | 魔王赵二狗

导读
隐私计算（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} m o d p = 75$ ，小红再同时计算 $s 2 = A^{b} m o d p = 22$ ；
小红把计算的 $B = 75$ 发给小明，小明计算 $s 1 = B^{a} m o d p = 22$ ，计算结果与乙算出的结果一样，都是 22。

所以最终双方协商出的密钥 $s = 22$ 。注意到这个密钥 $s$ 并没有在网络上传输。而通过网络传输的 $p$ , $g$ ， $A$ 和 $B$ 是无法推算出 $s$ 的，因为实际算法选择的素数是非常大的。

所以，更确切地说，DH 算法是一个密钥协商算法，双方最终协商出一个共同的密钥，而这个密钥不会通过网络传输，来保障了密钥的安全性。此时，小明和小红都露出了开心的笑容。

02 公式推导

本着严谨的态度，现在我们对 $s 1$ 与 $s 2$ 是否恒等做公式推导。一般来说，书上是如下解释：

这里是运用了求余的运算规则，也就是说以下等式默认是成立的：

其实当成定理记住也就 OK 的，但是想要证明这个公式也很简单：将求余运算转换为加减乘除运算，然后利用二项式展开公式便可以得到答案。

推导过程：

令

根据①②可得

则

将③带入上式，可得

使用二项式展开公式将展开，则

从这个表达式可以看出，前项每一项都是的整数倍，因此运算必定为 0，因此：

所以

成立。

03 应用实现

注：本示例以 Java 服务端作为小明，Android 客户端作为小红，下图为执行顺序。

1.客户端发起请求

获取服务端的 p，g，serverNum

 // 获取服务器的p，g，serverNumRequest 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 计算出密钥KTiDHClient 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——

百度Geek说

关注

百度官方技术账号 2021-01-22 加入

关注我们，带你了解更多百度技术干货。

发布

暂无评论

创作场景

Diffie-Hellman 密钥协商算法探究

01 什么是 DH 密钥协商算法

1.1 DH 由来

1.2 解决什么问题

1.3 实现原理

02 公式推导

03 应用实现

1.客户端发起请求

2. 服务端创建信息

3. 客户端收到信息后进行计算

4.客户端将 processedClientNum 计算结果给服务端

5.服务端计算密钥 key

百度Geek说

评论