加密算法之ElGamal算法
admin ElGamal算法既能用于數(shù)據(jù)加密也能用于數(shù)字簽名，其安全性依賴(lài)于計(jì)算有限域上離散對(duì)數(shù)這一難題。
密鑰對(duì)產(chǎn)生辦法。首先選擇一個(gè)素?cái)?shù)p，兩個(gè)隨機(jī)數(shù), g 和x，g, x < p, 計(jì)算 y = g^x ( mod p )，則其公鑰為 y, g 和p。私鑰是x。g和p可由一組用戶(hù)共享。
ElGamal用于數(shù)字簽名。被簽信息為M，首先選擇一個(gè)隨機(jī)數(shù)k, k與 p - 1互質(zhì)，計(jì)算a = g^k ( mod p )
再用擴(kuò)展 Euclidean 算法對(duì)下面方程求解b： M = xa + kb ( mod p - 1 )
簽名就是( a, b )。隨機(jī)數(shù)k須丟棄。
驗(yàn)證時(shí)要驗(yàn)證下式：
y^a * a^b ( mod p ) = g^M ( mod p )
同時(shí)一定要檢驗(yàn)是否滿(mǎn)足1<= a < p。否則簽名容易偽造。
ElGamal用于加密。被加密信息為M，首先選擇一個(gè)隨機(jī)數(shù)k，k與 p - 1互質(zhì)，計(jì)算a = g^k ( mod p )
b = y^k M ( mod p )
( a, b )為密文，是明文的兩倍長(zhǎng)。解密時(shí)計(jì)算M = b / a^x ( mod p )
ElGamal簽名的安全性依賴(lài)于乘法群(IFp)* 上的離散對(duì)數(shù)計(jì)算。素?cái)?shù)p必須足夠大，且p-1至少包含一個(gè)大素?cái)?shù)
因子以抵抗Pohlig & Hellman算法的攻擊。M一般都應(yīng)采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依賴(lài)于p和g，若選取不當(dāng)則簽名容易偽造，應(yīng)保證g對(duì)于p-1的大素?cái)?shù)因子不可約。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻擊方法和對(duì)策。ElGamal的一個(gè)不足之處是它的密文成倍擴(kuò)張。
美國(guó)的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是經(jīng)ElGamal算法演變而來(lái)。
