Diffie-Hellman密钥交换算法的原理及程序演示

作者：又ettl_329 | 来源：互联网 | 2023-06-10 09:56

在http:en.wikipedia.orgwikiDiffie-Hellman上面给出了这个密钥交换协议的历史，原理，重要文献的链接，以及演示代码。它的数学基础就是离散对数这个数学难题。用它

在http://en.wikipedia.org/wiki/Diffie-Hellman上面给出了这个密钥交换协议的历史，原理，重要文献的链接，以及演示代码。它的数学基础就是离散对数这个数学难题。用它进行密钥交换的过程简述如下：
选取两个大数p和g并公开，其中p是一个素数，g是p的一个模p本原单位根(primitive root module p)，所谓本原单位根就是指在模p乘法运算下，g的1次方，2次方……(p-1)次方这p-1个数互不相同，并且取遍1到p-1；
对于Alice(其中的一个通信者)，随机产生一个整数a，a对外保密，计算Ka = g^a mod p，将Ka发送给Bob；
对于Bob(另一个通信者)，随机产生一个整数b，b对外保密，计算Kb = g^b mod p，将Kb发送给Alice；
在Alice方面，收到Bob送来的Kb后，计算出密钥为：key = Kb^a mod p=(g^b)^a=g^(b*a) mod p；
对于Bob，收到Alice送来的Ka后，计算出密钥为：key = Ka ^ b mod p=(g^a)^b=g^(a*b) mod p。
攻击者知道p和g，并且截获了Ka和Kb，但是当它们都是非常大的数的时候，依靠这四个数来计算a和b非常困难，这就是离散对数数学难题。
要实现Diffie-Hellman密钥交换协议，需要能够快速计算大数模幂，在模幂算法中，仍需计算大数的乘法和模运算，所以整个过程需要三个算法：高精度乘法，高精度除法(用来同时求出一个大数除以另一个大数的商和余数)，快速模幂算法。
高精度的乘法和除法可以程序模拟手算。快速模幂算法也是从手算中总结出规律来，例如：
5^8 = (5^2)^4 = (25)^4 = (25^2)^2 = (625)^2，这样，原来计算5^8需要做8次乘法，而现在则只需要三次乘法，分别是：5^2, 25^2, 625^2。这就是快速模幂算法的基础。将算法描述出来，那就是：
算法M:输入整数a,b,p，计算a^b mod p：
M1.初始化c = 1
M2.如果b为0，　则c就是所要计算的结果。返回c的值。算法结束。
M3.如果b为奇数，则令c = c *a mod p，　令b = b-1，转到M2。
M4.如果b为偶数，则令a = a * a mod p，　令b = b / 2，转到M2。
高精度试除法原理简单，但是代码实现起来需要仔细考虑一些细节。
我的演示代码如下：
高精度运算类：

 class SuperNumber {
public:
    SuperNumber() {
        memset(data, 0, MAX_SIZE);
        high = 0;
    }
    // 一般整型到SuperNumber的转换，该版本中不支持负数 
    SuperNumber(unsigned long l) {
        memset(data, 0, MAX_SIZE);
        high = 0;
        while(l) {
            data[++high] = l % 10;
            l /= 10;
        }
    }
    // str为字符串形式表示的十进制数 
    SuperNumber(const char* str) {
        assert(str != NULL);
        high = strlen(str);
        for(int i = high, j = 0; i >= 1; i--, j++) {
            data[i] = str[j] - '0';
        }
    }
    SuperNumber(const SuperNumber& s) {
        memcpy(data, s.data, MAX_SIZE);
        high = s.high;
    }
    operator const char*() const {
        return toString(10);
    }
    SuperNumber& operator=(const SuperNumber& s) {
        if(this != &s) {
            memcpy(data, s.data, MAX_SIZE);
            high = s.high;
        }
        return *this;
    }
    // 将数据置为0 
    void reset() {
        memset(data, 0, MAX_SIZE);
        high = 0;
    }
    // str为字符串形式表示的十进制数 
    void setToStr(const char* str) {
        assert(str != NULL);
        high = strlen(str);
        for(int i = high, j = 0; i >= 1; i--, j++) {
            data[i] = str[j] - '0';
        }
    }
    // 将数据转换成以base指定的进制的字符串形式，默认为十进制 
    const char* toString(int base = 10) const {
        static char buf[MAX_SIZE];
        const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        if(high == 0) return "0";
        assert(base >= 2);      // 指定的进制应该不小于2 
        // 进制转换 
        buf[MAX_SIZE-1] = '/0';
        int begin = MAX_SIZE-1;
        char temp[MAX_SIZE];
        memcpy(temp, data, MAX_SIZE);
        while(1) {
            // 找最高位的起始位置 
            int h = high;
            while(temp[h] == 0 && h >= 1) h--;
            if(h == 0) break;
            // 除基取余 
            int t = 0;
            while(h >= 1) {
                t = t * 10 + temp[h];
                temp[h] = t / base;
                t = t % base;
                h--;
            }
            buf[--begin] = table[t];
        }
        return buf+begin;
    }
    // 乘法 
    SuperNumber operator*(const SuperNumber& s) const {
        SuperNumber result;     // default set to 0 
        int i, j;
        
        // 相乘 
        for(i = 1; i <= high; i++) {
            for(j = 1; j <= s.high; j++) {
                int k = data[i] * s.data[j] + result.data[i+j-1];
                result.data[i+j-1] = k % 10;
                result.data[i+j] += k / 10;
            }
        }
        // 进位 
        for(i = 1; i < MAX_SIZE - 1; i++) {
            if(result.data[i] >= 10) {
                result.data[i+1] += result.data[i] / 10;
                result.data[i] %= 10;
            }
        }
        // 确定最高位 
        for(i = MAX_SIZE-1; i >= 1 && result.data[i] == 0; i--);
        result.high = i;
        return result;
    }
    // 除法，内部调用doDivide来实现 
    SuperNumber operator/(const SuperNumber& s) const {
        SuperNumber q, r;
        doDivide(s, q, r);
        return q;
    }
    // 模运算，内部调用doDivide来实现 
    SuperNumber operator%(const SuperNumber& s) const {
        SuperNumber q, r;
        doDivide(s, q, r);
        return r;
    }
    // 除法运算，一次除法运算中同时得到商和余数，运算符/和%的重载 
    // 内部会调用这个函数，dest为除数，Q为商，R为余数，算法使用试除法 
    void doDivide(const SuperNumber& dest, SuperNumber& Q, SuperNumber& R) const {
        int i, j, t;
        Q.reset();
        Q.high = high - dest.high + 1; // 商的初始位数 
        R = *this;                     // 余数初始实为被除数 
        t = dest.high;
        // 判断除法是否结束 
        while(R >= dest) {
            // 循环相减进行试除 
            while(dest >= R.sub(1, t)) {
                Q.data[Q.high--] = 0;
                ++t;
            }
            while(R.sub(1, t) >= dest) {
                // i为相减时被除数最低下标，j为除数最低下标 
                for(i=R.high-t+1,j=1; j<=dest.high; i++,j++) {
                    R.data[i] -= dest.data[j];
                    if(R.data[i] < 0) {
                        R.data[i] += 10;
                        R.data[i+1] -= 1;
                    }
                }
                while(R.data[i] < 0 && i <= R.high) {
                    R.data[i] += 10;
                    R.data[i+1] -= 1;
                    ++i;
                }
                Q.data[Q.high] += 1;
            }
            // 一次试除结束，更新商的最高位下标 
            Q.high -= 1;
            // 更新被除数的最高位下标 
            while(R.data[R.high] == 0) {
                R.high--;
                t--;
            }
            t+=1;               // 下一位被除数 
        }
        Q.high = high - dest.high + 1; 
        while(Q.data[Q.high] == 0) Q.high -= 1;
        R.high = high;
        while(R.data[R.high] == 0) R.high -= 1;
    }
    // 大数模幂算法，很简单的自然算法，即将指数分解为二进制，换句 
    // 更简单的话来说，就是不断地找平方模幂，而不是全部乘方后再 
    // 做一次最终的模运算 
    // a.power_mod(p, n)计算a^p mod n 
    SuperNumber power_mod(int power, SuperNumber n) const {
        SuperNumber c("1"), t(*this);
        while(power) {
            if(power % 2) {
                c = c * t % n;
                power -= 1;
            } else {
                t = t * t % n;
                power /= 2;
            }
        }
        return c%n;
    }
    bool operator>=(const SuperNumber& s) const {
        if(high == s.high) {
            int k = high;
            while(data[k] == s.data[k] && k >= 1)k--;
            if(k < 1) return true; // equal 
            return data[k] > s.data[k];
        } else if(high > s.high) return true;
        return false;        
    }
    bool operator<(const SuperNumber& s) const {
        return !(*this >= s);
    }
    // 从十进制表示的最高位开始数起，数到第i位，从第i位开始截取连续 
    // 的c位数字出来组成一个新的数。例如：数据是12345678925698，则 
    // sub(3, 5)返回数字34567，如果数字不够取，例如在34567上运行 
    // sub(3, 5)，因为34567从高位数起第3个数字是5，剩下的数字是567， 
    // 最多只有三个，不够取要求的5个，这个时候返回567，不报错。 
    SuperNumber sub(int i, int c) const {
        SuperNumber ret;
        assert(high >= i);   // 保证可截取 
        i = high - i + 1;    // 从高位数起的第i个数位的下标 
        if(i >= c) {
            ret.high = c;
            while(c >= 1) ret.data[c--] = data[i--];
        } else {
            ret.high = i;
            while(i >= 1) {
                ret.data[i] = data[i];
                i--;
            }
        } 
        // 过滤前导0 
        while(ret.data[ret.high] == 0) ret.high--;
        return ret;
    }
    // I/O 
    friend istream& operator>>(istream& in, SuperNumber& s) {
        char t[256];
        in >> t;
        s.setToStr(t);
        return in;
    }
    friend ostream& operator<<(ostream& out, const SuperNumber& s) {
        return out << s.toString(10);
    }
private:
    enum {MAX_SIZE=256};        // 最大十进制位数 
    // 须注意，使用data[0]存储最高位所在下标是自己的一点小聪明，后来在 
    // 调试的时候发现这是一个极大的错误，不过对于此题目来说可以应付 
    char data[MAX_SIZE];        // 数据的内部表示，字符串形式的十进制 
                                // 其中data[0]存储最高位所在下标，data[1] 
                                // 存储数据的最低位，也就是个位 
    int high;
};

主函数：

 int main(int argc, char **argv) {
    freopen("in.txt", "r", stdin);
    SuperNumberTest st;
//    st.run(); 
    // g和n都是超过2^127的素数。它们在DH算法中公开 
    SuperNumber g, n;
    int a, b;
    SuperNumber ka, kb, key;
    srand(time(0));
    cin >> g >> n;
    cout << "g = " << g << endl
         << "n = " << n << endl;
    cout << "/nThis is Alice:/n";
    a = rand();
    cout << "Alice get a random integer a = " << a << endl;
    cout << "Alice computer g^a mod n:/n";
    ka = g.power_mod(a, n);
    cout << "Alice compute out ka = " << ka << endl;
    cout << "/nThis is Bob:/n";
    b = rand();
    cout << "Bob get a random integer b = " << b << endl;
    cout << "Bob compute g^b mod n:/n";
    kb = g.power_mod(b, n);
    cout << "Bob compute out kb = " << kb << endl;
    cout << "/nAlice get kb from Bob, she compute out key is:/n";
    cout << kb.power_mod(a, n) << endl;
    cout << "/nBob get ka from Alice, he compute out key is:/n";
    cout << ka.power_mod(b, n) << endl;
    return 0;
}

运行结果：
g = 170141183460469231731687303715884105757
n = 170141183460469231731687303715884106309

This is Alice:
Alice get a random integer a = 20276
Alice computer g^a mod n:
Alice compute out ka = 102075421398841759242347870420481896337

This is Bob:
Bob get a random integer b = 28664
Bob compute g^b mod n:
Bob compute out kb = 62348451302684698452476840835428450852

Alice get kb from Bob, she compute out key is:
80402514625208456390620786920929643017

Bob get ka from Alice, he compute out key is:
80402514625208456390620786920929643017
在 http://oldpiewiki.yoonkn.com/cgi-bin/moin.cgi/DiffieHellmanKeyExchange 上面给出了使用GNU gmp库实现的这个算法的演示代码

推荐阅读

const
Java太阳系小游戏分析和源码详解

本文介绍了一个基于Java的太阳系小游戏的分析和源码详解。通过对面向对象的知识的学习和实践，作者实现了太阳系各行星绕太阳转的效果。文章详细介绍了游戏的设计思路和源码结构，包括工具类、常量、图片加载、面板等。通过这个小游戏的制作，读者可以巩固和应用所学的知识，如类的继承、方法的重载与重写、多态和封装等。 ... [详细]

蜡笔小新 2023-12-14 19:53:34
string
Java猜拳小游戏代码

本文介绍了一个Java猜拳小游戏的代码，通过使用Scanner类获取用户输入的拳的数字，并随机生成计算机的拳，然后判断胜负。该游戏可以选择剪刀、石头、布三种拳，通过比较两者的拳来决定胜负。 ... [详细]

蜡笔小新 2023-12-14 15:39:08
string
Java容器中的compareto方法排序原理解析

本文从源码解析Java容器中的compareto方法的排序原理，讲解了在使用数组存储数据时的限制以及存储效率的问题。同时提到了Redis的五大数据结构和list、set等知识点，回忆了作者大学时代的Java学习经历。文章以作者做的思维导图作为目录，展示了整个讲解过程。 ... [详细]

蜡笔小新 2023-12-14 13:53:31
const
关于cuowu类的错误提示和使用AdjustmentListener的问题

本文讨论了一个关于cuowu类的问题，作者在使用cuowu类时遇到了错误提示和使用AdjustmentListener的问题。文章提供了16个解决方案，并给出了两个可能导致错误的原因。 ... [详细]

蜡笔小新 2023-12-13 22:09:56
go
在类中定义数组时出错 - Error on defining arrays in class

Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]

蜡笔小新 2023-12-14 17:38:12
controller
SpringBoot uri统一权限管理的实现方法及步骤详解

本文详细介绍了SpringBoot中实现uri统一权限管理的方法，包括表结构定义、自动统计URI并自动删除脏数据、程序启动加载等步骤。通过该方法可以提高系统的安全性，实现对系统任意接口的权限拦截验证。 ... [详细]

蜡笔小新 2023-12-14 16:11:30
string
阿里云物联网 .NET Core 客户端 | CZGL.AliIoTClient：4. 设备上报属性

阿,里,云,物,联网,net,core,客户端,czgl,aliiotclient, ... [详细]

蜡笔小新 2023-12-14 12:40:20
string
如何在有序字符序列中插入新字符并保持有序

本文介绍了如何在给定的有序字符序列中插入新字符，并保持序列的有序性。通过示例代码演示了插入过程，以及插入后的字符序列。 ... [详细]

蜡笔小新 2023-12-14 11:16:33
string
C# 7.0 新特性：基于Tuple的“多”返回值方法

本文介绍了C# 7.0中基于Tuple的“多”返回值方法的使用。通过对C# 6.0及更早版本的做法进行回顾，提出了问题：如何使一个方法可返回多个返回值。然后详细介绍了C# 7.0中使用Tuple的写法，并给出了示例代码。最后，总结了该新特性的优点。 ... [详细]

蜡笔小新 2023-12-13 19:55:20
string
Java实现大数乘法（分治算法）

本文介绍了使用Java实现大数乘法的分治算法，包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]

蜡笔小新 2023-12-14 15:43:50
string
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
string
JavaSE笔试题-接口、抽象类、多态等问题解答

本文解答了JavaSE笔试题中关于接口、抽象类、多态等问题。包括Math类的取整数方法、接口是否可继承、抽象类是否可实现接口、抽象类是否可继承具体类、抽象类中是否可以有静态main方法等问题。同时介绍了面向对象的特征，以及Java中实现多态的机制。 ... [详细]

蜡笔小新 2023-12-14 10:01:13
string
Spring特性实现接口多类的动态调用详解

本文详细介绍了如何使用Spring特性实现接口多类的动态调用。通过对Spring IoC容器的基础类BeanFactory和ApplicationContext的介绍，以及getBeansOfType方法的应用，解决了在实际工作中遇到的接口及多个实现类的问题。同时，文章还提到了SPI使用的不便之处，并介绍了借助ApplicationContext实现需求的方法。阅读本文，你将了解到Spring特性的实现原理和实际应用方式。 ... [详细]

蜡笔小新 2023-12-14 03:24:19
string
Java高并发程序设计学习-线程安全的概念与synchronized

本文介绍了Java高并发程序设计中线程安全的概念与synchronized关键字的使用。通过一个计数器的例子，演示了多线程同时对变量进行累加操作时可能出现的问题。最终值会小于预期的原因是因为两个线程同时对变量进行写入时，其中一个线程的结果会覆盖另一个线程的结果。为了解决这个问题，可以使用synchronized关键字来保证线程安全。 ... [详细]

蜡笔小新 2023-12-13 15:43:03
string
猜字母游戏

猜字母游戏猜字母游戏——设计数据结构猜字母游戏——设计程序结构猜字母游戏——实现字母生成方法猜字母游戏——实现字母检测方法猜字母游戏——实现主方法1猜字母游戏——设计数据结构1.1 ... [详细]

蜡笔小新 2023-12-13 12:04:03

又ettl_329

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章