加密算法：什么是 Deffi-Hellman 算法？

图解：什么是 Deffi-Hellman 算法？

背景

椭圆曲线（Elliptic Curve）的研究可以被追溯至十九世纪中叶，那时代数学家、几何代数学家、以及数论专家都在研究。1984年，Hendrik Lenstra 阐述了一个依据于椭圆曲线的因数分解算法，导致了研究者重新去研究椭圆曲线在密码学以及数论算法的新应用。

1976年，Whitfield Diffie 和 Martin Hellman 开创了公钥密码学的先河；次年，Ron Rivest、Adi Shamir、Len Adleman 提出了一个在当下还非常著名的、基于整数分解难题的 RSA 算法。1985年，Neal Koblitz 和 Victor Miller 提出了椭圆曲线密码学（Elliptic Curve Cryptography, ECC），它和 RSA 有着相同的公钥密码学功能。然而它和 RSA 所基于的数学难题不同，它基于椭圆曲线的离散对数问题（ECDLP）。目前，解决 ECDHP 最行之有效的方法需要消耗指数运算时间，这比整数分解所需要的时间大的多，这也就意味着，相同大小的输入，ECC 能够比 RSA 提供更高的安全性。例如 256 比特的椭圆曲线密钥和 3072 比特的 RSA 密钥的安全性相当。越小的密钥在速度、效率、带宽、存储上有着许多优势。

椭圆曲线的公式为：

其中 （这一条件保证椭圆曲线是非奇异的），这个等式就是椭圆曲线的 Weierstrass 范式。

非奇异就是椭圆曲线不存在尖峰或自相交，如下图所示：

上图表示的是不同椭圆曲线（其中 ， 从 2 变化到 -3对应的不同曲线）。

奇异就是下图的情况，左侧的曲线存在峰点（）；左侧的曲线自相交了（）。这两种情况都不是有效的椭圆曲线。

和 取不同的值，椭圆曲线在平面上有不同的形状。有一种典型的椭圆曲线，当绘制一条一线时，与椭圆曲线有 3 个交点，如下图所示，椭圆曲线关于 x 轴时对称的，这一特性在算法中起着关键作用：

Diffie-Hellman 加密算法

Diffie-Hellman 加密算法本身限于密钥交换的用途，被许多商用产品用作密钥交换技术，因此该加密算法通常也称之为 Diffie-Hellman 密钥交换。这种密钥交换技术的目的在于使得两个用户安全地交换一个秘密密钥以便用于以后的报文文件加密。

一、Diffie-Hellman加密算法原理

Diffie-Hellman 加密算法的有效性依赖于计算离散对数的难度。简言之，可以如下定义离散对数：首先定义一个素数 P 的原根 G，为其各次幂产生从 1 到 P-1 的所有整数根，也就是说，如果 G 是素数 P的一个原根，那么数值 , ,...,  是各不相同的整数，并且以某种排列方式组成了从 1 到 P-1 的所有整数。对于一个整数 a 和素数 P 的一个原根 G，可以找到惟一的指数 b，使得 ，其中 指数 称为 的以 为基数的模    的离散对数或者指数，该值被记为 。

二、Diffie-Hellman加密算法描述

基于 Diffie-Hellman 加密算法的定义及性质，可以定义 Diffie-Hellman 密钥交换加密算法。该加密算法描述如下：

1、有两个全局公开的参数，一个素数 和一个整数 ， 是 的一个原根。

2、假设用户 A 和 B 希望交换一个密钥，

用户 A 选择一个作为私有密钥的随机数

并计算公开密钥 。

A 对 的值保密存放而使 能被 B 公开获得。

类似地，用户 B选择一个私有的随机数

并计算公开密钥 。

B 对 的值保密存放而使 能被 A 公开获得。

3、用户 A 产生共享秘密密钥的计算方式是 。同样，用户 B 产生共享秘密密钥的计算是 。这两个计算产生相同的结果：

因此相当于双方已经交换了一个相同的秘密密钥。

4、因为 和 是保密的，一个敌对方可以利用的参数只有 ， ， 和 。因而敌对方被迫取离散对数来确定密钥。例如，要获取用户 B 的秘密密钥，敌对方必须先计算  ；然后再使用用户 B 采用的同样方法计算其秘密密钥  .

Diffie-Hellman 密钥交换算法的安全性依赖于这样一个事实：

虽然计算以一个素数为模的指数相对容易，但计算离散对数却很困难。对于大的素数，计算出离散对数几乎是不可能的。下面给出例子。

密钥交换基于素数 和 97 的一个原根 。A 和 B 分别选择私有密钥 和 。每人计算其公开密钥 、 在他们相互获取了公开密钥之后，各自通过计算得到双方共享的秘密密钥如下：

从 |50,44| 出发，攻击者要计算出 75 很不容易，下图给出了一个利用 Diffie-Hellman 计算的简单协议：

三、Diffie-Hellman 算法实现

下面我们用 JAVA 中的 SeverSocket 来模拟上客户端和服务端的通信过程。客户端（Client）将素数 、对应的原根 和生成公钥 发送给服务端；服务端接收客户端传来的值，并计算自身的公钥 ，将 响应给客户端。

客户端和服务器都使用公共密钥来计算对称加密的密钥 。

客户端程序

package com.cryptograph.ECC;

import java.net.*;
import java.io.*;

public class GreetingClient {
    public static void main(String[] args)
    {
        try {
            String pstr, gstr, Astr;
            String serverName = 'localhost';
            int port = 8080;    // 端口号

int p = 23;     // 素数
            int g = 9;      // 原根
            int a = 4;      // 客户端的私钥

double Adash, serverB;

// 建立连接
            System.out.println('连接到 ' + serverName
                    + ' 端口号：' + port);
            Socket client = new Socket(serverName, port);
            System.out.println('Server端地址： '
                    + client.getRemoteSocketAddress());

// 向服务端发送数据
            OutputStream outToServer = client.getOutputStream();
            DataOutputStream out = new DataOutputStream(outToServer);

pstr = Integer.toString(p);
            out.writeUTF(pstr); // Sending p

gstr = Integer.toString(g);
            out.writeUTF(gstr); // 发送 g

double A = ((Math.pow(g, a)) % p); // 计算公钥 A
            Astr = Double.toString(A);
            out.writeUTF(Astr); // 发送公钥 A

System.out.println('客户端的私钥 = ' + a);

// 接收数据
            DataInputStream in = new DataInputStream(client.getInputStream());

serverB = Double.parseDouble(in.readUTF());
            System.out.println('来自服务端的公钥 Y_B = ' + serverB);

Adash = ((Math.pow(serverB, a)) % p); // 计算共享密钥 K

System.out.println('对称加密的共享密钥 K = ' + Adash);
            client.close();
        }
        catch (Exception e) {
            e.printStackTrace();
        }
    }
}

服务端程序

package com.cryptograph.ECC;

import java.net.*;import java.io.*;

public class GreetingServer {    private static int port = 8080;    private static Socket server = null;    public static void main(String[] args) throws IOException    {        try {

            // 服务端的私钥            int b = 3;

            double clientP, clientG, clientA, B, Bdash;            String Bstr;

            // 建立连接            ServerSocket serverSocket = new ServerSocket(port);            System.out.println('等待客户端的请求 ' + serverSocket.getLocalPort() + '...');            server = serverSocket.accept();            System.out.println('连接： ' + server.getRemoteSocketAddress());

            System.out.println('服务端的私钥 = ' + b);

            // 接收来自客户端的数据            DataInputStream in = new DataInputStream(server.getInputStream());

            clientP = Integer.parseInt(in.readUTF()); // 接收 p            System.out.println('来自客户端的素数 P = ' + clientP);

            clientG = Integer.parseInt(in.readUTF()); // 接收 g            System.out.println('素数 P 的原根 G = ' + clientG);

            clientA = Double.parseDouble(in.readUTF()); // to accept A            System.out.println('客户端发来的公钥为 Y_A = ' + clientA);

            B = ((Math.pow(clientG, b)) % clientP); // 计算服务端的公钥 B            Bstr = Double.toString(B);

            // 将服务端的公钥 Y_B 发送给客户端            OutputStream outToClient = server.getOutputStream();            DataOutputStream out = new DataOutputStream(outToClient);

            out.writeUTF(Bstr); // 发送公钥 B

            Bdash = ((Math.pow(clientA, b)) % clientP); // 计算共享密钥 K

            System.out.println('执行对称加密的密钥 K = ' + Bdash);

        } catch (SocketTimeoutException s) {            System.out.println('Socket timed out!');        } catch (IOException e) {            e.printStackTrace();        } finally {            server.close();        }    }}

四、Diffie-Hellman 算法特征：

Diffie-Hellman 算法具有两个吸引力的特征：

1、仅当需要时才生成密钥，减小了将密钥存储很长一段时间而致使遭受攻击的机会。

2、除对全局参数的约定外，密钥交换不需要事先存在的基础结构。

小知识之加密算法：

数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理，使其成为不可读的一段代码，通常称为“密文”，使其只能在输入相应的密钥之后才能显示出本来内容，通过这样的途径来达到保护数据不被非法人窃取、阅读的目的。该过程的逆过程为解密，即将该编码信息转化为其原来数据的过程。

主要是最近项目设计到加密，就给大家以 Diffie-Hellman 算法作为引子介绍这一算法，要知道当年 CSDN 对用户的密码数据进行加密，也不至于 600 万的用户数据被盗（仅作调侃，加密其实也很重要，有些朋友是信息安全的，小达献丑了！）。

赞 (0)

相关推荐