Challenge: PolyRSA
Author: Shotokhan
Description: Exploiting polynomial-based generation of p and q in RSA
CTF: Crypto CTF 2022
Category: Crypto

We are given a modulus n and a ciphertext enc:

n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532

The source code of the challenge is also provided:

#!/usr/bin/env python3

from Crypto.Util.number import *
from flag import flag

def keygen(nbit = 64):
	while True:
		k = getRandomNBitInteger(nbit)
		p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
		q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
		if isPrime(p) and isPrime(q):
			return p, q

def encrypt(msg, n, e = 31337):
	m = bytes_to_long(msg)
	return pow(m, e, n)

p, q = keygen()
n = p * q
enc = encrypt(flag, n)
print(f'n = {n}')
print(f'enc = {enc}')

As you can see, there is a custom method to generate primes p and q for RSA. A random integer k of 64 bits is generated, and p is f1(k), q is f2(k), where f1 and f2 are polynomial functions. This operation is repeated until it results that p and q are both primes. At this point, the standard textbook RSA flow is followed, to encrypt the flag.

Where is the vulnerability? Since n = p * q, and p and q are both functions of k, then n is function of k:

n = f1(k) * f2(k) = k**11 - 8 * k**10 + 26 * k**9 - 409 * k**8 + 451 * k**7 + 10850 * k**6 + 44939 * k**5 - 158301 * k**4 + 71237 * k**3 - 9651273 * k**2 - 2036532 * k + 439623147

Note that this function is always increasing when k > k0 (for example k0 = 100), so we can search k1 | f1(k1) * f2(k1) == n using a binary search (bisection method).

Here is the script we used:

from Crypto.Util.number import long_to_bytes


def poly(k):
    return k**11 - 8 * k**10 + 26 * k**9 - 409 * k**8 + 451 * k**7 + 10850 * k**6 + 44939 * k**5 - 158301 * k**4 + 71237 * k**3 - 9651273 * k**2 - 2036532 * k + 439623147


def bin_search(n):
    low, high = 100, n
    while low < high:
        mid = (low + high) // 2
        value = poly(mid)
        if value == n:
            return mid
        elif value < n:
            low = mid + 1
        else:
            high = mid
    return low
    

def main():
    e = 31337
    n = 44538727182858207226040251762322467288176239968967952269350336889655421753182750730773886813281253762528207970314694060562016861614492626112150259048393048617529867598499261392152098087985858905944606287003243
    enc = 37578889436345667053409195986387874079577521081198523844555524501835825138236698001996990844798291201187483119265306641889824719989940722147655181198458261772053545832559971159703922610578530282146835945192532
    k = bin_search(n)
    print(f"{k = }")
    assert poly(k) == n
    p = k**6 + 7*k**4 - 40*k**3 + 12*k**2 - 114*k + 31377
    q = k**5 - 8*k**4 + 19*k**3 - 313*k**2 - 14*k + 14011
    phi = (p-1)*(q-1)
    d = pow(e, -1, phi)
    m = pow(enc, d, n)
    flag = long_to_bytes(m)
    print(flag)


if __name__ == "__main__":
    main()

And here is its execution log:

$ python script.py 
k = 9291098683758154336
b'CCTF{F4C70r!N9_tRIcK5_aR3_fUN_iN_RSA?!!!}'