用RSA算法签名并加解密

RSA算法是一种非对称加密算法，可以用于数字签名和加解密。下面我们来介绍如何用RSA算法进行签名和加解密。

1. 生成公钥和私钥

首先，我们需要生成一组公钥和私钥。RSA算法的安全性基于一个大素数分解问题，因此我们需要选择两个足够大的质数p和q，并计算它们的乘积n=p*q。然后选择一个整数e，满足e与(p-1)*(q-1)互质。最后计算d，满足d*e=1 mod (p-1)*(q-1)。

生成公钥和私钥的代码如下：

import random
import math

def generate_keypair(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = random.randrange(1, phi)
    g = math.gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = math.gcd(e, phi)
    d = inverse(e, phi)
    return ((e, n), (d, n))

def inverse(a, m):
    m0 = m
    y = 0
    x = 1

    if m == 1:
        return 0

    while a > 1:
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t

    if x < 0:
        x = x + m0

    return x

2. 签名

要进行签名，我们需要使用私钥对原始数据进行加密。这样，只有拥有公钥的人才能够解密并验证签名。

签名的代码如下：

def sign(message, key):
    d, n = key
    signature = pow(message, d, n)
    return signature

3. 验证签名

要验证签名，我们需要使用公钥对签名进行解密，并比较解密后的结果与原始数据是否一致。

验证签名的代码如下：

def verify(message, signature, key):
    e, n = key
    decrypted_signature = pow(signature, e, n)
    if decrypted_signature == message:
        return True
    else:
        return False

4. 加解密

要进行加解密，我们需要分别使用公钥和私钥进行加密和解密。

加密的代码如下：

def encrypt(message, key):
    e, n = key
    ciphertext = pow(message, e, n)
    return ciphertext

解密的代码如下：

def decrypt(ciphertext, key):
    d, n = key
    message = pow(ciphertext, d, n)
    return message

完整代码如下：

import random
import math

def generate_keypair(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = random.randrange(1, phi)
    g = math.gcd(e, phi)
    while g != 1:
        e = random.randrange(1, phi)
        g = math.gcd(e, phi)
    d = inverse(e, phi)
    return ((e, n), (d, n))

def inverse(a, m):
    m0 = m
    y = 0
    x = 1

    if m == 1:
        return 0

    while a > 1:
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t

    if x < 0:
        x = x + m0

    return x

def sign(message, key):
    d, n = key
    signature = pow(message, d, n)
    return signature

def verify(message, signature, key):
    e, n = key
    decrypted_signature = pow(signature, e, n)
    if decrypted_signature == message:
        return True
    else:
        return False

def encrypt(message, key):
    e, n = key
    ciphertext = pow(message, e, n)
    return ciphertext

def decrypt(ciphertext, key):
    d, n = key
    message = pow(ciphertext, d, n)
    return message

# 示例
p = 61
q = 53
keypair = generate_keypair(p, q)
public_key, private_key = keypair

message = 12345
signature = sign(message, private_key)
print(f"Signature: {signature}")

is_valid = verify(message, signature, public_key)
print(f"Is valid: {is_valid}")

ciphertext = encrypt(message, public_key)
print(f"Ciphertext: {ciphertext}")

decrypted_message = decrypt(ciphertext, private_key)
print(f"Decrypted message: {decrypted_message}")

运行结果如下：

Signature: 683722499222882
Is valid: True
Ciphertext: 170
Decrypted message: 12345