Le cours

Par ZebulonBof_27 le 3 Décembre 2008 à 17:14

Partie 1 : RSA

Crypter et décrypter

Quoi de mieux pour introduire la cryptologie qu'un petit historique ?
Il était une fois sur la planète bleue, dans un lointain passé

, le désir de cacher et de coder ses messages (attention, cacher fait appel à la stéganographie et coder à la cryptographie !). Tout commença en 1900 avant J-C où un scribe égyptien employa des hiéroglyphes erronés volontairement. (Je vais griller quelques étapes

). Nous arrivons donc aux méthodes grecques et hébraïques. On notera parmi les méthodes grecques, celle de l'historien Polybe, puisque son invention inspirera le futur. La méthode est basée sur un principe de substitution avec l'utilisation d'un carré (voir ici). Toujours avec le principe de substitution, le bon vieux César y a mis sa patte.

En effet vers 1 siècle avant J-C, César crypte ses messages en remplaçant une lettre par une autre n place(s) après. Accélérons le temps pour faire un tour en 1919, date de parution de la machine Enigma, machine à crypter, qui fut employée par les nazis durant la guerre. En 1977 apparait DES, qui est succédé par AES qui lui, sera utilisé pour le chiffrement de documents aux USA. Nous touchons le but.

Effectivement, avril 1977, RSA montre le bout de son nez.

Cryptage

On trouve principalement deux grandes familles de cryptage : le cryptage symétrique (ou dit à clé secrète) et le cryptage asymétrique (dit aussi à clé publique).

Le cryptage symétrique

On parle de cryptage symétrique lorsqu'un texte, document, etc. est crypté et décrypté avec la même clé, la clé secrète, ce procédé est à la fois simple et sûr. On trouvera principalement parmi les algorithmes de cryptage asymétrique : AES, qui serait utilisé pour protéger des documents secrets aux États-Unis (ici). Principal inconvénient : étant donné que l'on n'a qu'une clé, si vous la donnez à X pour qu'il puisse vous envoyer des messages cryptés avec celle-ci, il pourra aussi bien décrypter tous les documents que vous avez crypté avec cette dernière. La clé est donc connue uniquement par le destinataire et l'émetteur et il est plus sûr de faire une clé pour un échange entre X et Y, pour éviter qu'avec une clé on puisse tout décrypter.

Le cryptage asymétrique

Contrairement au cryptage symétrique, ici avec l'asymétrique, on a 2 clés.
Tout d'abord nous avons la clé publique. Celle-ci, tout le monde peut la posséder, il n'y a aucun risque, vous pouvez la transmettre à n'importe qui. Elle sert à crypter le message. Puis il y a la clé privée que seul le récepteur possède, en l'occurrence vous. Elle servira à décrypter le message crypté avec la clé publique.
Pour clarifier mon charabia, une petite illustration :

Devinez quoi ? RSA fait partie des cryptages asymétriques !

Rivest, Shamir, Adleman

Alors, vous avez remarqué ? R... S... A... ! Oui, RSA est un sigle provenant des noms de ses inventeurs, qui sont respectivement Ron Rivest, Adi Shamir et Léonard Adleman.
Quelques informations pour situer ces personnages tirées de Wikipédia :
Ron Rivest est né à New York en 1947, et devient cryptologue. Adi Shamir, d'origine Israëlienne, né à Tel Aviv en 1952, est cryptologue et professeur au département de mathématiques appliquées du Weizmann Institute of Science. Il est reconnu pour ses qualités de cryptanalyste. Pour finir, Leonard Adleman, chercheur en informatique théorique et professeur en informatique et en biologie moléculaire à l'Universitée de la Californie du Sud, né en 1945.
Avec cette brochette de génies, on ne peut pas dire que l'algorithme RSA a été fait à la légère.

Un algoriquoi ?

Un algorithme, c'est une suite d'instructions visant à résoudre un problème. Celui-ci a été créé en 1977 et breveté en 1983 par le MIT (Massachusetts Institute of Technology) qui expira le 21 septembre 2000.

Fonctionnement

Alice est retenue prisonnière dans une grotte sombre et répugnante par un ogre affamé, ses jours sont comptés, elle veut envoyer un message à Bob par pigeon voyageur pour qu'il prévienne la gendarmerie nationale.

Euh comment dire... Je veux apprendre à crypter avec RSA et toi tu me parles d'une grotte et d'un ogre.

Non, attendez, Alice va crypter son message à l'aide de RSA.

Avant que notre Alice soit prisonnière, Bob a créé une clé publique et une clé privée. Il donne la clé publique à Alice et garde soigneusement la clé privée.
Regardons de plus près le travail de Bob.
Bob créé 2 nombres p et q, les autres nombres seront trouvés grâce à eux :

Nombres	Descriptions
p, q	2 grands nombres premiers
n	p*q
n	(p-1)*(q-1)
e	p,q < e < n, pgcd(n , e) = 1
d	p,q < d < n, e*d mod n = 1

La clé publique est sous la forme (e, n), celle que Alice possède et que tout le monde peut avoir sans aucun problème, ce couple permettra le cryptage de chaque message et la clé privée qui servira au décryptage se présente sous la forme (d, n), celle que Bob garde précieusement.

Crypter un message, en théorie

Notre Alice veut envoyer un message à Bob. Elle a donc à la base un message clair (mc), elle doit tout d'abord transformer chaque caractère en numérique (cn). Exemple : position dans l'alphabet, ASCII, etc., puis chiffrer chaque nombre pour obtenir les caractères codés (cc).
cn^e mod n = cc
e et n sont connus grâce à la clé publique de Bob.

Déterminer p, q, n, n, e

Bon c'est bien gentil la théorie, mais Alice commence à déprimer dans la grotte. Passons à l'action !
Voyons les calculs de Bob pour obtenir les clés et pouvoir chiffrer et déchiffrer.
Bob choisit p = 503 et q = 563, 503 et 563 sont premiers car ils ne sont divisibles que par 1 et eux-mêmes, c'est justement ce qu'il nous faut. Leur taille est plutôt petite, mais pour les explications elle suffira, pour un cryptage fiable avec RSA, il est recommandé d'utiliser des nombres de l'ordre de 100 chiffres voir plus.
Une fois p et q généré, le reste n'est que calcul. Sans trop de difficulté, on trouve n = 283189 = 503*563 et on se calcule vite fait bien fait Image utilisateur

n = 282124 = (503-1)*(563-1).

On trouve e par conditions, celles vu plus haut, je vous les rappelle : p,q < e < Image utilisateur

n, PGCD(

n, e) = 1.
La première condition délimite une portion de nombre dans laquelle se trouve e. Avec la deuxième on teste chaque nombre compris dans cette portion. Ils sont testés avec le PGCD (plus grand commun diviseur). Il y a de fortes chances que plusieurs e soient possibles, prenez le premier trouvé.

Alors que nous a choisi Bob ?
Déjà on sait que e se trouve entre 563 et 282124. On teste chaque nombre et si PGCD( Image utilisateur

n, e) = 1, on arrête, on dit alors que Image utilisateur

n et e sont premiers entre eux. Vous êtes prêt à tester une centaine de milliers de nombres ?

Je vous rassure, e ne se cache pas très loin :
PGCD(282124, 564) = 4
PGCD(282124, 565) = 1
PGCD(282124, 566) = 2
PGCD(282124, 567) = 1
...
Donc comme je vous ai dit, prenez le 1^er venu, soit e = 565.
Bob a donc p, q, n, Image utilisateur

n et e ; il va pouvoir créer la clé publique (e, n).
Clé publique de Bob : (565, 283189).
Il peut maintenant la donner à Alice et même la publier, il n'y a aucun risque.

Alice est enfermée dans un coin obscur de la grotte, pendant que l'ogre, servi par des gobelins, mange ; elle griffonne sur un bout de papier les calculs pour crypter avec RSA et la clé publique de Bob.

Elle veut chiffrer le texte suivant :
"Help !".
Message d'une importance capitale.

Coder chaque caractère en ASCII

Tout d'abord qu'est ce que l'ASCII ?
Votre ordinateur ne sait lire et sauvegarder que des données numériques. Oh la grosse quiche !

Donc il doit remplacer chaque caractère par un nombre, grâce à l'ASCII (American Standard Code for Information Interchange). L'ASCII est en fait une table où chaque caractère a son équivalent numérique.
Une fois votre message élaboré, la première des choses à faire est de transcrire toutes les lettres le composant en un nombre, simplement pour réussir à calculer, donc à crypter chacune des lettres. On peut coder les caractères en ASCII, ou alors, les remplacer par leur position dans l'alphabet, ou encore d'autres possibilités, mais le récepteur devra être au courant de la méthode utilisée.

Caractère	ASCII
H	72
e	101
l	108
p	112
(espace)	32
!	33

Le message, transcrit en numérique avec l'ASCII, est donc 72 101 108 112 32 33.

Un problème d'envergure !

Imaginez un instant que l'on ait un long texte. Si ce texte venait à être crypté, on aurait donc pour chaque caractère un nombre qui résulte du cryptage, mais dans ce genre de texte la même lettre peut réapparaître plusieurs fois, donc aussi le nombre résultant du cryptage de celle-ci.
Exemple :
coucou
On retrouve le c, le o et le u 2 fois. Un cryptage potentiel pourrait donner :
1053 2035 8456 1053 2035 8456
Pour une même lettre, on retrouve le même code ! Pour un texte codé d'une page si pour une même lettre on a un même code, cela pourrait compromettre sérieusement la sécurité du document puisque si l'analyse de fréquence d'apparition des lettres est utilisé, le texte peut être facilement décodé. En quoi consiste cette analyse ? Tout simplement à dire que pour la langue française en moyenne telle lettre a une fréquence d'apparition de tant de pour cent. Si on retrouve donc sur un texte de 500 mots, 50 fois le code 5489, on peut admettre grâce à cette analyse que tous les 5489 correspondent à "a" par exemple. Même principe pour "b", "c", "d", etc.

La solution :

La solution est de regrouper les codes ASCII en blocs de même longueur.
On leur donne d'abord à tous une longueur fixe, ici 3, en rajoutant des 0 devant si nécessaire. Cette longueur fixe sera toujours 2 ou 3 puisque le code ASCII ne contient aucun nombre avec plus de 3 chiffres.
072 101 108 112 032 033
Et on les regroupe en blocs de longueur 4 :
0721 0110 8112 0320 0033

Chaque bloc doit être inférieur à n soit ici 283189.

Avec ceci on n'aura jamais un même code pour une même lettre. Par contre le destinataire devra connaître au préalable les longueurs, sinon une fois décrypté, il ne saura pas comment découper pour retrouver l'ASCII.
On crypte. On décrypte. On retrouve :
0721 0110 8112 0320 0033
On découpe en blocs de 3.
072 101 108 112 032 000 33
Soit :
72 101 108 112 32 33
On a bien retrouvé notre ASCII.
Bon faut avouer, la méthode est fastidieuse, pour la suite du tutoriel et pour le programme, on ne l'utilisera pas pour privilégier la simplicité.

Crypter le code ASCII

Nous allons crypter le code ASCII de chaque caractère du message. Ce cryptage se fait grâce à un simple calcul, qui prend en compte le bloc, e et n qui sont présents dans la clé publique.
Formule :
Bloc^e % n = cc
"%" signifie modulo (ou mod).

Maintenant, il suffit juste de crypter chaque bloc comme le montre la formule.

072⁵⁶⁵ % 283189 = 80488
101⁵⁶⁵ % 283189 = 2826
108⁵⁶⁵ % 283189 = 241808
112⁵⁶⁵ % 283189 = 183218
032⁵⁶⁵ % 283189 = 45154
033⁵⁶⁵ % 283189 = 84918

Chacun des résultats doit être inférieur à Image utilisateur

Alice a donc crypté son message "Help !", avec la clé publique de Bob, et elle obtient : 80488 2826 241808 183218 45154 84918.
Il ne lui reste plus qu'à transmettre le message crypté et elle aura fait ce qu'elle pouvait notre pauvre Alice.

Décryptage

À partir de maintenant, deux histoires peuvent s'écrire. Soit son message est intercepté et décrypté, soit Bob le reçoit et Alice est sauvée.

Décrypter un message, en théorie

Destinataire indésirable

Ce destinataire, une fois en possession du message, doit créer la clé privée, par le biais de la factorisation de n, puis il décrypte chaque caractère codé (cc) et il obtient le code ASCII de chaque caractère (cn), puis il les transcrit en caractères clairs (ccl) pour obtenir le message clair.
cc^d % n = cn
cn -> ccl -> mc
n connu grâce à la clé publique et d doit être calculé après la factorisation de n.

Véritable destinataire

Prenons l'exemple de Bob. Il reçoit le message crypté, il décrypte chaque caractère codé (cc) et il obtient le code ASCII de chaque caractère (cn), puis il les transcrit en caractères clairs (ccl) pour obtenir le message clair.
cc^d % n = cn
cn -> ccl -> mc
d et n sont connus grâce à la clé privée de Bob.

Comme vous pouvez le constater, ces 2 cas sont similaires, ce qui les différencie et d'ailleurs ce qui est à l'origine de la fiabilité de RSA, c'est la factorisation de n. On va donc envisager les 2 cas. Alors, on commence par lequel ?

Bon, commençons par le cas où le message serait malheureusement intercepté. Admettons que ce soit un gros gobelin méchant, qui en chassant le pigeon a récupéré celui d'Alice. Comme il n'y comprend rien, il va le porter au gobelin cryptologue. :-°

Celui-ci trouvera donc à l'intérieur du message les blocs cryptés. Puisque ce n'est pas lui le destinataire, l'approche pour le décryptage sera différente. Le véritable destinataire, le créateur des clés, aurait utilisé la clé privée, mais lui devra créer la clé privée à partir de la clé publique, pour réussir à décrypter le message !
Clé privée : (d, n).
Comme n est déjà présent dans la clé publique, il reste d à trouver.
Nous avions évoqué plus haut comment l'avoir. Je vous redonne la ligne : p,q < d < n, e*d mod n = 1. Misère ! p et q, on ne les connaît pas ! Exact, mais n est le produit de 2 facteurs premiers qui sont p et q, donc la factorisation de n, nous donne p et q. Cette factorisation est longue, voire très très longue selon la taille de n et vous verrez que c'est le but recherché. On regardera ceci de plus près quelques lignes plus bas.
En factorisant n, on retrouve donc p = 503, q = 563.
Je ne vais pas détailler les calculs suivants car nous les avons déjà rencontrés plus haut. Image utilisateur

n = 282124, e = 565.

Déterminer d

En analysant un peu les conditions pour trouver d, on remarque que le principe est le même que pour e. On délimite tout d'abord une portion de nombre où se trouve d, d plus grand que p et q et d inférieur à n. Puis on teste les nombres compris dans cette zone avec ce calcul e*d mod Image utilisateur

n = 1.
565 * 564 % 282124 = 566
565 * 565 % 282124 = 37101
...
565 * 140313 % 282124 = 1
565 * 140314 % 282124 = 566
Cette fois-ci, manuellement il aurait fallu passer un bon bout de temps avant de trouver d. Il vaut mieux appliquer cette méthode à un programme qui nous trouvera d. Mais il y a une autre solution bien plus rapide qui se résume à un seul calcul.

d = 1/e % Image utilisateur

n
d = 1/565 % 282124
d = 140313

Cette dernière méthode est bien plus pratique.
Avec ces 2 méthodes, on peut aisément trouver d, et donc la clé privée.
Clé privée de Bob (trouvée par les méchants gobelins avec la factorisation de n) : (140313, 282124).

Décrypter le message

Citation : Alice

80488 / 2826 / 241808 / 183218 / 45154 / 84918

Le décryptage sera aussi simple que le cryptage, une simple formule, et nous retrouverons nos blocs de départ, puis on les retranscrit en lettres grâce à la table ASCII.

Formule :
cc^d % n = cn

80488¹⁴⁰³¹³ % 283189 = 72
2826¹⁴⁰³¹³ % 283189 = 101
241808¹⁴⁰³¹³ % 283189 = 108
183218¹⁴⁰³¹³ % 283189 = 112
45154¹⁴⁰³¹³ % 283189 = 32
84918¹⁴⁰³¹³ % 283189 = 33

ASCII	Caractère
72	H
101	e
108	l
112	p
32	(espace)
33	!

Et voilà, le message est décrypté, même si ce n'était pas le véritable destinataire !
Pourquoi ?
Tout simplement parce que la sureté du RSA repose sur la factorisation de n et notre n était bien trop petit, il a été factorisé rapidement avec un factorisateur banal.

Je vais prendre un nombre semi-premier, c'est-à-dire le produit de 2 nombres premiers, soit n, du challenge RSA qui n'est plus en vigueur, mais il est encore possible d'accéder à ces nombres. C'est le RSA-576, composé de 174 chiffres :

Citation : Challenge RSA

188 198 812 920 607 963 838 697 239 461 650 439 807 163 563 379 417 382 700 763 356 422 988 859 715 234 665 485 319 060 606 504 743 045 317 388 011 303 396 716 199 692 321 205 734 031 879 550 656 996 221 305 168 759 307 650 257 059

La factorisation en image : début et fin.
Vous pouvez remarquer que fin, c'est vite dit

. En fait la factorisation n'a pas abouti et je ne pouvais pas me permettre de faire tourner mon ordinateur pendant des lustres. L'algorithme de factorisation est peut-être basique mais même avec du bon matériel et un bon algorithme, cela prend quand même énormément de temps, c'est pourquoi RSA est sûr !

Le décryptage du côté de Bob, qui lui est le vrai destinataire, soit le créateur des clés privée et publique, est similaire à celui d'un destinataire indésirable, à la différence que Bob ne doit pas passer par la factorisation de n pour trouver p et q puisqu'il les a déjà.
Voilà, la force de RSA !
Il calcule d, comme vu plus haut et il peut ensuite sans problème décrypter le message d'Alice.
Bob crée donc sa clé privée : (140313, 282124).
Rien de nouveau, il va décrypter de la même manière que notre gobelin cryptologue. Une fois décrypté, Bob pourra sauver Alice.

Houraa !

Pour un programme de décryptage, il y a donc toujours 2 cas à prendre en compte. Soit il faut factoriser n pour trouver la clé privée ou simplement demander la clé privée à l'utilisateur.

Clé de chiffrement

Dans cette partie annexe, nous allons approfondir le terme de clé et nous verrons les législations qui s'y rapportent.

Qu'est ce qu'une clé de chiffrement ?

Citation : Wikipédia

Une clé est un paramètre utilisé en entrée d'une opération cryptographique (chiffrement, déchiffrement, scellement, signature numérique, vérification de signature).
Une clé de chiffrement peut être symétrique (cryptographie symétrique) ou asymétrique (cryptographie asymétrique) : ...
Une clé peut se présenter sous plusieurs formes : mots ou phrases, procédure pour préparer une machine de chiffrement (connexions, câblage, etc. Voir machine Enigma ), données codées sous une forme binaire (cryptologie moderne).

Dans ce chapitre, nous avons travailler avec 2 clés pour un cryptage asymétrique. Ces 2 clés étaient sous forme de chiffres, mais tout ceci a été vu plus haut. Nous allons maintenant nous intéresser à la taille d'une clé, exprimée en bits.
La taille d'une clé en bits est le nombre de bits qu'il faut pour l'écrire.
Exemple :
Ma clé est 10. Elle a donc une taille 4 bits. Puisque 10 égal en binaire 1010, il y a deux 1 et deux 0 soit 4 bits.

En cryptage symétrique, on dira qu'il y a 2⁴ choix pour trouver la clé, soit 16 possibilités.

En asymétrique, c'est la taille de n qui est importante, puisque c'est n qui est factorisé et qui permet donc le décryptage.
Et le nombre de possibilités de n n'est guère utile puisqu'il est donné dans la clé publique.
Exemple :
Reprenons notre n.
n=283189 -> 1000101001000110101. Soit une taille de 19 bits, ce qui est beaucoup trop mince pour un chiffrement fiable.

Les tailles des clés utilisées en asymétrique et en symétrique ne peuvent être comparées. On utilise des tailles plus importantes pour des algorithmes comme RSA que pour DES.
Pourquoi ?
Parce que les chiffrements asymétriques reposent sur des problèmes arithmétiques, comme la factorisation pour RSA. Il est alors nécessaire que n dépasse les 1024 bits soit environ 300 chiffres, sinon la factorisation est trop rapide et le document n'est plus sécurisé.
Pour les chiffrements symétriques, étant donné qu'il n'y a qu'une clé, on utilise la méthode du brute force. Avec une clé beaucoup plus petit que n, on a quand même une sécurité fiable. Il faut un minimum de 128 bits soit 2¹²⁸ possibilités, ce qui laisse déjà un petit moment au brute force pour se faire les dents.

Il est possible aussi pour remédier au problème de l'échange de la clé secrète, de la crypter avec un chiffrement asymétrique et de crypter le message avec un chiffrement symétrique. Étant donné que la clé secrète est cryptée, elle peut être envoyée sans problème au destinataire du message qui devra faire un double décryptage : celui de la clé et celui du message.

La loi

La loi du 21 juin 2004, libéralise l'utilisation des moyens de cryptologie. Cependant la fourniture de clés de déchiffrement est soumise à déclaration ou autorisation. Voir wikipédia.

Avant de conclure, voici une petite liste de quelques outils qui pourront vous être d'une grande utilité avant d'avoir fait votre programme :

Ce chapitre est maintenant clos. J'espère avoir accompli ma noble tâche que je me suis fixée

: vous faire comprendre clairement l'utilisation de l'algorithme RSA. D'ailleurs si j'ai oublié des points importants, n'hésitez pas à m'envoyer des MP ou à laisser un commentaire.

Êtes-vous prêt à vous lancer dans l'élaboration de programmes pour RSA ? Je suis sûr que oui, alors rendez-vous à la partie suivante.

Les programmes de cryptage et décryptage

Passons dès maintenant à la programmation python ! Si vous pensez que vous allez devoir adopter un serpent, un conseil, rendez-vous ici.

Mais si vous avez déjà quelques bases, commençons tout de suite.

Le programme de cryptage

Pour ce qui est de la programmation python, ne vous inquiétez pas, elle est très intuitive. Tout d'abord il vous faudra installer Python.
Nous travaillerons avec l'IDLE, donc une fois ouvert comme sur l'image, faites : Files > New Window, et nous taperons le code dans cette nouvelle fenêtre.

Déterminer p, q, n et n :

Entrons dans le vif du sujet

, souvenez-vous pour crypter avec RSA nous avons tout d'abord choisi deux nombres premiers, nous allons donc demander à l'utilisateur d'en choisir deux par le biais de la commande input() :

Il faut savoir qu'en python : on n'utilise pas de ";" et de "{...}" , les parenthèses sont remplacées si je puis dire par l'indentation et les dièses servent à signaler les lignes de commentaires

Code : Python

# L'utilisateur entre p
p = input('Entrez un grand nombre premier p : ')

# L'utilisateur entre q
q = input('Entrez un grand nombre premier q : ')

Nous demandons donc à l'utilisateur d'entrer p et q, puis nous pouvons calculer n et Image utilisateur

n.
Pour ceux qui ont déjà fait du C, vous retrouverez "\n" le retour à la ligne.

Code : Python

# On calcule n 
n = p*q

print "\nn = ",n,

# On calcul phi(n)
phiden = (p-1)*(q-1)

print "\nphi de n = ",phiden,

Pensez à mettre cette ligne à la fin du code, pour que le programme ne se ferme sans avoir vu les résultats.

Code : Python

1	raw_input('\n\nFin\n\n')

Enregistrer et exécuter :

Déjà fatigué

, alors faisons un petit break pour l'exécution de notre ébauche de programme ! Comment faire ? Bon, je suppose que vous avez tapé le code au fur et à mesure dans la fenêtre "Untitled", alors faites donc : Files > Save as > Nom du fichier : nom_de_votre_fichier.py > Enregistrer.
Vous pouvez ensuite lancer votre .py ou faire F5 et le programme se lancera dans l'IDLE, c'est vous qui choisissez.

Si vous avez des problèmes d'encodage (dus aux accents, etc.), je vous conseille de mettre cette ligne en début de code.
Code : Python

1	# encoding: utf-8

Déterminer la clé publique :

Il nous faut trouver e pour créer la clé publique, remémorons-nous comment trouver e :

p,q < e < n
e et n premiers entre eux.

Nous allons donc faire une boucle qui cherche p,q < e < Image utilisateur

n et par-dessus une autre boucle qui continue jusqu'à ce que PGCD de e et Image utilisateur

n = 1.

Les variables :

Code : Python

# Variables de la boucle
compteur = 0
PGCD1 = 0

# Notre e qui s'incrémentera
e = 0

La boucle et le if :

Code : Python

# Tant que PGCD de e et phi(n) différents de 1
while PGCD1 != 1 :
    # Tant que compteur=0
    while compteur == 0 :   
        # Si p inférieur à e et si q inférieur à e et si e inférieur à n
        if((p < e)and(q < e)and(e < phiden)) : 
            # La boucle se coupe (on peut aussi mettre le mot-clé : break
            compteur = 1     
        # Tant que rien n'est trouvé, e s'incrémente
        e = e + 1
    # On récupère le résultat du pgcd    
    PGCD1 = pgcd(e,phiden)

Une fois que e répond à la première condition, on vérifie s'il est premier avec Image utilisateur

n. Pour cela on crée une fonction PGCD qui retourne le PGCD de e et Image utilisateur

n.
En Python, une fonction est définie à partir du mot-clé "def". Nous écrirons notre fonction en début de code.

Code : Python

# La fonction PGCD avec ses 2 arguments a et b
def pgcd(a,b):
    # L'algo PGCD
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a;

Maintenant que nous avons tout le nécessaire pour la clé publique, autant l'afficher.

Code : Python

1 2	# On affiche notre clé publique print "\nCle publique (",e,",",n,")"

Crypter

Comme tout à l'heure nous utiliserons une commande pour récupérer le texte que la personne voudra crypter, cette fois ce ne sera pas input() mais une variante, raw_input qui a une différence près : celle-ci prend les lettres.

Code : Python

1 2	# On demande d'entrer le texte à crypter mot = raw_input('\nEntrez le mot ou la phrase à crypter : ')

Qui se souvient de ce qu'il faut faire après ? hein ? Alors ! personne... Rohh.

On va devoir transcrire chaque lettre en son code ASCII, mais comment va-t-on s'y prendre ?
Tout simplement de cette manière :

On cherche la taille de la chaîne de caractères à crypter.
On se fait une petite boucle qui tourne autant de fois que le nombre de lettres de cette dernière chaîne.
Dans cette boucle, on convertit chaque caractère en son code ASCII et on crypte le code ASCII grâce à la clé publique.
Pour la simplicité et la bonne compréhension du programme, je crypterai chaque code ASCII un par un, je ne les regrouperai pas par deux, comme expliqué dans le premier chapitre.

Bon jusque là pas besoin de travailler à la NSA.

Arrêtons les bavardages et codons.

La taille de la chaîne :

Code : Python

1 2	# On récupère le nombre de caractères du texte. taille_du_mot = len(mot)

Les variables :

Code : Python

i = 0

La boucle :

Code : Python

1 2	# Tant que i inférieur au nombre de caractères while i < taille_du_mot :

À partir d'ici, tout le code devra être dans la boucle et n'oubliez pas d'indenter, à l'aide de la touche tab.

ASCII :

Avec la fonction ord, nous pouvons très facilement convertir chaque caractère en son code ASCII. Celle-ci prend en argument le caractère à convertir.

Code : Python

1 2	# Comme i s'incrémente jusqu'à égalité avec la taille du mot, à chaque passage dans la fonction chaque lettre sera convertie. ascii = ord(mot[i])

Crypter le code ASCII de chaque lettre :

Ahhh enfin on y est ! Aucun changement, ne vous inquiétez pas, le cryptage RSA se fait toujours sous la forme :
bloc ^ e % n

Code : Python

1 2	# On crypte la lettre ou plutôt son code ASCII lettre_crypt = pow(ascii,e)%n

Deux dernières petites conditions :

Je ne vais pas vous faire attendre les voilà :

ASCII < n
bloc crypter < n

Code : Python

1
2
3

# Si le code ASCII est supérieur à n 
    if ascii > n :
        print "Les nombres p et q sont trop petits veuillez recommencer."

Code : Python

1
2
3

# Si le bloc crypté est supérieur à phi(n)
    if lettre_crypt > phiden :
        print "Erreur de calcul"

Finalisons :
En affichant chaque lettre cryptée et sans oublier d'incrémenter i à la fin de la boucle.

Code : Python

# On affiche chaque bloc crypté 
    print "\n Block : ",lettre_crypt,
    
    # On incrémente i
    i = i + 1

# On bloque le programme avant la fermeture
raw_input('\n\nFin\n\n')

Et gracieusement je vous donne l'ensemble du code et le programme en python.

Le programme de décryptage

Les quelques notions importantes de python ont été comprises ? Alors, passons tout de suite au décryptage.
La sécurité comme le programme de décryptage repose sur la factorisation de n. Nous allons donc récupérer n puis le factoriser pour obtenir les deux grands nombres premiers p et q.

La fonction de factorisation :

Comme pour le PGCD, on lui envoie n et elle se débrouille pour nous retourner p et q

.

Code : Python

# La fonction factoriser avec en argument n
def factoriser(n):
    b=2
    while b:
        while n%b!=0 :
            b=b+1
        if n/b==1 :
            print "p = ", b,
            # On créé une variable globale p pour la réutiliser hors de la fonction et p=b
            global p
            p = b
            break
        print "\nq = ", b,
        # On créé une variable globale q pour la réutiliser hors de la fonction et q=b
        global q
        q=b
        n=n/b;

Vous placez donc la fonction en début de programme, puis nous allons utiliser input() pour demander n et appeler la fonction.

Code : Python

# On récupère n.
n = input("Entrez le nombre n : ")

# On appelle la fonction pour le factoriser.
factoriser(n)

Déterminer n, e et d:

Pour

n rien de bien compliqué, comme d'habitude, un petit calcul pour le trouver.

Code : Python

1 2	# On calcule phi(n) phiden = (p-1)*(q-1)

Nous savons déjà comment trouver e, on utilise le même principe que pour le cryptage.

Comme e est présent dans la clé publique, le code suivant est facultatif, vous pouvez si vous le souhaitez ajouter à la place la commande input() pour récupérer e.

Une boucle ;
Des conditions ;
Et vérification que PGCD(e, phiden)=1.

Il va d'abord falloir que vous réécriviez la fonction PGCD en début de code.

Code : Python

# La fonction PGCD avec ses 2 arguments a et b.
def pgcd(a,b):
    # L'algo PGCD
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a;

Et maintenant on récrit la boucle et l'appel du PGCD. Trouver e est très important pour le calcul qui nous permet d'avoir d.

Code : Python

# Variable pour notre boucle while
compteur = 0
PGCD1 = 0

# Notre e qui s'incrémentera
e = 0

# Tant que PGCD de e et phi(n) différent de 1
while PGCD1 != 1 :
    # Tant que compteur=0
    while compteur == 0 :   
        # Si p inférieur à e et si q inférieur à e et si e inférieur à n
        if((p < e)and(q < e)and(e < phiden)) : 
            # La boucle se coupe (on peut aussi mettre le mot-clé : break
            compteur = 1     
        # Tant que rien n'est trouvé, e s'incrémente
        e = e + 1
    # On récupère le résultat du pgcd    
    PGCD1 = pgcd(e,phiden)

Voilà nous y sommes, il faut calculer d et nous avons notre clé privée, si vous vous souvenez du premier chapitre :
e*d mod n = 1 et p,q < d < Image utilisateur

n.
Comme pour e une boucle et des des conditions.

Code : Python

# On calcule d
d = 0
compteur = 0
while compteur == 0:
    # Les conditions vues ci-dessus :
    if((e * d % phiden == 1)and(p < d)and(q < d)and(d < phiden)):
        compteur = 1
    d = d + 1
d = d - 1

# On affiche la clé privée
print "\nCle privee (",d,",",n,")"

Il ne faut pas oublier le cas où ce serait le vrai destinataire qui utiliserait le programme. Tout le code entré jusqu'à présent doit être dans un if, et avant ce if, on demande à l'utilisateur s'il connaît p et q. Soit il ne les connaît pas et on entre dans ce premier if avec la factorisation de n ou soit il les connaît et on a un deuxième if où il rentra p et q non pas n.

Modifiez le code en entrant après les fonctions ces lignes qui permettent de gagner du temps si l'utilisateur est le bon destinataire.

Code : Python

pqconnu = 0
pqconnu = input("Si vous êtes en possession de p et q, entrez 1 sinon 0 : ")

if pqconnu == 0 :

Dans ce if on met donc le code du dessus.
Et celui-ci, le cas où nous n'avons pas à faire à un hacker.

Code : Python

if pqconnu == 1 :
    p = input("Entrez le nombre p : ")
    q = input("Entrez le nombre q : ")

    # On calcule n
    n = p*q

    # On calcule phiden
    phiden = (p-1)*(q-1)

    #On demande d
    d = input("Entrez le nombre d : ")

Dans les deux cas on aboutit à d. Seul le deuxième permet de passer la factorisation si l'on connaît p et q. Il n'est pas nécessaire de connaître e car e sert dans le cas où il faut trouver d, ici nous n'en avons pas besoin. Maintenant que d est connu, le décryptage peut réellement commencer.

Décrypter

Tout aussi simple le décryptage, regardons ensemble comment on va s'y prendre :

Par ce calcul savant : lettre cryptée ^ d % n = ASCII de la lettre, on trouve notre code ASCII.
Avec la fonction chr(ASCII), on retrouve la lettre.

On fait mijoter tout ceci dans la casserole boucle qui va tourner le nombre de fois qu'il y a de lettres, donc ceci c'est nous qui lui disons.

Le nombre de blocs et la boucle :

Code : Python

compteur = 0
# Tant que r inférieur au nombre de lettres
while compteur < i :
    # L'utilisateur entre le premier bloc à décrypter
    lettre_crypt = input("\nEntrez le bloc a décrypter :")
    # On trouve le ASCII de chaque lettre par le calcul de décodage
    ascii = (pow(lettre_crypt,d)%n)
    # Avec la fonction chr(ASCII), on trouve le caractère correspondant.
    print "lettre :",chr(ascii),
    compteur = compteur + 1

Pour exécuter le programme reportez-vous à la première partie, sinon voici le code et le .py. Je vous ai fait aussi une petite démo sur photo.

Eh bien voilà, on l'a fait ce programme ! Pas si dur hein ?
Si l'envie vous prend, sachez que de multiples améliorations sont possibles pour les programmes, comme faire un même programme pour le cryptage et le décryptage, un 2 en 1

, ou améliorer l'algorithme de factorisation, en bref, libre cours à vos idées...
Par exemple, les 2 programmes avec interface graphique : ici et là.
Sinon pour toutes hésitations mathématiques, la partie suivante est là pour vous

(entièrement rédigée par L01c).
Bonne continuation et à bientôt !

Explication Mathématique

Bonjour à toutes et à tous !

Ce chapitre va aborder des points mathématiques importants pour bien comprendre le cryptage RSA.

Tout d'abord nous allons voir la division euclidienne, ce qui va nous permettre de définir les congruences. Ensuite nous verrons les nombres premiers qui sont la base du cryptage RSA puisque ce sont deux nombres premiers que nous avions appelés p et q qui nous permettront de calculer n. Ensuite pour le décryptage, vous aurez besoin de factoriser n. Nous verrons donc la factorisation.

Évidemment, je vais donc tout vous expliquer depuis le début (faut juste savoir un peu compter, multiplier, soustraire, additionner ; et encore ça sera souvent des programmes qui feront ça à notre place

), donc il n'y a pas vraiment de pré-requis spécifiques.

Vous êtes fort, grand, beau, intelligent, prêt ? Let's go.

La division euclidienne

Tout d'abord, avant de nous lancer dans les congruences, nous allons définir et expliquer la division euclidienne, dont on a grandement besoin de comprendre le fonctionnement pour attaquer la suite.

Un exemple pour une première approche

Nous allons commencer tout doucement ce tuto avec les divisions comme on les faisait en... CM2, c'est-à-dire avec uniquement des nombres entiers positifs. Qui a dit que ce tuto était réservé à une élite de mathématiciens ayant au moins un Bac + 5 ? :-°

Bien, nous allons donc prendre un exemple: diviser 1489 par 17, et sans calculatrice s'il vous plaît :

Mouais et c'est quoi ce truc moche ?

C'est sûr, c'est pas avec ça que vous allez inventer la poudre (quoique...

), mais c'est déjà un début, alors qu'est-ce que j'ai fait là ?
Je suis parti de 1489, et j'ai vu qu'en mettant 80*17 je trouvais 1360, je soustrais donc 1360 à 1489, et il ne me reste plus que 129, or je remarque que 7*17=119, je prends donc le 129 auquel je soustrais 119, et je trouve 10.

Vous remarquez qu'à aucun moment je n'ai fait une soustraction de telle sorte que je me retrouve avec un reste négatif : il faut toujours avoir des nombres positifs, c'est important. Si jamais vous dépassez (par exemple 100*17 est plus grand que 1489), diminuez le 100, essayez avec 90, "Ha mince c'est encore trop grand", jusqu'à ce que vous trouviez le 80. Ensuite, une fois que vous avez le bon chiffre avec les dizaines, vous passez aux unités, pour trouver de la même manière un 7.

Bon, je me retrouve donc avec un 10 à la fin de ma division euclidienne.
Et là je fais quoi ? Ben rien, je laisse tel quel, "pourquoi donc?" me direz-vous.
Tout simplement parce que 10 est plus petit que 17 et que donc on ne peut plus continuer tel quel car, comme je vous l'ai dit plus haut, nous n'utilisons que des nombres entiers positifs.

Nous avons donc fait ce que nous appellerons à partir de maintenant la division euclidienne de 1489 par 17, nous avons trouvé comme quotient 87 et comme reste 10.
Nous remarquons que nous pouvons toujours retrouver 1489, en effet 17*87 +10 = 1489.

Une définition de la division euclidienne

Nous pouvons définir la division euclidienne de a par n telle que :
a=nq+r

Plusieurs remarques s'imposent :

a, n, q et r sont des entiers et nous n'emploierons dans le domaine de la cryptologie (et donc dans ce chapitre) que des entiers positifs (appelés encore entiers naturels).
Il faut absolument que r < n ; sinon, si r > n cela veut dire que nous n'avons pas fini la division. Un peu comme si j'avais dit que le reste dans l'exemple précédent était 129 au lieu de 10.
Il faut aussi que r soit plus grand ou égal à 0. Si r est négatif, c'est que nous sommes allés trop loin.
Si vous effectuez la division euclidienne de a par n et que vous respectez les deux points ci-dessus, vous devez obtenir un (l'existence) et un seul (l'unicité) couple : q et r, qui sont respectivement le quotient et le reste de la division euclidienne de a par n.
La démonstration de l'existence et l'unicité de la division euclidienne ne seront pas développées ici, car c'est un peu compliqué et c'est franchement pas très utile ; néanmoins si vous êtes fous curieux, allez voir la démonstration sur le site de wikipedia : il faut cliquer sur le premier "Dérouler" pour voir apparaître sous vos yeux ébahis la démonstration.
Pour votre culture générale, on appelle a le dividende et n le diviseur ; si vous ne retenez pas cela, ce n'est pas très grave.
Lorsque le reste r est nul, alors a=nq : on dit que n divise a ou que a est un multiple de n.

Le PGCD

Avant de se lancer tête baissée dans l'abstrait, je vais vous donner un exemple pour essayer de vous faire comprendre la notion de PGCD :

Pierre et Marie (Curie)

travaillent tous les deux dans la même entreprise et sont amis. Pierre travaille 8 heures par jours et Marie 6 heures. Le matin, ils commencent à travailler en même temps à 8 heures.
Sachant que Pierre et Marie ont le droit de faire des pauses pour aller boire un café toutes les X heures avec (X un nombre entier et qui doit être le même pour tous les deux fixés par tous les deux), sachant que leur première pause peut être faite après au moins une heure de travail, que leur dernière heure de travail doit aboutir à une dernière pause et qu'il n'y a pas de d'arrêt de travail pour le repas du midi (bouuhh le méchant patron qui laisse pas ses employés manger).
Seulement il n'y pas longtemps, Pierre et Marie se sont brouillés. Depuis ils s'évitent.

Combien de fois Pierre et Marie peuvent-ils au minimum se supporter se voir à la machine à café ? Et quelle sera alors la valeur de X ?

Allons-y avec de la méthode, on sait que Pierre travaille 8 heures par jour et qu'il faut qu'il fasse des pauses toutes les X heures et que sa dernière heure de travail doit aboutir à une pause, donc 8=Xn, n étant le nombre de pauses que Pierre fera ; de même Marie travaille 6 heures donc 6=Xn' avec n' le nombre de pauses que fera Marie.
Donc X divise 6 et 8 (en effet le reste est nul et n est un nombre entier).
Les diviseurs de 6 sont : 1, 2, 3, 6
Les diviseurs de 8 sont : 1, 2, 4, 8
Il faut donc prendre ce qui est en commun aux deux listes de diviseurs, c'est-à-dire que X peut valoir 1 ou 2.
C'est-à-dire : soit ils font une pause toutes les heures, et dans ce cas Pierre va faire 8 pauses, et Marie 6, auquel cas ils se verront 6 fois ; soit ils font une pause toutes les deux heures et dans ce cas Pierre va faire 4 pauses et Marie trois, dans ce cas ils se verront trois fois.
Comme ils sont brouillés, ils vont prendre la deuxième option, puisque c'est là qu'ils se verront le moins.
Mais la valeur de X sera 2, donc la plus grande des valeurs que pouvait prendre X.

X divise 8 et 6. Quand X=2, X est le plus grand diviseur commun de 8 et 6 : on dit donc que X est le PGCD (8, 6) (PGCD = Plus Grand Commun Diviseur. L'inversion entre commun et diviseur est volontaire ; en effet, pour la petite histoire, sachez que les Anglais appellent ça le GCD (Greatest common divisor), comme ça ils comprennent notre "PGCD" :lol:

).

Si vous prenez deux nombres entiers positifs quelconques, ils ont au moins un diviseur en commun qui est 1. On a dans tous les cas un diviseur commun, il y a donc un de ces diviseurs qui est plus grand que tous les autres, donc le PGCD existe quels que soient ces nombres.

Déterminer le PGCD de deux nombres

On sait que, pour tout couple de nombres entiers, il existe un PGCD. Nous allons maintenant déterminer le PGCD de deux nombres : 1352 et 124. Pour cela, nous allons faire... plusieurs divisions euclidiennes, que nous appelons algorithme d'Euclide:

1352=124*10+112 //on pose la division euclidienne du plus grand nombre par le plus petit
124=112*1+12 //on refait une division euclidienne mais le diviseur 124 devient dividende et le reste 112 devient diviseur
112=12*9+4 //on continue en interchangeant les nombres de la même manière
12=4*3+0

Une fois qu'on a atteint le 0, c'est qu'on a fini, ouf !

Mais il est où le PGCD dans tout ça ?

Le PGCD est le dernier reste non nul. Autrement dit, dans la dernière division euclidienne, on avait le reste nul : il faut donc prendre le reste du dessus, c'est-à-dire 4, donc PGCD (1352, 124)=4.

J'ai rien compris,. Comment tu sais que c'est lui le PGCD et pas un autre, ? Et puis pourquoi t'as fait des divisions euclidiennes ? T'aurais pu prendre les deux nombres les soustraire, mettre à la racine carrée en passant le tout au cosinus.

Oui, mais cette méthode donne le PGCD. Je ne peux pas vous le démontrer car c'est assez difficile à comprendre, mais vous pouvez vérifier par vous-même sur ce lien sur Wikipedia.

Retenez le principe uniquement si vous voulez vous-même coder un programme pour obtenir le PGCD. Sinon, vous trouverez, sur le lien précédent, le code source de l'algorithme d'Euclide dans beaucoup de langages (pratique pour vos programmes de cryptage

Nombres premiers entre eux

Deux nombres sont premiers entre eux lorsque leur PGCD vaut 1. Cela veut dire que, si on met ces nombres en fraction (l'un en dénominateur, l'autre en numérateur), cette fraction n'est pas simplifiable.
Par exemple 8/6=4/3
PGCD (8, 6) = 2 : on peut donc simplifier la fraction en divisant en haut et en bas par 2 ce qui nous amène au 4/3 ; en revanche, PGCD (4, 3)=1 : on ne peut donc plus simplifier cette fraction.
On dit que cette fraction est irréductible gaulois qui résistent encore et toujours à l'envahisseur... Pardon je m'emporte là

Conséquences de la division euclidienne

Si vous avez compris ce qu'était une division euclidienne, vous serez d'accord avec moi : le reste de la division euclidienne de la division de a par 2 est un nombre positif inférieur à 2, il n'y a donc que deux restes possibles : 1 et 0.
Ainsi : a=2q+0
Ou : a'=2q+1

Dans le premier cas, nous avons un nombre qui vaut deux fois q (avec q un nombre entier), ce nombre est donc un nombre pair. Dans le deuxième cas, nous avons a' qui vaut un nombre pair (2q) ajouté à 1, nous avons donc a' qui est un nombre impair.

Il faut que vous compreniez que tous les nombres entiers peuvent s'écrire 2q ou 2q+1 (ben ouais, facile : un nombre entier est soit pair, soit impair). Mais il faut surtout que vous compreniez que, de la même manière, tous les nombres entiers peuvent s'écrire 3q, 3q +1 ou 3q+2. On peut encore aller plus loin et faire avec 4 : 4q, 4q+1, 4q+2, 4q+3 etc...

Il existe donc des nombres qui ont le même reste dans la division euclidienne par n. Par exemple, tous les nombres impairs ont pour reste 1, dans la division euclidienne par 2.
Autre exemple : si on fait la division euclidienne de 23 par 5 et de 18 par 5.
23 = 5 * 4 +3
18 = 5 * 3 +3

On a donc le même reste qui vaut 3.

Deux nombres a et a' qui ont le même reste r dans la division euclidienne par n peuvent s'écrire :
a=nq'+r
a'=nq'+ r
Si on soustrait les deux égalités, on obtient :
a-a'=nq +r -(nq' + r) =nq -nq'
On peut donc factoriser à droite par n et obtenir : a-a'=n(q-q')

On voit donc que a-a' est un multiple de n.

On peut alors établir que, lorsque deux nombres ont le même reste par la division euclidienne par n, la différence de ces deux nombres est un multiple de n.

La réciproque est aussi vraie : lorsque a-a' est un multiple de n, alors a et a' ont le même reste dans la division euclidienne par n.

Nous voilà donc aux congruences : a et a' sont congrus modulo n si et seulement si ils ont le même reste dans la division euclidienne par n.

Les congruences

Nous allons maintenant attaquer Image utilisateur

un point important de ce chapitre : les congruences. Nous avons vu avant que deux nombres étaient congrus modulo à un nombre n lorsque la différence de ces deux nombres est divisible par n. Nous allons maintenant voir plus en profondeur les congruences.

La notation

Soient deux nombres a et b qui sont congrus modulo n. Nous allons noter la congruence de manière mathématique :
a $\equiv$ b [n] qui se lit a et b congrus modulo n.

Oui mais là tu dis que ces deux nombres sont égaux, ce qui n'est pas forcément le cas.

Non le [n] veut dire "modulo n" et enlève donc toutes ambiguïtés et / ou absurdités, de plus le signe $\equiv$ n'est pas un égal, puisqu'il y a trois barres.

Plusieurs remarques

On sait que si a $\equiv$ b [n] cela veut dire que a-b=qn, q étant un entier relatif (c'est-à-dire un entier positif ou négatif). Donc, si b=0 alors qn=a-0=a donc n divise a.
Il existe plusieurs notations pour les modulo :
a $\equiv$ b (mod. n)
a $\equiv$ b (n)
Pendant la suite du tuto, j'utiliserai plus volontiers la dernière notation qui est plus simple à utiliser.
Si a $\equiv$ b (n), alors b $\equiv$ a (n).
Si n=1, alors a-b est toujours divisible par 1. En effet, on peut toujours écrire un nombre x tel que x=x*1). Donc a $\equiv$ b (1) quels que soient a et b. C'est pour ça que les congruences modulo 1 n'ont pas un grand intérêt. On utilisera donc n plus grand ou égal à 2.
Lorsque n=10, il faut que a-b=10q. Il faut donc que a et b aient la même unité. Par exemple : 37-17=20 donc 37 $\equiv$ 17 (10).
La division euclidienne de a par n est définie par a=qn+r, donc a-r=qn. Donc, a-r est divisible par n, donc a $\equiv$ r (n). Cela est noté a%n = r.

Un programme pour vérifier la congruence

Vous vous souvenez dans le premier chapitre nous faisions des calculs avec les modulos, comme ici :
Citation :

072⁵⁶⁵ % 283189 = 80488

Imaginez un moment que vous avez peur et que vous voulez vérifier vos calculs mais que vous n'avez pas envie de faire ça de tête. Pas de problème ! Il suffit de faire un petit programme où vous n'aurez qu'à rentrer vos trois nombres dans la console. Votre programme fait alors la différence des deux premiers nombres et voit si la division de la différence par le troisième nombre est une division dont le résultat est un entier (positif ou négatif car la soustraction de deux entiers naturels peut donner un nombre négatif

). Dans le cas contraire, les deux nombres ne sont pas congrus entre eux.

En clair si $\frac{072^{565}-80488}{283189}$ donne un nombre entier alors c'est bon

Les nombres premiers

Une définition

Prenons par exemple le nombre 24. Nous pouvons dire, grâce à nos souvenirs des tables de multiplication, que 24=12*2=6*4. Mais avec le nombre 17, si on cherche des nombres entiers a et b tels que a*b=17, on ne trouve pas beaucoup de possibilités : soit c'est a=1 et b=17, soit c'est l'inverse ; les diviseurs de 17 sont donc 17 et 1.

La définition d'un nombre premier est donc : un nombre est premier si et seulement s'il n'a que deux diviseurs positifs, à savoir 1 et lui-même.

Quelques remarques :

0 n'est pas premier. En effet, on peut écrire que 0=a*0, quel que soit a. 0 ayant une infinité de diviseurs, il n'est pas un nombre premier.
1 n'est pas non plus premier. En effet, pour être premier, un nombre doit avoir deux diviseurs ; or 1 n'a qu'un seul diviseur : lui-même.
2 est divisible uniquement par 2 et par 1 : c'est donc un nombre premier. Tous les nombres pairs étant de la forme 2q, ils sont toujours divisibles par 2. Lorsque q est plus grand que 1, on a un nombre pair divisible par 2 nombres différents de 1 : 2 et q, donc 2 est le seul nombre pair premier.
Il existe une infinité de nombres premiers, le démontrer est assez difficile car cela nécessite des propriétés supplémentaires dont on n'a pas vraiment besoin. Cependant, voici un lien de Wikipédia si vous voulez comprendre.
En tout cas, c'est plutôt une bonne nouvelle pour vos données car plus vous prendrez des nombres premiers élevés, plus n sera élevé et donc ça sera sécurisé.

Comment vérifier qu'un nombre est premier ?

Vous voulez crypter en utilisant le système RSA et vous avez choisi deux nombres dont vous n'êtes pas sûr qu'ils soient premiers. Il va donc falloir le vérifier, sinon votre cryptage ne marchera pas.
Il va falloir créer un petit programme qui va vérifier si le nombre que vous mettez est bien premier. Celui ci sera écrit en C histoire d'alterner avec le python, mais si vous le comprenez dans un langage vous le comprendrez dans l'autre

.
Le voici dans sa totalité, les explications du programme sont juste en-dessous :

Code : C

#include <stdio.h>
#include <stdlib.h>
#include <math.h> 

int main(int argc, char *argv[])
{
    long nombre = 0;
    long premier = 0;
    long essai = 0;
printf ("Bonjour, ce programme permet de tester la primalité d'un nombre!\n\n");
printf ("Entrez un nombre entier positif :");
scanf ("%ld", &nombre);
if ( nombre % 2 == 0 )
        {
    premier = 3;
        }
else
{
for (essai = 3 ; sqrt (nombre) >= essai  ; essai+=2)
        {
         if (nombre % essai == 0)
                {
                premier = essai;
                }
        }   
}

if (nombre == 2)
{
premier = 0;
}
if (nombre == 1)
{
premier = 1;
}
if ( premier == 0)
{
printf ("ce nombre est premier\n\n\n");
}
else
{
printf ("Ce nombre n'est pas premier\n\n\n");
}

getchar();
return 0;
}

Explication:
Pour la première partie : le if
Nous savons qu'aucun nombre pair, sauf 2, n'est premier.
Code : C

if ( nombre % 2 == 0 )
        {
    premier = 3;
        }

Le code ci-dessus nous permet de savoir si le nombre est pair. S'il est pair (et différent de 2), il n'est pas premier. Il va donc falloir que la variable premier prenne une valeur différente de 0 (ici 3). En effet, à la fin, le code teste la variable premier et indique qu'un nombre est premier si la variable premier est nulle. Il faut cependant retenir que 2 est le seul nombre pair premier ; il faut donc ensuite faire un test pour voir si le nombre rentré par l'utilisateur est 2 ou pas ; si c'est le cas, il faut que la variable premier soit égale à 0, d'où le Code : C

if (nombre == 2)
{
premier = 0;
}

Ce bout de code doit être inséré après le test qui permet de dire si le nombre est pair ou pas. Si ce n'est pas le cas, la variable premier prendra, dans le cas où le nombre est deux, d'abord la valeur 0, puis la valeur 3.

Deuxième partie : le else
Pour comprendre cette partie, il faut que vous sachiez une chose : un nombre non premier a des diviseurs autres que un et lui-même. Ça, vous le savez, mais ce que je ne vous ai pas dit, c'est que, parmi ces diviseurs, il y a au minimum un nombre premier : par exemple, dans le cas du nombre 36, ses diviseurs sont (en gras les diviseurs qui sont premiers) :
1, 2, 3, 4, 6, 9, 12, 18, 36

Donc, en fait, ça serait simple : il suffirait de prendre un nombre et de le diviser par tous les nombres premiers inférieurs à ce nombre, et voir si un de ces nombres premiers est bien un diviseur ?

Oui, mais cela suppose de connaître tous les nombres premiers qui sont inférieurs à ce nombre, et ce n'est pas dit que ça soit le cas : vous pouvez me réciter tous les nombres premiers inférieurs à 4787 :-°

?
Alors, pour le programme, on va devoir diviser par d'autres nombres que des nombres premiers. Essayer tous les nombres serait trop long mais on sait déjà que tous les nombres pairs supérieurs à 2 ne sont pas premiers : on n'a donc qu'à faire des tests pour des nombres impairs supérieurs à 3 et incrémenter la variable essai de 2 pour éviter d'avoir des nombres pairs, d'où ceci : Code : C

1	for (essai = 3 ; sqrt (nombre) >= essai ; essai+=2)

Oui mais pourquoi la racine carrée (représenté par sqrt) ?

Excellente question

, la question est aussi intéressante que la réponse sera compliquée.

Vous êtes d'accord pour dire que, si on prend un nombre a positif, alors on a : $a=\sqrt{a}*\sqrt{a}$ .
Dans la pratique, a aura des diviseurs ; on peut donc dire que certains seront supérieurs ou égaux à $\sqrt{a}$ et d'autres seront inférieurs ou égaux à $\sqrt{a}$ .
Supposons que b et c soient des diviseurs de a tels que a=bc et que $\sqrt{a}> b$ .
Si on prend cette égalité, que l'on multiplie tout par $\sqrt{a}$ , on obtient : $\sqrt{a}*\sqrt{a}>b*\sqrt{a}$
soit $a > \sqrt{a}*b$ , mais on sait aussi que a=bc, on remplace donc a par bc.
Donc $b*c> b* \sqrt{a}$ en divisant par b : $c> \sqrt{a}$
Et là tout s'éclaire o_O

, non ?
Ça veut dire qu'un nombre quelconque a autant de diviseurs supérieurs (ou égaux) à racine de a que de diviseurs inférieurs à racine de a.
D'ailleurs, on le voit avec les diviseurs de 36 : 1, 2, 3 et 4 sont inférieurs à 6 tandis que 9, 12, 18 et 36 sont supérieurs à 6.
Donc, si on fait des tests avec des nombres inférieurs à racine de a et qu'on ne trouve pas de diviseur, c'est qu'il n'y en aura pas non plus au-dessus de racine de a. Le nombre est donc premier.
A contrario, il suffit de trouver un nombre qui divise a pour que a ne soit plus premier. Et il faut donc changer la variable premier et lui mettre une autre valeur : j'ai pris la valeur essai dans mon programme, mais je peux très bien mettre 4 ou tout autre nombre différent de 0.

Troisième partie : les tests

Il suffit de tester avec des if si le nombre premier est nul ou pas. S'il est nul, le nombre est premier ; dans le cas contraire, il n'est pas premier. Il faut aussi faire attention au 1, qui n'est pas premier. Il faut donc modifier la variable premier en faisant un test.

Il est évident que si ce test vous a permis de vérifier que 11 était effectivement premier en quelques dixièmes de secondes, il est beaucoup plus lent. Tester la primalité d'un nombre (la primalité étant le fait qu'un nombre soit premier) demande des ordinateurs beaucoup plus puissants et des algorithmes plus avancés.

Générer des nombres premiers

On arrive à trouver des expressions où, en faisant varier un entier positif n, on peut aboutir à la génération de certains nombres premiers ; mais il faut être prudent car cela ne marche pas à tous les coups. Je vais donc vous donner 3 suites, ce qui vous permet déjà de créer quelques nombres premiers :

Une première suite

Soit l'équation p=n²-n+41 avec n un nombre entier positif. Si nous faisons varier n, nous voyons que p prend des valeurs de nombre premier. Ci-dessous le tableau des premières valeurs de p :

valeur de n	valeur que prend p	p premier ?
0	41	Oui
1	41	Oui
2	43	Oui
3	47	Oui
4	53	Oui
5	61	Oui
de 5 à 39	...	Oui
40	1601	Oui
41	41²-41+41=41²=1681	Non

Et là c'est le drame car pour n=41, p=41² : ce n'est pas un nombre premier car il a au moins 3 diviseurs : un, lui-même et 41.

Cette suite ne marche pas : dommage ça aurait été un bon moyen de créer une suite de nombres premiers. Si vous avez un tableau de nombres premiers sous les yeux, vous pouvez vous apercevoir que, pour des valeurs de n qui vont de 0 à 40, ça marche mais pas au-delà

.

Vous pouvez aussi remarquer que cette suite ne donne pas tous les nombres premiers. En effet, il y avait de grands écarts au bout d'un moment entre deux valeurs de p consécutives alors qu'il y avait plein d'autres nombres premiers au milieu. Mais cette suite peut quand même vous donner des nombres premiers jusqu'à 1601.
Le problème, c'est que si tout le monde utilisait les nombres premiers de cette suite, les pirates le sauraient et ils n'auraient plus qu'à prendre le nombre n et à le diviser par les nombres de la suite pour des valeurs de n inférieures à 41. Ils pourraient donc en un rien de temps factoriser n. Il va falloir donc trouver autre chose.

Les nombres de Fermat

Pierre de Fermat a conjecturé (sans le prouver) il y a quatre siècles que les nombres du genre p=2^2ⁿ+1 étaient premiers.

Avec cette suite, ça a marché jusqu'à n=4 où on avait un nombre premier p = 65 537, mais Euler (si vous êtes en Première ou en Terminale S, vous avez sûrement entendu parler d'Euler et de la méthode d'Euler pour les approximations affines) démontra que, pour n=5, on avait p=4 294 967 297, ceci étant (comme chacun sait

) le produit de 6 700 417 par 641.

Nous n'avons donc pas beaucoup de nombres premiers sûrs avec cette suite mais elle donne quelques valeurs assez grandes de nombres premiers. D'ailleurs, il existe d'autres nombres premiers qui sont supérieurs au contre-exemple d'Euler, mais on ne sait pas s'il y en a une infinité ou pas. Donc il faudra faire des vérifications.

Une autre suite : les nombres de Mersenne

Les nombres de Mersenne sont des nombres du genre : 2^p-1 avec p un nombre premier. Cette suite donne des nombres qui ne sont pas forcément premiers mais qui ont une possibilité de l'être. Il faut donc faire un test de primalité grâce au programme que je vous ai montré ci-dessus.
Cependant, les nombres de Mersenne peuvent quand même donner de grands nombres premiers. Par exemple, le nombre 124575026[&]053967871 est un nombre premier comprenant exactement 9 808 358 chiffres (si vous retenez que ça fait presque 10 millions de chiffres, vous comprendrez pourquoi je peux pas l'écrire en entier :-°

) .

Il existe beaucoup de méthodes différentes de créer des nombres premiers ou des nombres ayant une forte probabilité de l'être, il est évident que les gens qui utilisent le système RSA pour des transactions de banques ne vont pas se servir que des nombres de Mersenne

et autres...

Conclusion

Vous pouvez donc générer pas mal de nombres premiers en faisant un programme qui va choisir aléatoirement, entre ces trois suites (veuillez noter qu'il existe d'autres suites de ce genre), deux d'entre elles (si c'est la même suite c'est pas très grave) et générer deux nombres premiers q et p pour le cryptage RSA. Mais n'oubliez pas que, pour la première suite que je vous ai donnée, il faut que n soit inférieur à 41. Il faudra également faire des tests de primalité si vous utilisez les deux autres suites.
Évidemment, je vous ai présenté des moyens simples de créer des nombres premiers, il est évident qu'il existe d'autres algorithmes plus performant mais aussi plus compliqué

.

Vous pouvez aussi intégrer dans votre programme les autres suites que je vous ai données en lien pour augmenter le nombre de nombres premiers que vous pouvez faire.

La factorisation

La factorisation est un point important dans le décryptage, en effet, en connaissant n, il faut trouver les nombres p et q.
C'est ce qu'on appelle la factorisation.

Première approche : qu'est-ce que la factorisation ?

Vous avez peut-être appris en classe que k(a+b)=ka+kb (si vous ne l'avez encore jamais vu, maintenant au moins c'est fait :-°

), par exemple 12(5+4)=12*5+12*4.

Lorsque l'on passe de k(a+b) à ka+k,b cela s'appelle développer.
Et dans l'autre sens, c'est la factorisation : cela veut dire que quand vous avez une somme de plusieurs produits, vous prenez ce qui est commun à tous ces produits et vous le multipliez par le reste que vous mettez dans des parenthèses.

Concrètement cela donne : 8*6+8*7+1568*8+67*8-8*3+8
On remarque que dans chacun des différents produits il y a un 8. On met donc 8 en facteur et on obtient :
8*6+8*7+1568*8+67*8-8*-3+8*1=8(6+7+1568+67-3+1).
Ainsi, si vous voulez calculer le résultat, vous avez moins d'opérations à faire : il suffit de calculer le résultat de la parenthèse et de le multiplier ensuite par 8. Vous gagnez donc un temps précieux et ce même en faisant le calcul avec votre calculatrice car vous réduisez le risque d'erreur en rentrant vos nombres.

Deux petites remarques :

Je n'ai pris la propriété qu'avec trois nombres k, a et b mais, comme vous le voyez dans l'exemple, on peut en mettre beaucoup plus : en fait vous en mettez autant que vous voulez.
Vous remarquez qu'il y a 1 à la fin : c'est tout simplement parce que 8=8*1. Si j'oublie ce 1, je modifie le résultat, ce qui n'est pas bon.

Maintenant voyons ce qu'est la décomposition en produit de facteurs premiers.

La décomposition : ça va nous aider à trouver n

On a vu au-dessus qu'on pouvait factoriser, c'est-à-dire mettre sous forme de différents facteurs. C'est ce que nous allons maintenant faire mais cette fois-ci nous allons partir d'un seul nombre n et le décomposer.

Tout d'abord on peut dire que tous les nombres sont soit premiers soit un produit de nombres premiers, par exemple :

7 est premier
8=4*2=2*2*2=2³ avec 2 qui est premier,
42=7*6=7*3*2 avec 7, 3, 2 qui sont premiers,
etc.

Cette décomposition est unique, si on ne tient pas compte de l'ordre dans lequel on met les différents facteurs (voilà le lien de Wikipédia pour la démonstration).

Il va donc falloir maintenant savoir comment factoriser n :

vous prenez un nombre et vous voyez s'il est divisible par deux. Si c'est le cas, notez son résultat et notez que vous avez mis un 2. Ensuite vous divisez ce résultat par deux si vous le pouvez. Si vous ne pouvez pas vous passez au nombre premier suivant, c'est-à-dire 3, vous le divisez par 3 autant de fois que vous pouvez, et après vous passez à 5, etc.
Prenons un exemple pour bien comprendre. On va décomposer 3960 :

On part de la valeur 3960 et on la divise par le premier nombre premier qui est 2 : on note qu'on a divisé une fois par 2 à droite. On voit qu'on obtient 1980, un nombre encore divisible par 2 : on rajoute donc un autre 2 à droite. Une fois cela fait, on passe à trois, puis à 5 et pour finir à 11.
Au final on trouve 1. Cela veut dire qu'on a fini la factorisation. En effet : 2 *2 *2 *3 *3 * 5 *11=2³*3²*5*11=3960. On a donc bien décomposé 3960 en facteurs de nombres premiers. Dans la pratique, la décomposition est plus simple dans la mesure où n est un produit de deux nombres premiers : il n'y a donc que deux nombres à trouver, p et q, mais cela nécessite beaucoup plus de temps. En effet, le nombre n ne sera sûrement pas divisible par 2, par 3 ou par 5. Souvenez-vous que nous préférons mettre de grands nombres premiers.

Si vous regardez le code permettant de trouver p et q qui vous a été donné pour faire le programme de décryptage, vous verrez que cela correspond à ce que nous avons fait au dessus, seulement là c'est l'ordinateur qui fait tout pour vous, chanceux !

Voilà, j'espère que vous avez beaucoup appris et que vous comprenez mieux ces notions mathématiques essentielles pour bien maîtriser le système RSA sur le bout des doigts.
J'ai essayé de faire en sorte que ce chapitre ne soit pas un cours de maths classique souvent bien ennuyeux, car l'objectif est surtout de vous faire comprendre des points importants du cryptage RSA. C'est pour ça que j'ai décidé de ne pas vous mettre de QCM

.

Pour tout remerciement, critique, suggestion, insulte, admiration, signalement d'erreur, manque de clarté, vous pouvez poster un message dans les commentaires.

Rédigé par L01c.

Et voilà, c'est fini, vous avez maintenant toutes les cartes en main pour pouvoir crypter / décrypter ce que vous voulez (tant qu'il ne s'agit pas de décrypter le code secret de mon compte en banque

) . Vous pouvez, si vous le voulez, refaire vous-même un gros programme : pourquoi pas un programme avec de jolies fenêtres qui vous permet de crypter / décrypter, en faisant le gros du travail, c'est-à-dire en créant des nombres premiers, en générant les clefs publiques et secrètes etc. ? Vous voyez, même après avoir lu ce tuto, vous avez encore du travail.

votre commentaire

1 2

Suivre le flux RSS des articles de cette rubrique

Suivre le flux RSS des commentaires de cette rubrique