crypto_john

John-Bull (crypto, 141p, 29 solved)

In the challenge we get code and encryption results. The encryption code is quite simple:

def make_key(k):
    while True:
        r = getRandomInteger(k) << 2
        p, q = r**2+r+1, r**2+3*r+1
        if gmpy.is_prime(p) * gmpy.is_prime(q):
            break
    pubkey = r**6 + 5*r**5 + 10*r**4 + 13*r**3 + 10*r**2 + 5*r + 1
    return pubkey

def encrypt(m, pubkey):
    return pow(bytes_to_long(m), pubkey, pubkey)

The encryption looks like RSA with e set to n, and n itself is (p**2)*q. The first step is to recover r and thus factor n. We can see that n is a polynomial, and a nice property here is that for large r the higher order terms will be significantly bigger than lower order terms.

Imagine r=1000000, in such case r**6-r**5 ~= 0.999999*r**6

In our case we expect r to be much bigger than that, around 510 bits, which makes this property even stronger. This means that value of the polynomial r**6 + 5*r**5 + 10*r**4 + 13*r**3 + 10*r**2 + 5*r + 1 will be realtively close to r**6. And if we calculate 6-th root the value should be pretty much identical, because all lower order terms will simply be swallowed as small fractions.

We can confirm this by:

r = int(gmpy2.iroot(n, 6)[0])
p, q = r ** 2 + r + 1, r ** 2 + 3 * r + 1
print(gmpy2.is_prime(p))
print(gmpy2.is_prime(q))
assert n == p ** 2 * q

Now that we have p and q we can proceed with decrypting the flag. The issue now is that this encryption does not match RSA conditions -> gcd(e,phi(n))!=1. This is quite obvious since:

phi(n) = phi((p**2)*q) = phi(p**2) * phi(q) = p*(p-1) * (q-1)

And in our case e = n = (p**2)*q

So phi(n) and e share a factor p.

One approach we could try would be to divide e by p and calculate d for such e, but as a result we would just get flag**p mod n which doesn't help us much because we can't easily calculate k-th modular root. But we took a different path and guessed that flag might not be padded and thus it would be reasonably short. Specifically shorter not only than n, which is expected, but also shorted than p*q.

We could calculate ciphertext % (p*q) transforming this problem back to classic RSA. We were lucky and this approach worked just fine:

enc = enc % (p * q)
e = p * p * q
fi = (p - 1) * (q - 1)
d = modinv(e, fi)
flag_p = gmpy2.powmod(enc, d, (p * q))
print(long_to_bytes(flag_p))

Which gave us ASIS{_Wo0W_Y0u_4r3_Mas73R_In____Schmidt-Samoa___}

Whole solver here

As it turns out this is an existing cryptosystem, and could have been solved by:

d = modinv(n, lcm(p - 1, q - 1))
flag_p = gmpy2.powmod(enc, d, (p * q))
print(long_to_bytes(flag_p))