Safe Prime

Using a safe prime makes RSA secure, doesn't it?

We are given the challenge page and a python script that generates RSA parameters in a special way.

When we read the source code, we can see that the modulus is not built from two unrelated primes. The script first generates a prime p, and then builds the second prime as q = 2p + 1.

while True:
    p = getPrime(512)
    q = 2 * p + 1
    if isPrime(q):
        break

n = p * q

This is the weak point. Because q depends directly on p, we can write the modulus only with one unknown:

n = p * q
n = p * (2p + 1)
n = 2p^2 + p

Now we move everything to one side and we get a quadratic equation:

2p^2 + p - n = 0

So this is why the solve becomes a second degree equation problem. If we compare with the normal form ax^2 + bx + c = 0, then here we have:

a = 2
b = 1
c = -n

Using the quadratic formula, we get:

p = (-1 +/- sqrt(1 + 8n)) / 4

Only the positive solution makes sense, so the real value is:

p = (-1 + sqrt(1 + 8n)) / 4

This shows the math idea, but in practice I did not solve it directly with the quadratic equation formula. The number n is very large, so doing it in the usual direct way is not convenient here.

Because of that, I used another approach from the same equation. I defined the function below and searched for the integer root.

f(x) = 2x^2 + x - n

For x >= 0, the derivative is f'(x) = 4x + 1, which is always positive. This means the function is strictly increasing, so it has only one positive integer solution. Because of that, binary search works perfectly to find p.

from Crypto.Util.number import long_to_bytes, inverse

NUMBER = n
CIPHER = c

start = 0
stop = NUMBER
while start < stop:
    mid = (start + stop) // 2
    result = mid * (2 * mid + 1) - NUMBER
    if result == 0:
        PRIME = mid
        break
    if result > 0:
        stop = mid
    else:
        start = mid + 1

After we recover p, we compute q = 2p + 1, then calculate phi(n), recover the private exponent d, and finally decrypt the ciphertext.

q = 2 * PRIME + 1
phi_n = (PRIME - 1) * (q - 1)
d = inverse(65537, phi_n)
m = pow(CIPHER, d, NUMBER)
plaintext = long_to_bytes(m)

Using the given values, this gives us the plaintext flag below.

ctf4b{R3l4ted_pr1m3s_4re_vuLner4ble_n0_maTt3r_h0W_l4rGe_p_1s}