Challenge
File : Iran.py
Solve
Take a look on the given code, Iran.py
1 

We know that $r(p1)$, $s(q1)$, $p(r^3)$, $q(s^3)$, and p,q,r,s are primes.
1 

First, take a look on key_0
:
This module N is almost product of (r+s)
, 4(r+s)
, for factor theorem.
use coppersmith method, if we known the approximately value of factor, we can find it efficiently.
$$N = p * q \approx (r+s) * 4(r+s) \approx 4(r+s)^{2}$$
$$\sqrt{4N} \approx 4*(r+s) \approx q$$
Therefore, load in the given pubkey, calculate it then put into method,
we get the root about 976
, then we find the prime q
.
1 

decrypt the cipher, we can get half of the flag :
ASIS{0240093faf9ce
Next, go to key_1 :
we know where (r+s)
will be, so we could find it via brute force.
1 

What can we do if we find (r+s)
?
We have another information of key_1
:$r(p1)$, $s(q1)$, $p(r^31)$, $q(s^31)$
those equation point out :
$$p1 = ar$$
$$p = ar+1 \Rightarrow p > r$$
Next :
$$r^{3}1 \equiv 1 \ mod \ p$$
$$r^{3}1 = (r1)(r^2+r+1) = bp$$
$$p > r \Rightarrow p(r^2+r+1)$$
Therefore, we can further analysis :
$$(r^2+r+1) = kp$$
$$kp \equiv 1 \ mod \ r$$
we know $p \equiv 1 \ mod \ r$ at first,
so $k \equiv 1 \ mod \ r$ is also right.
$$\rightarrow k=1,(r+1),(2r+1)….$$
What if $k \geq (r+1)$ :
$$(r^2+r+1)  kp \leq (r^2+r+1)  (r+1)p \leq (r+1)(rp) +1 \leq (r+1)+1 \lt 0$$
conflict, hence, $k = 1$, and same with q
.
We can get a equation below :
$$N = p*q = (r^2+r+1)(s^2+s+1)$$
$$(r^2+r+1)(s^2+s+1) = (rs)^2+r^{2}s+r^2+rs^{2}+rs+r+s^2+s+1$$
$$= … = (rs)^2+(r+s1)rs+(r+s)^2+(r+s)+1$$
let rs
be x
, we solve $x^2 + (r+s1)x + (r+s)^2 + (r+s) + 1$, the root is rs
have rs
, r+s
, we can find out r
, s
, respectively.
$$p = r^2+r+1$$
$$q = s^2+s+1$$
1 

Then, decrypt second cipher and get the flag LoL.