Chiffre RSA

  On met en œuvre dans ce TD le chiffre RSA, un algorithme de chiffrage asymétrique décrit en 1977 par Ronald Rivest, Adi Shamir et Leonard Adleman qui est très utilisé aujourd'hui.

I) Cryptographie, chiffrage
II) Chiffre RSA
III) Lecture et écriture d'un fichier
IV) Algorithmes de chiffrage et de déchiffrage avec des clés données
V) Algorithmes de calcul des clés

I) Cryptographie, chiffrage

1) Cryptographie

  La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de clés. Son objectif est de rendre un message ou un fichier inintelligible à tout autre que qui-de-droit.
  Lorsque le message est un fichier informatique, on dit chiffrer au lieu de crypter.

2) Chiffrer, déchiffrer

  Chiffrer un fichier "en clair" F1 c'est le transformer, avec une clé de chiffrage, en un fichier "incompréhensible" F2.
Déchiffrer ce fichier F2 c'est, avec une clé de déchiffrage, le ramener à F1. Cette seconde clé peut être connue (si on est le destinataire du texte) ou "découverte" (si on a intercepté le fichier F2 avec de mauvaises intentions et si on est suffisamment doué...).

3) Principaux systèmes de chiffrement (Wikipédia)

Un système de chiffrement est dit :
    (1) symétrique quand il utilise la même clé pour chiffrer et déchiffrer.
    (2) asymétrique quand il utilise des clés différentes : une paire composée d'une clé publique, servant au chiffrement, et d'une clé privée, servant à déchiffrer. Le point fondamental soutenant cette décomposition publique/privée est l'impossibilité calculatoire de déduire la clé privée de la clé publique.

  Les méthodes les plus connues sont le DES, le triple DES et l'AES pour le chiffrement symétrique, et le RSA pour le chiffrement asymétrique, aussi appelé chiffrement à clé publique.

  L'utilisation d'un système symétrique ou asymétrique dépend des tâches à accomplir. La cryptographie asymétrique présente deux intérêts majeurs : elle supprime le problème de transmission sécurisée de la clé, et elle permet la signature électronique. Elle ne remplace cependant pas les systèmes symétriques car ses temps de calcul sont nettement plus longs et la cryptographie asymétrique est de par sa nature même plus vulnérable.

II) Chiffre RSA

1) Présentation

  C'est un système de chiffrage qui exploite le théorème d'arithmétique suivant.

Théorème: Soient p et q deux nombres premiers distincts.  On pose n = p q et m = ( p - 1 ) ( q - 1 ) . Alors:
    (1)   k { 1 , ... , n - 1 } , k m = 1 [ n ] .
    (2)   e { 1 , ... , m - 1 } n'ayant pas de facteur commun avec m , alors ! e ' { 1 , ... , m - 1 } / e e ' = 1 [ m ] .

  La démonstration de ce théorème n'est pas difficile et utilise le petit théorème de Fermat ainsi que le théorème de (Bachet-)Bezout:

Théorème de Fermat: Pour tout nombre premier p et tout entier n sans facteur commun avec p , alors n p - 1 = 1 [ p ] .
Théorème de Bezout: e , m N * sans facteur commun, u , v Z / e u + m v = 1 .

2) Description de l'algorithme RSA

• La création des clés est à la charge de Didier, le destinataire des messages chiffrés:
    (1) Didier choisit deux nombres premiers distincts p et q .
    (2) Didier calcule les produits n = p q et m = ( p - 1 ) ( q - 1 ) .
    (3) Didier choisit e { 2 , ... , m - 1 } sans facteur commun avec m et calcule l'entier e ' { 1 , ... , m - 1 } tel que e e ' = 1 [ m ] .
    (4) La clé publique (la clé de chiffrage)  est le couple ( cle , e_pub ) = ( n , e ) et la clé privée (la clé de déchiffrage) est le couple ( cle , e_priv ) = ( n , e ' ) .
    (5) Didier transmet la clé publique ( n , e ) aux personnes comme Ernest qui doivent lui envoyer des messages chiffrés et garde précieusement la clé privée ( n , e ' ) de déchiffrage. Une fois créées, les clés peuvent être utilisées aussi longtemps qu'elles paraissent sûres.

•• Ernest chiffre avec la clé publique ( n , e ) le fichier en clair F1 qu'il veut envoyer à Didier de la manière suivante:
    (1) Ernest découpe son fichier F1 en une suite d'entiers ( N 0 , N 1 , ... , N k - 1 ) de taille appropriée.
    (2) Ernest calcule la suite d'entiers ( M 0 , M 1 , ... M k - 1 ) définis par les relations M i = ( N i ) e [ n ] . (C'est le cœur du chiffrage)
    (3) Ernest convertit la suite d'entiers ( M 0 , M 1 , ... M k - 1 ) en un fichier F2
    (4) Ernest envoie à Didier le fichier chiffré F2

••• Didier déchiffre avec la clé privée ( n , e ' ) le fichier F2 envoyé par Ernest de la manière suivante:
    (1) Didier découpe le fichier F2 en la suite d'entiers   ( M 0 , M 1 , ... M k - 1 ) .
    (2) Didier retrouve la suite d'entiers ( N 0 , N 1 , ... , N k - 1 ) en calculant N i = ( M i ) e ' [ n ] . (C'est le cœur du déchiffrage)
    (3) Didier convertit la suite d'entiers ( N 0 , N 1 , ... , N k - 1 ) en le fichier F1 en clair envoyé par Ernest    

  En effet, en notant N = N i et M = M i ,  on a: M e ' = ( N e ) e ' = N e e ' = N 1 + k * m (car e e ' = 1 [ m ] ) = N * ( N m ) k = N * ( 1 ) k [ n ] = N [ n ] d'après le théorème initial.

3) Sécurité du système RSA

  La clé publique ( n , e ) ainsi que le fichier chiffré F2 peuvent être interceptés par Pierre le pirate. Mais tant que Pierre n'a pas calculé l'entier e ' de la clé privée ( n , e ' ) de déchiffrage, Pierre n'est pas capable de déchiffrer le fichier F1.
  Or pour calculer e ' , Pierre a besoin de l'entier m = ( p - 1 ) ( q - 1 ) , donc des entiers p et q . Pour calculer ces entiers p et q , Pierre doit factoriser l'entier n = p q . Cette factorisation est à l'heure actuelle impossible si les entiers p et q ont été choisis suffisamment grands.
  On estime aujourd'hui que lorsque la clé n est un entier d'au moins 1024 bits (c'est à dire que n 2 1000 10 300 ), la factorisation de n n'est pas possible.  Une compétition de factorisation RSA, organisée entre 1991 et 2010, a permis en 2010 de factoriser des clés RSA comportant jusqu'à 768 bits.

4) Calcul de la clé

  Comment calculer deux grands nombres premiers p et q alors que l'on ne sait pas factoriser un grand nombre et donc savoir s'il est premier ? Cette question de bon sens a trouvé une réponse en 1975-1976 et a permis de mettre en place le chiffrage RSA qui n'existerait pas sinon.
  Gary Lee Miller puis Michael O. Rabin ont proposé une méthode probabiliste pour déterminer si un entier donné n est premier, avec une probabilité que l'on peut choisir arbitrairement proche de 1. Avec ce qui s'appelle maintenant le test de Miller Rabin, on peut trouver de très grands entiers dont on est “certain”, avec par exemple une probabilité d'erreur plus petite que 10 - 6 , qui sont premiers.

5) Travail

On va dans la suite mettre en œuvre:
    (1) Le chiffrage et le déchiffrage d'un fichier, les clés étant données.
    (2) Le calcul de clés de longueurs quelconques à l'aide du test de Miller Rabin.

III) Lecture et écriture d'un fichier

  Un fichier informatique est une suite ordonnée d'octets enregistré sur un support. Pour travailler plus lisiblement ces octets seront convertis en entiers de {0,1,...,255}. Les entiers de {0,...,255} seront souvent dans la suite appelés des octets.

On donne les fonctions suivantes:

# -*- coding: UTF-8 -*
import os                    # Module contenant des fonctions utiles

##print(os.getcwd())        # Affiche le répertoire courant de travail
# Pour Changer (s'il le faut) le répertoire courant de travail, on utilise os.chdir()
# Par exemple:
##os.chdir("C:/Users/Eric/Documents/Algorithmique/2013 Informatique Exercices/Fichiers")

def lire_fichier(nom_fichier):
    """ Liste d'octets contenus dans fichier appelé nom_fichier convertis en
    une liste d'entiers de {0,...,255}"""
    with open(nom_fichier, "rb") as fich:   # Ouverture en lecture de fichier
         octets = fich.read()              # lecture du contenu de fichier
    return list(octets)                    # Conversion en une liste d'entiers

def enregistrer_fichier(nom_fichier, contenu):
    """Enregistrement du contenu dans le fichier appelé nom_fichier.
    contenu est une liste d'entiers de {0,...,255} qui est convertie en octets
    avant l'enregistrement"""
    octets = bytes(contenu)                # Conversion en liste d'octets
    with open(nom_fichier, "wb") as fich:  # Ouverture en écriture du fichier
        fich.write(octets)                 # Enregistrement

Un fichier est dans la suite une liste d'entiers (d'octets) de {0,...,255}. Les fonctions données ci-dessus permettent de travailler avec des vrais fichiers informatiques.

Les fichiers de données pour le chiffre RSA sont disponibles dans ce répertoire.

IV) Algorithmes de chiffrage et de déchiffrage avec des clés données

  On suppose dans cette partie disposer d'un triplet ( cle , e_pub , e_priv ) conforme au cahier des charges décrit dans le II).

Q1) Ecrire une fonction grouper_liste_octets(s, n) (avec s liste d'octets et n entier non nul) calculant la liste des entiers [ N 0 , N 1 , ... N k - 1 ] obtenus en convertissant les paquets de n octets consécutifs (sauf le dernier paquet qui pourra comportet moins de n octets) de la liste s d'octets en entiers. Le i ème paquet d'octets est l'écriture en base 256 de l'entier N i . Par exemple:

s = [100, 2, 1, 10, 7, 30, 4, 200, 3]
print(grouper_liste_octets(s, 2)) → [25602, 266, 1822, 1224, 3]
print(grouper_liste_octets(s, 3)) → [6554113, 657182, 313347]
print(grouper_liste_octets(s, 6)) → [109959770146590, 313347]

  En effet, 100*256  + 2 = 25602,    ..., 4*256+200 = 1224 pour n=2; 100 * 256 2 + 2 * 256 + 1 = 6554113,... pour n=3; 100 * 256 5 + 2 * 256 4 + 256 3 + 10 * 256 2 + 7 * 256 + 30 = 109959770146590 et 4 * 256 2 + 200 * 256 + 3 = 313347 pour n=6.
  On peut écrire cette fonction de manière élémentaire ou exploiter la fonction int.from_bytes(liste_octets, ‘big') qui convertit liste_octet en entier.  Par exemple:

int.from_bytes([4, 200, 3], 'big') = 313347

  Le paramètre ‘big' (ou ‘little') indique l'ordre de traitement des octets, voir l'aide de Pyton pour des détails.

Q2) Ecrire une fonction separer_liste_entiers(s, n) (avec s liste d'entiers et n entier non nul) calculant la liste d'octets résultant de la transformation de chaque entier N de la liste s en la liste des n octets de l'écriture de N en base 256, en ajoutant éventuellement des 0 au début. Par exemple (noter la présence de 0 supplémentaires dans la conversion du dernier entier de s:

print(separer_liste_entiers([25602, 266, 1822, 1224, 3], 2)) → [100, 2, 1, 10, 7, 30, 4, 200, 0, 3]
print(separer_liste_entiers([6554113, 657182, 313347], 3)) → [100, 2, 1, 10, 7, 30, 4, 200, 3]
print(separer_liste_entiers([109959770146590, 313347], 6)) → [100, 2, 1, 10, 7, 30, 0, 0, 0, 4, 200, 3]

  On peut écrire cette fonction de manière élémentaire ou exploiter la méthode N.to_bytes(n, byteorder='big') qui convertit l'entier N en la liste de n octets de son écriture en base 256. Par exemple:

n = 313347
m = n.to_bytes(3, 'big')
p = n.to_bytes(6, 'big')
print(list(m), list(p))→ [4, 200, 3] [0, 0, 0, 4, 200, 3]

Q3) Ecrire une fonction exp_modulo(s, e, n) (avecs liste d'entiers et e, n deux entiers non nuls) calculant la liste des éléments de s élevés à la puissance e modulo n. Cette fonction doit utiliser l'exponentiation modulaire rapide qui est implémentée dans Python  avec la fonction pow(x, y, n) qui calcule x y [ n ] avec l'exponentiation modulaire rapide. Par exemple, en un instant:

pow(10**100 + 1, 10**1000 + 1, 10**30 + 1) = 542493058445750694165424930585
s = [337**i for i in range(100, 110)]
exp_modulo(s, 10**10 + 1, 2**40) → [380958337345, 1061274406545, 291679939809, 614192043057, 241717908609, 867317235153, 712349917217, 738581056369, 963758575553, 39637925137]

Q4) Ecrire une fonction nombre_octets(n) calculant le nombre d'octets nécessaires pour écrire n en base 256. Utliser la méthode .bit_length() qui apliquée à un entier donne le nombre de bits nécessaires pour l'écrire en base 2. Par exemple:

n = 255
print(n.bit_length()) → 8
print(nombre_octets(255), nombre_octets(256), nombre_octets(1000**1000)) → 1 2 1246

Q5) Ecrire une fonction rsa_chiffrer(nom_fichier, cle, e_pub) (avec nom_fichier une chaîne de caractères et cle, e_pub deux entiers non nuls qui ouvre, chiffre par l'algorithme RSA avecla clé publique (cle, e_pub) puis enregistre sous le nom rsa_nom_fichier le fichier appelé nom_fichier. Plus précisément, il faudra:
    (1) Calculer le nombre n = nombre_octets(cle)
    (2) Lire la listes s d'octets du fichier applelé nom_fichier
    (3) Calculer s = grouper_liste_octets(s, n - 1)
    (4) Calculer  s = exp_modulo(s, e_pub, cle)
    (5) Calculer  s = separer_liste_entiers(s, n)
    (6) Enregistrer dans le même répertoire la liste s dans un fichier appelé rsa_nom_fichier.
Faire des essais de chiffrage de fichiers que votre choix avec les clés données dans la fichier liste_cles_RSA.txt

Q6) Ecrire une fonction rsa_dechiffrer(nom_fichier, cle, e_priv) (avec nom_fichier une chaîne de caractères et cle, e_priv deux entiers non nuls qui ouvre, déchiffre par l'algorithme RSA avec la clé privée (cle, e_priv) puis enregistre sous le nom dec_nom_fichier le fichier appelé nom_fichier. Plus précisément, il faudra:
    (1) Calculer le nombre n = nombre_octets(cle)
    (2) Lire la listes s d'octets du fichier applelé nom_fichier
    (3) Calculer s = grouper_liste_octets(s, n)
    (4) Calculer  s = exp_modulo(s, e_priv, cle)
    (5) Calculer  s = separer_liste_entiers(s, n - 1)
    (6) Enregistrer dans le même répertoire la liste s dans un fichier appelé dec_nom_fichier.
  Faire des essais de déchiffrage des fichiers que vous chiffrés dans Q5) avec les clés données dans la fichier liste_cles_RSA.txt et vérifier que l'on retrouve les fichiers d'origine.

V) Algorithmes de calcul des clés

  Le calcul de grands nombres premiers repose sur le critère de Miller Rabin, qui exploite le petit théorème de Fermat ainsi que le fait que Z / p Z est intègre lorsque p est un nombre premier: si a b = 0 [ p ] , alors a = 0 [ p ] ou b = 0 [ p ] . Ce critère donne une condition nécessaire de primalité.

Théorème et définition (Critère de Miller Rabin)
  Soient n un nombre premier et a { 2 , 3 , ... , n - 1 } . Ecrivons n - 1 = 2 q m avec m entier impair et posons b = a m [ n ] . Alors:
       b = 1 ou k { 0 , ... , q - 1 } / b 2 k = - 1 [ n ] .  (Critère de Miller Rabin)
   La réciproque est fausse: un entier n impair qui vérifie la propriété précédente n'est pas forcément premier. On dit qu'il est a -pseudo-premier ou encore qu'il vérifie le critère de Miller Rabin pour l'entier a .

En effet: a n - 1 - 1 = ( b - 1 ) Π k = 0 q - 1 ( b 2 k + 1 ) [ n ] et si si n est premier alors a n - 1 - 1 = 0 [ n ] . Donc l'un des facteurs est nul modulo n .

Q7)  Ecrire une fonction  miller_rabin(n, a) (avec n entier et a ∈ {2,..., n-1})  à valeurs booléennes valant True lorsque n est impair et a-pseudo-premier pour le critère de Miller Rabin et False sinon. Vérifier par exemple que:

miller_rabin(2209, 71) = True
miller_rabin(10**10 + 19, 2) = True
miller_rabin(10**100 + 3,  1001) = False

  Nous allons maintenant évaluer la probabilité p n , pour un entier n impair pris au hasard, que n ne soit pas premier sachant que   k tests aléatoires de Miller Rabin sont tous vrais.
  La densité de nombres premiers au voisinage d'un entier n est de 1 ln ( n ) . Par ailleurs on peut démontrer que la probabilité pour que le critère de Miller Rabin soit vérifié alors que n n'est pas premier est inférieure à 1 4 .
  On peut en déduire que, si l'on effectue k tests aléatoires indépendants (pour le choix de a ) successifs de Miller Rabin pour l'entier n , la probabilité pour que tous les tests de Miller Rabin sont au “vert” (le critère est vérifié) sachant que cet entier n n'est pas premier  est plus petite que 1 4 k .

  Evaluons p n .  Fixons un entier k N * , choisissons un entier impair n au hasard et définissons les événements suivants:
    • A : l'entier n est composé et donc A _ : l'entier n est premier
    • B: les k essais aléatoires du critère de Miller Rabin sont tous vrais ( n est a -pseudo-premier pour les k choix aléatoires de a { 2 , 3 , ... , n - 1 } )
On sait que P A ( B ) 1 4 k (les essais aléatoires sont indépendants), que P A _ ( B ) = 1 et que P ( A _ ) 1 ln ( n ) , et on veut calculer p n = P B ( A ) , la probabilité d'erreur: l'entier n n'est pas premier sachant que tous les tests de Miller Rabin sont vrais.
p n = P B ( A ) = P ( A B ) P ( B ) = P ( A B ) P ( A ) P ( A ) P ( B ) = P A ( B ) P ( A ) P ( B ) (C'est la formule d'inversion des conditionnements).
Or P ( A ) 1 - 1 ln ( n ) 1 et P ( B ) = P ( A ) P A ( B ) + P ( A _ ) P A _ ( B ) (Formule de probabilités totales) ( 1 - 1 ln ( n ) ) 1 4 k + 1 ln ( n ) 1 1 ln ( n ) si 4 k 1 ln ( n ) .
   Donc p n = P B ( A ) 1 4 k 1 / ( 1 / ln ( n ) ) = ln ( n ) 4 k

Q8) Ecrire une fonction premier_MR(n, prob) avec (n entier impair et prob ∈ ]0, 1[) à valeurs booléennes qui renvoie True lorsque la probabilité que n ne soit pas premier est plus petite que prob et False sinon. Il faudra pour que premier_MR(n, prob) = True:
    (1) Calculer un entier k tel que prob ln ( n ) 4 k .
    (2) Effectuer k tests aléatoires de Miller Rabin qui devront tous être vrais.
  Faire des tests avec les entiers que vous voulez puis avec  avec n = 2 127 - 1 , n = 2 521 - 1 , n = 2 3217 - 1 , n = 2 4423 - 1 (qui sont premiers) et des produits de ces nombres. Prendre par exemple prob = 10 - 6 . Calculer par ailleurs ces entiers...
  Pour la petite histoire ces entiers sont tous des nombres de Mersenne, parmi lesquels les mathématiciens traquent les monstres premiers. Le nombre n = 2 127 - 1 (qui comporte 39 chiffres) a longtemps été le plus grand nombre premier connu (de 1876 à 1951).

  On rappelle que la fonction pgcd(a, b) calculant le pgcd de deux entiers a et b par l'algorithme d'Euclide est:

def pgcd(a, b):
    """ Calcul itératif du pgcd par l'algorithme d'Euclide"""
    while b > 0:
        a, b = b, a % b
    return a

On va utiliser cet algorithme d'Euclide pour calculer, étant donnés deux entiers a et b , un couple ( x , y ) d'entiers tel que a x + b y = pgcd ( a , b ) .

Commençons par un exemple. Avec a = 105 et b =16, l'algorithme d'Euclide s'écrit:
105 = 6×16 + 9
16 = 1×9 + 7
9 = 1×7 + 2
7 = 3×2 + 1
2 = 2×1 + 0
  Donc d = pgcd(105, 16) = 1. On écrit alors à chaque étape le reste comme combinaison linéaire de a et b, en exploitant les deux étapes précédentes
9 = 105 - 6×16
7 = 16 - 1×9 = 16 -1×(105 - 6×16) = 7×16 - 1×105
2 = 9 - 1×7 = (105 - 6×16) - (7×16 - 1×105) = 2×105 - 13× 16
1 = 7 - 3×2 = (7×16 - 1×105) - 3×(2×105 - 13× 16) =  46×16 - 7×105
Le couple ( x , y ) = ( - 7 , 46 ) est un couple solution de l'équation 105 x + 16 y = 1 .

  Notons a n et b n les valeurs des paramètres a et b après la n ième itération de l'algorithme d'Euclide .  On a: { a 0 = a b 0 = b et { a n + 1 = b n b n + 1 = a n % b n pour n N , tant que b n > 0 .
  Notons, si b n > 0 , (1): a n = b n q n + r n la division euclidienne de a n par b n .
  Pour n N ,     r n = a n % b n = b n + 1 = a n + 2   et q n = ( a n // b n ) = ( a n // a n + 1 ) , alors  l'égalité (1) s'écrit    a n = a n + 1 q n + a n + 2 . Le pgcd de a et b est le dernier terme non nul a N (avec N 1 ) de cette suite ( a n ) .

  On va calculer pour n N les entiers relatifs x n et y n tels que a n = x n a + y n b .  Pour n = N , on aura pgcd ( a , b ) = a N = x N a + y N b . Le couple ( x , y ) = ( x N , y N ) sera solution de notre problème.
  Pour n=0 : a 0 = a = 1 a + 0 b ; le couple ( x 0 , y 0 ) = ( 1 , 0 ) convient. Pour n = 1 : a 1 = b = 0 a + 1 b ; le couple ( x 1 , y 1 ) = ( 0 , 1 ) convient.
  Si aux rangs n et n + 1 on a:   a n = x n a + y n b et   a n + 1 = x n + 1 a + y n + 1 b , alors:
a n + 2 = a n - a n + 1 q n = x n a + y n b - ( x n + 1 a + y n + 1 b ) q n = ( x n - x n + 1 q n ) a + ( y n - y n + 1 q n ) b avec q n = ( a n // a n + 1 ) .
  Au rang n + 2 le couple ( x n + 2 , y n + 2 ) = ( x n - x n + 1 q n , y n - y n + 1 q n ) convient.
  On calcule ainsi de proche en proche les couples ( x n , y n ) jusqu'à notre solution ( x N , y N )

Q9) Ecrire une fonction inverse_modulo(a, b) (avec a et b entiers non nuls) calculant s'il existe l'inverse de a modulo b et renvoyant 0 sinon.
  L'inverse de a modulo b est, s'il existe, l'entier c { 1 , ... , b - 1 } tel que a c = 1 [ b ] . Cet entier c n'existe que si a et b n'ont pas de facteurs communs, c'est à dire lorsque pgcd ( a , b ) = 1 . Par exemple:

inverse_modulo(18241, 10**10 + 1) = 2196151527
inverse_modulo(1725, 10**10 + 2) = 0

  Toutes les fonctions nécessaires pour calculer une clé de longueur arbitraire de l'algorithme RSA ont été écrites: on peut maintenant demander:

Q10) Ecrire une fonction calcul_cle_RSA(n_bits) (avec n_bits un entier > 5) calculant une clé [cle=p*q, e_pub, e_priv] avec les conditions suivantes, en posant   k = n_bits // 2
    (1) Un entier p aléatoire de l'intervalle [ 2 k - 1 , 2 k ] avec qui est avec une probabilité d'erreur moindre que 10 - 6 , un nombre premier .
    (2) Un entier q aléatoire de l'intervalle [ 2 k , 2 k + 1 ] avec qui est avec une probabilité d'erreur moindre que 10 - 6 , un nombre premier .
Ainsi p et q sont des nombres premiers distincts et   n = p * q [ 2 2 k - 1 , 2 2 k + 1 ]   sera une clé de 2 k ou 2 k + 1 bits. Lorsque n_bits est pair, la clé aura n_bits ou n_bits + 1 bits et lorsque n_bits est impair, la clé aura n_bits - 1 ou n_bits bits.
    (3) Un entier aléatoire e_pub = e [ 2 , m - 1 = ( p - 1 ) ( q - 1 ) - 1 ] premier avec m , c'est à dire tel que pgcd ( e , m ) = 1 .
    (4) L'entier e_priv qui est l'inverse de e_pub modulo m = ( p - 1 ) ( q - 1 ) .
Faire des essais en voyant jusqu'à quelle valeur peut être augmentée la longueur de la clé. Des résultats possibles sont:

calcul_cle_RSA(8) = [187, 73, 57]
calcul_cle_RSA(64) = [20160520914882124163, 5548594565931247457, 5644252270202438993]

  On veut enregistrer dans un fichier texte une clé générée pour pouvoir la réutiliser dans plusieurs chiffrages. le fichier texte stockant la clé générée doit comporter les 6 lignes suivantes,  les lignes 1, 3 et 5 contiennent les entiers cle, e_pub, e_priv:

clé de n bits =
****************
e_public =
****************
e_privé =
****************

On donne les fonctions d'enregistrement et de récupération d'une clé:

def enregistrer_cle(cle, e_pub, e_priv, nom_fichier):
    """ Enregistrement d'une clé RSA dans le fichier texte cle_RSA_nom_fichier"""
    n_bits = cle.bit_length()
    cle, e_pub, e_priv = str(cle), str(e_pub), str(e_priv)
    nom_fichier = "cle_RSA_" + nom_fichier
    with open(nom_fichier, "w") as fich:
        fich.write("clé de {0} bits = \n".format(n_bits) + cle + "\n")
        fich.write("e_public =\n" + e_pub + "\n")
        fich.write("e_privé =\n" + e_priv)

  Le caractère \n génère le retour à la ligne.

def recuperer_cle(nom_fichier):
    """ Clé RSA (cle, e_pub_,e_priv) stockée dans le fichier nom_fichier"""
    with open(nom_fichier, "r") as fich:
        lignes = fich.readlines()
    return [int(lignes[i]) for i in (1, 3, 5)]

Q11) En utilisant ces fonctions, déchiffrer les fichiers:
    (1) fichier1.rsa chiffré avec la clé RSA stockée dans le fichier cle_RSA_mystere.txt
    (2) fichier2.rsa chiffré avec la clé RSA stockée dans le fichier cle_RSA_mystere.txt
Avant d'exploiter ces fichiers déchiffrés il faudra retrouver la bonne extension de leur nom.

Vous pouvez chiffrer maintenant vos communications de manière inviolable, tant que la clé privée reste bien protégée...

© 2015 - Eric Obermeyer      Powered by      Corrigé