Maojui

2018-05-01

File : Iran.py

Solve

Take a look on the given code, Iran.py

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

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.

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.

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$$

Then, decrypt second cipher and get the flag LoL.

solve.py

Tags: RSA