May
11

## 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[0] * N[1]: it would yield us P[0]*Q[1] and P[1]*Q[0] and then GCD would reveal all the factors.

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

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

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

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

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

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

.

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

(quadratic equation over integers with unknown q).

The code:

M = gmpy.next_prime(1 << 1000) C = (N[0] + (M - 1) * N[1]) % 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[0]) D = b ** 2 - 4 * a * c if D < 0: continue sqrD = D.root(2)[0] if sqrD ** 2 != D: continue for add in (-sqrD, sqrD): q = (-b + add) / (2 * a) if N[1] % q == 0: p_sp = N[1] / q break if p_sp: break   assert p_sp, "no solution?" P = [None] * 3 Q = [None] * 3 P[2] = gmpy.next_prime(p_sp) Q[0] = N[2] / P[2] Q[1] = gmpy.next_prime(Q[0]) Q[2] = gmpy.next_prime(Q[1]) P[0] = N[0] / Q[2] P[1] = gmpy.next_prime(P[0]) assert P[0] * Q[2] == N[0] assert P[1] * Q[1] == N[1] assert P[2] * Q[0] == N[2]   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

1. ##### horokey says:

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

1. ##### hellman says:

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

1. ##### horokey says:

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