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]](documents/FM1.pdf)
[[Exemple jouet pour Cocks]](documents/cocks-test.txt)
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](https://www.iacr.org/archive/pkc2016/96140177/96140177.pdf). Qui repose sur de l'arithmétique modulaire (comme [RSA](https://fr.wikipedia.org/wiki/Chiffrement_RSA) par exemple). Nécessite de manipuler des grands entiers, et donc de passer par une bibliothèque de calcul multiprécision, comme [GMP](https://gmplib.org/).
* L'[IBE de Boneh et Franklin](https://crypto.stanford.edu/~dabo/papers/bfibe.pdf). 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](https://github.com/relic-toolkit).
* L'[IBE de Gentry, Peikert et Vaikuntanathan](https://people.csail.mit.edu/vinodv/GentryPeikertV-STOC2008.pdf). 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](https://github.com/shaih/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](https://fr.wikipedia.org/wiki/Advanced_Encryption_Standard) déjà implémenté à [plusieurs reprises](https://wiki.openssl.org/index.php/EVP_Symmetric_Encryption_and_Decryption)) 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 ».
* [Comment écrire une extension pour thunderbird](https://developer.mozilla.org/en-US/docs/Mozilla/Add-ons/WebExtensions/Developing_WebExtensions_for_Thunderbird).
* [rfc5408 – Identity-Based Encryption Architecture and Supporting Data Structures](https://tools.ietf.org/html/rfc5408)
### FM2. Cryptanalyse de schémas asymétriques
**Un groupe :** 8
[[Sujet Complet]](documents/FM2.pdf)
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](https://fr.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization) (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](http://www.ams.org/notices/199612/pomerance.pdf) 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 <tt>MPI</tt>).
La manipulation de grands entiers pourra être fait par le biais d'une bibliothèque ([GMP](https://gmplib.org/) par exemple), des batteries de tests unitaires et leur vérification pourra être faite par le biais de [sage](https://sagemath.org/).
### FM3. Système de sondage anonyme
**Un groupe :** 41
[[Sujet (*presque*) Complet]](documents/FM3.pdf)
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](https://courses.cs.washington.edu/courses/csep590a/11wi/slides/CSEP590a-anoncredsv3.pdf) 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](https://fr.wikipedia.org/wiki/Cryptosyst%C3%A8me_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](https://fr.wikipedia.org/wiki/Django_(framework)) ou [flask](https://fr.wikipedia.org/wiki/Flask_(framework)) par exemple) pour permettre un branchement au programme cœur plus aisé.
