Page en construction !
L'usage de la cryptographie à clef publique est de plus en plus répandu. En effet un certain nombre de tâches sont désormais possibles électroniquement, comme la signature, l'authentification et bien sûr la confidentialité des transferts de données ce qui s'avère utile voire indispensable pour des applications courantes: transactions bancaires, santé, commerce électronique, ...
L'exemple le plus célèbre d'une solution à ces problèmes est le protocole RSA, dont la sécurité est basée sur la difficulté de la factorisation d'entiers. D'autres protocoles permettent d'effectuer essentiellement les mêmes tâches en travaillant sur un groupe abélien fini . La sécurité repose alors sur la difficulté du problème du logarithme discret dans le groupe. Les protocoles Diffie-Hellman et ElGamal rentrent dans cette catégorie.
Les premiers groupes proposés pour usage cryptographique furent les groupes (Z/pZ)* où p est un grand nombre premier, puis les groupes de classes de corps quadratiques. Ensuite Miller et Koblitz montrèrent que l'on pouvait aussi utiliser les courbes elliptiques définies sur un corps fini. En effet un tel objet géométrique peut être muni d'une loi d'addition et forme alors un groupe fini.
Plus généralement, pour toute courbe C définie sur un corps fini, on peut construire un groupe abélien fini, appelé la Jacobienne de C avec lequel il est possible de bâtir des protocoles cryptographiques.
L'avantage des courbes est que pour une sécurité donnée, la taille des clefs est plus petite. Ceci est dû au fait que le meilleur algorithme connu pour calculer le logarithme discret sur la Jacobienne d'une courbe elliptique est exponentiel, alors que l'on dispose d'algorithmes sous-exponentiels pour factoriser les entiers et pour le logarithme discret dans (Z/pZ)*.
Il est en général admis qu'une clef elliptique de 160 bits offre une sécurité équivalente à une clef RSA 1024 bits. Ceci n'est qu'un ordre de grandeur. Pour se faire une idée plus précise, le record de la plus grande clef cassée pour RSA est 512 bits (le labo a participé! voir ici ), et la plus grande clef elliptique cassée est de taille 109 bits (cf. la page de R. Harley, le recordman actuel).
Les courbes non elliptiques offrent le même genre d'avantage par rapport à RSA: la taille de clef nécessaire est la même que pour les courbes elliptiques, à sécurité égale. Une différence qui peut être intéressante à exploiter est que le corps fini sur lequel on travaille est bien plus petit, ce qui peut s'avérer décisif dans des milieux très contraints. Les courbes hyperelliptiques sont une famille de courbes pour lesquelles les calculs dans la Jacobienne sont assez facile à mener.
Une courbe hyperelliptique est une courbe C qui admet une équation de la forme
Voici à quoi ressemble une courbe hyperelliptique de genre 2:
Contrairement aux courbes elliptiques, il n'y a pas de loi de groupe définissable directement sur l'ensemble des points de la courbe. C'est pourquoi on étudie la Jacobienne de C qui, elle, peut être munie d'une loi d'addition. Nous allons nous restreindre au cas du genre 2 pour simplifier. Toutes les définitions peuvent se généraliser au genre supérieur.
La Jacobienne d'une courbe C de genre 2 est la réunion des ensembles suivants:
Pour faire la somme de deux diviseurs D1 = P1 + P2 et D2 = Q1 + Q2, on applique une méthode qui ressemble assez à la loi "corde et tangente" pour les courbes elliptiques. On trace la courbe y=p(x) passant par les quatre points P1, P2, Q1, Q2, où p(x) est un polynôme de degré 3. Cette courbe coupe C en deux autres points R1 et R2 et on prend leur symetriques S1 et S2. On a alors
Telle qu'elle est présentée ci-dessus la loi de groupe dans la Jacobienne d'une courbe hyperelliptique ne paraît pas très facile à effectuer. Cantor a trouvé un algorithme efficace pour la loi de groupe utilisant une représentation des diviseurs due à Mumford. Finalement, calculer dans la Jacobienne d'une courbe hyperelliptique peut se faire en utilisant seulement des opérations de base sur des polynômes : addition, produit, pgcd.
Les problèmes suivants ne sont pas encore résolus:
La connaissance du cardinal exact d'un groupe est nécessaire si l'on veut construire un cryptosystème. En effet, afin de garantir une bonne sécurité, le cardinal doit être premier ou presque premier. Il existe un algorithme théorique dû à Pila qui effectue cette tâche en temps polynomial. Cet algorithme s'inspire de l'algorithme de Schoof pour les courbes elliptiques.
Les axes de recherche sur ce sujet sont:
En 1994, Adleman, Demarrais et Huang ont présenté un algorithme résolvant le problème du log discret pour une courbe hyperelliptique de genre "grand". Il s'agit d'un algorithme de complexité sous-exponentiel i.e. le même genre de complexité que pour attaquer RSA. Depuis cette attaque, on préfère les courbes de genre faible afin de garder une taille de clef minimale.
Récemment, il a été montré que les courbes de genre supérieur à 4 étaient moins sûres que les autres. En plus des conséquences directes sur la cryptogaphie hyperelliptique, il y a des retombées sur la cryptographie elliptique. En effet, la descente de Weil permet dans certaines conditions de ramener un problème elliptique à un problème de genre supérieur. Il est désormais déconseillé d'utiliser les courbes définies sur une extension composée de GF(2) .
Le principal problème ouvert est: