作者 | 魔王赵二狗

导读

隐衷计算(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,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——

举荐浏览:

贴吧低代码高性能规定引擎设计

浅谈权限零碎在多利熊业务利用

分布式系统要害门路提早剖析实际

百度工程师教你玩转设计模式(装璜器模式)

百度工程师带你体验引擎中的nodejs

揭秘百度智能测试在测试定位畛域实际