-
Notifications
You must be signed in to change notification settings - Fork 0
/
cryptopals_39.py
executable file
·108 lines (79 loc) · 2.32 KB
/
cryptopals_39.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
#!/usr/bin/env python
from typing import Tuple
from Crypto.Util import number
from cryptopals_33 import modpow
def egcd(a: int, b: int) -> Tuple[int, int, int]:
"""Extended greatest common denominator.
Taken from:
https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
"""
if a == 0:
return b, 0, 1
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a: int, m: int) -> int:
"""Calculates the modular multiplicative inverse of a number `a` against
mod `m`.
Equivalent in Python 3.8+: `y = pow(x, -1, m)`
"""
g, x, y = egcd(a, m)
if g != 1:
raise Exception('Modular inverse does not exist')
else:
return x % m
def moddiv(a: int, b: int, m: int) -> int:
"""Divides a over b under modulo m.
"""
a = a % m
return (modinv(b, m) * a) % m
class RSA(object):
def __init__(self, key_len=1024):
"""
Arguments:
key_len (int):
Number of bits in each of p and q
"""
while True:
p = number.getPrime(key_len)
q = number.getPrime(key_len)
n = p * q # our modulo
et = (p - 1) * (q - 1) # "totient"
e = 3
try:
d = modinv(e, et)
break
except:
pass
self.p = p
self.q = q
self.n = n
self.e = e
self.d = d
def encrypt(self, plaintext: int) -> int:
return modpow(plaintext, self.e, self.n)
def decrypt(self, ciphertext: int) -> int:
return modpow(ciphertext, self.d, self.n)
if __name__ == '__main__':
print('Challenge #39 - Implement RSA')
# Public key is (e, n)
# Private key is (d, n)
rsa = RSA()
print(f'P: {rsa.p}')
print(f'Q: {rsa.q}')
# Encryption
inp = 45
c = rsa.encrypt(inp)
# Decryption
out = rsa.decrypt(c)
assert out == inp
# Silly, larger string
inp = b'a test string'
c = rsa.encrypt(int.from_bytes(inp, 'big'))
out = rsa.decrypt(c).to_bytes(len(inp), 'big')
assert inp == out
# NOTE: `n` must be less than the numeric input value for this to work
inp = rsa.n
c = rsa.encrypt(inp)
out = rsa.decrypt(c)
assert inp != out