RSA Backdoor Viability

I hate recursion depths. Sage on Windows sucks at configuring anything related to this.

The challenge gives a peculiar way of generating primes

xxxxxxxxxx
def get_complex_prime():
    D = 427
    while True:
        s = random.randint(2 ** 1020, 2 ** 1021 - 1)
        tmp = D * s ** 2 + 1
        if tmp % 4 == 0 and isPrime((tmp // 4)):
            return tmp // 4

And given the name of the challenge, we are pretty sure that this leads to a vulnerability. Indeed, the name of the challenge leads to a paper regarding the $4p-1$$4p - 1$ method and the related RSA backdoor viability.

The Github repo containing the code. The paper is at this link. The Github repo should contain the script for factorising primes in the form of 4p - 1, and D = 427 as seen in the Python code above.

Modified Sage script, kudos to ConnorM:

xxxxxxxxxx
class FactorRes(object):
    def __init__(self, r=None, c=None, u=None, a=None):
        self.r = r
        self.c = c
        self.u = u
        self.a = a

def xgcd(f, g, N):
    toswap = False
    if f.degree() < g.degree():
        toswap = True
        f, g = g, f
    r_i = f
    r_i_plus = g
    r_i_plus_plus = f
    s_i, s_i_plus = 1, 0
    t_i, t_i_plus = 0, 1
    while (True):
        lc = r_i.lc().lift()
        lc *= r_i_plus.lc().lift()
        lc *= r_i_plus_plus.lc().lift()
        divisor = gcd(lc, N)
        if divisor > 1:
            return divisor, None, None
        q = r_i // r_i_plus
        s_i_plus_plus = s_i - q * s_i_plus
        t_i_plus_plus = t_i - q * t_i_plus
        r_i_plus_plus = r_i - q * r_i_plus
        if r_i_plus.degree() <= r_i_plus_plus.degree() or r_i_plus_plus.degree() == -1:
            if toswap == True:
                return r_i_plus, t_i_plus, s_i_plus
            else:
                return r_i_plus, s_i_plus, t_i_plus,
        r_i, r_i_plus = r_i_plus, r_i_plus_plus
        s_i, s_i_plus = s_i_plus, s_i_plus_plus
        t_i, t_i_plus = t_i_plus, t_i_plus_plus

def Qinverse (Hx, a, N):
    r,s,t = xgcd(a.lift(), Hx, N)
    if (s,t) == (None, None):
        res = r, 0
    else:
        rinv = r[0]^(-1)
        res = 1, s * rinv
    return res

def CMfactor(D, N):
    Hx = hilbert_class_polynomial(-D)
    res = FactorRes()
    ZN = Integers(N)
    R.<x> = PolynomialRing(ZN)
    Hx = R(Hx)
    Q.<j> = QuotientRing(R, R.ideal(Hx))
    gcd, inverse = Qinverse(Hx, 1728 - j, N)
    if gcd == 1:
        a = Q(j * inverse)
    return CMfactor_core(N, a, Q, ZN, Hx, res)

def CMfactor_core(N, a, Q, ZN, Hx, res):
    for c in [1..10]:
        E = EllipticCurve(Q, [0, 0, 0, 3 * a * c ^ 2, 2 * a * c ^ 3])
        for u in [1..10]:
            rand_elem = ZN.random_element()
            res.rand_elem = int(rand_elem)
            w = E.division_polynomial(N, Q(rand_elem), two_torsion_multiplicity=0)
            poly_gcd = xgcd(w.lift(), Hx, N)[0]
            r = gcd(ZZ(poly_gcd), N)
            res.c = c
            res.u = u
            if r > 1 and r != N:
                return r, N//r

def main():
    sys.setrecursionlimit(50000)
    #####################################INPUTS####################################
    d = 427
    n = ...
    c = ...
    e = 65537
    #####################################INPUTS####################################

    p, q = CMfactor(d, n)

    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    flag = int(pow(c, d, n))
    print(flag.to_bytes((flag.bit_length() + 7) // 8, 'big').decode())

if __name__ == "__main__":
    main()

A good rule of thumb for the challenges with the weird prime generation - FactorDB always work, and probably will save your sanity in fixing the recursion depths of Python in Sage.