Aller au contenu
skifo/ BA26 CTF
Tous les challenges
Crypto Résolu

ecrsa

KMOV, un « RSA » sur courbe elliptique : le chiffré trahit un point d'ordre 3.

Scripts
1 fichier

Énoncé (résumé)

Chiffrement KMOV (Koyama, Maurer, Okamoto, Vanstone, 1991) : un « RSA » sur la courbe elliptique y² = x³ + b mod n.

  • Le message est encodé en point M = (m₁, m₂). b est déduit de M et n’est pas publié ; les formules d’addition n’en ont pas besoin (a = 0).
  • Chiffrement : C = e·M, avec e = 65537. Déchiffrement : M = d·C.
  • n fait 1024 bits.

Les indices :

  • La clé a été générée « sans soin » (« Kä Luscht »).
  • Pollard p−1 ne marche pas, mais « ce n’est pas du RSA ».
  • Si l’attaque demande de choisir un point, il faut le prendre au hasard.

Fichiers fournis : kmov.py (arithmétique de la courbe et encodage) et output.txt (n, e, C = (cx, cy)).

Reconnaissance

Deux observations :

  1. Le chiffré a cx = 0. cy est très proche de n : n − cy ne fait qu’environ 220 bits.
  2. L’encodage complète le message par des zéros à gauche. encode() remplit avec des zéros jusqu’à 2k octets, puis coupe en deux moitiés de k octets. Un message court tient donc entièrement dans m₂, et on obtient m₁ = 0.

Vulnérabilité

1. Le clair est un point d’ordre 3 (exploitation directe)

Sur y² = x³ + b, un point (0, y) est un point d’inflexion. La tangente y a la pente 3x²/2y = 0. Le doublement donne x₃ = 0 et y₃ = −y, donc 2P = −P : le point est d’ordre 3.

Comme e = 65537 ≡ 2 (mod 3), on a :

C = e·M = 2·M = −M     ⇒     M = −C = (0, n − cy)

On n’a besoin ni de la clé privée ni de factoriser n. Il suffit de décoder n − cy en octets.

2. p+1 est smooth (la faiblesse de la clé, voie prévue)

Pour p ≡ 2 (mod 3), toutes les courbes y² = x³ + b mod p sont supersingulières : elles ont exactement p + 1 points, quel que soit b. Le groupe qui compte est donc d’ordre (p+1)(q+1), et non (p−1)(q−1). C’est pour ça que Pollard p−1 échoue.

Ici, p+1 est smooth. On prend un point au hasard P mod n, ce qui fixe implicitement une courbe b aléatoire (« one curve always works »). On calcule ensuite k·P, où k est le produit des puissances des premiers jusqu’à B = 200 000. Dans F_p, le point devient l’infini : un dénominateur n’est plus inversible mod n, et gcd(dénominateur, n) = p.

Le point (2, 3) sur y² = x³ + 1 ne convient pas : il est d’ordre 6 partout, d’où l’avertissement de l’énoncé.

Facteurs obtenus en environ 17 s :

p = 7324841276285030912641981522450434899557228926744082328881359338878181450068075236543038921697178260102942469204290599509012090666807563820496961460367501
q = 7493259826304015283500794199789027157644058742218744453821437213689740701620175281316139730427779717805259384818701931945262288093902701351731710644293069

Exploitation (reproductible)

  1. Lire n, e, cx, cy dans output.txt, en les extrayant par regex sans exécuter le fichier.
  2. Vérifier que cx == 0, poser M = (0, (−cy) mod n) et vérifier que e·M == C.
  3. Décoder : k = (n.bit_length() − 1) // 8, puis concaténer m₁ et m₂ sur k octets chacun et retirer les octets nuls de tête.
  4. (Optionnel) --factor exécute l’attaque p+1 sur la courbe supersingulière et affiche p et q.
python3 -I solve.py files/output.txt            # flag
python3 -I solve.py files/output.txt --factor   # flag + p, q (~17 s)

Sortie :

BA26{0ne_curve_always_w0rks}

Script

solve.py : arithmétique de la courbe réimplémentée (aucun import du kmov.py téléchargé), raccourci de l’ordre 3 et factorisation p+1.

Leçons

  • Encoder un message court avec un remplissage de zéros déterministe donne une coordonnée nulle, donc un point de petit ordre. C’est fatal, quelle que soit la clé.
  • En KMOV, l’ordre du groupe est (p+1)(q+1). Il faut donc des premiers dont p+1 (et pas seulement p−1) a un grand facteur premier.

Code

"""ecrsa (BlackAlps) -- KMOV on y^2 = x^3 + b mod n.

Flaw: the flag is short, so encode() left-pads it into the second half and
m1 = 0.  M = (0, m2) is an inflection point of y^2 = x^3 + b: 2M = -M, so M
has order 3 and C = e*M = (e mod 3)*M = 2*M = -M.  Hence M = -C = (0, n - cy),
no key needed.  (The intended route, matching the flag text: for p = 2 mod 3
every curve y^2 = x^3 + b mod p is supersingular with order p+1, and p+1 is
smooth, so a random point times a smooth bound leaks p -- see factor().)

Usage: python3 -I solve.py files/output.txt
"""
import re
import sys
from math import gcd
import random


def inv(a, n):
    g = gcd(a % n, n)
    if g != 1:
        raise ZeroDivisionError(g)
    return pow(a, -1, n)


def add(P, Q, n):
    if P is None:
        return Q
    if Q is None:
        return P
    (x1, y1), (x2, y2) = P, Q
    if x1 == x2 and (y1 + y2) % n == 0:
        return None
    if P == Q:
        lam = 3 * x1 * x1 * inv(2 * y1, n) % n
    else:
        lam = (y2 - y1) * inv(x2 - x1, n) % n
    x3 = (lam * lam - x1 - x2) % n
    return x3, (lam * (x1 - x3) - y1) % n


def mul(k, P, n):
    R = None
    while k:
        if k & 1:
            R = add(R, P, n)
        P, k = add(P, P, n), k >> 1
    return R


def primes(B):
    s = bytearray([1]) * (B + 1)
    s[0] = s[1] = 0
    for i in range(2, int(B ** 0.5) + 1):
        if s[i]:
            s[i * i::i] = bytearray(len(s[i * i::i]))
    return [i for i in range(B + 1) if s[i]]


def factor(n, B=200000):
    """p+1 attack via supersingular y^2 = x^3 + b (random point, random b)."""
    P = (random.randrange(n), random.randrange(n))
    try:
        for q in primes(B):
            qk = q
            while qk * q <= B:
                qk *= q
            P = mul(qk, P, n)
            if P is None:
                return None
    except ZeroDivisionError as z:
        g = z.args[0]
        return g if 1 < g < n else None
    return None


def main(path):
    v = dict(re.findall(r"(\w+)\s*=\s*(\d+)", open(path).read()))
    n, e, cx, cy = (int(v[k]) for k in ("n", "e", "cx", "cy"))
    C = (cx, cy)
    assert cx == 0, "shortcut needs m1 = 0"
    M = (0, (-cy) % n)
    assert mul(e, M, n) == C
    k = (n.bit_length() - 1) // 8
    flag = (M[0].to_bytes(k) + M[1].to_bytes(k)).lstrip(b"\0")
    print(flag.decode())
    if "--factor" in sys.argv:
        p = factor(n)
        print("p =", p, "q =", n // p if p else None)


if __name__ == "__main__":
    main(sys.argv[1])

Aussi en Crypto