Diffie-Hellman密钥协商算法探究

2023-01-10 503

作者 | 魔王赵二狗

导读

隐私计算（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 mod p=75$ ，小红再同时计算$s2=A^b mod p=22$；
小红把计算的$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——

智能流程机器人助你“聚划算”

摘要：RPA可以模拟人工进行操作，比如平时的登录，操作文件，抓取数据，调用api，与数据库进行交互等操作，从而实现一系列自动化的实现。本文分享自华为云社区《智能流程机器人助你“聚划算”》，作者：华为云社区精选。相信大家都知道最近的数字员工非常火，比如我们中国的商飞上飞院三所的数字员工“思睿”，还有他的专属工号：20952227、还有首位数字化员工，获得21年万科优秀奖的新人奖获得者“崔筱盼” 当然我们华为内部也有8000+的数字员工，在HR、供应链、物流、内审等行业工作，是不是很厉害呢，聪明的同学这时候就要问了，那他们是通过什么实现的呢，这就是接下来我们要介绍的 RPA。 1. 什么是智能流程机器人？ RPA能做哪些工作? RPA可以模拟人工进行操作，比如平时的登录，操作文件，抓取数据，调用api，与数据库进行交互等操作，从而实现数据采集。文档制作，报表生成，业务审核、问题诊断已经处理等一系列自动化的实现什么是华为 RPA? 部署环境：Linux Windows UOS等操作系统部署基础能力： • 自动化：Web页面、用户交互、触发感知、国产OS、桌面应用、数据服务、逻辑控...

2023-01-09

369

本文来自于 Doris Summit 2022 演讲实录，演讲人：陈明雨十年对于数据库意味着什么？身处在日新月异的时代，我们见惯了技术的兴起与繁荣、变迁与衰落，甚至是朝荣夕灭。信息技术以前所未有的速度更迭，给周遭事物带来了颠覆性地变化。数据库亦是如此，无数数据库悄然湮没在技术更迭的浪潮里，直到在浩渺如海的代码片段中都找不到些许印记。而有的则历久而弥新，经受了时间的考验，彰显出强大的生命力，并以更加繁茂的姿态扎根生长。十年对于数据库而言，可能是一段从诞生到消逝的完整软件生命周期，也可能是迈过里程碑之后的全新旅程。所以从 MySQL 1.0 版本诞生，到具备颠覆性意义的 MySQL 5.7 版本正式发布，时间跨度刚好是十年，而十年之后的故事，大家已经都知道了。所以从 Benoit、Thierry、Marcin 联合创建 Snowflake，到在纽交所成功上市、成为软件行业有史以来最大规模的IPO，再到全面开启云数据仓库时代，时间跨度也差不多十年。而对于 Apache Doris，十年意味着什么？留个悬念，在回答这个问题之前，我们不妨来回顾下社区发展历程。尽管最早的历史可以追...

2023-01-10

389

资源下载

更多资源

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能，例如代码缩略图，Python的插件，代码段等。还可自定义键绑定，菜单和工具栏。Sublime Text 的主要功能包括：拼写检查，书签，完整的 Python API ， Goto 功能，即时项目切换，多选择，多窗口等等。Sublime Text 是一个跨平台的编辑器，同时支持Windows、Linux、Mac OS X等操作系统。

WebStorm

WebStorm 是jetbrains公司旗下一款JavaScript 开发工具。目前已经被广大中国JS开发者誉为“Web前端开发神器”、“最强大的HTML5编辑器”、“最智能的JavaScript IDE”等。与IntelliJ IDEA同源，继承了IntelliJ IDEA强大的JS部分的功能。