AlpacaHack Round 3 (Crypto): qrime Upsolve

qrime

authored by xornet

not crime and prime

import os
from Crypto.Util.number import bytes_to_long, getRandomNBitInteger, isPrime

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

def gen():
    while True:
        q = getRandomNBitInteger(256)
        if not isPrime(q):
            continue
        r = getRandomNBitInteger(256)
        p = q * nextPrime(r) + nextPrime(q) * r
        if isPrime(p) and isPrime(q):
            return p, q, r

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q, r = gen()
n = p * q

phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)
c = pow(m, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c=}")
print(f"{r=}")

p = q * nextPrime(r) + nextPrime(q) * rで計算されており、$r$の値は与えられています。

解法

$r$の値は既知であることから、nextPrimeの値は93306715077150526900611207656501624167797808502485855834333355823957291927851であることがわかります。これを$r'$とします。そして、nextPrime(q)の値を$q+\alpha$とすると、先程の式は
$$
p = qr' + (q+\alpha)r
$$
と書き換えることができます。
つまり、
$$
N = pq = p(qr' + (q+\alpha)r)
$$
となり、未知変数は$q,\alpha$の2つとなります。ここで、$\alpha$の値は素数定理により概ね$\log q$であり、$q$は256bitであることから小さいと言えます。以上から、$\alpha$をある一定の大きさまで総当りし、解が得られたら$q$の値が求まります。

from Crypto.Util.number import  long_to_bytes
from sympy import nextprime, integer_nthroot


n=1597349797582252189737622221791988995702203505409122048213056145385432056678668011744383472026126622313229593211723275251532300454579372254725326775404977015496304747248416324105306138292084116374337609917577700786808299040936359837
e=65537
c=972720840499592344446463443980685660383495734796643528156038336075094110601869565083456517200700906514513655122880885701228182964785192363570987340004695486727354284548049636771649892722940274205296325372249242376864953467610809561
r=93306715077150526900611207656501624167797808502485855834333355823957291927822
q=0

r_next = nextprime(r)
for i in range(10000):
    a = r_next + r
    b = i * r
    D = b*b + 4*a*n
    s, exact = integer_nthroot(D, 2)
    if not exact:
        continue

    denom = 2 * a
    for j in (-b+s, -b-s):
        if j % denom != 0:
            continue
        x = j // denom
        if x > 0 and n%x == 0:
            q = x
            break

p = n // q
d = pow(e, -1, (p-1)*(q-1))

print(long_to_bytes(pow(c, d, n)).decode())

Flag: Alpaca{q_and_r_have_nothing_to_do_with_QR_code}