Chiffrement asymétrique
Principes cryptographiques et chiffrement asymétrique¶
Le cryptologue militaire néerlandais Auguste Kerckhoff stipule dans un article publié dans le Journal des sciences militaires quelles sont les règles de base pour qu'un système cryptographique soit considéré comme sécurisé.
- Le système doit être matériellement, sinon mathématiquement indéchiffrable ;
- Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi ;
- La clef doit pouvoir en être communiquée et retenue sans le secours de notes écrites, et être changée ou modifiée au gré des correspondants ;
Ces principes sont considérés comme les principes fondamentaux de la cryptographie moderne. Traduits en langage moderne, cela veut dire que l'on ne doit évaluer la sécurité d'un système de chiffrement en supposant uniquement que la clé de chiffrement est secrète, tous les autres paramètres doivent être supposés publiquement connus. En particulier :
- le système de chiffrement utilisé est supposé connu ;
- tous les messages échangés peuvent être interceptés ;
Ils soulèvent toutefois un grave problème dans le cas où on utilise la même clé pour chiffrer et pour déchiffrer un message. Il est en effet alors impossible de s'échanger une clé de chiffrement sur un canal non sécurisé : toute personne interceptant cette communication pourra alors déchiffrer n'importe quel message à l'aide de cette clé ! Pour palier à ce problème de confidentialité de la clé, d'autres méthodes de chiffrement ont été découvertes, en particulier les méthodes de chiffrement asymétriques. Celles-ci reposent sur un couple de clés :
- une clé publique qui sert uniquement à chiffrer les messages, et tout le monde peut y avoir accès ;
- une clé privée qui sert uniquement à déchiffrer les messages chiffrés à l'aide de la clé publique correspondante. Cette clé n'est jamais divulguée.
Le chiffrement RSA (du nom de ses auteurs : Rivest, Shamir et Adleman) est un exemple d'un chiffrement asymétrique. Il repose sur des propriétés avancées des nombres entiers qui ne sont pas au programme de terminale, on se contentera juste de constater que "ça marche".
Propriétés arithmétiques¶
Nous utiliserons dans la suite de ce TP les définitions suivantes :
- un nombre est dit premier s'il possède exactement deux diviseurs : \(1\) et lui-même. En particulier, \(1\) n'est pas un nombre premier.
- deux nombres \(n\) et \(e\) sont dits premiers entre eux si leur plus grand diviseur commun est 1.
- \(a\) et \(b\) sont égaux modulo \(n\) si le reste dans la division euclidienne de \(a\) par \(n\) est le même que le reste dans la division euclidienne de \(b\) par \(n\). On note alors \(a \equiv b\) modulo \(n\).
- \(a\) et \(b\) sont des inverses modulo \(n\) lorsque \(a\times b \equiv 1\) modulo \(n\).
Rappels. En python, pour calculer le reste dans la division euclidienne de n par q on utilise l'instruction n % q (se lit \(n\) modulo \(q\)).
-
Donner la liste des nombres premiers inférieurs à \(20\).
-
Parmi les nombres entiers inférieurs à \(20\), lequels sont premiers avec \(10\) ?
-
Dans chacun des cas suivants, répondre vrai ou faux, en justifiant.
- \(3 \equiv 6\) modulo \(2\).
- \(3 \equiv 6\) modulo \(3\).
- \(3 \equiv 6\) modulo \(4\).
- \(6 \equiv 16\) modulo \(5\).
-
Justifier votre réponse dans chacun des cas suivants.
- \(3\) et \(4\) sont-ils des inverses modulo \(11\) ?
- \(7\) et \(6\) sont-ils des inverses modulo \(2\) ?
- Quel est l'inverse de \(2\) modulo \(13\) ?
- Quel est l'inverse de \(5\) modulo \(10\) ?
-
Soient \(n\in \mathbb{N}\) et \(a\in \mathbb{N}\) vérifiant \(0 \leq a < n\).
À quelle condition sur \(a\) et \(n\) peut-on trouver un nombre \(b\) tel que \(a\times b \equiv 1\) modulo \(n\) ?
Listes des nombres premiers : le crible d'Ératosthène¶
Ératosthène de Cyrène, né vers 276 av. J.-C. à Cyrène et mort vers 194 av. J.-C. à Alexandrie, est un astronome, géographe, philosophe et mathématicien grec.
Il est particulièrement connu pour son évaluation de la circonférence de la Terre grâce à un calcul géométrique, fondé sur la longueur de l'ombre à midi le jour du solstice d'été en un endroit situé sur un méridien donné à une distance connue du Tropique du Cancer, où à cette heure précise, il n'y a aucune ombre, le Soleil se trouvant exactement à la verticale.
Érathosthène est également l'auteur d'un algorithme permettant de donner la liste des nombres premiers inférieurs à \(n\), pour un certain entier \(n \in \mathbb{N}\) fixé à l'avance. L'algorithme procède par élimination : il s'agit de supprimer d'une table des entiers de \(0\) à \(n\) tous les multiples d'un entier (autres que lui-même). On commence par rayer les multiples de 2, puis les multiples de 3 restants, puis les multiples de 5 restants, et ainsi de suite en rayant à chaque fois tous les multiples du plus petit entier restant. À la fin il ne reste plus que les nombres premiers.
On utilise pour cela un tableau tab de n booléens, initialement tous égaux
à True, sauf tab[0] et tab[1] qui valent False (\(0\) et \(1\) n’étant pas des nombres premiers).
On parcourt alors ce tableau de gauche à droite et pour chaque indice i :
- si
tab[i]vautFalse: le nombrein’est pas premier et on n’effectue aucun changement sur le tableau. - si
tab[i]vautTrue: le nombreiest premier et on affecteFalseà toutes les cases du tableau dont l’indice est un multiple dei, à partir de2*i.
À l'issue de l'exécution de cet algorithme, tab[i] vaut True si et seulement si i est un nombre premier. On fera attention au cas particulier où n est inférieur ou égal à 1. Écrire une fonction nombre_premiers qui étant donné un entier n renvoie la liste de tous les nombres premiers inférieurs ou égaux à n.
def nombrespy-undpremiers(N):bksl-nl """ int -> [int]bksl-nl Renvoie la liste des nombres premiers inférieurs ou égaux à n """bksl-nl passbksl-nlbksl-nl
Diviseurs premiers d'un nombre¶
Écrire une fonction diviseurs_premiers qui étant donné un nombre n renvoie l'ensemble des diviseurs premiers de n. On pourra faire appel à la fonction nombre_premiers pour déterminer la liste des nombres premiers inférieurs à n, puis tester pour chacun de ces nombres si celui-ci divise n à l'aide de l'opération %.
def diviseurspy-undpremiers(n):bksl-nl """ int -> {int}bksl-nl Renvoie l'ensemble des diviseurs de n """bksl-nl passbksl-nlbksl-nl
Nombres premiers entre eux¶
Écrire une fonction premiers_entre_eux qui étant donné deux entiers a et b renvoie True si et seulement si a et b sont premiers entre eux. On rappelle que deux nombres sont dit premiers entre eux lorsque leur plus grand diviseurs commun est 1, autrement dit lorsqu'ils n'ont aucun diviseur premier commun. On rappelle également que si A et B sont objets de type set, alors A.intersection(B) renvoie l'ensemble constituée des éléments présents à la fois dans A et dans B (ni A ni B ne sont modifiés).
def premierspy-undentrepy-undeux(a, b):bksl-nl """ int, int -> boolbksl-nl Renvoie True si et seulement si a et b sont premiers entre eux """bksl-nl passbksl-nlbksl-nl
Inverse modulaire¶
Écrire une fonction inverse_modulo qui étant donné deux nombres n et a renvoie un nombre b tel que b soit l'inverse de a modulo n. La fonction renverra None dans le cas où a ne serait pas inversible modulo n.
def inversepy-undmodulo(n, a):bksl-nl """ int, int -> intbksl-nl Renvoie (si possible) l'inverse de a modulo n """bksl-nl passbksl-nlbksl-nl
Décomposition en facteurs premiers¶
Écrire une fonction decompose qui étant donné un entier n renvoie le dictionnaire correspondant à sa décomposition en facteurs premiers : les clés correspondront aux facteurs premiers de n ; la valeur associée à la clé p correspondra à l'exposant de p dans la décomposition en facteurs premiers de n.
def decompose(n):bksl-nl """ int -> {int:int}bksl-nl Décompose n en produit de facteurs premiers """bksl-nl passbksl-nlbksl-nl
Chiffrement RSA¶
Description de la méthode de chiffrement¶
Le chiffrement RSA fonctionne en trois grandes étapes :
-
Génération des clés.: On commence par choisir deux nombres premiers \(p\) et \(q\) "assez grands" et on note \(n = pq\). On calcule ensuite :
- \(\phi(n) = (p - 1)(q - 1)\)
- un nombre \(e \in \mathbb{N}\), avec \(0 \leq e < \phi(n)\), premier avec \(\phi(n)\).
- \(d\), l'inverse modulaire de \(e\) modulo \(\phi(n)\).
Le couple \((n, e)\) est la clé publique de chiffrement. Elle peut-être diffusée librement. Le couple \((n, d)\) est la clé privée de déchiffrement, elle ne doit jamais être communiquée. - Chiffrement.: Si \(M < n\) est un entier naturel représentant un message, alors le message chiffré à l'aide de la clé publique \((n, e)\) sera représenté par un entier \(C < n\) vérifiant :
\[C \equiv M^e \text{ modulo } n\] -
Déchiffrement: Si \(C < n\) est un entier naturel représentant un message \(M < n\) chiffré à l'aide de la clé publique \((n, e)\), alors on a :
\[ M = C^d \text{ modulo } n \]
(Dé)chiffrement d'un nombre¶
Génération des clés privées et publiques¶
Écrire une fonction genere_RSA qui étant donné deux nombres premiers \(p\) et \(q\) renvoie deux couples (n, e) et (n, d) correspondant respectivement à la clé publique et à la clé privée.
Remarque. Vous choisirez le nombre \(e\) aléatoirement à l'aide de la fonction choice du module random.
def generepy-undRSA(p, q):bksl-nl """ int, int -> (int, int), (int, int)bksl-nl Génère un couple de clé privée/clé publique pour RSA """bksl-nl passbksl-nlbksl-nl
Chiffrement avec la clé publique¶
Écrire une fonction chiffre_RSA qui chiffre l'entier M à l'aide de la méthode de chiffrement RSA en utilisant la clé publique pk = (n, e)
def chiffrepy-undRSA(M, pk):bksl-nl """ int, (int, int) -> intbksl-nl Chiffre le message M à l'aide de la clé publique """bksl-nl n, e = pkbksl-nl # À compléterbksl-nlbksl-nl
Déchiffrement avec la clé privée¶
Écrire une fonction dechiffre_RSA qui déchiffre l'entier C à l'aide de la méthode de déchiffrement RSA en utilisant la clé privée pk = (n, d)
def dechiffrepy-undRSA(C, sk):bksl-nl """ int, (int, int)bksl-nl Déchiffre le message chiffré C à l'aide de la clé secrète """bksl-nl passbksl-nlbksl-nl
(Dé)chiffrement d'un message¶
Chiffrement d'un message¶
M. Picard veut envoyer un message à M. Couturier, sans que celui-ci ne puisse être déchiffré par Mme. Sahbani. La clé publique de M. Couturier est écrite sur le tableau en salle des professeurs : il s'agit de (5893, 2519). Pour chiffrer un texte de longueur arbitraire, on convertit chacun des caractères qui le composent en son code ASCII correspondant et chiffre le code ASCII à l'aide de la méthode de chiffrement RSA et de la clé publique.
Écrire une fonction chiffre_texte_RSA qui étant donné un texte clair chiffre celui-ci avec la clé publique pk.
def chiffrepy-undtextepy-undRSA(clair, pk):bksl-nl """ str, (int, int) -> [int]bksl-nl Chiffre le texte à l'aide du chiffrement RSA et de la clé publique pk """bksl-nl passbksl-nlbksl-nl
Déchiffrement d'un message¶
M. Picard dépose au vu et au su de tous le message C en salle des professeurs. M. Couturier n'a jamais divulgué à qui que ce soit sa clé de déchiffrement privée, à part aux élèves de terminale NSI en qui il a toute confiance : il s'agit de (5893, 139) (mais chut !).
Écrire une fonction dechiffre_texte_RSA qui étant donné une clé privée sk et une liste d'entiers C correspondant à un message chiffré à l'aide de la clé publique associée à sk renvoie le texte correspondant.
def dechiffrepy-undtextepy-undRSA(chiffre, sk):bksl-nl """ [int], (int, int) -> strbksl-nl Déchiffre le message chiffre """bksl-nl passbksl-nlbksl-nl
(Dé)chiffrement par blocs¶
On suppose que M. Picard et M. Couturier continuer à utiliser méthode précédente avec le même couple de clé privée/clé publique pour chiffrer toutes leurs communications.
Expliquer pourquoi Mme. Sahbani, qui écoute tous leurs échanges chiffrés, pourra à terme "deviner" les messages en clair, sans avoir besoin de la clé privée de M. Couturier ?
Chiffrement RSA par bloc¶
Afin de palier au problème soulevé par la question précédente, on décide de mettre en place une méthode de chiffrement "par blocs", basée sur RSA. Par exemple, pour chiffrer la chaine de caractères : "nsi=cool!!!!" en se basant sur des blocs de taille 2 :
-
On commence par convertir tous les caractères de la chaîne à chiffrer en leur code ASCII correspondant.
La chaine "nsi=cool!!!!" devient : [110, 115, 105, 61, 99, 111, 111, 108, 33, 33, 33, 33] -
Tous les codes ASCII obtenus sont des nombres inférieurs à 128. Ils s'écrivent donc sur trois chiffres. On concatène toutes les chaînes de caractères correspondants aux codes ASCII en prenant soin d'ajouter des
"0"pour les nombres inférieurs à 100.110 115 105 061 099 111 111 108 033 033 033 033 -
On réorganise les chiffres par blocs de taille
2, puis on chiffre chaque bloc à l'aide de la méthode de chiffrement RSA.11 01 15 10 50 61 09 91 11 11 11 08 03 30 33 03 30 33 [3634, 1, 3214, 5673, 4003, 788, 5049, 4789, 3634, 3634, 3634, 5121, 5207, 3595, 5708, 5207, 3595, 5708]
Écire une fonction chiffre_texte_RSA_blocs qui étant donné un texte clair et une clé publique pk renvoie la liste des entiers correspondant à la méthode de chiffrement RSA par blocs.
def chiffrepy-undtextepy-undRSApy-undblocs(clair, pk):bksl-nl """ str, (int, int) -> [int]bksl-nl Chiffre le texte clair à l'aide d'un chiffrement RSA par bloc """bksl-nl passbksl-nlbksl-nl
Déchiffrement RSA par bloc¶
Pour déchiffrer le message chiffré C obtenu, on effectue les étapes suivantes :
-
On déchiffre chacun des entiers du message
Cà l'aide de la clé secrètesk. On retrouve alors :[11, 1, 15, 10, 50, 61, 9, 91, 11, 11, 11, 8, 3, 30, 33, 3, 30, 33] -
On concatène tous les nombres obtenus, en utilisant une taille de bloc de
2(on rajoute des"0"si besoin).11 01 15 10 50 61 09 91 11 11 11 08 03 30 33 03 30 33 -
On réorganise les chiffres par blocs de
3et on détermine le caractère correspondant à chacun des codes ASCII obtenus.110 115 105 061 099 111 111 108 033 033 033 033 n s i = c o o l ! ! ! !
Écire une fonction dechiffre_texte_RSA_blocs qui étant donné un texte chiffre et une clé privée sk renvoie le texte en clair correspondant à la méthode de chiffrement RSA par blocs.
def dechiffrepy-undtextepy-undRSApy-undblocs(chiffre, sk):bksl-nl """ [int], (int, int) -> strbksl-nl Déchiffre le message chiffre à l'aide d'un chiffrement RSA par blocs """bksl-nl passbksl-nlbksl-nl