Recently Updated
Cryptography 450: Super Safe RSA 2
Challenge
Wow, he made the exponent really large so the encryption MUST be safe, right?!
Connect with nc 2018shell1.picoctf.com 47295.
Solution
We connect to the service and get a set of RSA parameters
1
2
3
4
5
$ nc 2018shell1.picoctf.com 47295
c: 25768046345727464502597520221366212769169471825365967634630931748647232910338751793422711728554855006367814407810621525958992286707789113053995635463407498955539964935155035496760107228272520704862671855993478994453136635235568232731879221074380473331175949428476338755714015215366964946019773206537518303256
n: 62521990254455432739739098327679950602675797333442676086848188780355806233664586212815747058830242509072941471918606448376223071702950597243409185734520501054880754651705541198856749099694484071501292887111220558418712756088261843103763153296918795811242273836779338023623847026392962143077450363442487934689
e: 11376394003149076634899198125602078382240701942434104587266195449986160326784109595920286001442706286840942170874916183177235151594636401912319064648735169214636981775404170094629988884687077578483030764227613917415801022670556750159920041801902797676162135948461328656879638396798506273263833645665345860373
This uses an extremely large public exponent (e) which is potentially just as bad as using a very small one (like the Safe RSA challenge) and might imply a very small private exponent (d). If that is the case, we can use Wiener’s attack to find d given e and N.
We find this python library that uses some results about continued fractions approximations to infer the private key from public key in the cases the encryption exponent is too small or too large. We use it to find d:
(see also supersafersa2.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
import gmpy2
def isqrt(n):
'''
Calculates the integer square root
for arbitrary large nonnegative integers
'''
if n < 0:
raise ValueError('square root not defined for negative numbers')
if n == 0:
return 0
a, b = divmod(bitlength(n), 2)
x = 2**(a+b)
while True:
y = (x + n//x)//2
if y >= x:
return x
x = y
def is_perfect_square(n):
'''
If n is a perfect square it returns sqrt(n),
otherwise returns -1
'''
h = n & 0xF # last hexadecimal "digit"
if h > 9:
return -1 # return immediately in 6 cases out of 16.
# Take advantage of Boolean short-circuit evaluation
if (h != 2 and h != 3 and h != 5 and h != 6 and h != 7 and h != 8):
# take square root if you must
t = isqrt(n)
if t*t == n:
return t
else:
return -1
return -1
def rational_to_contfrac(x, y):
'''
Converts a rational x/y fraction into
a list of partial quotients [a0, ..., an]
'''
a = x//y
pquotients = [a]
while a * y != x:
x, y = y, x-a*y
a = x//y
pquotients.append(a)
return pquotients
def convergents_from_contfrac(frac):
'''
computes the list of convergents
using the list of partial quotients
'''
convs = []
for i in range(len(frac)):
convs.append(contfrac_to_rational(frac[0:i]))
return convs
def contfrac_to_rational(frac):
'''Converts a finite continued fraction [a0, ..., an]
to an x/y rational.
'''
if len(frac) == 0:
return (0, 1)
num = frac[-1]
denom = 1
for _ in range(-2, -len(frac)-1, -1):
num, denom = frac[_]*num+denom, num
return (num, denom)
def bitlength(x):
'''
Calculates the bitlength of x
'''
assert x >= 0
n = 0
while x > 0:
n = n+1
x = x >> 1
return n
def hack_RSA(e, n):
'''
Finds d knowing (e,n)
applying the Wiener continued fraction attack
'''
frac = rational_to_contfrac(e, n)
convergents = convergents_from_contfrac(frac)
for (k, d) in convergents:
# check if d is actually the key
if k != 0 and (e*d-1) % k == 0:
phi = (e*d-1)//k
s = n - phi + 1
# check if the equation x^2 - s*x + n = 0
# has integer roots
discr = s*s - 4*n
if(discr >= 0):
t = is_perfect_square(discr)
if t != -1 and (s+t)%2 == 0:
print("Hacked!")
print(d)
return d
if __name__ == "__main__":
n = 62521990254455432739739098327679950602675797333442676086848188780355806233664586212815747058830242509072941471918606448376223071702950597243409185734520501054880754651705541198856749099694484071501292887111220558418712756088261843103763153296918795811242273836779338023623847026392962143077450363442487934689
e = 11376394003149076634899198125602078382240701942434104587266195449986160326784109595920286001442706286840942170874916183177235151594636401912319064648735169214636981775404170094629988884687077578483030764227613917415801022670556750159920041801902797676162135948461328656879638396798506273263833645665345860373
c = 25768046345727464502597520221366212769169471825365967634630931748647232910338751793422711728554855006367814407810621525958992286707789113053995635463407498955539964935155035496760107228272520704862671855993478994453136635235568232731879221074380473331175949428476338755714015215366964946019773206537518303256
# find d using wieners algorithm
d = hack_RSA(e, n)
# use d to decrypt message
pt = gmpy2.powmod(c, d, n)
print(pt)
print("".join([chr((pt >> j) & 0xff) for j in reversed(range(0, 1000 << 3, 8))]))
when we run this we get the flag:
1
2
3
4
5
$ python supersafersa2.py
Hacked!
65537
264003602020102370693041857442610586342633199683725005643958437442448465210344626586049655752028764806997162365
picoCTF{w@tch_y0ur_Xp0n3nt$_c@r3fu11y_6498999}
Flag
picoCTF{w@tch_y0ur_Xp0n3nt$_c@r3fu11y_6498999}