Travaux pratiques: Lundi ou mardi.
Une description plus détaillée du cours est disponible [ici].
Le but de ce cours est de mener à bien un projet collaboratif. Les sujets que je propose sont principalement orientés autour de la cryptologie : cryptographie et cryptanalyse.
FM1. Chiffrement fondé sur l’identité
Six groupes : 2, 11, 21, 27, 33, 44
[Sujet Complet]
[Exemple jouet pour Cocks]
Le but de ce projet est de coder une infrastructure de chiffrement sur l’identité (IBE) pour une possible intégration à un client mail lourd (par exemple thunderbird).
Un chiffrement fondé sur l’identité est une infrastructure qui s’articule autour de plusieurs acteurs :
- une autorité qui délivre les clefs secrètes ;
- les utilisateurs autorisés à déchiffrer à l’aide de leur clef secrète ;
- tout le monde, en mesure de chiffrer pour n’importe qui à l’aide de son identifiant (par exemple une adresse e-mail).
Un exemple d’interface pour la cryptographie est gpg, qui même si elle n’est pas nécessairement très user friendly, ça reste un exemple pour les premières interfaces du programme.
Au delà de l’interface d’utilisation et de déboggage, il reste la question des méthodes cryptographiques à utiliser. Pour cela, je propose aux groupes de choisir parmi les schémas qui suivent :
- L’IBE de Cocks. Qui repose sur de l’arithmétique modulaire (comme RSA par exemple). Nécessite de manipuler des grands entiers, et donc de passer par une bibliothèque de calcul multiprécision, comme GMP.
- L’IBE de Boneh et Franklin. Qui repose sur une structure un peu plus velue que l’arithmétique modulaire : les couplages. Ceux-ci reposent sur des calculs un peu poussés sur les courbes elliptiques. Une bibliothèque pour la manipulation des couplages serait Relic.
- L’IBE de Gentry, Peikert et Vaikuntanathan. Qui est construit sur les réseaux euclidiens. La partie technique est la manipulation des distributions de probabilités sur les réseaux. Une bibliothèque pour manipuler les réseaux pourrait être HElib.
Quel que soit le choix du protocole de chiffrement, celui-ci sera utilisé – pour des raisons d’efficacité – dans le cadre d’un chiffrement hybride. C’est-à-dire que le chiffrement fondé sur l’identité sera utilisé pour chiffrer une clef de session pour un schéma symétrique (par exemple AES déjà implémenté à plusieurs reprises) qui chiffrera le message.
Parmi ces choix, la manipulation des opérations de base sur les différentes structures pourra être effectuée à l’aide de bibliothèques (GMP pour les grands entiers par exemple). En revanche, l’implantation des algorithmes cryptographiques devra être faite « à la main ».
Autres ressources :
- Comment écrire une extension pour thunderbird.
- Répertoire git d’enigmail: git://git.code.sf.net/p/enigmail/source
- rfc5408 – Identity-Based Encryption Architecture and Supporting Data Structures
FM2. Cryptanalyse de schémas asymétriques
Un groupe : 8
Le but de ce projet est l’implantation d’un algorithme de calcul de factorisation de grands nombres.
Un premier échauffement consiste à implanter le crible quadratique, qui est une méthode simple de calcul de la factorisation d’un grand nombre, et qui repose sur la relation \[(x+y)(x-y) = x^2 - y^2.\]
Un autre algorithme classique pour la factorisation d’entiers de
taille moyenne est la factorisation
sur les courbes elliptiques (ou ECM en anglais pour
Elliptic-Curve Method). Soit \(N\) notre nombre à factoriser, l’idée
consiste à construire une courbe sur \(\mathbb{Z}_{/N \mathbb{Z}}\) (qui n’est pas
un groupe, puisqu’il existe des éléments non inversibles, qui sont les
facteurs de \(N\)) et de parcourir
cette courbe jusqu’à trouver un « problème », qui indique la présence
d’un élément non inversible, et donc nous donne des informations sur un
facteur de \(N\).
Cette méthode probabiliste a pour avantage d’être facilement
parallélisable, par exemple en parcourant sur différents cœurs des
courbes différentes.
Une fois ceci fait, et s’il reste du temps, une implantation du crible algébrique pourra être faite. Elle nécessite l’utilisation d’une algèbre linéaire creuse efficace que vous implémenterez vous-même.
Le but de ce projet sera donc de factoriser des grands nombres (par exemple les challenges RSA) après avoir parallélisé le code (par exemple en utilisant MPI).
La manipulation de grands entiers pourra être fait par le biais d’une bibliothèque (GMP par exemple), des batteries de tests unitaires et leur vérification pourra être faite par le biais de sage.
FM3. Système de sondage anonyme
Un groupe : 41
Dans ce projet, vous devrez implanter une interface web connectée à un moteur cryptographique codé dans un langage suffisamment bas-niveau pour éviter les attaques par canaux cachés par exemple.
L’ergonomie de l’interface sera aussi importante que la réalisation du backend.
L’idée sera d’implanter un mécanisme d’accréditation
anonyme pour gérer les droits d’accès au sondage.
Les votes seront ensuite agrégées via un chiffrement additivement
homomorphe (comme le chiffrement
de Paillier par exemple).
Dans ce projet, les structures de données (manipulation de gros entiers pourront être gérées par une bibliothèque. Le reste devra être codé à la main, en faisant attention autant que possible à la sécurité générale du système.
L’interface web pourra être gérée par python (via django ou flask par exemple) pour permettre un branchement au programme cœur plus aisé.