qrime

Easy, same as the last challenge, but with a different relation between the primes.

We are given the challenge page, the source code and the output values n, e, c and r.

When we read the source code, we can see that this time the primes are generated with another formula:

q = getRandomNBitInteger(256)
p = q * nextPrime(r) + nextPrime(q) * r
n = p * q

So the modulus is not using two unrelated values. The prime p depends on q and on r, and the value r is given to us in the output.

First we compute nextPrime(r). In this case the gap is very small:

nextPrime(r) - r = 29

So we know exactly one part of the relation. If we write everything with a guessed value for q, we get:

p = q * nextPrime(r) + nextPrime(q) * r
n = q * p
n = q * (q * nextPrime(r) + nextPrime(q) * r)

Unlike the previous challenge, here we do not get a simple quadratic equation that we can use directly, because nextPrime(q) is also inside the formula.

Because of that, I used brute force with binary search on q. I define the function below and check where it becomes zero:

f(x) = x * (x * nextPrime(r) + nextPrime(x) * r) - n

This function is increasing for positive values, so binary search works here too. For each middle value, we compute the formula and compare it with n. If the result is too large, we move left. If it is too small, we move right.

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

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

After the search, we recover the correct value of q:

92518496741750090011518392072429201839177129268391902596140634421942700183041

Then we reconstruct p with the original formula, and verify that it is correct by checking that p * q == n.

P = Q * nextPrime(R) + nextPrime(Q) * R
print(NUMBER == Q * P)  # True

Now that both primes are known, the rest is just standard RSA decryption: compute phi(n), recover d, decrypt c, and convert the result back to bytes.

phi = (P - 1) * (Q - 1)
d = inverse(65537, phi)
m = pow(CIPHER, d, NUMBER)
plaintext = long_to_bytes(m)

This gives the plaintext flag below.

Alpaca{q_and_r_have_nothing_to_do_with_QR_code}