Contexte

L’ECM est une méthode de factorisation d'entiers basée sur les courbes elliptiques dont la particularité est d'avoir une complexité dépendant uniquement du plus petit facteur premier de l'entier traité. Cette méthode permet aujourd'hui de trouver des facteurs d'une centaine de bits. Outre son intérêt intrinsèque, elle est aussi utilisée comme sous-méthode de méthodes applicables à de plus grands nombres (QS et NFS). Les FPGAs étant de bons accélérateurs matériels pour les algorithmes demandant une importante puissance de calcul, une implantation matérielle sur FPGA de l’ECM pourrait être une avancée pour les méthodes de factorisation.

Description

L'objet de cette étude est de déterminer quelles sont les implantations les plus efficaces de l'algorithme ECM sur FPGA dans le but de sélectionner rapidement des nombres assurés d'être composites. Cette détermination passera par la synthèse et la simulation sur les dernières générations de composants FPGA disponibles auprès des principaux acteurs du marché (Xilinx, Altera). Dans ce cadre, nous envisageons les axes de recherche suivants :

• Exploration des implantations possibles des briques arithmétiques de base dans l’environnement développé par le LIP6.
• Exploration des implantations d'opérations arithmétiques dans des corps finis quelconques en utilisant, par exemple, des algorithmes de type Montgomery, automates cellulaires, etc.
• Choix de classes de courbes (Edwards, Montgomery, etc.) dont la complexité de calcul de la loi de groupe est plus faible sans exclure bien évidemment d'autres axes y compris d'origine plus théorique.

La performance des implantations sera évaluée selon le nombre de points ou de courbes calculés par unité de temps et sera comparée à une implémentation de référence sur CPU déjà disponible, comme par exemple GMP-ECM.

Compétences requises

Le candidat devra avoir effectué un doctorat dans la thématique des architectures matérielles si possible autour de la sécurité. Il devra avoir les notions mathématiques liées à la cryptographie (algèbre, corps finis etc.) ainsi que de bonnes compétences en programmation. Une expérience d’implantation d’architectures sur FPGA est fortement recommandée.

Conditions

L’offre correspond à un CDD d’un an éventuellement renouvelable en cas de prolongation du projet et est à pourvoir immédiatement. Le salaire est d’environ 1900 € net par mois à moduler en fonction de l’expérience du candidat. Le travail se déroulera dans les locaux du LIP6, 4 place Jussieu, Paris 5e.

Contact

Roselyne Chotin-Avot, +33 (0)1.44.27.65.28