TP1 Implémentation de RSA et Pailler

Ce TP consiste en l’implémentation naïve du crypto-système RSA et du crypto-système de Pailler. Le sujet reprend les exercices 78 et 79 du livret.

Introduction

Dans ce TP et les autres, le langage de programmation Python et son écosystème seront utilisés.

💯 Ne pas bloquer à cette section et lire la suite. La configuration de l’environnement peut se faire progressivement, c’est pour 💯

Environnement de développement Python

Il est demandé :

• D’utiliser une version 3.10 ou supérieure de Python.
• D’utiliser VSCode ou VSCodium comme IDE.
  • Alternativement, vous pouvez utiliser Jupyter intégré ou pas à l’IDE, voire directement IPython.
• D’installer les extensions :
  • (obligatoires) Python, Black et Pylint.
  • (optionnelles) autoDocstring, Pylance, Mypy pour le static type checker Mypy.

⚠️ Ces outils assureront un code de qualité minimale. Si vous n’avez pas l’habitude de Python, contentez-vous pour l’instant des trois premières extensions VSCode. ⚠️

Il est plutôt recommandé d’utiliser un gestionnaire d’environnements virtuels comme venv. La gestion des environnements virtuels est intégrée à VSCode via les extensions Python sus-citées.

On peut créer et charger manuellement un environnement virtuel comme suit, voir Python Virtual Environments: A Primer pour plus d’aide :

# crée le sous-dossier .venv
python3 -m venv .venv

# charge le venv
. .venv/bin/activate

# on utilise python et pip

# on décharge
deactivate

Bibliothèques cryptographiques

Les bibliothèques suivantes proposent toutes deux un ensemble d’outils cryptographiques :

• PyCryptodome
• pyca/cryptography

On les installera avec la commande pip install pycryptodome cryptography (ou commande équivalente pour votre environnement si vous utilisez Conda par exemple).

Base de départ et modalité de rendu

Les fichiers de départ mif29_tp1.py et TextbookRSACipher.py sont fournis. Pour les questions en texte libre, utiliser les docstring au début du module.

⌛ La classe TextbookRSACipher du fichier TextbookRSACipher.py est à rendre complétée dans la case idoine de Tomuss pour mardi 26 mars 14:00 au plus tard. ⌛

Exercice 1 : implémentation du crypto-système RSA

On demande ici de réaliser une implémentation de RSA naïf (textbook RSA), c’est-à-dire la version mathématique minimale définie comme suit. On démontrera dans d’autres TP que cette implémentation naïve est vulnérable.

• Avec $m$, le message clair et $c$ le chiffré correspondant,
• Avec $n=p\times q$, $e$ et $d$ définis dans RSA :
  • pour le chiffrement $E(m)=m^e(\mathrm{mod}n)$
  • pour le déchiffrement $D(c)=c^d(\mathrm{mod}n)$
• Pour qu’on ait $D(E(m))=(m^e{)}^d(\mathrm{mod}n)=m^{e\cdot d}(\mathrm{mod}n)=m$.

On remarque que les entiers natifs de Python, le type int, sont de tailles arbitraires, ce qui est incontournable en cryptographie.

Question 1.1 Combien faut-il de chiffres en base 10 et en base 2 pour représenter la factorielle de $100000$ ($100000!$) ? Le calculer en Python avec math, e.g., from math import factorial; factorial(1_000).

Question 1.2 Compléter les fonctions textbook_rsa_keygen(), textbook_rsa_encrypt() et textbook_rsa_decrypt() qui pour l’instant lèvent une exception.

Question 1.3 Avec des assertions, vérifier la correction de vos implémentations en testant l’exemple de Wikipedia et en testant $D(E(m))=m$ pour $m$ aléatoire.

Question 1.4 Quelle est la taille (en bits) actuellement recommandée pour $q$ et $q$ ?

Question 1.5 Quelle est la taille (en bits) maximale du message clair que l’on peut chiffrer ?

Question 1.6 Pourquoi $e$ doit-il être premier avec $\varphi (n)$ ?

Question 1.7 $e$ peut-il être pair ? $d$ peut-il être pair ?

Question 1.8 Quel est l’intérêt de choisir $e$ petit ? Quelle est la valeur la plus couramment utilisée ?

Question 1.9 Évaluer le temps d’exécution fonctions précédentes avec la bibliothèque timeit.

Question 1.10 Déduire le temps nécessaire en minutes pour chiffrer 1 GB de données avec RSA. Est-ce que cela vous semble adapté à de la vidéo ?

Exercice 2 : implémentation crypto-système de Pailler

Question 2.1 Compléter les fonctions pailler_keygen(), pailler_encrypt() et pailler_decrypt() qui pour l’instant lèvent une exception.

Question 2.2 Avec des assertions, vérifier la correction de vos implémentations en testant $D(E(m))=m$.

Question 2.3 Similairement, vérifier les que ce crypto-système est additivement homomorphe, c’est-à-dire que

$$D(sk,(E(pk,x)\times E(pk,y))(\mathrm{mod}{n}^2))=(x+y)(\mathrm{mod}n)$$

Question 2.4 Proposer une application de la propriété précédente.

Exercice 3 (à terminer après la séance) : interface PyCryptodome

On va utiliser API de PyCryptodome pour l’implémentation de RSA.

Introduction à PyCryptodome

On considère le script suivant :

from Crypto.PublicKey import RSA

key = RSA.generate(2048)
secret_key = key.export_key(format="PEM", pkcs=8)
public_key = key.publickey().export_key()

with open("rsa_key.pem", "wb") as file_out:
    file_out.write(secret_key)

with open("rsa_key.pub", "wb") as file_out:
    file_out.write(public_key)

On donne les nombres p = 559212886079726860470346917343663228747 et q = 155668656214909251471186475194459383417 et un exposant public e = 2 ** 16 + 1.

Question 3.1 Expliquer ce que fait le script précédent.

Question 3.2 Que contiennent les objets secret_key et public_key du script ? Consulter la documentation ou le code source pour retrouver ses paramètres n, e, d, p et q.

Question 3.3 Vérifier avec PyCryptodome que p et q sont (très probablement) premiers et que e n’est pas un facteur de (p - 1) * (q - 1).

Question 3.4 Avec RSA.construct() construire la clef secrète ayant les paramètres n, e, d, p et q donnés avec et enregistrer la clef dans un fichier rsa_key_256.pem.

Question (bonus) 3.5 si seuls n, e et d sont fournis, RSA.construct() calcule automatiquement p et q. Retrouver dans le code source la référence bibliographique de l’algorithme utilisé.

Classe Cipher au format PyCryptodome

On considère la classe TextbookRSACipher suivante, voir fichier TextbookRSACipher.py :

class TextbookRSACipher(object):
    """Variante de la classe Cipher pour textbook RSA (sans padding).

    https://pycryptodome.readthedocs.io/en/latest/src/cipher/cipher.html
    """

    def __init__(self, key: RSA.RsaKey):
        self._key = key

    def encrypt(self, msg: bytes):
        """textbook RSA cipher"""
        m: int = int.from_bytes(msg, "big")
        raise NotImplementedError("TODO: implement TextbookRSACipher.encrypt")


    def decrypt(self, msg: bytes):
        """textbook RSA cipher"""
        c = int.from_bytes(msg, "big")
        raise NotImplementedError("TODO: implement TextbookRSACipher.decrypt")


    @classmethod
    def new(cls, key):
      """Uniquement pour l'interface Cipher"""
      return TextbookRSACipher(key)

Les méthodes TextbookRSACipher.encrypt() et TextbookRSACipher.decrypt() prennent en renvoient des messages binaires (clairs comme chiffrés) sous forme de tableau d’octets de type bytes et non plus des messages en int comme dans l’exercice 1.

On passe de bytes à int et vice-versa avec la convention big endian (bits de poids forts en premier, par défaut) via les méthodes de classe int.from_bytes() et int.to_bytes(). Pour le passage de int à bytes, prenez le tableau le plus court possible.

Question 3.6 Reprendre le premier exercice en réorganisant vos fonctions sous forme d’une classe TextbookRSACipher qui utilise clefs de PyCryptodome et reprend l’interface des chiffrements implémentés dans la bibliothèque.

Question 3.7 Tester votre classe dans un fichier de test qui importe la classe TextbookRSACipher. Chiffrer cleartext = b"Attack at dawn!", enregistrer dans un fichier binaire. Vérifier que le fichier contient b'mw\x95\x0e1\x1f&\xf9Ns\xbd\x1d\x17i\xa20\x9bwe\xb7\x81\x15M\x0f+\x1f)\x15B\x81)\xc2' et que vous arrivez à déchiffrer.

Exercice 4 (pour aller plus loin)

Les int de Python ne sont pas très performants. On pourrait utiliser avantageusement une bibliothèque comme gmpy2 qui permet d’utiliser en Python l’incontournable https://gmplib.org/. On initialisera gpmy2 comme suit

import gmpy2
from gmpy2 import mpz
gmpy2.set_context(gmpy2.context())

Question 4.1 Reprendre l’exercice 1 ou le 3 avec gmpy2.

Question 4.2 Comparer la différence de performance face à l’implémentation originale avec les int natifs.

⚠️ La bibliothèque gmpy2 n’est pas aussi facile à installer sous Windows que sous Linux. Utiliser WSL2. ⚠️