forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrsa.py
More file actions
129 lines (95 loc) · 2.79 KB
/
rsa.py
File metadata and controls
129 lines (95 loc) · 2.79 KB
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
"""
RSA Encryption Algorithm
Implements RSA key generation, encryption, and decryption. RSA uses separate
public and private keys where ((x^e)^d) % n == x % n.
Reference: https://en.wikipedia.org/wiki/RSA_(cryptosystem)
Complexity:
Time: O(k^3) for key generation (k = bit length)
Space: O(k)
"""
from __future__ import annotations
import random
def generate_key(k: int, seed: int | None = None) -> tuple[int, int, int]:
"""Generate an RSA key triplet (n, e, d).
Args:
k: The number of bits in the modulus n.
seed: Optional random seed for reproducibility.
Returns:
A tuple (n, e, d) where n is the modulus, e is the encryption
exponent, and d is the decryption exponent.
Examples:
>>> n, e, d = generate_key(16, seed=42)
"""
def _modinv(a: int, m: int) -> int:
"""Calculate the modular inverse of a mod m.
Args:
a: The integer.
m: The modulus.
Returns:
b such that (a * b) % m == 1.
"""
b = 1
while (a * b) % m != 1:
b += 1
return b
def _gen_prime(k: int, seed: int | None = None) -> int:
"""Generate a random prime with k bits.
Args:
k: The number of bits.
seed: Optional random seed.
Returns:
A prime number.
"""
def _is_prime(num: int) -> bool:
if num == 2:
return True
return all(
num % i != 0
for i in range(2, int(num**0.5) + 1)
)
random.seed(seed)
while True:
key = random.randrange(int(2 ** (k - 1)), int(2**k))
if _is_prime(key):
return key
p_size = k / 2
q_size = k - p_size
e = _gen_prime(k, seed)
while True:
p = _gen_prime(p_size, seed)
if p % e != 1:
break
while True:
q = _gen_prime(q_size, seed)
if q % e != 1:
break
n = p * q
totient = (p - 1) * (q - 1)
d = _modinv(e, totient)
return int(n), int(e), int(d)
def encrypt(data: int, e: int, n: int) -> int:
"""Encrypt data using RSA public key.
Args:
data: The plaintext integer.
e: The encryption exponent.
n: The modulus.
Returns:
The encrypted integer.
Examples:
>>> encrypt(7, 23, 143)
2
"""
return pow(int(data), int(e), int(n))
def decrypt(data: int, d: int, n: int) -> int:
"""Decrypt data using RSA private key.
Args:
data: The encrypted integer.
d: The decryption exponent.
n: The modulus.
Returns:
The decrypted plaintext integer.
Examples:
>>> decrypt(2, 47, 143)
7
"""
return pow(int(data), int(d), int(n))