blob: 0d5b71942bdb6475287243e0c21bc693b03c6a54 (
plain)
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
|
# Google Beginner CTF: ReadySetAction
**SPOILER WARNING: Go play the CTF at
[capturetheflag.withgoogle.com](https://capturetheflag.withgoogle.com/) first**
The challenge was a short python script with the following code:
```py
from Crypto.Util.number import *
flag = b"REDACTED"
p = getPrime(1024)
q = getPrime(1024)
n = p*q
m = bytes_to_long(flag)
c = pow(m,3,n)
print(c)
print(n)
#154780 ... 6709
#210348 ... 4477
#(i removed both 617 digit long numbers here)
```
It was immediatly obvious to me that this has to do with RSA cryptography
because it multiplies large primes and then does some powmod magic. Because I
didn't remember exactly how RSA worked, I quickly read the Wikipedia article
again - specifically section
[4.1 Attacks against plain RSA](https://en.wikipedia.org/wiki/RSA_%29cryptosystem%29#Attacks_against_plain_RSA)
The first item already seems like the solution:
> When encrypting with low encryption exponents (e.g., e = 3) and small values
> of the m (i.e., m < n1/e), the result of me is strictly less than the modulus
> n. In this case, ciphertexts can be decrypted easily by taking the eth root of
> the ciphertext over the integers.
Which would mean that $\sqrt[3]{c}$ is a solution _if_ $m$ is small enough.
However
$c = m^3 \mod n \\$
so the exponentiation could yield a much higher result that we dont get because
it is wrapped at $n$. So we can try out how often it wrapped:
$m = \sqrt[3]{c + x*n} \quad x \in \N\\$
where $x$ can be brute-forced if $m$ is sufficiently small. Back in python it
looks like this:
```py
c = ...
n = ...
# simple but bad binary search for n-th root
def nth_root(c,e):
high = 1
while high**e < c:
high *= 2
low = 0
mid = 0
last_mid = 0
while mid**e != c:
mid = (low + high) // 2
if last_mid == mid:
return 0 # i use 0 to indicate a failure
if mid**e > c:
high = mid
else:
low = mid
last_mid = mid
return mid
for x in range(100000):
m = nth_root(c + n*x, e)
# the probability of finding a perfect cube number is low, so any result is what we want
if m != 0: print(long_to_bytes(m))
```
Thats it! With $x=1831$ we get our flag: `CTF{34sy_RS4_1s_e4sy_us3}`
|
