L’alorithme de signature se résume en une exponentiation modulo N (le s.n du programme). C’est donc une fonction déterministe et multiplicative : si s1 et s2 sont les signatures de m1 et m2, alors s1·s2 mod N est la signature pour m1·m2.
Comme le challenge est choisi inférieur à 2^24, il y a 16 millions de possibilités, ce qui est plus que de requêtes qu’on peut faire en une minute. On doit donc exploiter la multiplicativité de la signature : on peut demander la signature de tous les nombres premiers. Ensuite il suffit de factoriser le challenge (il est assez petit pour que ce soit faisable) et de multiplier les signatures des facteurs premiers.
Cependant, il y a encore trop de nombres premiers inférieurs à 2^24 (il y en a environ 2^24/ln(2^24), soit environ 10^6). Il faut donc réduire encore le nombre de requêtes. On chercher le plus petit nombre de nombres premiers qui permettent de factoriser une fraction suffisante des challenges possibles. Pour chaque nombre premier inférieur à 2^24, on peut compter le nombre de multiples qu’il a entre 0 et 2^24. On se rend alors compte que si on se garde que les nombres premiers inférieurs à 20 000, on peut encore factoriser 50% des challenges possibles, avec seulement 2000 nombres premiers (20000/ln(20000)). On ne pourra donc pas forger une signature à chaque fois, mais il suffit de recommencer une ou deux fois pour réussir.
from sympy.ntheory import Sieve, factorint
def crack():
s = Sieve()
s.extend(20000)
sigs = {}
for p in s._list :
sig = query(p)
sigs[p] = sig
challenge = get_challenge()
factors = factorint(challenge, unique=True)
forge = 1
for i in factors:
forge = (forge * sigs[i]) % N
verif(forge)