Diffie-Hellman密钥协商算法探究
GEEK TALK
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，底数是的一个原根，例如：5，随机数，例如：123，然后计算 ，然后，小红发送，，给小红； 小红收到后，也选择一个随机数，例如：456，然后计算 ，小红再同时计算 ； 小红把计算的发给小明，小明计算 ，计算结果与乙算出的结果一样，都是22。
GEEK TALK
02
公式推导
这里是运用了求余的运算规则，也就是说以下等式默认是成立的：
其实当成定理记住也就OK的，但是想要证明这个公式也很简单：将求余运算转换为加减乘除运算，然后利用二项式展开公式便可以得到答案。
推导过程：
令
根据①②可得
则
将③带入上式，可得
GEEK TALK
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生成服务器当前固定的pBigInteger 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();}
接收服务端数据
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);// 计算密钥keymPublicKey = 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