ZEITOUN Rina

PhD graduated
Team : PolSys
Departure date : 11/20/2015
https://lip6.fr/Rina.Zeitoun

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