在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; 
}