Here is output of Double.sage. Catch The Flag.
The challenge setting/exploit code is almost identical on this awesome writeup: Confidence CTF 2015 rsa1.
The only part to modify from original writeup is the solution size argument for sage's small_root() function.
Two messages M1, M2 are generated as below.
M1 = Flag + md5(Flag).digest()
M2 = Flag + md5(b'One more time!' + Flag).digest()To apply Coppersmith's short pad attack, knowing length of padding is necessary. Fortunately, md5 is used for padding, having length of 16 bytes or 128 bits. Give this information to small_root() function like below.
roots = h.small_roots(X=2**128, beta=0.3)
diff = roots[0]Difference of plaintexts(diff) is known. Apply Franklin-Reiter related message attack and get flag:
Defenit{Oh_C@Pp3r_SM1TH_SH0Rt_P4D_4TT4CK!!_Th1S_I5_Ve12Y_F4M0US3_D0_Y0u_UnderSt4Nd_ab@ut_LLL_AlgoriTHM?}
Original problem: double.sage, out.txt
Exploit code: solve.sage with config.py