This repository has been archived by the owner on Jul 27, 2020. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 9
/
crack.py
65 lines (54 loc) · 1.46 KB
/
crack.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
def is_sqrt(number):
x = number
y = (x + number // x) // 2
while y < x:
x = y
y = (x + number // x) // 2
return x
def isqrt(n):
return int(n**.5)
def fermat(n, verbose=False):
a = is_sqrt(n)
b2 = a ** 2 - n
b = isqrt(n)
count = 0
while b ** 2 != b2:
if verbose:
print('%s. Trying: a=%s b2=%s b=%s' % (count, a, b2, b))
a += 1
b2 = a ** 2 - n
b = isqrt(b2)
count += 1
p = a + b
q = a - b
assert n == p * q
return p, q
def extended_gcd(aa, bb):
lastremainder, remainder = abs(aa), abs(bb)
x, lastx, y, lasty = 0, 1, 1, 0
while remainder:
lastremainder, (quotient, remainder) = remainder, divmod(lastremainder, remainder)
x, lastx = lastx - quotient * x, x
y, lasty = lasty - quotient * y, y
return lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise ValueError
return x % m
def crack(n, e, c, output_type='str'):
p, q = fermat(n)
phi = (p - 1) * (q - 1)
d = modinv(e, phi)
m = pow(c, d, n)
if output_type == 'int':
return m
elif output_type == 'str':
m = str(hex(m))[2:-1].decode("hex")
return m
elif output_type == 'hex':
m = str(hex(m))[2:-1]
return m
# Edit it, if you want
n, e, c = map(int, raw_input('n e c: ').split())
print crack(n, e, c)