elgamal密码是除了rsa之外最有代表性的公开密钥密码之一，它的安全性建立在离散对数问题的困难性之上，是一种公认安全的公钥密码。
设p为素数，若存在一个正整数α，使得α、α2、...、αp-1关于模p互不同余，则称α为模p的一个原根。于是有如下运算：
α的幂乘运算：
y=αx(mod p)，1≤x≤p-1
α的对数运算：
x=logαy，1≤y≤p-1
只要p足够大，求解离散对数问题时相当复杂的。离散对数问题具有较好的单向性。
1.随机地选择一个大素数p，且要求p-1有大素数因子，将p公开。
2.选择一个模p的原根α，并将α公开。
3.随机地选择一个整数d（1＜d＜p-1）作为私钥，并对d保密。
4.计算公钥y=αd(mod p)，并将y公开。
1.随机地选取一个整数k（1＜k＜p-1）。
2.计算u=yk(mod p)、c1=αk(mod p)、c2=um(mod p)。
3.取(c1,c2)作为密文。
1.计算v=c1d(mod p)。
2.计算m=c2v-1(mod p)。
实现elgamal算法，需要实现以下几个部分：
1.对大数的素数判定；
2.判断原根；
3.模指运算；
4.模逆运算。
已知a和m互素，如果d是满足ad=1(mod m)的最小正整数，则称d为a模m的阶，记为d=σm(a)。由于a和m互素，根据欧拉定理可知aφ(m)=1(mod m)，由此可以得到σm(a) | φ(m)。
若a是m的原根，则σm(a)=φ(m)。
根据上述两点，推出逆否命题：如果∃d | φ(m)且d≠φ(m)，使得ad=1(mod m)，则a不是模m的原根。所以判断a是否为模m的原根，最快的方法就是判断φ(m)的每一个因子d是否使得ad=1(mod m)。如果满足ad=1(mod m)的d=φ(m)，则a是模m的原根。
e.m.判断2是不是模11的原根
φ(11)=10
10的因子有1、2、5、10，所以：
2(mod 11)=2
22(mod 11)=4
25(mod 11)=10
210(mod 11)=1
因此，2是模11的原根。
由于elgamal密码的安全性建立在gf(p)上离散对数的困难性之上，而目前尚无求解gf(p)上离散对数的有效算法，所以在p足够大时elgamal密码是安全的。理想情况下p为强素数，p-1=2q，q为大素数。
为了安全加密所使用的k必须是一次性的。如果长期使用同一个k加密的话，就可能被攻击者获取，从而根据v=u=yk(mod p)，m=c2v-1(mod p)而得到明文。另外，使用同一个k加密不同的明文m和m'，则由于
如果攻击者知道m，则很容易求出m'。此外，k选取时还要保证u=yk(mod p)≠1。
我要评论 1 do {
2 p = biginteger.probableprime(100, new random());
3 } while (p.subtract(biginteger.one).divide(new biginteger("2")).isprobableprime(100));
4 do {
5 alpha = new biginteger(100, new random());
6 } while (! isorigin(alpha, p));
7 do {
8 d = new biginteger(100, new random());
9 } while (d.compareto(biginteger.one) != 1 || d.compareto(p.subtract(biginteger.one)) != -1);
10 y = alpha.modpow(d, p);
1 /**
2 * 加密
3 * @param m
4 * @return
5 */
6 biginteger[] encrypt(biginteger m) {
7 biginteger[] c = new biginteger[2];
8 biginteger k, u;
9 do {
10 do {
11 k = new biginteger(100, new random());
12 } while (k.compareto(biginteger.one) != 1 || k.compareto(p.subtract(biginteger.one)) != -1);
13 u = y.modpow(k, p);
14 } while (u.intvalue() != 1);
15 c[0] = alpha.modpow(k, p);
16 c[1] = u.multiply(m).mod(p);
17 return c;
18 }
1 /**
2 * 解密
3 * @param c
4 * @return
5 */
6 biginteger decrypt(biginteger[] c) {
7 biginteger v = c[0].modpow(d, p);
8 biginteger m = c[1].multiply(v.modpow(new biginteger("-1"), p)).mod(p);
9 return m;
10 }
1 /**
2 * 判断a是否为模m的原根，其中m为素数
3 * @param a
4 * @param m
5 * @return
6 */
7 static boolean isorigin(biginteger a, biginteger m) {
8 if (a.gcd(m).intvalue() != 1) return false;
9 biginteger i = new biginteger("2");
10 while (i.compareto(m.subtract(biginteger.one)) == -1) {
11 if (m.mod(i).intvalue() == 0) {
12 if (a.modpow(i, m).intvalue() == 1)
13 return false;
14 while (m.mod(i).intvalue() == 0)
15 m = m.divide(i);
16 }
17 i = i.add(biginteger.one);
18 }
19 return true;
20 }
p=2579
α=2
d=765
m=1299
k=853
张焕国，唐明.密码学引论（第三版）.武汉大学出版社，2015年
如对本文有疑问， 点击进行留言回复！！
Android 4.0使用Kotlin调用C语言以及汇编语言
Java Class.forName()用法和newInstance()方法原理解析
网友评论