安全协商共享密钥 - 迪菲.赫尔曼算法

    迪菲-赫尔曼算法是一种双方在没有预先共享信息的情况下，通过公共信道安全协商生成一个共享密钥，这个密钥随后可用于对称加密通信。该算法本身不加密数据，而是用于安全地生成密钥，因此通常与其他加密算法结合使用。

一、数学基础

    算法依赖于模幂运算和离散对数问题的单向性：

    模幂运算：给定底数b、指数e和模m，计算 c = b^e mod m。

    离散对数问题：已知 b,c,m 求 e 非常困难，这保证了密钥交换的安全性。

    协议中，双方选择一个大素数 p 和其原根 g（公开参数），然后各自生成私钥 a 和 b，计算公钥 A=g^a mod p  和 B = g^b mod p 并交换。

    最终共享密钥为：K=B^a mod p = A^b mod p

    由于离散对数问题的难度，攻击者无法从公开的 A 和 B 推导出私钥，从而保证了密钥安全 。

二、算法流程

    1. 双方公开素数 p（模数） 和生成元（底数） g。

    2. Alice 选择私钥 a，计算公钥 A=g^a mod p 并发送给 Bob。

        Bob 选择私钥 b，计算公钥 B = g^b mod p 并发送给 Alice。

    3. 双方分别计算共享密钥：

        Alice: K=B^a mod p

        Bob: K=A^b mod p

    得到相同的共享密钥 K，用于后续对称加密通信。

三、计算示例

    1. 双方公开的底数 2、模数19。

    2.  双方计算公钥

        A：随机数幂 8

         2^8 mod 19  = 256 mod 19 = 9

        B：随机数幂15

        2^15 mode 19 = 32768 mod 19 = 12

    3. 计算共享密钥

        A: 12 ^ 8 mode 19 = 429981696 mod 19 = 11

        B: 9 ^ 15 mode 19 = 205891132094649 mod 19 = 11

四、C/C++示例

#include <iostream>

#include <cmath>

using namespace std;

// Function to calculate power modulo P

long long int calculatePower(long long int base, long long int exponent, long long int modulus) {

    if (exponent == 1)

        return base;

    else

        return (((long long int)pow(base, exponent)) % modulus);

}

int main() {

    long long int prime, generator, secretAlice, secretBob, publicAlice, publicBob, secretKeyAlice, secretKeyBob;

    prime = 23;

    cout << "Prime number (P): " << prime << endl;

    generator = 5;

    cout << "Generator value (G): " << generator << endl;

    // Alice's private key initialization

    secretAlice = 6;

    cout << "Alice's private key (a): " << secretAlice << endl;

    // Calculate Alice's public key

    publicAlice = calculatePower(generator, secretAlice, prime);

    // Bob's private key initialization

    secretBob = 15;

    cout << "Bob's private key (b): " << secretBob << endl;

    // Calculate Bob's public key

    publicBob = calculatePower(generator, secretBob, prime);

    // Calculate secret keys for Alice and Bob

    secretKeyAlice = calculatePower(publicBob, secretAlice, prime);

    secretKeyBob = calculatePower(publicAlice, secretBob, prime);

    // Output secret keys

    cout << "Secret key for Alice: " << secretKeyAlice << endl;

    cout << "Secret key for Bob: " << secretKeyBob << endl;

    return 0;

}

五、开源库

    https://codeload.github.com/kmackay/micro-ecc

#include "uECC.h"

#include <stdio.h>

#include <string.h>

int main() {

    int i, c;

    uint8_t private1[32] = { 0 };

    uint8_t private2[32] = { 0 };

    uint8_t public1[64] = { 0 };

    uint8_t public2[64] = { 0 };

    uint8_t secret1[32] = { 0 };

    uint8_t secret2[32] = { 0 };

    const struct uECC_Curve_t* curves[5];

    int num_curves = 0;

#if uECC_SUPPORTS_secp160r1

    curves[num_curves++] = uECC_secp160r1();

#endif

#if uECC_SUPPORTS_secp192r1

    curves[num_curves++] = uECC_secp192r1();

#endif

#if uECC_SUPPORTS_secp224r1

    curves[num_curves++] = uECC_secp224r1();

#endif

#if uECC_SUPPORTS_secp256r1

    curves[num_curves++] = uECC_secp256r1();

#endif

#if uECC_SUPPORTS_secp256k1

    curves[num_curves++] = uECC_secp256k1();

#endif

    printf("Testing 256 random private key pairs\n");

    for (c = 0; c < num_curves; ++c) {

        for (i = 0; i < 256; ++i) {

            printf(".");

            fflush(stdout);

            if (!uECC_make_key(public1, private1, curves[c]) || !uECC_make_key(public2, private2, curves[c])) 

                return 1;

            if (!uECC_shared_secret(public2, private1, secret1, curves[c]))

               return 1;

            if (!uECC_shared_secret(public1, private2, secret2, curves[c]))

                return 1;

            if (memcmp(secret1, secret2, sizeof(secret1)) != 0) 

                printf("Shared secrets are not identical!\n");

        }

        printf("\n");

    }

    return 0;

}

六、mod运算的性质

(a+b) mod n=((a mod n)+(b mod n)) mod n

(a−b) mod n=((a mod n)−(b mod n)) mod n

(a×b) mod n=((a mod n)×(b mod n)) mod n

(a×(b+c)) mod n=(((a×b) mod n)+((a×c) mod n))) mod n

利用如上规律可以有效避免大数求模中的溢出问题。