p & q generated using polynomials

Introduction

The variables p and q are generated with two polynomials of degree 6.

from Crypto.Util.number import *

p = 0
q = 0

while not (isPrime(p) and isPrime(q)):
    x = getRandomNBitInteger(64)
    p = 4*x**6 - 3*x**5 + 11*x**4 + 20*x**3 - 45*x**2 - 330*x - 17278375800565216289
    q = 5*x**6 + 27*x**5 - 2*x**4 + 9*x**3 - 192*x**2 + 78*x + 10651084407042190747

flag = "REDACTED"

m = bytes_to_long(flag.encode())

e = 65537
n = p*q
c = pow(m, e, n)

print("n = ", n)
print("e = ", e)
print("c = ", c)

n = 27661155682945406296834641714229496113140677805888382790421626659346711309446537965369777800574848759345203078671186013952201838877477218641554372916186800798088056028062582246032292303213542743992560935007190568490046409570447984281
e = 65537
c = 14671408702812896429694652959162813028288676202828966307809724394839552033486470729281236535989508878356172110388630226132307759882878757888207566185362724635740058625661145146348634360596698033503223911574509129656430741775326019844

Solve

Write-up for the challenge RSA 2 from Midnight Flag Final 2023.

To solve this challenge, it is possible to make a dichotomy between the minimum and maximum value of the random variable x. Once we know the value of x, we can generate p and q to obtain the flag.

To see if our x is correct, we can process n = p * q (this equation is based on the variable x).

from Crypto.Util.number import long_to_bytes 


n = 27661155682945406296834641714229496113140677805888382790421626659346711309446537965369777800574848759345203078671186013952201838877477218641554372916186800798088056028062582246032292303213542743992560935007190568490046409570447984281
e = 65537
c = 14671408702812896429694652959162813028288676202828966307809724394839552033486470729281236535989508878356172110388630226132307759882878757888207566185362724635740058625661145146348634360596698033503223911574509129656430741775326019844

p = lambda : 4*x**6 - 3*x**5 + 11*x**4 + 20*x**3 - 45*x**2 - 330*x - 17278375800565216289
q = lambda : 5*x**6 + 27*x**5 - 2*x**4 + 9*x**3 - 192*x**2 + 78*x + 10651084407042190747
pq = lambda : p() * q()

"""
x = getRandomNBitInteger(64)
x is a random number between 2**63 and 2**64-1
"""
min_x = pow(2, 63)
max_x = pow(2, 64) - 1

x = (max_x + min_x) // 2
res = pq()
while res != n:
    if res > n:
        max_x = x
    else:
        min_x = x + 1

    x = (max_x + min_x) // 2
    res = pq()

print("x =", x)
print("p =", p())
print("q =", q())

phi_n = (p() - 1) * (q() - 1)
d = pow(e, -1, phi_n)
m = pow(c, d, n)
print("d =", d)
print("m =", long_to_bytes(m))

Output:

x = 18269922023474656794
p = 148757939439736543528780916678183831111114502767353758676630055608563878936243914674090503384168040515494347763197559
q = 185947424299670679473569552539538103053284482082033361877830302959784260840170778721132728425964854540838167554043759
d = 26630884522805794523781658507423658189339216119754236546446174766897174066265449432579634406595826133629017706819615356481964336545389017365798082795009908086085965580006380901854971797142596705883091379681392251160435996488556530785
m = b'MCTF{cdbb393f8bb7f8c0162ecc6d42020c7c}'