CryptoHack | Modular Square Root

Modular Square Root

Modular Square Root sur CryptoHack est un challenge à 35 points. On reçoit un entier a et un nombre premier p de 2048 bits. Il faut trouver un nombre dont le carré redonne a modulo p.

Deux racines sont possibles. L'énoncé demande la plus petite.

Préparer les valeurs

Les données du challenge contiennent deux entiers. a est le nombre dont on cherche la racine. p est le nombre premier utilisé comme modulo.

J'ouvre une console avec python3 puis je copie les deux affectations complètes a = ... et p = ....

Vérifier qu'une racine existe

Je vérifie la taille de p et son reste modulo 4. Le critère d'Euler permet ensuite de vérifier que a possède une racine :

print("Taille de p :", p.bit_length(), "bits")
print("p modulo 4 :", p % 4)
print("Racine existante:", pow(a, (p - 1) // 2, p) == 1)

Le résultat confirme que p fait 2048 bits et que son reste modulo 4 vaut 1. Le test d'Euler renvoie True car pow(a, (p - 1) // 2, p) vaut 1.

pow calcule directement une puissance modulo p. Le // correspond à une division entière.

La formule pow(a, (p + 1) // 4, p) ne convient que lorsque p % 4 == 3. Ici le reste vaut 1. Il faut donc utiliser une autre méthode.

Utiliser Tonelli-Shanks

Tonelli-Shanks permet de calculer une racine modulo un premier impair. Il couvre aussi le cas p % 4 == 1 rencontré ici.

L'algorithme commence par écrire p - 1 = q × 2^s avec q impair. Pour cela on divise p - 1 par deux tant que le résultat reste pair.

Il cherche ensuite un non-résidu quadratique z. C'est un entier pour lequel le test d'Euler donne p - 1 au lieu de 1. Ce nombre sert à construire les corrections appliquées à la racine.

On initialise alors trois valeurs. r est la racine à ajuster. t sert à suivre ce qu'il reste à corriger. c fournit les facteurs de correction. La boucle ajuste ces valeurs jusqu'à obtenir t == 1.

Voici la fonction utilisée pour reproduire le calcul :

def tonelli_shanks(a, p):
    a %= p
    if a == 0:
        return 0
    if p == 2:
        return a
    if pow(a, (p - 1) // 2, p) != 1:
        raise ValueError("Ce nombre ne possède pas de racine modulo p")

    q = p - 1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1

    z = 2
    while pow(z, (p - 1) // 2, p) != p - 1:
        z += 1

    c = pow(z, q, p)
    r = pow(a, (q + 1) // 2, p)
    t = pow(a, q, p)
    m = s

    while t != 1:
        i = 0
        test = t
        while test != 1:
            test = test * test % p
            i += 1

        b = pow(c, 2 ** (m - i - 1), p)
        r = r * b % p
        c = b * b % p
        t = t * c % p
        m = i

    return r

Cette fonction suppose que p est premier. C'est une donnée de l'énoncé. Le test du début vérifie que a possède une racine mais ne vérifie pas la primalité de p.

On peut suivre la logique de la boucle avec deux relations. Elle conserve r² ≡ a × t modulo p. Elle fait aussi diminuer m à chaque tour. Quand t arrive à 1 on a donc r² ≡ a modulo p.

Pour info : pour les valeurs de ce challenge la décomposition donne s = 5. Le premier non-résidu trouvé en testant les entiers à partir de 2 est z = 29.

Choisir la plus petite racine

Depuis la console Python ouverte dans le même dossier que tonelli.py je charge la fonction. Les variables a et p doivent toujours contenir les valeurs du challenge.

from tonelli import tonelli_shanks

r = tonelli_shanks(a, p)
autre_racine = p - r
flag = min(r, autre_racine)

Si r est une racine alors −r en est une aussi car les deux ont le même carré. Entre 0 et p - 1 cette seconde racine s'écrit p - r.

min conserve la plus petite des deux.

Vérifier la réponse

Je contrôle les deux racines puis le choix de la plus petite :

print("Première racine valide :", pow(r, 2, p) == a)
print("Seconde racine valide :", pow(autre_racine, 2, p) == a)
print("Plus petite racine choisie :", flag < p - flag)

Les trois tests renvoient True. Les deux premiers confirment que les deux carrés redonnent a modulo p.

Il reste à afficher le nombre à soumettre :

print(flag)

Son carré modulo p doit redonner exactement a. Tonelli-Shanks permet de le trouver sans tester tous les entiers possibles.

Conclusion

Le test d'Euler confirme qu'une racine existe. Avec p % 4 == 1 on utilise Tonelli-Shanks pour la calculer. On garde ensuite la plus petite des deux racines. Le dernier contrôle consiste à vérifier que son carré modulo p redonne bien a.