-
Notifications
You must be signed in to change notification settings - Fork 4.7k
Expand file tree
/
Copy pathrsa.py
More file actions
133 lines (98 loc) · 3 KB
/
rsa.py
File metadata and controls
133 lines (98 loc) · 3 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
130
131
132
133
"""
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 secrets
def _extended_gcd(a: int, b: int) -> tuple[int, int, int]:
old_r, r = a, b
old_s, s = 1, 0
old_t, t = 0, 1
while r != 0:
q = old_r // r
old_r, r = r, old_r - q * r
old_s, s = s, old_s - q * s
old_t, t = t, old_t - q * t
return old_r, old_s, old_t
def _modinv(a: int, m: int) -> int:
g, x, _ = _extended_gcd(a, m)
if g != 1:
raise ValueError(f"Modular inverse does not exist: gcd({a}, {m}) = {g}")
return x % m
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
(ignored, kept for API compatibility).
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)
"""
def _gen_prime(k: int, seed: int | None = None) -> int:
"""Generate a random prime with k bits.
Args:
k: The number of bits.
seed: Unused, kept for API compatibility.
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)
)
while True:
key = secrets.randbelow(int(2**k) - int(2 ** (k - 1))) + int(2 ** (k - 1))
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))