ElGamal暗号化アルゴリズム

4818 ワード
ElGamalアルゴリズムは一般的な暗号化アルゴリズムであり、Diffie-Hellmanアルゴリズムと密接に関連している.
このアルゴリズムの安全性は,有限領域における離散対数問題の計算に依存している.離散対数を解くことは困難であり,その逆演算指数演算は簡単である.
アルゴリズムの考え:AliceとBobが2人いると仮定し、BobはElGamal暗号化アルゴリズムを使ってAliceに情報を送信しようとしている.Aliceに対しては、まず素数qを選択します.α素数qの素です.［本ルートの概念は、モードq乗算群(要循環群)の生成元に対応する.］
  • AliceはXA、XA∈(1、q-1)
    • を生成する.
  • 計算YA=αXA mod q
  • Aの秘密鍵はXAであり、公開鍵は｛q、α, YA}
    • 公開鍵は信頼された公開センターディレクトリに存在します.どのユーザもアクセスできます.
    Bobに対しては、まず上記の中心ディレクトリに行ってAliceの公開鍵｛q,α, そして自分が送りたい明文Mをきれいに洗って準備します.
  • ランダム整数kを選択します.k∈[1,q-1]
  • は、自分の暗号文を解読することができる秘密鍵PrivatK=(YA)k mod qを計算する.αXA＊k mod q)
  • はMを平文ペア(C 1,C 2)に暗号化する.ここでC 1=αk mod q,C 2=PrivatK*M mod q
  • 明文ペアはAlice
    • に送信されます.
    Aliceは明文を受け取りました.
  • Private K=(C 1)XA mod q(つまり、XA mod q)αk*XA mod q)
  • M=C 2*Private K-1 mod q
    • ここに来てください.アルゴリズムの多くは掛け算、べき乗などの演算です.残りの肝心な内容は素数pの原根をどうやって探しますか?あるいは有限ドメインGF(p)の生成元をどうやって探しますか?グループという概念で議論します.pは素数で、Zp={1,2,3,…,p-1}を掛け算を考えて、0元素を抜きました.2つの定理:
  • Euler定理:Pとaをラッセルの二つの整数とすると、aがある.φ(p)＝1 mod p
  • ラグランジュの定理:Gを有限群とし、HをGのサブ群とし、124 Hを12464;G 12462を排除する.
    このような2つの概念を振り返ると、Gは群であり、a＿Gは、式a k＝eが成立する最小整数kを要素aの段と呼ぶ.群の段はその群の中の要素の個数を指す.注目すべきは、ある生成元であるサブ群を生成する.このサブ群の次数はこの要素の次数である.
    Zp中のすべての元素はpと相互素であるため、Oullによって定理され、Zp中のすべての元素の次数はp-1を超えない.φ(p)はp-1で、少なくともaがあります.φ(p)＝1 mod p)です.Zpのいずれかの要素に対して、この元素を生成元として形成される循環群は、S(群Sの次数が数値的にはこの元素の次数)として設定されています.群の閉鎖性から、SがZpのサブグループであることが分かります.ラグランジュの定理から、Zpの要素の次数は、必ず124 Zp−1の因子であることが分かります.
    したがって、aのような要素があれば、Kaの次数はp−1の平凡な因子(すなわち因子1または因子p−1)であると結論することができる.Aまたは単位元、または生成元は、Zpの単位元が1であるということを知っていますが、単位元の一意性によって、aが1でないとaは必ず生成元となります.問題は、p-1の因子が多いかもしれません.階段はp-1の平凡な要素ではないですか?
    このため、p-1の因子数が少ないように特殊な素数を構築しました.p-1=2*Qを取って、pは素数で、Qも素数です.Qは素数ですので、因子は1、Qだけです.p-1の因子は｛1、2、Q、p-1｝だけです.以上で明らかになりました.上記の条件を満たす素数pを見つけて、Zpの中でこのような元素aを探します.aの次数は2ではなく、Qではなく、a^2 mod pです.=1&a^Q mod p!=1、aが単位でない場合は、aは必ず元を生成します.
    注意Zpは必ずしも生成元があるとは限らないので、もし1から(p-1)までは上記の検査を経ても満足できないなら、もう一つの素数pを取りたいです.コード実現上の問題点は、mpzubupum(tmp.mt,6)==1をmpzubuplimeup(tmp.mt,6)=2に変更すると、本当に速いです.
    コードの実装
    #include
#include
#include
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                  
map ttp;    

//   start   end      
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         ，       ，  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    
            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) {}
};

/*
 *          name         m    
 *      (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);
}

//      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<>n;
    if (n > ttp["Alice"].p) cout<
      
» ./ElGamal 
Input the message: 1024
decrypt   result : 1024
    このブログとLJFさんの討論を参考にしました.
    • アルゴリズムの下書き
    ［.NET］intとbyte[]の相互変換【転】