Vous vous apprêtez à lire un tutoriel rédigé par un membre de ce site. Malgré tout le soin que ce membre a pu apporter au tutoriel, nous ne pouvons pas garantir que les informations contenues sur cette page sont exactes à 100%. Merci de garder cela en tête lorsque vous lirez cette page ;o)
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 : Python1
2
3
4
5 | # 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
n.
Pour ceux qui ont déjà fait du C, vous retrouverez "\n" le retour à la ligne.
Code : Python1
2
3
4
5
6
7
8
9 | # 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.
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
Si les problèmes persistent rendez-vous
ici.
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 <
n et par-dessus une autre boucle qui continue jusqu'à ce que PGCD de e et
n = 1.
Les variables :
Code : Python1
2
3
4
5
6 | # Variables de la boucle
compteur = 0
PGCD1 = 0
# Notre e qui s'incrémentera
e = 0
|
La boucle et le if :
Code : Python 1
2
3
4
5
6
7
8
9
10
11
12 | # 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
n. Pour cela on crée une fonction PGCD qui retourne le PGCD de e et
n.
En Python, une fonction est définie à partir du mot-clé "def". Nous écrirons notre fonction en début de code.
Code : Python1
2
3
4
5
6
7
8
9 | # 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 : Python1
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 : Python1
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 : Python1
2 | # On récupère le nombre de caractères du texte.
taille_du_mot = len(mot)
|
Les variables :
Code : Python
La boucle :
Code : Python1
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 : Python1
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 : Python1
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 : Python1
2
3 | # Si le code ASCII est supérieur à n
if ascii > n :
print "Les nombres p et q sont trop petits veuillez recommencer."
|
1
2
3 | # Si le bloc crypté est supérieur à phi(n)
if lettre_crypt > phiden :
print "Erreur de calcul"
|
En affichant chaque lettre cryptée et sans oublier d'incrémenter i à la fin de la boucle.
Code : Python1
2
3
4
5
6
7
8 | # 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.
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 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | # 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 : Python1
2
3
4
5 | # 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 : Python1
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 : Python1
2
3
4
5
6
7
8
9 | # 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 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | # 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 <
n.
Comme pour e une boucle et des des conditions.
Code : Python 1
2
3
4
5
6
7
8
9
10
11
12 | # 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 : Python1
2
3
4 | 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 1
2
3
4
5
6
7
8
9
10
11
12 | 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 1
2
3
4
5
6
7
8
9
10 | 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.
Tutoriels
Communauté
Mon compte
Recherche
Livre d'or
Publicité
625 Zéros connectés |
10 requêtes |
0.0343s (0.0228s)
