ccc

Yet another problem of RSA with weirdly generated primes.

def create_prime(p_bit_len, add_bit_len, a):
    p = getPrime(p_bit_len)
    p_bit_len2 = 2*p_bit_len // 3 + add_bit_len
    while True:
        b = getRandomInteger(p_bit_len2)
        _p = a * p
        q = _p**2 + 3*_p*b + 3*b**2
        if isPrime(q):
            return p, q

Here, p_bit_len=1024, add_bit_len=9, and a=23, (so p_bit_len2 = 691) though I think these parameters are pretty arbitrary.

This problem I solved pretty much just rambling algebra as comments in the “solve script” (that ended up just empty save for the comments since again I solved it in REPL).

#         q = _p**2 + 3*_p*b + 3*b**2
# P = 23p
# Pq =P^3 3P^2b + 3Pb^3
# + b^3 = (P+b)^3
#  23n + b^3 == (P+b)^3

So, we have , and, by intuition, because , we see will be extremely close to . How close? Well, if we set

Under the assumption ,

and from what we know about the parameters, is expected to be less than bits, plus/minus whatever errors I’ve made in this napkin math. But either way: small.

So we find the first cube first_st(lambda k: is_cube((est+k)**3 - 23*n)), which will be and then we factor and done.