<- BALSN CTF

Prime

9 minutos de lectura

Se nos proporciona el código fuente del servidor en 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()

Análisis del código fuente

El script implementa la prueba de primalidad AKS y pide un número primo que tenga un factor diferente de $1$ y el mismo número:

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

Si esto sucede, el servidor mostrará la flag. Pero esto es una contradicción, ya que un número primo solo es divisible entre $1$ y entre sí mismo. Por lo tanto, el objetivo del reto es enviar un número compuesto especial que sea considerado como número primo por la implementación de la prueba de primalidad AKS. En resumen, necesitamos romper esta prueba de primalidad.

Prueba de primalidad AKS

En primer lugar, necesitamos investigar un poco sobre la prueba de primalidad AKS. Encontré buena información sobre estos recursos:

Básicamente, la prueba está construida a partir del Pequeño Teorema de Fermat, donde $a^p \equiv a \pmod{p}$. Esto es válido para todos los números primos, pero hay otros números especiales que también satisfacen la condición. (números de Carmichael, más sobre esto a continuación). Para superar esto, la prueba AKS considera la potencia $p$-ésima de un monomio $X + a$, y se cumple que

$$ \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} $$

Ya que $\displaystyle{p \choose i} \equiv 0 \pmod{p} \quad\forall\; i \in \{1, \dots, p - 1\}$. La congruencia anterior es cierta solo para números primos. Como resultado, dado un número $n$, la prueba AKS toma un monomio $X + a$ por un cierto $a$ y calcula $(X + a)^n$. Solo si al reducir módulo $n$ se obtiene como resultado $X^n + a$, entonces $n$ es primo.

La prueba de AKS utiliza también un polinomio irreducible para hacer que el cálculo sea más eficiente, es decir:

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

Aplicar módulo $X^r - 1$ no cambia el resultado de la prueba, solo reduce el grado de $(X + a)^p$ en cada iteración para ser más eficiente.

De acuerdo con PRIMES is in P, Estos son los pasos del algoritmo AKS:

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.

El fallo de implementación

Hemos visto que la prueba AKS es determinista, entonces, ¿cómo vamos a romperla? Bueno, esta es solo una implementación vulnerable:

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

Hay dos cosas en esta implementación que difieren del algoritmo.:

  • El script de SageMath utiliza pruebas varios valores de $r$ (todos los números primos de menores que $100$), mientras que el algoritmo AKS sugiere buscar un valor específico de $r$ (paso 2)
  • El script de SageMath toma un valor aleatorio $a \in [1, 256]$ para la prueba, mientras que el algoritmo de AKS itera desde $a = 1$ hasta $a = \lfloor\sqrt{\phi(r)} \log{n}\rfloor$ (paso 5)

Rompiendo la implementación de AKS

No está claro qué puede suceder si $a$ o $r$ no se eligen correctamente, o lo peligroso que es para que la prueba falle.

Después de investigar sobre cómo romper pruebas de primalidad, podemos encontrar los números de Carmichael. Estos son números compuestos que satisfacen el Pequeño Teorema de Fermat. En otras palabras, $n$ es un número Carmichael si $n$ es compuesto y $b^n \equiv b \pmod{n}$ fpara cualquier entero $b$ que es coprimo con $n$.

Vamos a probarlo:

$ 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

Encontrando números de Carmichael

Algunos números de Carmichael devuelven True, Podríamos estar en el camino correcto.Hay una manera de generar algunos números de Carmichael: si $6k + 1$ y $12k + 1$ y $18k + 1$ son números primos para algún $k$, entonces $n = (6k + 1) (12k + 1) (18k + 1)$ es un número de Carmichael. Vamos a generar unos cuantos:

$ 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

Probemos el último con todos con los valores de $r$ de la implementación:

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)]

Como se puede ver, para $r \in \{2, 3, 5, 13\}$, la prueba falla.Ahora tenemos que averiguar por qué.

Después de muchas pruebas con números más grandes de Carmichael, descubrí que la prueba falla cuando $r$ divide a $\phi(n)$. Como $n = (6k + 1) (12k + 1) (18k + 1)$ y los tres factores son números primos, entonces $\phi(n) = (6k)(12k)(18k) = 2^4 \cdot 3^4 \cdot k^3$.

En el ejemplo anterior, $n = 1201586232601$ es el número de Carmichael con $k = 975 = 3 \cdot 5^2 \cdot 13$, por lo que $\phi(n) = 2^4 \cdot 3^7 \cdot 5^6 \cdot 13^3$, que es divisible por todo $r \in \{2, 3, 5, 13\}$.

Solución

Entonces, necesitamos un número $n$ tal que $\phi(n) = 2^4 \cdot 3^4 \cdot k^3$ sea divisible por todos los números primos menores que $100$. Esto se puede lograr fácilmente estableciendo $k_0 = 5 \cdot 7 \cdots 97$ y luego $k = m \cdot k_0$ para algún entero $m$. Así, como $k_0$ es divisible por cada $r$ en la implementación de AKS, también los será $k$ y romperemos la prueba.

>>> 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

Y aquí tenemos un candidato y rompe la prueba:

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

Ahora que tenemos un número Carmichael que rompe la prueba y su valor de $k$ correspondiente, debemos ingresar el número y un factor (por ejemplo, $6k + 1$) para obtener la 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}