ElGamal算法是一種常見加密算法, 與Diffie-Hellman算法有密切關(guān)聯(lián)。

該算法安全性依賴于計(jì)算有限域上離散對數(shù)難題：求解離散對數(shù)(目前)是困難的,其逆運(yùn)算指數(shù)運(yùn)算簡單。

算法思路:
假設(shè)有2個(gè)用戶Alice 和 Bob，Bob欲使用ElGamal加密算法向Alice發(fā)送信息。
對于Alice,首先要選擇一個(gè)素?cái)?shù)q, α是素?cái)?shù)q的本原根。 [本原根的概念對應(yīng)模q乘法群(需循環(huán)群)中的生成元。]

• Alice產(chǎn)生一個(gè)XA, XA∈(1, q - 1)
• 計(jì)算Y_A = α^XA mod q
• A的私鑰為XA, 公鑰為 {q, α, Y_A}

公鑰存在于某個(gè)可信公開中心目錄,任何用戶都可訪問

對于Bob, 首先去上述中心目錄訪問得Alice的公鑰 {q, α, Y_A}
然后將自己欲發(fā)送的明文M, (M ∈ [1, q - 1]）洗干凈備好。

• 選一個(gè)隨機(jī)整數(shù)k, k ∈ [1, q - 1]
• 計(jì)算可解密自己密文的秘鑰 PrivateK = （Y_A)^k mod q (即α^XA*k mod q)
• 將M加密成明文對(C1, C2) 其中
  C1 = α^k mod q , C2 = PrivateK * M mod q
• 明文對發(fā)送給Alice

Alice收到明文對：

• PrivateK = (C1)^XA mod q(即α^k*XA mod q)
• M = C2 * PrivateK^-1 mod q

到這里..發(fā)現(xiàn)算法大多就是一些乘法,求冪之類的運(yùn)算。剩下個(gè)關(guān)鍵內(nèi)容就是如何尋找素?cái)?shù)p的本原根，或者說如何找有限域GF(p)中的生成元。
我們在群這個(gè)概念里討論。
p是素?cái)?shù)，令Zp = {1, 2, 3, ..., p - 1},因?yàn)榭紤]乘法，去掉了0元素。
2個(gè)定理：

• Euler定理：設(shè)P和a是互素的兩個(gè)整數(shù)，則有a^φ(p)＝1 mod p
• 拉格朗日定理: 設(shè) G 是有限群， H 是 G 的子群,|H| 整除 |G|

回顧這樣2個(gè)概念：設(shè)G是群, a∈G, 使得等式a^k = e成立的最小整數(shù)k稱為元素a的階。而群的階是指該群中的元素個(gè)數(shù)。值得留意的是，以某個(gè)生成元去生成某個(gè)子群，該子群的階就是該元素的階(當(dāng)然了）。

因Zp中所有元素與p互素,由歐拉定理，Zp中所有元素的階不超過p-1,(因?yàn)槿旱碾Aφ(p)是p-1,而至少有a^φ(p)＝1 mod p)。
對于Zp中的任一元素，以該元素為生成元形成的一個(gè)循環(huán)群，設(shè)為S(群S的階在數(shù)值上即該元素的階)，根據(jù)群的封閉性可知S必然為Zp的子群，根據(jù)拉格朗日定理，可知Zp的元素的階必然是|Zp| (即p-1)的因子。

于是可以得到這樣一個(gè)結(jié)論：若有這樣一個(gè)元素a，其階為Ka, Ka是p-1的平凡因子(即因子1 或者因子p-1), 那么a或者是單位元，或者是生成元。 又知Zp的單位元是1，那么根據(jù)單位元的唯一性，可知若a非1，則a必為生成元。問題在于，p-1的因子可能很多，我們還不是得一個(gè)個(gè)去找到階是p-1的平凡因子的元素？

為此，我們構(gòu)造一種特殊的素?cái)?shù)，使得p-1的因子數(shù)量很少。取p - 1 = 2 * Q ，其中p是素?cái)?shù)，Q也是素?cái)?shù)。 因?yàn)镼是素?cái)?shù)，因子僅1， Q。所以p - 1的因子只有 {1, 2, Q, p - 1}四個(gè)。
到此已經(jīng)非常明朗，我們找到滿足上述條件的素?cái)?shù)p，然后在Zp中尋找這樣一個(gè)元素a，a的階非2，非Q，即a^2 mod p != 1 && a^Q mod p != 1，若a又非單位元1，那么a必然是生成元。

留意Zp未必一定有生成元, 若1 到 (p - 1)經(jīng)上述檢驗(yàn)都不滿足, 考慮另取一個(gè)素?cái)?shù)p。至于代碼實(shí)現(xiàn)上出現(xiàn)的問題：若mpz_probab_prime_p(tmp.mt, 6) == 1 改為 mpz_probab_prime_p(tmp.mt, 6) == 2，p一旦較大，程序運(yùn)行速度很慢。取2為真素?cái)?shù)檢驗(yàn)，速度很慢，1為概率素?cái)?shù)檢驗(yàn)，速度快。

代碼實(shí)現(xiàn)

#include<bits/stdc++.h>
#include<gmp.h>
#include<gmpxx.h>
using namespace std;

#define mt get_mpz_t()
typedef mpz_class bn;

gmp_randstate_t rstate;

struct public_keys {
    // Big prime p, primitive root, Y = XA^(primitive root)
    bn p, pr, Y; 
    public_keys(bn _p = 0, bn _pr = 0, bn _Y = 0) : p(_p), pr(_pr), Y(_Y) {}
};

// Trusted third party  一個(gè)所有用戶可訪問的公開中心目錄
map<string, public_keys> ttp;    

// 返回start 到 end的一個(gè)隨機(jī)數(shù)
inline bn randNum(bn start, bn end) {
    bn tmp;
    mpz_urandomm(tmp.mt, rstate, bn(end + 1 - start).mt);
    return tmp + start;
}
// 返回 a^b mod n
inline bn aebmodn(bn a, bn b, bn n) {
    bn ret;
    mpz_powm(ret.mt, a.mt, b.mt, n.mt);
    return ret;
}
// 在2^bits范圍內(nèi)生成一副公鑰，存于公開目錄中，記在name名下 返回私鑰
bn elgmal_keyGen(string name, unsigned long int bits) {
    bn p = 2, pr = -1, Y = -1, bounds = 2;
    mpz_pow_ui(bounds.mt, bounds.mt, bits);

    bool found = 0;
    while(1) {
        mpz_urandomm(p.mt, rstate, bounds.mt);
        mpz_nextprime(p.mt, p.mt);
        bn tmp = (p - 1) / 2;

        if (p < bounds && mpz_probab_prime_p(tmp.mt, 6) == 1) {
            // pr是1到p-1的一個(gè)數(shù)
            pr = randNum(1, p - 1);
            while (1) {
                // pr^tmp % p
                bn pexpn = aebmodn(pr, tmp, p);
                if (pr != 1 && (pr * pr) % p != 1 && pexpn != 1) {
                    found = 1;
                    break;
                }
                pr = (pr + 1) % p;
            }
        }
        if (found) break;
    }

    bn XA = randNum(2, p - 2);
    Y = aebmodn(pr, XA, p);
    ttp[name] = public_keys(p, pr, Y);
    return XA;
}

// 密文對(C1, C2)
struct cipher_text {
    bn c1, c2;
    cipher_text(bn _c1 = 0, bn _c2 = 0) : c1(_c1), c2(_c2) {}
};

/*
 * 根據(jù)公開中心目錄中name名下的公鑰 對明文m進(jìn)行加密
 * 返回密文對(C1, C2)
 */
cipher_text elgamal_encrypt(string name, bn m) {
    public_keys pk = ttp[name];
    bn k = randNum(1, pk.p - 1);
    bn privateKey;
    mpz_powm(privateKey.mt, pk.Y.mt, k.mt, pk.p.mt);
    bn cipher1 = aebmodn(pk.pr, k, pk.p);
    bn cipher2 = (m * privateKey) % pk.p;
    return cipher_text(cipher1, cipher2);
}

// 根據(jù)在自己name名下的公鑰及 自己的秘鑰dk 解密密文對ct 返回明文
bn elgamal_decrypt(string name, bn dk, cipher_text ct) {
    public_keys pk = ttp[name];
    bn privateKey = aebmodn(ct.c1, dk, pk.p);
    bn k_inverse;
    mpz_invert(k_inverse.mt, privateKey.mt, pk.p.mt);
    return (ct.c2 * k_inverse) % pk.p;
}

int main() {
    gmp_randinit_mt(rstate);
    gmp_randseed_ui(rstate, time(NULL));
    // Alice初始化自己在中心的公鑰并得到自己的私鑰
    bn dk = elgmal_keyGen("Alice", 128);
    cout<<"Input the message: ";
    bn n; cin>>n;
    if (n > ttp["Alice"].p) cout<<"message's length is out of bounds\n"; 
    // Bob根據(jù)Alice用戶信息對明文n加密
    cipher_text ct = elgamal_encrypt("Alice", n);
    // Alice進(jìn)行解密
    bn res = elgamal_decrypt("Alice", dk, ct);
    cout<<"decrypt   result : " <<res <<"\n";
    return 0;
}                             

示例
? ./ElGamal 
Input the message: 1024
decrypt   result : 1024

注：參考了這篇博客和LJF同學(xué)的討論..有不對請指正..