2011年7月31日星期日

ElGamal encryption

Encryption有兩種,Private key encryptionPublic key encryption,在Public key encryption當中,最為人熟識的是基於數學上factorization problemRSA,而今次介紹的,是基於另一數學難題Discrete logarithm problem(DLP)的ElGamal encryption

DLP困難在於,

g i a mod p
當有g, i和p,要求得a是一件很容易的事。相反,有g, a和p,要求i就困難得多。i就像real number中求logg(a),但若a1和a2是兩連續數,這個log function所得的i1和i2並不連續,故稱作discrete。ElGamal encryption就是利用這困難作為public key encryption。

首先,generate private key/decryption key Dk = (p, r, a),p是prime number,r是p的primitive root,a是random number 2≤a<p。然後由private key Dk generate public key/encryption key Ek = (p, r, ra mod p)。當要encrypt message m時,先generate一個random number b 2≤b<p,然後

e 1 r b mod p
e 2 m · E k2 b mod p

Ek2即是public key第三個數。然後將這兩個數一併寄給收件人,當收件人decrypt時,只要

m e 2 · e 1 -a mod p

當然,這program並不能作production encryption之用,一來缺乏string/int encode/decode功能,二來速度問題尚未解決,但作範例也還可以。

大功告成。

沒有留言:

發佈留言