python实现DSA加密算法

DSA（Digital Signature Algorithm）数字签名算法是一种用于数字签名和验证的标准，可以用于确保数据的完整性、真实性和不可抵赖性。下面是Python实现DSA加密算法的示例代码：

import hashlib
import random

# 生成一个大素数
def generate_prime_number(n):
    while True:
        p = random.getrandbits(n) | 1
        if is_prime(p):
            return p

# 判断一个数是否为素数
def is_prime(n):
    if n == 2 or n == 3:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

# 计算模反元素
def mod_inverse(a, p):
    for i in range(1, p):
        if (a * i) % p == 1:
            return i
    return None

# 生成密钥对
def generate_key_pair(n):
    q = generate_prime_number(n // 2)
    p = 2 * q + 1
    while not is_prime(p):
        q = generate_prime_number(n // 2)
        p = 2 * q + 1
    g = 2
    while pow(g, q, p) == 1:
        g += 1
    x = random.randint(1, q)
    y = pow(g, x, p)
    return (p, q, g, x, y)

# 签名
def sign(msg, p, q, g, x):
    h = int(hashlib.sha1(msg.encode()).hexdigest(), 16)
    k = random.randint(1, q)
    r = pow(g, k, p) % q
    s = (mod_inverse(k, q) * (h + x * r)) % q
    return (r, s)

# 验证签名
def verify(msg, signature, p, q, g, y):
    r, s = signature
    if not (0 < r < q and 0 < s < q):
        return False
    h = int(hashlib.sha1(msg.encode()).hexdigest(), 16)
    w = mod_inverse(s, q)
    u1 = (h * w) % q
    u2 = (r * w) % q
    v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
    return v == r

使用示例：

# 生成密钥对
p, q, g, x, y = generate_key_pair(1024)

# 要签名的消息
msg = 'hello world'

# 签名
signature = sign(msg, p, q, g, x)

# 验证签名
print(verify(msg, signature, p, q, g, y))  # True

需要注意的是，该示例代码中使用了SHA-1哈希算法，但实际上SHA-1已经被认为是不安全的，应该选择更安全的哈希算法，比如SHA-256。此外，该示例代码中的参数都是固定的，实际使用时需要根据具体情况进行调整。