Méthodes Algébriques pour la Cryptographie – MAC

Ce projet se situe dans le domaine de la protection de l'information ; les deux themes de recherche
concernes sont la cryptographie et calcul symbolique. Nous nous interessons ici essentiellement - mais
pas exclusivement - a la cryptographie a clef publique. La cryptographie a clef publique est basee sur la
notion de fonction a sens unique avec trappe. Informellement, une telle fonction est facile a calculer (i.e.
calculable en temps polynomial), mais difficile a inverser (calcul de l'inverse au mieux sous-exponentiel),
sauf si l'on connait une information supplementaire (trappe), rendant le calul de l'inverse polynomial.
De telles fonctions sont elles-memes construites a partir de problemes “difficiles” (pour lesquels aucun
algorithme polynomial n'est connu). Bien que plusieurs problemes aient ete proposes pour la construction
de systemes a clef publique, ceux qui sont effectivement utilises sont la factorisation (ex. RSA) et le
logarithme discret (ex. l'echange de clef Diffie-Hellman). Il n'est certes pas connu a ce jour d'algorithme
polynomial pour resoudre la factorisation ou le logarithme discret, mais ces deux problemes ne sont pas
a l'abri d'une percee theorique qui remettrait en cause la securite des schemas bases sur ces problemes.
En outre, ces schemas sont trop lents pour tre utilises dans des environnements fortement contraints (en
particulier, les communications mobiles : RFID, reseaux ad-hoc...) Ainsi, l'un des principaux enjeux de
la cryptographie a clef publique est l'identification de “bons” problemes et l'elaboration de schemas non
bases sur la theorie des nombres. Etant donne les nombreuses applications de la cryptographie dans le
monde reel (controle d'acces, authentification, securisation des transactions via Internet, protection des
communications...), de nouveaux resultats dans ce domaine ne sont pas seulement d'intert scientifique,
mais ont egalement un impact important d'un point de vue economique.
C'est pour repondre a cette problematique que les schemas multivaries ont vu le jour au milieu des annees
quatre-vingt (Diffie et Fell 85, Matsumoto et Imai 85). Rappelons que, par cryptographie multivariee, nous
entendons tout schema utilisant des systemes de polynomes multivaries. Mentionnons ici que les schemas
bases sur le probleme difficile de resolution d'equations multivariees sur un corps fini ne sont pas concernes
par la “menace” que constituent les ordinateurs quantiques (contrairement aux schemas bases sur la
theorie des nombres). En outre, les schemas multivaries sont peu demandeurs de ressources de calcul, et
peuvent produire des signatures courtes, ce qui est un atout majeur. Ces dernieres annees, la cryptographie
multivariee est devenue une branche de recherche importante. Ceci s'explique principalement par le fait
qu'un projet Europeen ( nessie) a preconise l'utilisation d'un tel schema ( sflash) dans le contexte des
cartes a puces. De plus, a peu pres toutes les fonctionalites cryptographiques ont ete illustrees par un
schema multivarie : signature ( sflash, quartz, tts, enTTS, uov, rainbow), chiffrement ( hfe, mi, pmi, 2r,...),
stream cipher ( quad), “traitor tracing”... Dans le monde industriel en revanche, on observe une certaine
reticence a l'utilisation de ces schemas ; ceci est du au fait que leur securite n'est pas bien matrisee.
Dans le but d'evaluer la securite de nouveaux schemas, il convient de developper des methodes de cryptanalyse
puissantes et efficaces. Dans ce projet, nous nous proposons essentiellement d'evaluer la securite
de primitives cryptographiques par des methodes algebriques. L'idee est de modeliser une primitive cryptographique
a l'aide d'un systeme d'equations algebriques. Le systeme est construit de telle sorte a avoir
une correspondence entre les solutions du systeme et une information secrete sur la primitive en question.
Une fois cette mise en equation realisee, il s'agit de resoudre le systeme algebrique. Notre appproche
est motivee par le fait que l'analyse algebrique appliquee au contexte cryptographique est apparue voila
quelques annees seulement, et consitue donc une nouvelle methode d'investigation des primitives cryptographiques.
De plus, la portee de cette methode est mal connue, et les resultats sur le sujet sont encore
flous. Notre but est premierement d'identifier les schemas qui resistent a la cryptanalyse algebrique. Pour
ceux-la, nous donnerons les tailles de parametres a choisir pour une utilisation sure, ce qui permettra de
clarifier un point crucial souvent absent dans les schemas proposes. Mais dans une acception plus large,
notre projet vise a concevoir les meilleures methodes de resolution d'un systeme d'equations aleatoire.
Dans une premiere phase du projet, nous identifierons les schemas, ou classes de schemas, qui sont
pertinents a etudier du point de vue de l'analyse algebrique. Nous nous interesserons principalement aux
schemas multivaries ; comme mentionne plus haut, nous avons un certain nombre de schemas a notre
disposition. Mais, jusqu'a present, la situation n'est pas claire quant a quel type de schema est vulnerable
a quel type d'attaque. De plus, pour certaines classes de schemas, la mise en equation est immediate, alors
que pour d'autres, elle constitue deja un probleme a part entiere. Ensuite, nous commencerons le coeur
de notre etude, a savoir l'analyse proprement dite. Ce travail sera mene en fonction des classes identifiees
dans la premiere phase. A ce propos, mentionnons qu'il existe toujours l'approche “force brute”, qui
consiste a essayer de resoudre le systeme obtenu en considerant la primitive cryptographique comme un
polynome dans une extension de GF(q) ; cela ne donne en general pas de bons systemes du point de vue
de la resolution. Un des aspects fondamentaux sera donc ici de construire les systemes les plus adaptes.
Notre travail analytique comportera egalement une partie prospective, dans laquelle nous elargirons notre
cadre en considerant des schemas issus de la cryptographie a clef secrete (schemas par blocs comme aes,
schemas a flot comme quad), ou d'autres primitives (comme sha1). Notons que l'utilisation de telles
methodes algebriques dans ces contextes n'est pas bien matrisee aujourd'hui.
Dans une derniere phase, nous utliserons les resultats obtenus pour elaborer, ou au moins donner des
elements pour l'elaboration de schemas multivaries surs (choix des parametres, choix des instances...).