MENU

ELGamal算法

December 13, 2020 • Read: 30 • 编程之路,密码学

一、基本概念

  • 基于离散对数问题
  • 非对称加密算法(公钥加密、私钥解密)
  • 乘法同态算法
  • 生成的密文长度是明文的两倍,且每次加密后都会在密文中生成一个随机数K

1、离散对数问题

一种基于同余运算和原根的一种对数运算

原根:设素数$p$,若存在一个正整数$α$,使得$α,α^2,...,α^{p-1}$关于模$p$互斥(不同余),则称$α$为模$p$的一个原根。

于是有如下运算:

$α$的幂乘运算:

$$ y = α^x(mod\ p), 1\le x\le p-1 $$

$α$的对数运算:

$$ x=log_α y,1 \le y \le p-1 $$

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

单向函数 是一种具有下述特点的单射函数:对于每一个输入,函数值都容易计算(多项式时间),但是给出一个随机输入的函数值,算出原始输入却比较困难(无法在多项式时间内使用确定性图灵机计算)。 单向函数是否存在仍然是计算机科学中的一个开放性问题。事实上,如果单向函数存在,将证明复杂性类P/NP问题中,P不等于NP。

2、ELGamal加解密算法

0x01 准备公钥和私钥

  1. 随机地选择一个大素数$p$,且要求$p-1$有大素数因子,$p$公开。
  2. 选择一个模$p$的原根$α$,$α$公开。
  3. 随机选择一个整数$d\ (1\lt d\lt p-1)$作为私钥,$d$保密。
  4. 计算$y=α^d(mod\ p)$作为公钥,$y$公开。

|符号|含义|是否公开|
|-|-|-|
|$p$|大素数($p-1$有大素数因子)|公开|
|$α$|$p$的原根|公开|
|$d$|私钥$(1\lt d\lt p-1)$|保密|
|$y$|公钥 $y=α^d(mod\ p)$|公开|

0x02 加密

对明文 $M$ 进行加密

  1. 随机地选取一个整数$k(1<k<p-1)$。
  2. 计算$U=y^k(mod\ p)、C1=α^k(mod\ p)、C2=MU(mod\ p)$。
  3. 取$(C1,C2)$作为密文。

0x03 解密

$M= C_2/C_1^d\ (mod\ p)=C_2{C_1^d}^{-1}(mod\ p)$。

3、实例

选取素数$p=150001$,原根$α=7$,私钥$d = 113$

=> $y = α^d\ \% p = 66436$

加密:

随机数$k = 1000$,明文$M = 809$。

=> $C_1 = α^k\ (mod\ p) = 90429$

=> $C_2 = MU = M·y^k\ \%p = 15061$

=> $(c1,c2)=(90429,15061)$

解密:

${C_1^d} = 4654$

${C_1^d}^{-1} = 4654^{-1} = 80802 (mod\ p)$

=> 得出: $M = C_2{C_1^d}^{-1} (mod\ p) = 15061 * 80802 mod\ p = 809$

4、安全性问题

由于ELGamal密码的安全性建立在GF(p)上离散对数的困难性之上,而目前尚无求解GF(p)上离散对数的有效算法,所以在$p$足够大时ELGamal密码是安全的。理想情况下p为强素数,$p-1=2q$,$q$为大素数。

为了安全加密所使用的k必须是一次性的。如果长期使用同一个$k$加密的话,就可能被攻击者获取,从而根据$V=U=y^k(mod\ p)$,$M=C_2V^{-1}(mod\ p)$而得到明文。另外,使用同一个$k$加密不同的明文$M$和$M'$,则由于$\frac{C_2}{C_2'} = \frac{M}{M'}$,如果攻击者知道$M$,则很容易求出$M'$。此外,$k$选取时还要保证$U=y^k(mod\ p)≠1$。

二、算法实现

1、算法细节

0x01 判断原根

已知$a$和$m$互素,如果$d$是满足$a^d=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)$,使得$a^d=1(mod\ m)$,则$a$不是模$m$的原根。

所以判断$a$是否为模$m$的原根,最快的方法就是判断$φ(m)$的每一个因子$d$是否使得$a^d=1(mod\ m)$。如果不存在这样的$d$,则$a$是模$m$的原根。

0x02 实例:判断2是不是模11的原根

$φ(11)=10$,$10$的因子有$1、2、5、10$,

$2^1(mod\ 11)=2$、$2^2(mod\ 11)=4$、$2^5(mod\ 11)=10$、$2^{10}(mod\ 11)=1$

因此,$2$是模$11$的原根。

2、Java实现

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Random;

public class ELGamal {

    static BigInteger p, alpha, d, y;

    public static void main(String[] args) {
        init();
        BigInteger M = new BigInteger("809");
        BigInteger[] C = encrypt(M);
        System.out.println(Arrays.toString(C));
        BigInteger M2 = decrypt(C);
        System.out.println(M2);
    }

    /**
     * 初始化参数:素数p、原根α、私钥d,公钥y
     */
    private static void init(){
        do {
            p = BigInteger.probablePrime(10, new Random());
        } while (p.subtract(BigInteger.ONE).divide(new BigInteger("2")).isProbablePrime(100)); // (p-1)/2可能是个素数
        do {
            alpha = new BigInteger(10, new Random());
        } while (! isOrigin(alpha, p)); // 判断是否是原根
        do {
            d = new BigInteger(10, new Random()); // 私钥
        } while (d.compareTo(BigInteger.ONE) <= 0 || d.compareTo(p.subtract(BigInteger.ONE)) >= 0);
        //p = BigInteger.valueOf(150001); alpha = BigInteger.valueOf(7); d = BigInteger.valueOf(113);
        y = alpha.modPow(d, p); // 公钥y = alpha^d %p
        System.out.println("p = " + p + ", alpha = " + alpha + ", d = " + d + ", y = " + y);
    }

    /**
     * 加密
     * @return (C0, C1)
     */
    private static BigInteger[] encrypt(BigInteger M) {
        BigInteger[] C = new BigInteger[2]; // C0 C1
        BigInteger k, U;
        do {
            do {
                k = new BigInteger(10, new Random());
            } while (k.compareTo(BigInteger.ONE) <= 0 || k.compareTo(p.subtract(BigInteger.ONE)) >= 0); // 必须保证 k > 1 && k < p - 1
            U = y.modPow(k, p);
        } while (U.intValue() == 1);
        //k = BigInteger.valueOf(1000);
        System.out.println("k = " + k);
        C[0] = alpha.modPow(k, p); // C0 = α^k
        C[1] = U.multiply(M).mod(p); // C1 = MU %p
        return C;
    }

    /**
     * 解密
     */
    private static BigInteger decrypt(BigInteger[] C) {
        BigInteger V = C[0].modPow(d, p); // C0^d
        BigInteger M = C[1].multiply(V.modPow(new BigInteger("-1"), p)).mod(p); // C1 * C0^-1 mod p
        return M;
    }

    /**
     * 判断a是否为模m的原根,其中m为素数
     *
     * **判断$φ(m)$的每一个因子$d$是否使得$a^d=1(mod\ m)$。如果不存在这样的$d$,则$a$是模$m$的原根。**
     */
    private static boolean isOrigin(BigInteger a, BigInteger m) {
        if (a.gcd(m).intValue() != 1) return false;
        BigInteger i = new BigInteger("2");
        while (i.compareTo(m.subtract(BigInteger.ONE)) < 0) {
            if (m.mod(i).intValue() == 0) { // 判断因子
                if (a.modPow(i, m).intValue() == 1)
                    return false; // 如果 a^因子 == 1,说明不是原根
                while (m.mod(i).intValue() == 0)
                    m = m.divide(i); // 把因子除尽
            }
            i = i.add(BigInteger.ONE); // i++
        }
        return true;
    }
}

三、ELGamal数字签名

整数模 n 乘法群:在同余理论中,模 $**n**$ 的互质同余类成一个乘法群,称为整数模 n 乘法群翻译成人话就是:在$[1,n-1]$区间内互质的数组成例如:模$4$的乘法群 $\{1, 3\}$、模$8$的乘法群 $\{1, 3, 5, 7\}$、模 $16$ 乘法群$\{1,3,5,7,9,11,13,15\}$

0x01 系统初始化

选取一个大的素数$p$,$g$是GF(p)的生成元,$p,g$公开

0x02 数字签名

假定要发送消息$m \in [1, p-1]$

  1. 随机选取整数$x$,$1≤x≤p-2$,计算$y=g^x(mod p)$,$y$是公开密钥,而$x$是保密密钥。
  2. 随机选取 $k \in [1, p-1]$,且$gcd(k, p-1) = 1$,即$k,p$互质
  3. 计算$r,s$,$r = g^k\ mod \ p$,$s = k^{-1}(m-xr)\ mod\ p$
  4. $(m,rs)$即为对消息$m$的数字签名

0x03 签名验证

公开的变量有$p, g, y$

  1. 计算$left$, $left = g^m\ mod\ p$
  2. 计算$right$, $right = y^rr^s\ mod\ p$
  3. 比较$left$和$right$,相等则验证通过。

参考资料:
ELGamal详解(Java实现)

- - - 结束 - - -
  • 文章标题:ELGamal算法
  • 文章链接:https://blog.canye365.cn/archives/288.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: February 9, 2021