Séance 2 : RSA

Séance 2 : RSA#

Exercice 1 : RSA « brut »#

Le but de cet exercice est d’implémenter le chiffrement RSA brut avec des paramètres réels. En particulier :

  • on choisira l’exposant public \(e\) égal à \(2^{16}+1 = 65537\), quitte à regénérer des nombres premiers

  • le chiffrement et déchiffrement seront déterministes (pour la conversion sémantiquement sûre, voir exercice suivant)

Question 1. Écrire une fonction rsa_keygen(t) qui retourne une paire de clés publique/privée du chiffrement RSA. Cette fonction prend en entrée un paramètre t, la taille en bits du module RSA (l’entier \(n = pq\)) qui sera construit. On peut supposer t pair pour simplifier.

# À compléter

Question 2. Écrire une fonction rsa_encrypt(m, pk), qui prend en entrée un message m sous forme d’entier, et qui retourne un chiffré de RSA par la clé publique pk.

# À compléter

Question 3. Écrire une fonction rsa_decrypt(c, pk, sk), qui prend en entrée un chiffré RSA c sous forme d’entier, et qui retourne le déchiffré de c par la paire de clés pk/sk.

# À compléter

Question 4. Test.

  1. Créer une paire de clés publique/privée pour \(t = 2048\).

  2. Calculer le chiffré de \(n+1\), puis le déchiffrer. Que remarquez-vous ? Modifier la fonction de chiffrement en fonction.

  3. Vérifier, sur une centaine de tests, que le déchiffrement du chiffré d’un message aléatoire se déroule correctement.

# À compléter

Exercice 2 : déchiffrement accéléré pour RSA#

Nous avons vu en cours qu’il est possible d’accélérer la procédure de déchiffrement, en effectuant les calculs sur des entiers de taille plus petite.

Rappelons la méthode (voir le cours si nécessaire) :

  1. Dans la génération des clefs, les données suivantes sont calculées :

    • l’entier \(d_p = d \mod (p-1)\)

    • l’entier \(d_q = d \mod (q-1)\)

    • l’entier \(i_q = q^{-1} \mod p\)

  2. La clé privée \(d\) est remplacée par les cinq entiers \((d_p, d_q, i_q, p, q)\)

  3. Lors du déchiffrement, au lieu de calculer \(c^d \mod n\), on calcule successivement :

    • l’entier \(m_p = c^{d_p} \mod p\)

    • l’entier \(m_q = c^{d_q} \mod q\)

    • la combinaison linéaire entière (sans réduction \(\mod n\)) : \(m = m_q + q \cdot (i_q \cdot (m_p - m_q) \mod p)\)

Question 1. Dans le même contexte que pour l’exercice 1, écrire une fonction rsa_keygen_fast(t) qui effectue la génération de ces nouvelles clefs RSA.

# À compléter

Question 2. Écrire une fonction rsa_decrypt_fast(c, sk), qui prend en entrée un chiffré RSA c sous forme d’entier, et qui retourne le déchiffré de c par la nouvelle clé privée sk.

# À compléter

Question 3. Vérifier sur des exemples que le déchiffrement est correct. On pourra utiliser la fonction de chiffrement de l’exercice 1.

# À compléter

Question 4. En faisant la moyenne des temps d’exécution sur des centaines de déchiffrement, donner une valeur expériementale du facteur de réduction de temps de calcul obtenu par cette accélération. On donnera la valeur obtenue pour \(t = 1024\), et on pourra également tracer les temps de calculs en fonction \(t\).

# À compléter
Contenu