# Cube

Challenge Script:

from Crypto.Util.number import bytes_to_long, getPrime, isPrime

FLAG = <REDACTED>

def gen(n):
    while True:
        p = getPrime(n - 1) * 2 + 1
        if (isPrime(p)):
            return p

def cube(m, n, p):
    res = m
    for i in range(n):
        res = (res * res * res) % p
    return res

p = gen(1024)
m = bytes_to_long(FLAG)
c = cube(m, 2 ** 100, p)

print(p)
print(c)

# p = 147271787827929374875021125075644322658199797362157810465584602627709052665153637157027284239972360505065250939071494710661089022260751215312981674288246413821920620065721158367282080824823494257083257784305248518512283466952090977840589689160607681176791401729705268519662036067738830529129470059752131312559
# c = 117161008971867369525278118431420359590253064575766275058434686951139287312472337733007748860692306037011621762414693540474268832444018133392145498303438944989809563579460392165032736630619930502524106312155019251740588974743475569686312108671045987239439227420716606411244839847197214002961245189316124796380

Summary: This challenge essentially involves performing ``2^100`` consecutive modular cube roots on ``c`` to derive the flag. More formally, ``flag = c^(1/(3^(2^100))) mod p``, where ``p`` is prime.

Since ``p`` is prime, modular roots can be easily computed, as modular root algorithms such as [Tonelli-Shanks Algorithm](https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm) and [Adleman-Manders-Miller Algorithm](http://www.cs.cmu.edu/~glmiller/Publications/AMM77.pdf) all require prime moduli.

In the case of modular cube roots, from [this post](https://stackoverflow.com/a/6752874), it can be seen that there are only a few possible valid cases for which a modular cube root can be calculated.

Test Script:

# Value from Challenge Script
p = 147271787827929374875021125075644322658199797362157810465584602627709052665153637157027284239972360505065250939071494710661089022260751215312981674288246413821920620065721158367282080824823494257083257784305248518512283466952090977840589689160607681176791401729705268519662036067738830529129470059752131312559

print(p%3, p%9)

Output:

2 8

This implies that the cube root of ``c mod p`` can be calculated as ``pow(c, (2*p - 1)//3, p)``.

However, since we need to compute ``2^100`` consecutive cube roots, ``flag = pow(c, ((2*p - 1)//3)^(2^100), p)``.

This is an issue, since ``((2*p - 1)//3)^(2^100)`` is too large of an exponent to use in modular exponentiation.

Fortunately, the exponent can be simplified using modular arithmetic. [Euler's Theorem](https://en.wikipedia.org/wiki/Euler%27s_theorem) states that ``a^k ≡ a^(k mod φ(n)) mod n`` if ``gcd(a, n) = 1`` for ``k >= 1``, where ``φ(n)`` is Euler's totient function.

Test Script:

# Values from Challenge Script
p = 147271787827929374875021125075644322658199797362157810465584602627709052665153637157027284239972360505065250939071494710661089022260751215312981674288246413821920620065721158367282080824823494257083257784305248518512283466952090977840589689160607681176791401729705268519662036067738830529129470059752131312559
c = 117161008971867369525278118431420359590253064575766275058434686951139287312472337733007748860692306037011621762414693540474268832444018133392145498303438944989809563579460392165032736630619930502524106312155019251740588974743475569686312108671045987239439227420716606411244839847197214002961245189316124796380

print(gcd(c, p))

Output:

1

This shows that ``c`` and ``p`` are coprime (i.e. their gcd is ``1``), meaning that Euler's Theorem can be applied.

Since ``p`` is prime, ``φ(p) = p-1``.

Solve Script:

# Values from Challenge Script
p = 147271787827929374875021125075644322658199797362157810465584602627709052665153637157027284239972360505065250939071494710661089022260751215312981674288246413821920620065721158367282080824823494257083257784305248518512283466952090977840589689160607681176791401729705268519662036067738830529129470059752131312559
c = 117161008971867369525278118431420359590253064575766275058434686951139287312472337733007748860692306037011621762414693540474268832444018133392145498303438944989809563579460392165032736630619930502524106312155019251740588974743475569686312108671045987239439227420716606411244839847197214002961245189316124796380

assert p%3 == 2
assert gcd(c, p) == 1

exp = pow((2*p - 1)//3, 2^100, p-1) # Apply Euler's Theorem to make the exponent smaller
c = pow(c, exp, p)

from Crypto.Util.number import long_to_bytes

print(long_to_bytes(Integer(c)))

Output:

b'grey{CubeIsSquarerThanSquare_FjUFynTNUdTyJu5x}'