Maojui

ASIS 2018 - Iran (Crypto, 230)

2018-05-01

Challenge

File : Iran.py

Solve

Take a look on the given code, Iran.py

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

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

1
2
key_0, key_1 = keysaz(gmpy.next_prime(r+s), gmpy.next_prime((r+s)<<2)), keysaz(p, q)
pkey_0, pkey_1 = key_0.publickey().exportKey(), key_1.publickey().exportKey()

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
2
3
q = 90829988108297459126723951986073924022504128225586222454376617387900632408868147010157825639889602300446053601539575136123106704382046836252729190919472251
p = key1.n//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.

1
2
3
4
# sage
# rps_min = max(p.previous_prime(), (q.previous_prime()>>2)+1)
# rps_max = min(p1-1, q1>>2)
rps_min , rps_max = [22707497027074364781680987996518481005626032056396555613594154346975158102217036752539456409972400575111513400384893784030776676095511709063182297729867955, 22707497027074364781680987996518481005626032056396555613594154346975158102217036752539456409972400575111513400384893784030776676095511709063182297729868062]

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for rps in range(rps_min, rps_max):
    # solve x**2+(r+s-1)*x+((r+s)**2+(r+s)+1-N) = 0
    x   = Symbol('x')
    krs = solve(x**2 + (rps-1) * x +  rps**2 + rps + 1 - N, x )
    rs = int(max(krs).round())
    rms = nroot(pow(rps,2) - 4*rs,2)
    r = ( rps + rms )//2
    s = ( rps - rms )//2
    p = pow(r,2) + r + 1
    q = pow(s,2) + s + 1
    if isprime(r) + isprime(s) + isprime(p) + isprime(q) == 4 :
        break

# r = 12499634052322197156517113844570074858063070132180093106949981756315114873173955244125349117851113985103413267665336997816163464207102752932176612131841251
# s = 10207862974752167625163874151948406147562961924216462506644172590660043229043081508414107292121286590008100132719556786214613211888408956131005685598026799
# p = 156240851441972631802221590872365199548433251427920958861525362326561429385229704503678026122109494099033132273746193481805470952959264526942790128361011138938521756301147040476473263577899760465829409316910880775950966399157885433015477980346046385388892181847745614165640358705448231145462307601951597086253
# q = 104200466511316172778869399412484232432410577006734517689040806370664632008414169969876197410209734803078366536335955234365028495924842514540398861721394984700616799057849702480143488978231977381728134018264755205067162244435476000113140356804090143668453486397378604853972171073327866641690391346367920213201

Then, decrypt second cipher and get the flag LoL.

ASIS{0240093faf9ce4d7be86d87d49a95cf7}

solve.py

Tags: RSA
← ASIS 2018 - Uncle-Sam (Crypto, 123) PlaidCTF 2018 - Macsh (Crypto, 125) →