From 84177ad397b31b1a73bb3585f8deb2a8b7343353 Mon Sep 17 00:00:00 2001 From: Michael Lang Date: Wed, 15 Jan 2020 16:03:17 +0100 Subject: [PATCH] add writeup for asis19/serifin --- writeups/mla/asis19.md | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) diff --git a/writeups/mla/asis19.md b/writeups/mla/asis19.md index cffe87c..c6ae05b 100644 --- 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 -- 2.43.0