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 * 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):

• • 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 + (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

1. ##### horokey says:

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

1. ##### hellman says:

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

1. ##### horokey says:

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

2. ##### bowknotbowknot says:

3. 