欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

ELGamal详解(Java实现)

程序员文章站 2022-09-30 18:37:43
GitHub ELGamal密码 ELGamal密码是除了RSA之外最有代表性的公开密钥密码之一,它的安全性建立在离散对数问题的困难性之上,是一种公认安全的公钥密码。 离散对数问题 设p为素数,若存在一个正整数α,使得α、α2、...、αp-1关于模p互不同余,则称α为模p的一个原根。于是有如下运算 ......

github


elgamal密码

  elgamal密码是除了rsa之外最有代表性的公开密钥密码之一,它的安全性建立在离散对数问题的困难性之上,是一种公认安全的公钥密码。

离散对数问题

  设p为素数,若存在一个正整数α,使得α、α2、...、αp-1关于模p互不同余,则称α为模p的一个原根。于是有如下运算:

  α的幂乘运算:

y=αx(mod p),1≤x≤p-1

  α的对数运算:

x=logαy,1≤y≤p-1

  只要p足够大,求解离散对数问题时相当复杂的。离散对数问题具有较好的单向性。


elgamal加解密算法

  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)、c1k(mod p)、c2=um(mod p)。

  3.取(c1,c2)作为密文。

解密

  1.计算v=c1d(mod p)。

  2.计算m=c2v-1(mod p)。


elgamal算法细节

  实现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密码的安全性

  由于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',则由于

ELGamal详解(Java实现)

如果攻击者知道m,则很容易求出m'此外,k选取时还要保证u=yk(mod p)≠1。


java实现

elgamal

 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

测试结果

ELGamal详解(Java实现)


参考文献

  张焕国,唐明.密码学引论(第三版).武汉大学出版社,2015年