<- BALSN CTF

Prime

9 minutes to read

We are given the source code of the server in SageMath:

import gmpy2
import random
from secret import FLAG

def main():
    n = int(input("prime: "))

    if n <= 0:
        print("No mystiz trick")
    elif n.bit_length() < 256 or n.bit_length() > 512:
        print("Not in range")
    elif not is_prime(n):
        print("Not prime")
    else:
        x = int(input("factor: "))

        if x > 1 and x < n and n % x == 0:
            print("You got me")
            print(FLAG)
        else:
            print("gg")

def is_prime(n):
    # check if n = a^b for some a, b > 1
    for i in range(2, n.bit_length()):
        root, is_exact = gmpy2.iroot(n, i)
        if is_exact:
            return False

    rs = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]  
    return all(test(n, r) for r in rs)

def test(n, r):
    """
    check whether `(x + a) ^ n = x ^ n + a (mod x ^ r - 1)` in Z/nZ for some `a`.
    """
    R.<x> = Zmod(n)[]
    S = R.quotient_ring(x ^ r - 1)

    a = 1 + random.getrandbits(8)
    if S(x + a) ^ n != S(x ^ (n % r)) + a:
        return False
    return True

if __name__ == "__main__":
    main()

Source code analysis

The script implements the AKS primality test, and asks for a prime number that has a factor different than $1$ and the same number:

def main():
    n = int(input("prime: "))

    if n <= 0:
        print("No mystiz trick")
    elif n.bit_length() < 256 or n.bit_length() > 512:  
        print("Not in range")
    elif not is_prime(n):
        print("Not prime")
    else:
        x = int(input("factor: "))

        if x > 1 and x < n and n % x == 0:
            print("You got me")
            print(FLAG)
        else:
            print("gg")

def is_prime(n):
    # check if n = a^b for some a, b > 1
    for i in range(2, n.bit_length()):
        root, is_exact = gmpy2.iroot(n, i)
        if is_exact:
            return False

If so happens, the server will show the flag. But this is a contradiction, since a prime number is only divisible by $1$ and itself. Therefore, the objective of the challenge is to send a special composite number that is considered a prime number by the AKS primality test implementation. In short, we need to break this primality test.

AKS primality test

First of all, we need to do a bit of research on the AKS primality test. I found good information on these resources:

Basically, the test is built from Fermat’s Little Theorem, where $a^p \equiv a \pmod{p}$. This holds for all prime numbers, but there are other special numbers that also satisfy the condition (Carmichael numbers, more on this later). To overcome this, the AKS test considers the $p$-th power of a mononial $X + a$, and it holds that

$$ \begin{align} (X + a)^p & = X^p + {p \choose 1} X^{p - 1} a + {p \choose 2} X^{p - 2} a^2 + \dots + {p \choose p - 1} X a^{p - 1} + a^p \\ & \equiv X^p + a^p \\ & \equiv X^p + a \pmod{p} \end{align} $$

Because $\displaystyle{p \choose i} \equiv 0 \pmod{p} \quad\forall\; i \in \{1, \dots, p - 1\}$. The above congruence holds true only for prime numbers. As a result, given a number $n$, the AKS test takes a monomial $X + a$ for some $a$ and computes $(X + a)^n$. Only if reducing modulo $n$ results in $X^n + a$, then $n$ is prime.

The AKS test uses also an irreducible polynomial to make computation more efficient, that is:

$$ (X + a)^p \equiv X^p + a \pmod{X^r - 1, p} $$

Applying modulo $X^r - 1$ does not change the result of the test, it only reduces the degree of $(X + a)^p$ on each iteration to be more efficient.

According to PRIMES is in P, these are the steps of the AKS algorithm:

Input: integer $n > 1$.

  1. If $n = a^b$ for $a \in \mathbb{N}$ and $b > 1$, output COMPOSITE.
  2. Find the smallest $r$ such that $\phi_r(n) > \log^2{n}$.
  3. If $1 < \gcd(a, n) < n$ for some $a \leqslant r$, output COMPOSITE.
  4. If $n \leqslant r$, output PRIME.
  5. For $a = 1$ to $\lfloor\sqrt{\phi(r)} \log{n}\rfloor$ do if $(X + a)^n = X^n + a \pmod{X^r − 1, n}$, output COMPOSITE;
  6. Output PRIME.

The implementation mistake

We have seen that AKS test is deterministic, so how are we going to break it? Well, this is just a vulnerable implementation:

def is_prime(n):
    # check if n = a^b for some a, b > 1
    for i in range(2, n.bit_length()):
        root, is_exact = gmpy2.iroot(n, i)
        if is_exact:
            return False

    rs = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]  
    return all(test(n, r) for r in rs)

def test(n, r):
    """
    check whether `(x + a) ^ n = x ^ n + a (mod x ^ r - 1)` in Z/nZ for some `a`.
    """
    R.<x> = Zmod(n)[]
    S = R.quotient_ring(x ^ r - 1)

    a = 1 + random.getrandbits(8)
    if S(x + a) ^ n != S(x ^ (n % r)) + a:
        return False
    return True

There are two things in this implementation that differ from the algorithm:

  • The SageMath script tests several $r$ values (all prime numbers lower than $100$), whereas the AKS algorithm suggests looking for a specific value of $r$ (step 2)
  • The SageMath script takes a random $a \in [1, 256]$ for the test, whereas the AKS algorithm iterates from $a = 1$ to $a = \lfloor\sqrt{\phi(r)} \log{n}\rfloor$ (step 5)

Breaking the AKS implementation

It is not clear what can happen if $a$ or $r$ are not correctly chosen, or how dangerous it is for the test to fail.

After researching on how to break primality tests, we can find Carmichael numbers. These are composite numbers that satisfy Fermat’s Little Theorem. In other words, $n$ is a Carmichael number if $n$ is composite and $b^n \equiv b \pmod{n}$ for all integers $b$ that are coprime with $n$.

Let’s try it:

$ sage -q
sage: import gmpy2
....: import random
sage:
sage: def test(n, r):
....:     """
....:     check whether `(x + a) ^ n = x ^ n + a (mod x ^ r - 1)` in Z/nZ for some `a`.  
....:     """
....:     R.<x> = Zmod(n)[]
....:     S = R.quotient_ring(x ^ r - 1)
....:
....:     a = 1 + random.getrandbits(8)
....:     if S(x + a) ^ n != S(x ^ (n % r)) + a:
....:         return False
....:     return True
....:
sage: test(561, 2)
True
sage: test(561, 3)
False
sage: test(561, 4)
False
sage: test(561, 5)
False
sage: test(1105, 2)
True
sage: test(1105, 3)
False
sage: test(1729, 2)
True
sage: test(1729, 3)
True
sage: test(1729, 5)
False

Finding Carmichael numbers

Some Carmichael numbers output True, we might be on the right track. There is a way to generate some Carmichael numbers: If $6k + 1$ and $12k + 1$ and $18k + 1$ are prime numbers for some integer $k$, then $n = (6k + 1) (12k + 1) (18k + 1)$ is a Carmichael number. Let’s generate a bunch of them:

$ python3 -q
>>> from Crypto.Util.number import isPrime
>>>
>>> for k in range(1000):
...     if isPrime(6 * k + 1) and isPrime(12 * k + 1) and isPrime(18 * k + 1):  
...         print(k, (6 * k + 1) * (12 * k + 1) * (18 * k + 1))
...
1 1729
6 294409
35 56052361
45 118901521
51 172947529
55 216821881
56 228842209
100 1299963601
121 2301745249
195 9624742921
206 11346205609
216 13079177569
255 21515221081
276 27278026129
370 65700513721
380 71171308081
426 100264053529
506 168003672409
510 172018713961
511 173032371289
710 464052305161
741 527519713969
800 663805468801
825 727993807201
871 856666552249
930 1042789205881
975 1201586232601

Let’s try the last one with all $r$ values of the implementation:

sage: rs = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]  
sage: [(r, test(1201586232601, r)) for r in rs]
[(2, True),
 (3, True),
 (5, True),
 (7, False),
 (11, False),
 (13, True),
 (17, False),
 (19, False),
 (23, False),
 (29, False),
 (31, False),
 (37, False),
 (41, False),
 (43, False),
 (47, False),
 (53, False),
 (59, False),
 (61, False),
 (67, False),
 (71, False),
 (73, False),
 (79, False),
 (83, False),
 (89, False),
 (97, False)]

As can be seen, for $r \in \{2, 3, 5, 13\}$, the test fails. Now we need to figure out why.

After a lot of tests with bigger Carmichael numbers, I found out that the test fails when $r$ divides $\phi(n)$. Since $n = (6k + 1) (12k + 1) (18k + 1)$ and the three factors are prime numbers, then $\phi(n) = (6k)(12k)(18k) = 2^4 \cdot 3^4 \cdot k^3$.

In the previous example, $n = 1201586232601$ is the Carmichael number with $k = 975 = 3 \cdot 5^2 \cdot 13$, so $\phi(n) = 2^4 \cdot 3^7 \cdot 5^6 \cdot 13^3$, which is divisible by every $r \in \{2, 3, 5, 13\}$.

Solution

So, we need a number $n$ such that $\phi(n) = 2^4 \cdot 3^4 \cdot k^3$ is divisible by all prime numbers less than $100$. This can be easily achieved by setting $k_0 = 5 \cdot 7 \cdots 97$ and then $k = m \cdot k_0$ for some integer $m$. As a result, since $k_0$ is divisible by every $r$ in the AKS implementation, so will be $k$ and we will break the test.

>>> from math import prod
>>>
>>> rs = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
>>> k_0 = prod(rs[2:])
>>> k_0
384261327324253070792183691221959345
>>>
>>> m = 1
>>> while True:
...     k = m * k_0
...     m += 1
...     if isPrime(6 * k + 1) and isPrime(12 * k + 1) and isPrime(18 * k + 1):
...         print(k, (6 * k + 1) * (12 * k + 1) * (18 * k + 1))
...         break
...
141792429782649383122315782060902998305 3694572010169851255631956434046586025725603891058582291439147359413655694039141973775417050450842378469305302694178881

There we have one candidate, and it breaks the test:

sage: [(r, test(3694572010169851255631956434046586025725603891058582291439147359413655694039141973775417050450842378469305302694178881, r)) for r in rs]  
[(2, True),
 (3, True),
 (5, True),
 (7, True),
 (11, True),
 (13, True),
 (17, True),
 (19, True),
 (23, True),
 (29, True),
 (31, True),
 (37, True),
 (41, True),
 (43, True),
 (47, True),
 (53, True),
 (59, True),
 (61, True),
 (67, True),
 (71, True),
 (73, True),
 (79, True),
 (83, True),
 (89, True),
 (97, True)]

Flag

Now that we have a Carmichael number that breaks the test and the corresponding $k$ value, we must enter the number and a factor (for instance, $6k + 1$) to get the flag:

$ nc prime.balsnctf.com 10003
prime: 3694572010169851255631956434046586025725603891058582291439147359413655694039141973775417050450842378469305302694178881  
factor: 850754578695896298733894692365417989831
You got me
BALSN{th3_imp1_15_bR0k3n_4nd_mUch_sL0W3r_tH4n_pycrypto_is_prime_qwq}