We are given a simple_rsa.py
This is just a typical RSA factorization attack, just fancier and forces you to either be amazing at getting code from github and/or know how RSA works
First we notice that N isn’t just made from 2 primes, it actually is 4 primes multiplied together. These 4 primes satisfy the relation
p2=10p1+c1
p3=10p2+c2
p4=10p3+c3
where c1,2,3 are some small constants so that p2,3,4 are prime and p1 is 251 bits long.
Using p1*p4≈1000p1^2=(100p1)*(10p1)≈p2*p3, we see that this is a basic setup for fermat factorization, thus I just went to github to grab some fermat factorization code to find p1*p4 and p2*p3
p1*p4=24556891073418994576751524607635760117996811894972202516187698043229292302109114380884247668494990605537878648233446996676371523211326680052450374168750431
p2*p3=24556891073418994576751524607635760117996811894972202516187698043229292302185592473522031534536176858756163591603824821794497153855658790721132779232081801
We know that p4≈1000p1 and p3≈10p2, thus we can use coppersmith attack on it. MeePwn recently had a similar challenge where 7331q≈1337p but the last 512 bits are scrambled. For here, after some approximation using Daniel Goldston, János Pintz and Cem Yıldırım’s estimation of prime gaps(2007), I chose the error to be 17 bits, then I used p4’s code, modified a little, ran on sagecell, and got all 4 primes.
Ok so we got all 4 primes, how do we decrypt?
We know that m^e mod N=c, thus we need to find a number d such that m^(ed) mod N=m=c^d
Using Euler’s theorem, we know that ed mod φ(N)=1, and since N is just a product of 4 primes, φ(n)=(p1-1)(p2-1)(p3-1)(p4-1)
With this we can easily decrypt and get the flag
p.s. I believe that p1 is 251 bits long to emulate 512-bit RSA. Notice how N=p1*p2*p3*p4≈(1000p1^2)^2, 1000p1^2 is likely to be 512 bits long(log2(10)^3+251*3=511.965784...)
Flag:
ISITDTU{f6b2b7472273aacf803ecfe93607a914}