Rabin加解密算法(python3)

Rabin加解密算法

详细代码如下：

# 空空
# dahouzi.cn
import random
from sympy import isprime


def decrypt_rabin(c, p, q):
    """
    解密 Rabin 密文

    Args:
        c (int): 密文
        p (int): 素数 p
        q (int): 素数 q

    Returns:
        tuple: 解密结果 M1, M2, M3, M4
    """
    n = p * q
    # 计算 m1, m2, m3, m4
    m1 = pow(c, (p + 1) // 4, p)
    m2 = (-m1) % p
    m3 = pow(c, (q + 1) // 4, q)
    m4 = (-m3) % q

    # 计算 a, b
    a = q * ModReverse(q, p)
    b = p * ModReverse(p, q)

    # 计算解密结果 M1, M2, M3, M4
    M1 = (a * m1 + b * m3) % n
    M2 = (a * m1 + b * m4) % n
    M3 = (a * m2 + b * m3) % n
    M4 = (a * m2 + b * m4) % n

    return M1, M2, M3, M4


def ModReverse(a, n):
    """
    计算模逆

    Args:
        a (int): 整数
        n (int): 模数

    Returns:
        int: a 在模 n 下的逆
    """
    arr = [0, 1]
    gcd = EX_GCD(a, n, arr)
    if gcd == 1:
        return (arr[0] % n + n) % n
    else:
        return -1


def EX_GCD(a, b, arr):
    """
    计算扩展欧几里得算法

    Args:
        a (int): 整数 a
        b (int): 整数 b
        arr (list): 结果数组

    Returns:
        int: 最大公约数
    """
    if b == 0:
        arr[0] = 1
        arr[1] = 0
        return a
    g = EX_GCD(b, a % b, arr)
    t = arr[0]
    arr[0] = arr[1]
    arr[1] = t - a // b * arr[1]
    return g


def rabin_encrypt(plaintext, p, q):
    """
    Rabin 加密

    Args:
        plaintext (int): 明文
        p (int): 素数 p
        q (int): 素数 q

    Returns:
        int: 密文
    """
    # 计算公钥 n
    n = p * q
    # 计算密文
    ciphertext = pow(plaintext, 2, n)
    return ciphertext


# 示例用法

p = 19
q = 23
plaintext = 183
ciphertext = rabin_encrypt(plaintext, p, q)
print("---------message-----------")
print("plaintext：", plaintext)
print("ciphertext：", ciphertext)

print("---------public key[n]、private key[p、q]------------")
print("p:", p)
print("q:", q)
print("n:", p * q)
#print("---------公钥n、私钥p、q------------")

# 解密
M1, M2, M3, M4 = decrypt_rabin(ciphertext, p, q)
print("---------Decrypt------------")
print("M1:", M1)
print("M2:", M2)
print("M3:", M3)
print("M4:", M4)
#print("---------解密------------")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124