LIP6 CNRS Sorbonne Université Tremplin Carnot Interfaces
Direct Link LIP6 » News » PhD students

ZEITOUN Rina

PhD graduated
Team : PolSys
Departure date : 11/20/2015
Supervision : Jean-Charles FAUGÈRE
Co-supervision : RENAULT Guénaël

Méthodes algébriques pour l'analyse de sécurité des implantations d'algorithmes Cryptographiques

Le 10ème problème de Hilbert, consistant à trouver les solutions entières d'équations polynomiales, est un problème crucial en cryptanalyse. Si ce dernier a été prouvé indécidable, Coppersmith publia en 1996 une méthode basée sur la réduction de réseaux permettant de trouver efficacement l'ensemble des petites solutions de certaines équations polynomiales. De nombreuses applications de cette méthode ont vu le jour dans le domaine de la cryptanalyse de chiffrements à clé publique, notamment lorsque le cryptosystème est exécuté sur un système embarqué et qu'une partie de la clé secrète est dévoilée par la réalisation d'attaques physiques sur le dispositif. Dans ce contexte, nous proposons une attaque physique sur le schéma de signature RSA en mode CRT où une application de la méthode de Coppersmith permet de compléter l'information obtenue par l'attaque physique. Nous proposons également un nouvel algorithme déterministe basé sur la méthode de Coppersmith pour factoriser les entiers de la forme $N=p^rq^s$ en temps polynomial lorsque $r$ ou $s$ sont suffisamment grands.
Enfin, si les applications de la méthode de Coppersmith sont nombreuses, en pratique, du fait que les réseaux euclidiens à réduire soient gigantesques, les petites solutions ne peuvent être retrouvées que jusqu'à une borne qui est plus petite que la borne théorique annoncée. Aussi, une autre contribution de cette thèse consiste en la proposition de deux méthodes permettant une accélération du temps d'exécution de l'algorithme de Coppersmith. Lorsque les deux méthodes sont combinées, le nouvel algorithme s'effectue des centaines de fois plus rapidement pour des paramètres typiques, permettant ainsi dans de nombreux cas d'atteindre la borne théorique.
Defence : 07/16/2015 - 14h15 - Site Jussieu 25-26/105
Jury members :
STEHLE Damien (ENS Lyon) [Rapporteur]
GUTIERREZ Jaime (Université de Cantabria) [Rapporteur]
FAUGÈRE Jean-Charles (INRIA, UPMC, CNRS, LIP6)
RENAULT Guénaël (INRIA, UPMC, CNRS, LIP6)
CORON Jean-Sébastien (Université du Luxembourg)
NGUYEN Phong (INRIA, ENS Ulm)
GRAILLAT Stef (UPMC, CNRS, LIP6)

2013-2016 Publications

 Mentions légales
Site map |