Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 4 Janvier 2000

Hachage et identification

par Marc Girault (France Telecom)

Le sujet de cet exposé est la longueur des valeurs de hachage dans les protocoles d'identification. Nous montrons que le modèle introduit par Stern et l'auteur à Crypto'94 est insuffisant, en ce qu'il se restreint implicitement aux attaquants "off-line", qui ne se livrent à des calculs frauduleux qu'avant la procédure d'identification. Il s'ensuit que les théorèmes dérivés deviennent faux, quand on les applique à des valeurs de hachage trop courtes. Nous proposons un modèle plus réaliste, dans lequel des attaques off-line et on-line peuvent être perpétrées. De façon un peu surprenante, non seulement la "borne" (ou considérée comme telle) jusqu'ici admise d'environ 85 bits est encore valide, mais elle peut être fortement améliorée (entre 32 et 50 bits !) en faisant une hypothèse très acceptable, à savoir que l'identification doit se dérouler en un temps limité. En appliquant ce résultat à des schémas basés sur le logarithme discret, on atteint une certaine optimalité (identification quasi-instantanée, mémoire requise faible).

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr