📚关于ElGamal密码

• ElGamal公钥密码体制是T.ElGamal于1985年提出的，其基本思想正是借用了D-H密钥交换协议的设计思路。
• 基于数据困难问题——离散对数问题
  
• 具体过程如下：
  • 选取一个较大的素数p，再选取一个本原根g，并将p和g公开；
  • 随机选取整数a：1 ≤ a ≤ p-2，并计算出$A=g^a$，将A作为公开的加密密钥，将a作为保密的脱密密钥。
  • 明文：m, 1 ≤ m ≤p−1
    
    

📚实验目的

编程实现ElGamal公钥密码算法。

• 设EIGamal体制的公用素数q=71，其本原根α=7。
  • （a）若B的公钥YB=3，A选择的随机整数k=2，则M=30的密文是多少？
  • （b）若A选择的k值使得M=30的密文为C=(59,C2)，则整数C2是多少？

📚流程梳理

🐇Step1：实现快速幂取模运算

• 实现快速幂取模运算，返回 (base^exp) % mod。

  # 实现快速幂取模运算，返回 (base^exp) % mod
  def mod_exp(base, exp, mod):
     result = 1
     # 将底数取模，防止中间结果过大
     base = base % mod
     while exp > 0:  # 当指数大于0时循环
         if exp % 2 == 1:  # 若指数的当前位为1
             result = (result * base) % mod  # 将当前的底数乘到结果中，并对模取余
         exp = exp // 2  # 将指数右移一位，相当于除以2
         base = (base * base) % mod  # 底数取平方并对模取余
     return result
  

🐇Step2：求解问题一

# 公用素数q=71，其本原根α=7
q = 71
a = 7

# (a)若B的公钥YB=3，A选择的随机整数k=2，则M=30的密文是?
YB = 3
k = 2
M = 30
print("题一：")
C1 = mod_exp(a, k, q)
C2 = M * mod_exp(YB, k, q) % q
print("若B的公钥YB=3，A选择的随机整数k=2，则M=30的密文为：C=({}, {})".format(C1, C2))

🐇Step3：求解问题二

# (b)若A选择的k值使得M=30的密文为C=(59,C2)，则整数C2是?
print("题二：")
C1 = 59
for i in range(1, q - 1):
    temp = mod_exp(a, i, q) % q
    if temp == C1:
        print("此时的随机数k为：", i)
        k = i
        C2 = M * mod_exp(YB, k, q) % q
        print("若A选择的k值使得M=30的密文为C=(59,C2)，则整数C2是:",C2)

📚实验结果

参考博客：网络安全期末复习3】Diffie-Hellman密钥交换算法