Tags: rsa

Rating:

# Simple RSA
>We are given a [simple_rsa.py](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.

## Factoring

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](fermat.py) 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](coppersmith.sage), ran on [sagecell](http://sagecell.sagemath.org/), and got all 4 [primes](primes.txt).

## Decrypting message

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](decrypt.py) and get the flag

>Flag: ISITDTU{f6b2b7472273aacf803ecfe93607a914}

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...)