Discussion :

[BillaEAS]

Bonjour à tous
j'ai une question concernant la cryptographie
on dit il n'existe pas un algorithme exponentiel pour résoudre un tel problème, dans un autre cas on dit qu'il n'existe pas un algorithme sous exponentiel pour résoudre par exemple le problème du logarithme discret elliptique
Quelle est la définition d'un algorithme exponentiel et d'un algorithme sous exponentiel (la différence entre les deux)

[gangsoleil]

Bonjour,

Je pense que tu devrais commencer par la : https://secure.wikimedia.org/wikiped...%A8me_P_%3D_NP

[Invité]

Effectivement, ces dernières années on note une émergence des clés ECC (Elliptic Curve Cryptography) parce qu'il n'existe pas d'algorithme sous-exponentiel pour résoudre le problème du logarithme discret elliptique.

A taille égale, une clé ECC est donc plus résistante qu'une clé RSA. De mémoire je crois que la complexité de crackage d'une clé de 350 bits ECC est équivalente à celle d'une clé RSA de plus de 10000 bits si l'elliptique est judicieusement choisie.

Et c'est pas pour rien que BlackBerry, IBM et Microsoft (je crois qu'ils appellent ça CNG - Cryptography Next Gen) ont adopté le cryptage elliptique. Hormis le "side chanel attack" (possible aussi pour tout RSA-cryptosytème), c'est inviolable.

Steph