上个星期日，在公司做完事，上网无意之中看到QuipuKit，一个java faces的商用组件。查看之下发觉好像还不错的样子，450美刀一份。想起来自resin 3.1.x破解之后，好像好久没反编译过东西了，碰巧这个东西的试用版还是全功能的，就拉下来看了一下。很快就定位了注册验证的部分。用的是ElGamal算法（离散对数问题），注册信息用ElGamal签名之后，通过公钥验证。本来以为会是RSA或是DSA的，以前没接触过ElGamal，于是本着探索的精神，去挖了一下这个算法。原理性的东西不多写了，和RSA有点像，大数，乘方，模运算，三者混合而成，签名过程会产生两个Signature，然后目的端用一个等式验证。

a = g^k ( mod p )
再用扩展 Euclidean 算法对下面方程求解b：

M = xa + kb ( mod p - 1 )

签名就是( a, b )。随机数k须丢弃。
验证时要验证下式：

y^a * a^b ( mod p ) = g^M ( mod p )

同时一定要检验是否满足1<= a < p。否则签名容易伪造。
ElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算

a = g^k ( mod p )
b = y^k M ( mod p )

( a, b )为密文，是明文的两倍长。解密时计算

M = b / a^x ( mod p )

　　ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数
因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。

QuipuKit用到签名部分，而且是以注册信息的SHA值来作为M，如果希望做个Keygen来意淫一下，那么需要抽换程序中的相关公钥，换上自己的，然后就可以随便写自己的注册信息了，当然自己用也可以直接跳过签名验证部分。

ElGamal算法已经被承认是优秀的，而且也有改进型，而它没有注册版权，虽然出现的时间比较早，但在1997年开始不受老美的出口限制。老美的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演
变而来。