add writeup for asis19/serifin

diff --git a/writeups/mla/asis19.md b/writeups/mla/asis19.md
index cffe87ce533b3ec029e3b5241d1e33f6f893cdd9..c6ae05bd48568c1b3b0598336defca1324b89041 100644 (file)
--- a/writeups/mla/asis19.md
+++ b/writeups/mla/asis19.md
@@ -143,3 +143,34 @@ Performance-wise, I am sure there are some possible improvements ;).
 
 [1]: https://github.com/p4-team/ctf/tree/master/2019-11-16-asis-finals/close_primes
 [2]: https://gmpy2.readthedocs.io/en/latest/mpfr.html#contexts
+
+
+## Serifin (crypto)
+    A sincere gift for cryptographers, enjoy solving it!
+
+We got an archive with the following files:
++ output.txt
++ serifin.py
+
+output.txt contains two large numbers, `c and n`:
+
+    c = 78643169701772559588799235367819734778096402374604527417084323620408059019575192358078539818358733737255857476385895538384775148891045101302925145675409962992412316886938945993724412615232830803246511441681246452297825709122570818987869680882524715843237380910432586361889181947636507663665579725822511143923
+    n = 420908150499931060459278096327098138187098413066337803068086719915371572799398579907099206882673150969295710355168269114763450250269978036896492091647087033643409285987088104286084134380067603342891743645230429893458468679597440933612118398950431574177624142313058494887351382310900902645184808573011083971351
+
+serifin.py contains code that encodes the flag by performing `c = encrypt(flag, n)`. It seems we have to reverse engineer the code and somehow calculate the flag given the two values `c,n` from the output.txt file.
+
+### Attempt
+First I looked at the source code: two prime numbers p and q are generated but with some condition
+    
+    p%9 = 1, q%9 = 1, p%27 > 1, q%27 > 1 and q = next_prime(fun(p))
+
+Then, the flag is encoded with `c = flag^3 mod n` with `n=p*q`.
+Essentially we have to solve the congruence  `f³ = c mod n` with c and n given.
+First, I tried solving this with z3 and the python bindings for it. Unfortunately, that didn't work.
+I then took a closer look at the serifin function and found that it basically calculates the partial sum of the geometric series `a + a/l + a/l² + a/l³ + ..`, but with the caveat that if the difference between the current and last term is smaller than `0.0001`, the function stops. Maybe that information can be used to factor `n` into `p and q`.
+
+I then spent a long time reading up about modular arithmetic and RSA.
+Apparently, the solution has something to do with the [Chinese Remainder Theorem][1], because I found and [stackexchange entry][2]. I spent some more time reading up on the CRT but unfortunately did not learn how to solve the problem.
+
+[1]: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
+[2]: https://math.stackexchange.com/questions/2689987/solving-cubic-congruence
\ No newline at end of file