PGCD & Bézout
Algorithme d'Euclide étendu, utilisé pour calculer l'inverse modulaire (clé privée).
Le projet en quelques mots
Le sujet officiel progresse en trois niveaux : d'abord avec le type entier natif d'OCaml, puis avec des entiers de taille arbitraire représentés par des listes de bits, puis avec le module Zarith pour l'optimisation. Ce rendu correspond au premier niveau, réalisé avec les entiers natifs OCaml.
Des maths au code
Le premier niveau du sujet réutilise la même base arithmétique pour construire les deux cryptosystèmes visés.
Tests de primalité
Génération des nombres premiers utilisés par RSA et ElGamal.
Exponentiation modulaire rapide
Cœur des opérations de chiffrement et de déchiffrement des deux cryptosystèmes.
RSA & ElGamal
Génération de clés, chiffrement et déchiffrement de messages sur des entiers natifs.
Ce qui est présent dans le rendu
RSA & ElGamal
Les deux cryptosystèmes visés par le sujet officiel ont été implémentés, réutilisant la même base arithmétique (PGCD, Bézout, exponentiation modulaire, primalité) tout en respectant les spécificités de chacun.
Limites des entiers natifs
Le type int natif d'OCaml est borné (63 bits) : les clés
restent donc de taille modeste, bien loin des tailles utilisées en
production. Gérer cette limite a été une contrainte constante de ce
premier niveau.
Synthèse du projet
Travail réalisé
Programme OCaml capable de chiffrer et déchiffrer des messages avec RSA et ElGamal, sur des entiers natifs, en traduisant en code les notions d'arithmétique modulaire, de PGCD et de primalité vues en cours.
Ce que le projet m'a apporté
Une compréhension concrète du fonctionnement de RSA, d'ElGamal et de la cryptographie asymétrique, ainsi qu'une première prise en main du langage OCaml à travers un sujet mathématique exigeant.