Un protocole de signature électronique
dans Arithmétique
Bonjour,
ce message est un essai de protocole de signature électronique.
Alice choisit $Q$ un polynôme sur un corps fini, elle choisit aussi un entier $n$ et elle calcule $P(X)=Q (Q(Q(\cdots(Q(X))))$, la composée $n$ fois de $Q$ par lui même. Le banquier est Bob qui vérifie, sachant $P$, qu'Alice lui a bien fournit $Q$ et $n$. La difficulté pour Oscar est de trouver $Q$ et $n$ sachant $P$.
Merci de casser ce cryptosystème,
Apollonius
ce message est un essai de protocole de signature électronique.
Alice choisit $Q$ un polynôme sur un corps fini, elle choisit aussi un entier $n$ et elle calcule $P(X)=Q (Q(Q(\cdots(Q(X))))$, la composée $n$ fois de $Q$ par lui même. Le banquier est Bob qui vérifie, sachant $P$, qu'Alice lui a bien fournit $Q$ et $n$. La difficulté pour Oscar est de trouver $Q$ et $n$ sachant $P$.
Merci de casser ce cryptosystème,
Apollonius
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Dans un autre esprit, la taille de $Q$ augmente de façon exponentielle, ce qui borne $n$ assez fort – par exemple, sur Sage, c'est-à-dire sur Singular, le degré maximal d'un polynôme est $65536=2^{16}$ par défaut (encore plus petit que prévu). Il faut 1,7 s à Sage pour calculer la 15e itération de $x^2+1$ sur $\mathbf{F}_{25}$ (mais Sage n'est pas très fort à ça).
De plus, le degré de $P$ permet de retrouver $d^n$, où $d$ est le degré de $Q$. Vu la remarque précédente, cela permet de trouver $d$ avec peu d'indétermination (le pire qui puisse arriver, c'est de remplacer $d^n$ par $(d^e)^{n'}$ avec $n=en'$). Connaître le degré de $Q$, sans doute assez petit, pourrait permettre une attaque par force brute.
Le principe d'une signature électronique est que tout le monde peut en vérifier l'authenticité d'une signature qui théoriquement ne peut être élaborée que par une seule personne.
Une façon de procéder est de combiner l'usage de sa clé privée et de la clé publique du destinataire: il y a tout un tas de vidéos sur le net expliquant cela bien mieux que je n'en serais capable ;-)
Bonne journée
F.