J'ai entendu dire que ça pourrait résister quand même, pour plusieurs raisons:
polynomial n'implique pas rapide, si la vérification est en O(N) et que le cassage de la clé publique se fait en O(N10) (et pas mieux), et qu'on casse en un temps raisonnable (disons 1 jour) une clé de taille k, en prenant simplement une clé de taille 2*k il faudrait un peu plus de 2 ans pour casser la clé, ça devient plus raisonnable. Bon c'est pas aussi bien que d'avoir un algo exponentiel en face mais ça peut être pas mal à condition de renouveler souvent les clés.
la notation en O cache une constante, si la constante est très élevée pour l'algo de cassage il se peut que la solution polynomiale ne vaille pas la peine (il y a d'ailleurs des problèmes où il existe une solution polynomiale mais où les gens préfèrent la solution exponentielle parce qu'elle est plus rapide en pratique).
Donc ça serait certes problématique, mais pas forcément la fin de la cryptographie asymétrique. On vivrait toujours dans la crainte qu'il existe un algo plus rapide que ceux qu'on connaît, et que quelqu'un le garde pour soi, mais cette crainte existe déjà aujourd'hui.
[^] # Re: Des commentaires de chercheur ?
Posté par Shuba . En réponse au journal P=NP démontré ?. Évalué à 5.
J'ai entendu dire que ça pourrait résister quand même, pour plusieurs raisons:
Donc ça serait certes problématique, mais pas forcément la fin de la cryptographie asymétrique. On vivrait toujours dans la crainte qu'il existe un algo plus rapide que ceux qu'on connaît, et que quelqu'un le garde pour soi, mais cette crainte existe déjà aujourd'hui.