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
Réponses
-
Je ne comprends pas le principe. Comment est-ce que Bob peut vérifier quelque chose sans calculer $Q$ ni $n$ ?
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. -
J'avoue qu'on arrive à connaître $n$, mais le degré de $Q$ peut être grand si, par exemple, $n=2$. Donc je ne suis pas satisfait par cette réponse.
-
Si Oscar intercepte $P$, il lui suffit ensuite de réenvoyer $P$ pour se faire passer pour Alice ??
-
Surtout que dans ce protocole il ne semble n'y avoir qu'une signature possible pour Alice....
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. -
Il y en a qui devraient regarder des vidéos sur le net.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres