TP : implantation de NTRU

Le but de ce TP est d'implanter une version simple du système de chiffrement NTRU avec le logiciel Sagemath. Vous pouvez retrouver la spécification du système dans les slides de cours, à l'adresse suivante :

https://lvzl.fr/teaching/2023-24/docs/cp/slides/cours8.pdf

Question 1. Créer les paramètres systèmes qui vous seront utiles tout au long du TP. Des (petites) valeurs sont proposées pour pouvoir ensuite faire des tests.

1. Une dimension $N = 11$,
2. Des entiers $p = 3$ et $q = 101$ qui feront office de modules,
3. Des entiers $d_f = 3$, $d_g = 2$ et $d_r = 2$ qui contrôlent les coefficients dans la génération aléatoire des polynômes,
4. Les anneaux de polynômes $R_p = \mathbb{Z}_p[x]$ et $R_q = \mathbb{Z}_q[x]$ (comme $p$ et $q$ sont premiers dans cet exemple, on peut manipuler les corps finis $\mathbb{F}_p$ et $\mathbb{F}_q$), et leurs variables associées.

N, p, q, df, dg, dr = 11, 3, 101, 3, 2, 2   
Rp = PolynomialRing(GF(p), "x")

# à compléter

Question 2. Implanter une fonction generate_vect(d1, d2) qui retourne un vecteur aléatoire $v = (v_1, \dots, v_N) \in \{-1,0,1\}$ qui a exactement $d_1$ coefficients à $1$, $d_2$ coefficients à $-1$ et $N-d_1-d_2$ coefficients à $0$.

Indication : pour cela, partir du vecteur nul de longueur $N$, et ajouter progressivement des coeffcients à $1$ et à $-1$ sur des positions aléatoires.

Question 3. Créer une fonction center(x, m) qui prend en entrée deux entiers x et m, et qui retourne la représentation centrée de x modulo m.

Par exemple, si $x = 12$ et $m = 7$, alors on doit retourner l'unique représentant de la classe de $x \!\!\mod m$ dans l'ensemble

$$\Big\{ -\lceil\tfrac{m-1}{2}\rceil = -3, -2, \dots, 2, 3 = \lfloor\tfrac{m-1}{2}\rfloor \Big\},$$

c'est-à-dire $-2$.

Question 3. Créer une fonction map_to_ZZ(poly, m) qui prend en entrée un polynôme poly et un entier m, et qui retourne la liste des coefficients de poly sous une forme centrée modulo m, dans l'ordre croissant des degrés.

La fonction devra retourner des listes de longueur exactement $N$, quitte à rajouter des $0$ en fin de liste si le degré de poly est trop petit.

Par exemple, si $N$ vaut $11$ et poly vaut $7 x^3 + 9 x^2 + 3$ et $m = 5$, alors la fonction retournera la liste $(-2, 0, -1, 2, 0, 0, 0, 0, 0, 0, 0)$.

Question 4. Écrire la fonction keygen() de génération de clés de NTRU. Cette fonction retournera la clé publique pk (sous la forme d'une liste de coefficients centrés modulo $q$) et la clé privée sk (sous la forme de deux listes de coefficients centrés modulo $p$).

Question 5. Implanter une fonction encrypt(message, pk) qui prend en entrée un vecteur message et la clé publique pk, et qui retourne le chiffré sous la forme d'un vecteur à coefficients (centrés) dans $\mathbb{Z}_q$.

Question 6. Implanter une fonction decrypt(ct, sk) qui prend en entrée le chiffré ct et la clé privée sk, et qui retourne le message clair associé sous la forme d'un vecteur à coefficients (centrés) dans $\mathbb{Z}_p$.

Question 7. Vérifier sur des exemples que votre implantation est correcte (c'est-à-dire que le déchiffrement se comporte bien), pour les paramètres donnés en début de TP.

Question 8. Choisir maintenant les paramètres

$$ (N, p, q, d_f, d_g, d_r) = (11, 3, 17, 3, 2, 2) $$

(c'est-à-dire, réduire la valeur de $q$ à $17$ au lieu de $101$), et observer sur une centaine de tests d'éventuelles erreurs de déchiffrement. Expliquer la raison de ces erreurs de déchiffrement.