rsa 模重复平方 蒙哥马利算法 中国剩余定理代码实现

以下是Python语言的代码实现：

1. RSA算法

加密：

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

# 生成RSA公私钥
key = RSA.generate(2048)

# 保存公私钥
private_key = key.export_key()
public_key = key.publickey().export_key()

# 使用公钥加密
cipher = PKCS1_OAEP.new(RSA.import_key(public_key))
ciphertext = cipher.encrypt(b'plaintext')

解密：

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

# 使用私钥解密
cipher = PKCS1_OAEP.new(RSA.import_key(private_key))
plaintext = cipher.decrypt(ciphertext)

2. 模重复平方算法

def mod_exp(base, exponent, modulus):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent //= 2
        base = (base * base) % modulus
    return result

3. 蒙哥马利算法

def montgomery_reduction(x, r, n, n_inv):
    # Step 1
    m = (x * r) % n
    # Step 2
    t = (x + m * n) * n_inv % r
    # Step 3
    if t >= r:
        return t - r
    else:
        return t

def mod_exp_montgomery(base, exponent, modulus):
    # Step 1
    r = 1
    while r < modulus:
        r <<= 1
    # Step 2
    n_inv = pow(modulus, -1, r)
    # Step 3
    base = (base * r) % modulus
    # Step 4
    x = r % modulus
    for i in reversed(bin(exponent)[2:]):
        if i == '1':
            x = montgomery_reduction(x * base, r, modulus, n_inv)
        base = montgomery_reduction(base * base, r, modulus, n_inv)
    # Step 5
    return montgomery_reduction(x, r, modulus, n_inv)

4. 中国剩余定理

def chinese_remainder_theorem(c, n):
    # Step 1
    N = 1
    for ni in n:
        N *= ni
    # Step 2
    x = 0
    for ni, ci in zip(n, c):
        Ni = N // ni
        Mi = pow(Ni, -1, ni)
        x += ci * Ni * Mi
    # Step 3
    return x % N