# ASIS CTF Quals 2015 – Cross Check (Crypto 350)

The flag is encrypted by this code, can you decrypt it?
crosscheck.tar.xz

Summary: breaking RSA modulos with related primes.

In this challenge we have 3 RSA modulos and 3 parts of flag encrypted. Here’s how the keys are generated:

p = random.randint(1 << 510, 1 << 511) q = random.randint(1 << 510, 1 << 511)   for i in range(0, 3): p = gmpy.next_prime(p) q = gmpy.next_prime(q) P.append(p) Q.append(q)   for i in range(0, 3): N.append(P[i] * Q[2 - i])

All the primes are very close to each other. Each modulus is related to any other: one factor is slightly increased, another one is slightly decreased.

Note: if both factors were slightly increased (e.g. N[i] = P[i] * Q[i]), then it would be easy to break with Fermat method for factorization for N * N: it would yield us P*Q and P*Q and then GCD would reveal all the factors.

Let’s look closer at some pair of modulos, let’s say N and N (p and q redefined for simplicity):

• $N_0=p*(q+s_q)$
• $N_1=(p+s_p)*q$

We want to exploit the fact that $s_p$ and $s_q$ are small (we can bruteforce them). Consider linear combination of this modulos:

$$c = a N_0 + b N_1 = p q(a + b) + a p s_q + b q s_p$$

If we consider this modulo (a + b) then we will have:

$$c \equiv{} a p s_q + b q s_p \pmod{a + b}$$

Let M be some large prime,a=1 and b=M-1. Then

$$c \equiv{} p s_q – q s_p \pmod{M}$$

And if M is large enough, modulo reduction can be dropped and we will learn the exact value of

$$c \mod{M} = p s_q – q s_p$$

UPD: I just realized that modulo M is not needed at all. Simply

$$c = N_0 – N_1 = p s_q – q s_p$$

Having this linear combination of p and q we can easily bruteforce $s_p$ and $s_q$ and factor all the modulos!

$$\Rightarrow{} p = \frac{c + s_p q}{s_q}$$

$$\Rightarrow{} N_0 s_q = (c + s_p q)(q + s_q)$$

$$\Rightarrow{} q^2 s_p + q(c + s_p s_q) + s_q(c + N_0) = 0$$

(quadratic equation over integers with unknown q).

The code:

M = gmpy.next_prime(1 << 1000) C = (N + (M - 1) * N) % M if C > M / 2: # p s_q - q s_p can be negative C = -(M - C)   p_sp = None for sp in xrange(1, 2000): for sq in xrange(1, 2000): # solve quadratic equation over ZZ a = sp b = C + sp * sq c = sq * (C - N) D = b ** 2 - 4 * a * c if D < 0: continue sqrD = D.root(2) if sqrD ** 2 != D: continue for add in (-sqrD, sqrD): q = (-b + add) / (2 * a) if N % q == 0: p_sp = N / q break if p_sp: break   assert p_sp, "no solution?" P = [None] * 3 Q = [None] * 3 P = gmpy.next_prime(p_sp) Q = N / P Q = gmpy.next_prime(Q) Q = gmpy.next_prime(Q) P = N / Q P = gmpy.next_prime(P) assert P * Q == N assert P * Q == N assert P * Q == N   cts = [ "DjXmcsw0QXBRBiUOx2Uu4kS/gFvIYyf6MSJLWlwy8i7WjVB8vOtUb90GTFSuHDX6iawvUg/XVjU7DVAi9EhMGSS2LyvgMH4nD4gjlVlC2PkxkNDILuUq//5DMoTUyootReoke1jXDnmHg1y0KglkIylL2dufsHc74cAKnciNU9U=", "DkYN4JwQU+EstIvIs662BISkzXxqqfb62DrJFV5efVuXtkLSQrzHgLczgC1blF8e29x46Jz2yjqb1eb2IJX59yuDBHiQ13ckId+E732Bpu00ee9UqYtSNNnQFIo8LIBWFxIUK3+XjNynDD9ArcF5OkLvk8o8AU1DcAdusQtsURo=", "CuMo9lJNex64Wh63DORfMPkcwX7inwNd3QEi/OKb2vbh69v4iF46/4tCz8ZF7FEKfNxmXuyPREdS7YPqNGi9hQT21CmeiXe/AbDCITrhYVMWJi4A6wjZjkdslHklnmJFnULRkSLVCYAgVQAbPGO3CmQ+3y9QSAhZM5qi8NQnoOo=" ]   for i in range(0, 3): d = gmpy.invert(long(65537), (P[i] - 1) * (Q[2 - i] - 1)) priv = RSA.construct((long(N[i]), long(65537), long(d), long(P[i]), long(Q[2 - i]))) priv = PKCS1_v1_5.new(priv) ct = cts[i].decode("base64") print priv.decrypt(ct, None)
\$ time py cross_check.py hi all the flag is ASIS{a0c8f997d5cdd6 99d336b0f2f12af326}   real 0m1.110s user 0m1.091s sys 0m0.016s

• • horokey on May 12, 2015 at 19:52

Ферма тоже работает.
https://b01lers.net/challenges/ASIS%202015/Cross%20Check/52/
что мы делали нет так ;(
Но крутости решения “by hellman” это не отменяет)

• • hellman on May 12, 2015 at 20:01
Author

Да, видимо нужно просто не останавливаться на первой выдаче от Ферма (которая даст уже известную факуторизацию на N1 * N2), а продолжать алгоритм.

• • horokey on May 13, 2015 at 14:27

кто-то просто метод Ферма криво закодил (и не проверил) и оно вообще ниче никогда не выводило ;)

• • bowknotbowknot on December 16, 2015 at 13:01

• 