密码学之公钥密码体系(3):ElGamal算法

文章目录

      • 1. ElGamal算法
      • 2. ElGamal算法基本原理
          • 2.1 ElGamal密钥生成
          • 2.2 ElGamal加密过程
          • 2.3 ElGamal解密过程
          • 2.4 ElGamal签名过程
            • 2.4.1 签名:
            • 2.4.2 验签:
            • 2.4.3 具体案例:
          • 2.5 ElGamal算法软件算法实现的快慢

1. ElGamal算法

ElGamal算法是基于离散对数求解困难的加密体系。与RSA算法一样,都能用于数据加密和数据签名。但是两者的原理不一样,ELGmal算法基于离散对数问题,而RSA算法基于大数分级困难问题。此外,对于ElGamal算法对于使用相同的私钥,对相同的明文进行加密,每次得到的加密结果却不一样,这是ElGamal算法另一个重要特征。

2. ElGamal算法基本原理

2.1 ElGamal密钥生成
  1. 随机选择一个大素数 ppp,且要求 p − 1p-1p1有大素数因子。再选择一个模 ppp的本原元 ggg。将 ppp ggg公开。
  2. 随机选择一个整数 xxx作为私钥 2 ≤ x ≤ p − 22≤x≤ p-22xp2
  3. 计算y= g xmodpy=g^x mod p y=gxmodp
    yyy公钥
2.2 ElGamal加密过程
  1. 对明文 MMM进行加密,随机地选取一个整数 kkk 2 ≤ k ≤ p − 22≤k≤p-22kp2,并要求 kkk p − 1p-1p1互素
  2. 计算:
    a= g kmodpa=g^k mod p agkmodp b=M∗ y kmodpb=M*y^k mod p bMykmodp
  3. 密文对为 ( a , b )(a,b)a,b,并且密文的大小时明文的两倍。
2.3 ElGamal解密过程
  1. 由密文可得明文 MMM,计算
    M=b/ a xmodpM=b/a^x mod p M=b/axmodp
    其中 xxx为私钥。
  2. 解密过程和Diffie-Hellman密钥交换过程极为类似。
  3. 下面给出了加密和解密过程
2.4 ElGamal签名过程
2.4.1 签名:
  1. 对消息 MMM进行签名时,首先选择一个随机数 kkk,并要求 kkk p − 1p-1p1互素。
  2. 计算:
    a= g kmodpa=g^kmodp a=gkmodp
  3. 利用扩展欧几里得算法,求出 bbb:
    M=(xa+kb)mod(p−1)M=(xa+kb)mod(p-1) M=(xa+kb)mod(p1)
  4. 签名结果为(a,b)。需要注意的是,k需要保密。
2.4.2 验签:
  1. 需要验证下面公式成立:
    y a a bmodp= g Mmodpy^aa^bmodp=g^Mmodp yaabmodp=gMmodp
  2. 下面给出签名和验签的大致流程
  3. 需要注意的是,在每次使用ElGamal算法进行签名时,都需要更新随机数k。
2.4.3 具体案例:
  1. 选择 p = 11 , g = 2p=11,g=2p=11,g=2,私人秘钥 x = 8x=8x=8,计算:
    y= g xmodp=>y= 2 8mod11=3y=g^xmodp => y=2^8 mod 11 = 3 y=gxmodp=>y=28mod11=3
  2. 因此,公开秘钥是 y = 3 , g = 2 , p = 11y=3,g=2,p=11y=3,g=2,p=11
  3. 对消息 M = 5M=5M=5进行签名,首先随机选择随机数 k = 9k=9k=9,验证 g c d ( 9 , 10 ) = 1gcd(9,10)=1gcd9,10=1,计算:
    a= g kmodp= 2 9mod11=6a=g^kmodp=2^9mod11=6 a=gkmodp=29mod11=6
    利用欧几里得算法求 bbb:
    M=(ax+kbmod(p−1))M=(ax+kbmod(p-1))M=(ax+kbmod(p1)) 5=(8∗6+9∗b)mod10 5=(8*6 + 9*b)mod10 5=(86+9b)mod10
    求解得到 b = 3b=3b=3,于是签名对 ( a , b )(a,b)(a,b) ( 6 , 3 )(6,3)6,3
  4. 验签上述签名的正确性,只需要验证下面:
    y a a bmodp= g Mmodpy^aa^bmodp=g^Mmodp yaabmodp=gMmodp 3 6 6 3mod11= 2 5mod113^66^3mod11=2^5mod11 3663mod11=25mod11
2.5 ElGamal算法软件算法实现的快慢

具有160bit160 bit 160bit的指数的ElGamal算法对不同模数长度的快慢表