forked from Unicuby/FMSI
-
Notifications
You must be signed in to change notification settings - Fork 0
/
rsa.py
141 lines (107 loc) · 2.63 KB
/
rsa.py
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
# -*- coding: utf-8 -*-
import math
class RSA:
"""
Constructor of the RSA ciphering object
@param pub_key the public key
@param priv_key the private key
"""
def __init__(self, pub_key, priv_key = None):
assert(isinstance(pub_key, tuple))
self.n = pub_key[0]
self.e = pub_key[1]
self.d = None
if priv_key:
assert(isinstance(pub_key, tuple))
assert(pub_key[0] == priv_key[0])
self.d = priv_key[1]
"""
Return the RSA public key
"""
def pub_key(self):
return (self.n, self.e)
"""
Return the RSA private key
"""
def priv_key(self):
return (self.n, self.d)
"""
Encrypt an integer using the public key
@param m integer
"""
def encrypt_int(self, m):
# (m ** e) % n
return pow(m, self.e, self.n)
"""
Encrypt a message using the public key
@param m the message
"""
def encrypt(self, m, encoding = "utf-8"):
if self.e is None:
return None # Not capable of encrypting
# Convert the string into an array of bytes
bstr = bytes(m, encoding)
# Encrypt each byte of the string individually
E = []
for c in bstr:
E.append(self.encrypt_int(c))
return E
"""
Decrypt an integer using the private key
@param m encrypted integer
"""
def decrypt_int(self, m):
# (m ** d) % n
return pow(m, self.d, self.n)
"""
Decrypt an array of integers using the private key
@param m an array of encrypted integers
"""
def decrypt(self, m, encoding = "utf-8"):
if self.d is None:
return None # Not capable of decrypting
s = ""
for v in m:
# Decrypt each integer
c = self.decrypt_int(v)
s += chr(c)
return s
"""
Generate RSA ciphering keys and object
Involved prime numbers need to be distinct.
Returns an object containing a couple of public and private keys.
@param p prime number
@param q prime number
"""
@classmethod
def generate(cls, p, q):
# Generate RSA ciphering keys
(pub_key, priv_key) = cls.generate_keys(p, q)
# Instantiate an object
return cls(pub_key, priv_key)
"""
Generate RSA ciphering keys
Involved prime numbers need to be distinct.
Returns a couple of public and private keys.
@param p a prime number
@param q a prime number
"""
@staticmethod
def generate_keys(p, q):
n = p * q
phi = (p - 1) * (q - 1)
# Find an integer matching the predicate
def findint(x, predicate):
def rfind(x):
if predicate(x): return x
return rfind(x + 1)
return rfind(x)
# Compute the inverse of x modulo phi
def inverse(x, phi):
val = 1
while (x * val) % phi != 1: val += 1
return val
# Compute the public and private exponents
e = findint(2, lambda x : math.gcd(x, phi) == 1)
d = inverse(e, phi)
return ((n, e), (n, d))