DH 密钥交换算法

阅读 skyent 的登陆服务的源码了解到在客户端和服务器之间产生秘密密钥使用的算法是 Diffie-Hellman 算法. 这个算法由于不直接传递密钥, 而是通过双方各自通过取模运算计算得出. 这个方案的安全性源自于计算离散对数比计算指数更为困难. 这个算法需要双方使用相同的较大的素数 n 和 g , 在 skynet 的 lua-crypt.c 文件中使用 n = 0xffffffffffffffc5 ( 64 位无符号最大的素数) 以及 g = 5 .

具体的协议如下:

Alice 选取一个大的随机整数 x, 并发送 X = g^x \mod{n};
Bob 选取一个大的随机整数 y, 并发送 Y = g^y \mod{m} ;
Alice 计算 k = Y^x \mod{n} ;
Bob 计算 k’ = X^y \mod{n};

其中 k 和 k’ 都等于 g^{xy} \mod{n} . 证明如下: X^y \mod{n} 为 y 个 X 相乘并对 n 取模, 进而由公式 ((a\mod{m})(b\mod{m}))\mod{m} = ab \mod{m} 推断出 y 个 X 相乘并对 n 取模等价于 g^{xy}\mod{n}.

在计算模幂运算(Modular Exponentiation)时, 即处理如下 3^{644} \mod{645} 时这种比较大整数运算时用到了两种算法, 这两种算法都将多次使用公式 ((a\mod{m})(b\mod{m}))\mod{m} = ab \mod{m} .

将 644 按照二进制展开为 (1010000100)_2, 这样 3^{644} \mod{645} 就会变成 (3^{2^9}*3^{2^7}*3^{2^2})\mod{645} 进而变为 ((3^{2^9}\mod{645})*(3^{2^7}\mod{645})*(3^{2^2}\mod{645}))\mod{645}

第一种方法先计算指数中的高位的模, 并在位向下移动时对模做平方运算并取模, 如果当前位是 1 还将 3\mod{645} 计算进去, 从而逐步计算得到这个整体的模. 具体做法如下: 首先移动到最高位为 1, 计算此处的模为 3, 当往后移动一位此时位为 0, 相当于计算 3^{(10)_2} \mod{645} , 指数是原来的两倍, 从而幂是原来的平方, 3^2 \mod{645} \equiv (3\mod{645})*(3\mod{645})\mod{645} 从而就是高位的模做平方运算并取模. 当在往后移动一位时为 1, 相当于计算 3^{(100)_2+(1)_2}\mod{645} \equiv (3^{(100)_2}*3) \mod{645}, 从而便是先对原来模做平方运算取模, 再乘以 3\mod{645} 再去取模. 依次往后一直计算下去. 得到的代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


// calc a^b % p
static uint64_t
powmodp(uint64_t a, uint64_t b) {
    if (a > P)
        a%=P;
    return pow_mod_p(a,b);
}

/* 要求参数 a 一定是小于 P 的, 否则需要先取模后再带入 */
static inline uint64_t
pow_mod_p(uint64_t a, uint64_t b) {
    if (b==1) {
        return a;
    }
    /* 计算前面高位的对 P 的模 */
    uint64_t t = pow_mod_p(a, b>>1);
    /* 对模做平方运算并对 P 取模 */
    t = mul_mod_p(t,t);
    /* 如果当前位是 1 , 再乘以当前模再去取模 */
    if (b % 2) {
        t = mul_mod_p(t, a);
    }
    return t;
}

还有一种算法是先计算较低指数位的模, 即为先计算 3 mod 645, 然后 3^{2} \mod {645} 就是低位取模平方运算再取模, 这样就得到了当前最高位的模, 按照乘法原则并入到整个低位模中去, 即为当前的模. 代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


// calc a^b % p
static uint64_t
powmodp(uint64_t a, uint64_t b) {
    if (a > P)
        a%=P;
    return pow_mod_p(a,b);
}

static inline uint64_t
pow_mod_p(uint64_t a, uint64_t b) {
    uint64_t t = 1;
    uint64_t power = a;
    while (b) {
        /* 如果当前位是 1 , 将低位整体的模和当前为模相乘再去取模 */
        if (b&1) {
            t = mul_mod_p(t, power);
        }
        /* 将低位的模做平方运算并取模, 从而得到高一位的模 */
        power = mul_mod_p(power, power);
        b >>= 1;
    }
    return t;
}

在 mul_mod_p 中将运用 (a + b) mod m = ((a mod m) + (b mod m)) mod m 去更加高效的实现. 代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


/* 对 a*644 取模就相当于对(a*2^2 + a*2^7 + a*2^9)取模 */
static inline uint64_t
mul_mod_p(uint64_t a, uint64_t b) {
    uint64_t m = 0;
    while(b) {
        /* 如果当前位为 1 ,将当前的单项的模加入到前面低位整体的模中 */
        if(b&1) {
            uint64_t t = P-a;
            if ( m >= t) {
                m -= t;
            } else {
                m += a;
            }
        }
        /* 计算单项的模, 每向高位移动一位均会乘以 2, 再取模 */
        if (a >= P - a) {
            a = a * 2 - P;
        } else {
            a = a * 2;
        }
        b>>=1;
    }
    return m;
}

Contents

DH 密钥交换算法