Exercices td rsa chiffrement dchiffrement cls prives et modu

Exercices td rsa chiffrement dchiffrement cls prives et modu

Télécharger PDF

TD 3 - RSA

Exercice 1

La clé publique de Bob est N = 247 et E = 11, et sa clé privée est D = 59.

1. Aidez Alice à chiffrer le message clair M = 100 pour l’envoyer à Bob.

2. Le cryptogramme C = 52 est reçu par Bob. Aidez-le à le déchiffrer.

Exercice 2

1. Pour fabriquer son chiffre RSA, Bob a choisi les deux nombres premiers p = 13 et q = 23. Calculer le module N et le nombre φ(N).

2. Bob doit maintenant choisir son exposant E. Le nombre 41 constitue-t-il un exposant acceptable ? Pourquoi ? Le nombre 72 constitue-t-il un exposant acceptable ? Pourquoi ?

3. Réflexion faite, Bob a choisi l’exposant E = 83. Calculer l’exposant correspondant D.

4. Bob va maintenant publier la partie publique de son chiffre RSA. Indiquez de quoi est constituée cette partie publique.

Exercice 3

Alice a publié la partie publique de son chiffre RSA : EA = 179 et NA = 629. La partie privée de son chiffre est DA = 251. Bob a publié la partie publique de son chiffre RSA : EB = 601 et NB = 851. La partie privée de son chiffre est DB = 481.

Alice veut envoyer un message (codé numériquement par un seul nombre M = 342) à Bob.

1. Quel est le calcul que doit effectuer Alice pour chiffrer son message ? Vous noterez C le message chiffré.

2. Quel est le calcul que doit effectuer Bob pour déchiffrer C ? Vous noterez M0 le message déchiffré.

Exercice 4

Alice a publié la clé publique de son chiffre RSA : N = 391 et E = 151, et elle a conservé en lieu sûr sa clé privée D = 7.

1. Bob lui transmet un message sous la forme du nombre : C = 17. Quelle opération Alice va-t-elle effectuer pour déchiffrer ce message ? Quel nombre va-t-elle obtenir ?

2. Retrouvez les deux nombres premiers p et q (le nombre N étant petit, c’est faisable). En déduire φ(N).

3. Quelle relation existe-t-il entre E et D ? Vérifiez cette relation sur les nombres donnés.

Exercice 5

1. On considère un chiffre RSA constitué du module N = 221, du compliceur E = 11 et du faciliteur D = 35.

(a) Chiffrer le message M = 112.

(b) Déchiffrer le cryptogramme C = 78.

2. Pour fabriquer un chiffre RSA, on a choisi p = 53 et q = 71.

(a) Calculer le module N et le nombre φ(N).

(b) On choisit le compliceur E = 307. Vérifier qu’il est acceptable et calculer le faciliteur correspondant D.

(c) Indiquer quels sont les éléments qui constituent la clé publique et quels sont les éléments qui constituent la clé privée de ce chiffre RSA.

(d) Que faut-il faire des éléments restants ? Pourquoi ?

Cryptanalyse et attaques par canaux cachés

Attaque par force brute

Cette méthode consiste à énumérer toutes les clés secrètes possibles.

• Chiffrements par décalage : 26 clés possibles.
• Chiffrements affines : 12 × 26 = 312 clés possibles.
• Permutation quelconque lettre à lettre : 26! ≈ 4,03 × 10²⁶ clés possibles.
• Pour Enigma (allemand, Seconde Guerre mondiale) : environ 10¹⁶ clés possibles.
• Pour DES (Data Encryption Standard) : 2⁵⁶ ≈ 7,2 × 10¹⁶ clés possibles.

Attaques plus subtiles

Ces attaques exploitent des faiblesses des protocoles.

• Chiffrement par décalage : correspondance entre deux lettres.
• Chiffrement affine : parfois correspondance entre deux paires.
• Chiffrement par permutation : fréquences des lettres et dictionnaire.
• Pour Enigma : faiblesses dans la mise en œuvre.
• Pour DES : cryptanalyse différentielle (observation de l’effet de petites perturbations sur le chiffré).

Remarque : Ces attaques nécessitent souvent des conditions spécifiques, comme l’accès à de nombreux messages chiffrés pour la cryptanalyse différentielle. Cela est réalisable dans des contextes comme la cryptographie embarquée (sur des puces électroniques).

Attaques par canaux cachés

Ces attaques exploitent des informations physiques liées au traitement des données.

• Temps de calcul.
• Consommation énergétique.
• Température.
• Rayonnement électromagnétique.

D’autres attaques plus sophistiquées, comme l’attaque au flash ou l’attaque au laser, perturbent physiquement un composant de la puce pour inverser des bits pendant le calcul.

Attaque par canaux cachés de RSA

Le déchiffrement RSA repose sur le calcul de C^D mod N, où D est la clé secrète.

Si un attaquant découvre D, il peut déchiffrer tous les messages envoyés à Alice.

Exponentielle modulaire rapide

Exemple : Calcul de 17⁴³⁷ mod 187.

On utilise la décomposition de 37 en bits : 37 = 32 + 4 + 1.

Le calcul se fait en utilisant des carrés et des multiplications successives.

Exemple de calcul :

(17⁴)² mod 187, (17⁴)² × 17 mod 187, etc.

Résultat : 17⁴³⁷ mod 187 = 4.

Attaques temporelles et par analyse de consommation

Attaque temporelle : basée sur le nombre de bits de la clé et le nombre de 1.

Attaque par analyse de consommation : basée sur la différence entre un produit et un carré.

• Un carré seul (bit de la clé = 0).
• Un carré puis une multiplication (bit de la clé = 1).

L’attaquant peut ainsi lire les bits de la clé (de droite à gauche).

Contre-mesure : Square and multiply always

Pour éviter ces attaques, on peut toujours effectuer une multiplication à chaque étape, même si elle est inutile.

Exemple de pseudo-code :

x2 = x
x1 = 1
b = 1
if d0 == 1:
    x1 = x1 * x2 % N
else:
    b = b * x2 % N

for i = 1 to k-1 do
    x2 = x2^2 % N
    if di == 0:
        b = b * x2 % N
    else:
        x1 = x1 * x2 % N

return x1

Attaque au flash et technique de Montgomery

L’attaque au flash exploite les différences physiques entre les calculs de carrés et de multiplications.

La technique de Montgomery permet d’éviter ces attaques en modifiant le calcul de l’exponentielle rapide.

Exemple de pseudo-code :

x1 = x
x2 = x^2 % N

for i = k-2 to 0 do
    if di == 0:
        x2 = x1 * x2 % N
        x1 = x1^2 % N
    else:
        x1 = x1 * x2 % N
        x2 = x2^2 % N

return x1

Exercice 1

Charlie observe le tracé de l’oscilloscope branché sur l’ordinateur d’Alice. En analysant les différences de consommation, il peut déduire les bits de la clé secrète D d’Alice.

Exercice 2

Charlie observe le tracé de l’oscilloscope branché sur l’ordinateur de Bob. En analysant les différences de consommation, il peut déduire les bits de la clé secrète D de Bob.

Exercice 3

Charlie peut-il retrouver la clé D de Bob en observant le tracé de l’oscilloscope ? Non, car la nouvelle implémentation de Bob effectue toujours une multiplication à chaque étape, rendant l’analyse des bits de la clé impossible.

Exercice 4

Comparaison des méthodes classique et Montgomery pour le calcul de 17⁴³⁷ mod 187.

Exercice 5

Démonstration que la méthode de Montgomery calcule bien x^D mod N.

FAQ

Qu’est-ce qu’une attaque par canal caché ?

Une attaque par canal caché exploite des informations physiques (comme la consommation d’énergie ou le temps de calcul) pour déduire des détails sur une clé secrète ou un message chiffré.

Pourquoi l’attaque temporelle est-elle efficace ?

L’attaque temporelle est efficace car elle permet de déterminer le nombre de bits à 1 dans l’exposant, ce qui réduit le nombre de clés possibles à analyser.

Comment la technique de Montgomery protège-t-elle contre les attaques par canaux cachés ?

La technique de Montgomery uniformise les opérations de calcul (carrés et multiplications) à chaque étape, ce qui empêche un attaquant d’identifier les bits de la clé secrète via des différences de consommation ou de temps.