Coppersmith pour les nuls

Recemment je suis tombe sur un probleme "interessant" ayant trait a RSA. La facon dont c'etait implemente me laissant a penser que quelque chose n'allait pas, et meme si j'apprecie la cryptographie, je n'ai pas la science infuse et il m'a fallu chercher a droite et a gauche une solution adequate (et simple).

En voici la version anonymisee.

Considerons le probleme ou Bob le developpeur veut chiffrer une cle AES 128 avec du RSA - 1024 bits parceque Bob sait qu'en dessous c'est pas "sur". Bob n'est pas super au point avec les standards, et il ne dispose que de quelques API d'arithmetique modulaire. Toujours est-il que Bob reussit a generer ses nombres premiers, choisit e=3 (pour la simplicite?), et calcule d correctement. Maintenant Bob se doute que si il chiffre sa cle AES (m) directement avec e=3, cela ne va pas mener a grand chose puisque m^3 < n. Donc Bob complete son message avec des 1 (padding fixe). En python, cela ressemblerait a:



La problematique est la suivante: connaissant n et e de la cle RSA (parametres publiques), et le message chiffre m', peut-on recouvrer la cle AES?

Et bien cela tombe pile poil dans le domaine couvert par l'attaque de Coppersmith (sugere par @kyprizel) avec f(x)=(2^1023-2^128+x)^3-mprime. Maintenant le probleme est de trouver une implementation de Lenstra–Lenstra–Lovász, ou de le reimplementer soi-meme. La solution se trouve dans la bibliotheque Sage, et le Sage Notebook disponible en ligne si vous ne voulez pas installer les 400MB sous Linux, ou la VM VirtualBox sous Windows - et probablement ailleurs mais je me suis arrete a ce qui marchait.

Avec les quelques lignes de code suivantes sous Sage Notebook vous recupererez les 128 bits de la cle instantanement:



C'est moche pour Bob, il avait fait un effort ce coup-ci :(