1 files changed, 84 insertions, 0 deletions
diff --git a/articles/2022-09-19-gctf-readysetaction.md b/articles/2022-09-19-gctf-readysetaction.md
new file mode 100644
index 0000000..0d5b719
--- /dev/null
+++ b/articles/2022-09-19-gctf-readysetaction.md
@@ -0,0 +1,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}`