# Challenge

File : Iran.py

# Solve

Take a look on the given code, `Iran.py`

1 | assert ((p-1) % r)**2 + ((q-1) % s)**4 + ((r**3 - 1) % p)**8 + ((s**3 - 1) % q)**16 == 0 |

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

1 | key_0, key_1 = keysaz(gmpy.next_prime(r+s), gmpy.next_prime((r+s)<<2)), keysaz(p, q) |

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 | q = 90829988108297459126723951986073924022504128225586222454376617387900632408868147010157825639889602300446053601539575136123106704382046836252729190919472251 |

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 | # sage |

What can we do if we find `(r+s)`

?

We have another information of `key_1`

:$r|(p-1)$, $s|(q-1)$, $p|(r^3-1)$, $q|(s^3-1)$

those equation point out :

$$p-1 = ar$$

$$p = ar+1 \Rightarrow p > r$$

Next :

$$r^{3}-1 \equiv 1 \ mod \ p$$

$$r^{3}-1 = (r-1)(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)(r-p) +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+s-1)rs+(r+s)^2+(r+s)+1$$

let `rs`

be `x`

, we solve $x^2 + (r+s-1)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 | for rps in range(rps_min, rps_max): |

Then, decrypt second cipher and get the flag LoL.