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
import random                                     # import random to use randint 
from Crypto.Util import number                    # import Crypto.Util.number to use getPrime

def Exgcd(r0, r1):						# 扩展欧几里得算法
    s0, s1 = 1, 0
    t0, t1 = 0, 1
    q, r = r0 // r1, r0 % r1
    while (r):
        s, t = s0 - q * s1, t0 - q * t1  
        s0, s1, t0, t1 = s1, s, t1, t
        r0, r1 = r1, r
        q, r = r0 // r1, r0 % r1
    return s1, t1, r1 
                              
count = 1                                   	#  count = number of divisions
def gcd(A, B):                         		#  Euclidean Algorithm, compute gcd(A, B) 
    if A % B == 0:
        return B
    global count
    count += 1
    r = A % B
    return gcd(B, r)


def GenKey(bitlen):                               # 生成密钥对
    p = number.getPrime(bitlen)                   # generate prime p
    q = number.getPrime(bitlen)                   # generate prime q
    n = p * q                                     # n = p * q
    phi_n = (p-1) * (q-1)                         # phi_n = (p-1) * (q-1)
    e = random.randint(0, phi_n - 1)              # randomly choose e
    while (gcd(e, phi_n) != 1):                   # if gcd(e, phi_n) != 1    
        e = random.randint(0, phi_n - 1)          # choose e again 
    [d, k, r] = Exgcd(e, phi_n)                   # use Exgcd(e, phi_n) to compute d
    d = d % phi_n                                 # d = d % phi_n
    return n, e, d

def fastPowMod(b,n,m):					# 快速模逆
    b = b % m
    a = 1
    while (n):
        if n & 1:                                 
            a = (a * b) % m                                     
        n>>=1                                      
        b = (b * b) % m
    return a

def Enc(m, e, n):
    return fastPowMod(m, e, n)

def Dec(c, d, n):
    return fastPowMod(c, d, n)

def str_to_int(s):
        b = str.encode(s)                    # str to bytes
        return int.from_bytes(b, 'big')      # bytes to int

def int_to_str(i, str_len):              # str_len is the length of str converted
    b = i.to_bytes(str_len, 'big')       # convert int to bytes 
    return bytes.decode(b)               # convert bytes to str 


if __name__ == '__main__':                        # main function
    [n, e, d] = GenKey(512)
    print("\nn = %d\ne = %d\nd = %d\n" %(n,e,d))  # print n, e, d
    m = input("Input m(digits): ")                # input the message m(数字形式)
    print("\n    m = %s\n" %m)                    # print m 
    c = Enc(int(m),e,n)                           # encrypt m 
    print("c = %d\n" %c)                          # print the ciphertext c
    m_dec = Dec(c,d,n)                            # decrypt c
    print("m_dec = %d\n" %m_dec)                  # print the decrypted message m_dec
    print( int(m) == m_dec )

    m = input("Input m(string): ")
    print("\n    m = %s\n" %m)
    m_len = len(m)
    c = Enc(str_to_int(m),e,n)
    print("c = %s\n" %c)
    m_dec = Dec(c,d,n)
    print("m_dec = %s\n" %int_to_str(m_dec,m_len))