密码学之ElGamal 数字签名 密钥产生 数字签名 验证 python实现

密码学之ElGamal 数字签名 密钥产生 数字签名 验证 python实现 ElGamal 数字签名 实验目的

1. 通过实验了解数字签名的过程（签名过程和认证过程），掌握 ElGamal签名方案。

实验原理 ElGamal 数字签名的实现过程 1密钥产生:Alice 要对一个消息签名。

• 她选择一个大素数 p 和一个本原根g。选择一个秘密整数 1 ≤ x ≤ p − 2 1leq x leq p-2 1≤x≤p−2，并且计算 y ≡ g x m o d    p yequiv g^x mod p y≡gxmodp, ( p , g , y ) (p,g,y) (p,g,y)公开。x 秘密保存。
  • 使得 a m ≡ 1 m o d    p a^mequiv1 mod p am≡1modp成立的最小正幂m满足 m = φ ( p ) m=varphi(p) m=φ(p),则称a是p的本原根。
  • 注：ElGamal 签名方案的安全性在于 x 的保密性。由于离散对数问题难解，很难由(p,g,y)确定 x.

2数字签名:Alice 签署消息 m

• 选择一个安全的随机数 k, 使得 g c d ( k , p − 1 ) = 1 gcd(k,p-1)=1 gcd(k,p−1)=1;
• 计算 r ≡ g k m o d    p r equiv g^k mod p r≡gkmodp;
• 计算 s ≡ k − 1 ( m − x r ) m o d    ( p − 1 ) s equiv k^{-1} (m-xr)mod (p-1) s≡k−1(m−xr)mod(p−1);
• Alice 签署的消息是三元组 ( m , r , s ) (m,r,s) (m,r,s);

3验证:Bob 确认签名

• 下载 Alice 的公钥 ( p , g , y ) (p,g,y) (p,g,y)；

• 计算 v 1 ≡ y r r s m o d    p v1 equiv y^rr^s mod p v1≡yrrsmodp和 v 2 ≡ g m m o d    p v2 equiv g^m mod p v2≡gmmodp；

• 当且仅当 v 1 ≡ v 2 m o d    p v1 equiv v2 mod p v1≡v2modp时，签名是有效的。

实验内容 ElGamal 数字签名

生成各自的密钥（注意素数 p 的选择，及 p 的本原根的选择），并公布公钥 ( p , g , y ) (p,g,y) (p,g,y)，A 和 B 之间约定签署的消息 m，A 署消息 m，将三元组 ( m , r , s ) (m,r,s) (m,r,s)发给 B，B 验证签名。

1密钥产生

import random


def gcd(a: int, b: int):
    """欧几里得算法求最大公约数"""
    while a != 0:
        a, b = b % a, a
    return b


def euler(n):
    """欧拉函数"""
    # 如果n是质数直接返回n-1
    if (n, 1) == 1:
        return n - 1
    m = 0
    for i in range(n):
        if gcd(i, n) == 1:
            m += 1
    return m


def getFirstPrimitiveRoot(p):
    """算出第一个本原根"""
    # 得到欧拉函数值m
    euler_n = euler(p)
    # 双循环
    for a in range(2, p):
        for m in range(2, p):
            # 第一个m满足a^m = 1 mod p 同时m = euler_n则a为第一个本原根
            if pow(a, m, p) == 1:
                # 如果最小的正幂a不为欧拉函数，进行下一轮循环
                if m == euler_n:
                    return a
                else:
                    break
    return False


def getAllPrimitiveRoot(p, first):
    primitiveRoot = []
    for i in range(p):
        # 若 i与p互素，即i是 p-1的简化剩余系一员
        if gcd(i, p - 1) == 1:
            # 将 原根 加入列表
            primitiveRoot.append(pow(first, i, p))
    return primitiveRoot


if __name__ == '__main__':
    p = 41
    firstp = getFirstPrimitiveRoot(p)
    pR = getAllPrimitiveRoot(p, firstp)
    print(pR)

    # 随机选择一个本原根g
    g = pR[random.randint(0, len(pR) - 1)]
    # 随机生成一个 x
    x = random.randint(1, p - 2)
    # 计算出 y = g^x mod p
    y = pow(g, x, p)

    print(f"公开(p,g,y)：{(p, g, y)}")
    print(f"秘密保存x ：{x}")

2数字签名

import random

# 第一步公开的信息
p, g = 521, 186
# 秘密保存的x
x = 401
# 签署的信息m
m = 1914168


def gcd(a: int, b: int):
    """欧几里得算法求最大公约数"""
    while a != 0:
        a, b = b % a, a
    return b


# 选择k 使得 gcd(k,p-1)=1
while True:
    k = random.randint(0, p - 1)
    if gcd(k, p - 1) == 1:
        break

# 计算 r = g^k mod p
r = pow(g, k, p)
# 求 k^-1

# 扩展欧几里得算法求逆 ki即为最终需要的逆元
ai, bi = k, p - 1
ki, ti, xi, yi = 1, 0, 0, 1  # 初始化s,t,x2,y2
while bi:
    qi, ri = divmod(ai, bi)
    ai, bi = bi, ri  # 求最大公约数
    ki, ti, xi, yi = xi, yi, ki - qi * xi, ti - qi * yi  # 辗转相除

# s = k^{-1} * (m-xr) mod (p-1)
s = ki * (m - x * r) % (p - 1)

print(f"Alice签署的消息(m,r,s)：{(m, r, s)}")

3验证

#  Alice 的公钥
p, g, y = 41, 11, 10
# Alice签署的消息
m, r, s = 168, 13, 0
# 计算 v1 v2 并比较
v1 = pow(y, r, p) * pow(r, s, p) % p
v2 = pow(g, m, p)

print(f"v1:{v1},v2:{v2}")
if v1 == v2:
    print("验证成功，签名有效")