python implémente l'algorithme RSA

L'exemple de cet article décrit l'implémentation de l'algorithme RSA en python. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

1. Théorie des nombres de base

1. >

• Si deux entiers positifs n'ont pas de facteur commun sauf 1, on dit que ces deux nombres ont une relation coprime (coprime). Par exemple, 15 et 32 ​​n’ont pas de diviseur commun, ils sont donc premiers entre eux. Cela montre que même les nombres non premiers peuvent former une relation première entre eux.

2. Fonction d'Euler

• Définition : étant donné tout entier positif n, Parmi les entiers positifs inférieurs ou égaux à n, combien sont premiers par rapport à n ? (Par exemple, parmi 1 à 8, combien de nombres sont dans une relation première entre eux avec 8 ?) La méthode de calcul de cette valeur est appelée fonction d'Euler , représentée par φ(n).

• Méthode de calcul et propriétés de la fonction eulérienne :

1. Pour le nombre premier p, φ(p)=p-1, Pour deux nombres premiers p, q, φ(pq)=pq-1, La fonction d'Euler est la fonction sexuelle du produit, mais pas une fonction produit complète.

2. Pour la décomposition en puissance première d'un entier positif N N=P1^q1*P2^ q2* ...*Pn^qn, alors φ(N)=N*(1-1/P1)*(1-1/P2)*…*(1-1/Pn).

3. Sauf N=2, φ(N) sont tous des nombres pairs.

4. Si n peut être décomposé en deux premiers entre eux Le produit d'entiers, n = p1 × p2, alors φ(n) = φ(p1p2) = φ(p1)φ(p2)

2. chiffrement

La première étape consiste à sélectionner au hasard deux nombres premiers inégaux p et q.

Alice a choisi 61 et 53. (Dans les applications pratiques, plus ces deux nombres premiers sont grands, plus il est difficile de les déchiffrer.)

La deuxième étape consiste à calculer le produit n de p et q.

Alice multiplie 61 et 53.

　n = 61×53 = 3233

La longueur de n est la longueur de la clé. 3233 écrit en binaire est 110010100001, qui comporte 12 chiffres au total, donc la clé comporte 12 chiffres. Dans les applications pratiques, la clé RSA est généralement de 1 024 bits, et dans les cas importants, de 2 048 bits.

La troisième étape consiste à calculer la fonction d'Euler φ(n) de n.

Selon la formule :

　φ(n) = (p-1)(q-1)

Alice a calculé que φ(3233) est égal à 60×52, soit 3120.

La quatrième étape consiste à sélectionner au hasard un entier e, la condition est 1< e <

Alice avait entre 1 et 3120 et en a sélectionné 17 au hasard. (Dans les applications pratiques, 65537 est souvent choisi.)

La cinquième étape consiste à calculer l'élément inverse modulaire d de e par rapport à φ(n).

Ce qu'on appelle "l'élément modulo négatif" signifie qu'il existe un entier d qui peut rendre le reste de ed divisé par φ(n) égal à 1.

　ed ≡ 1 (mod φ(n))

Cette formule est équivalente à

　ed - 1 = kφ(n )

Ainsi, trouver l'élément inverse modulaire d revient essentiellement à résoudre l'équation linéaire suivante à deux variables.

　ex + φ(n)y = 1

On sait que e=17, φ(n)=3120,

　17x + 3120y = 1

Cette équation peut être résolue en utilisant « l'algorithme euclidien étendu », et le processus spécifique est omis ici. En résumé, Alice calcule un ensemble de solutions entières comme (x,y)=(2753,-15), soit d=2753.

Maintenant, tous les calculs sont terminés.

La sixième étape consiste à encapsuler n et e dans des clés publiques, et n et d dans des clés privées.

Dans l'exemple d'Alice, n=3233, e=17, d=2753, donc la clé publique est (3233,17) et la clé privée est (3233, 2753).

Dans les applications actuelles, les données des clés publiques et privées sont exprimées au format ASN.1 (exemple).

7. Fiabilité de l'algorithme RSA

En examinant les étapes de génération de clés ci-dessus, un total de six nombres apparaissent :

p
q
n
φ(n)
e
d

Parmi ces six nombres, la clé publique est utilisée Deux (n et e), les quatre numéros restants ne sont pas publics. Le plus critique est d, car n et d forment la clé privée. Une fois d divulgué, cela signifie que la clé privée a été divulguée.

Alors, est-il possible de déduire d lorsque n et e sont connus ?

　 (1) ed≡1 (mod φ(n)). Ce n'est qu'en connaissant e et φ(n) que nous pouvons calculer d.

(2)φ(n)=(p-1)(q-1). Ce n'est qu'en connaissant p et q que nous pouvons calculer φ(n).

(3) n=pq. Ce n'est qu'en factorisant n que nous pouvons calculer p et q.

Conclusion : Si n peut être factorisé, d peut être calculé, ce qui signifie que la clé privée a été craquée.

Cependant, factoriser de grands entiers est une chose très difficile. À l’heure actuelle, hormis le cracking par force brute, aucune autre méthode efficace n’a été trouvée. Wikipédia écrit :

"La difficulté de factoriser un très grand entier détermine la fiabilité de l'algorithme RSA. En d'autres termes, plus il est difficile de factoriser un très grand entier, plus le RSA est fiable. l'algorithme est. .

Si quelqu'un trouve un algorithme de factorisation rapide, alors la fiabilité de RSA sera extrêmement réduite, mais la possibilité de trouver un tel algorithme est très faible aujourd'hui. il n'existe aucun moyen fiable d'attaquer l'algorithme RSA. Tant que la longueur de la clé est suffisamment longue, les informations cryptées avec RSA ne peuvent pas être déchiffrées

Par exemple, vous pouvez factoriser 3233 (61×53). , mais vous ne pouvez pas factoriser l'entier suivant. <🎜>36575187452021997864693899　56474942774063845925192557

　32630345373154826850791702

　61221 4291346167042921 43116

　02221240479274737794080665

　351419597459856902143413


Il est égal au produit de deux nombres premiers 780
02287614711652531743087737
814467999489
227915816434308
　76426760322838157396665112
　7923337341 7143396810270092

　798736308917

En fait, il s'agit probablement du plus grand entier pris en compte par les humains (232 chiffres décimaux, 768 chiffres binaires). Aucune factorisation plus grande n’a été signalée, donc la clé RSA la plus longue jamais craquée est de 768 bits.

8. Cryptage et décryptage

Avec la clé publique et la clé, vous pouvez crypter et décrypter.

(1) Le cryptage nécessite une clé publique (n, e)

Supposons que Bob veuille envoyer des informations cryptées m à Alice, il doit utiliser la clé publique d'Alice (n, e) crypte m. Il convient de noter ici que m doit être un entier (la chaîne peut prendre une valeur ascii ou une valeur unicode) et m doit être inférieur à n.

Le soi-disant « cryptage » consiste à calculer c de la formule suivante :

　m^e ≡ c (mod n)

La clé publique d'Alice est (3233, 17), et le m de Bob est supposé être 65, alors l'équation suivante peut être calculée :

　65¹⁷ ≡ 2790 (mod 3233)

Donc, c est égal à 2790, et Bob envoie 2790 à Alice.

(2) Le décryptage nécessite la clé privée (n, d)

Après qu'Alice ait reçu le 2790 envoyé par Bob, elle utilise sa propre clé privée (3233, 2753 ) pour le décryptage. On peut prouver que l'équation suivante doit être vraie :

　c^d ≡ m (mod n)

En d'autres termes, c fois d Le reste lorsqu'un carré est divisé par n est m. Maintenant, c est égal à 2790 et la clé privée est (3233, 2753). Ensuite, Alice calcule

　2790²⁷⁵³ ≡ 65 (mod 3233)

<.> Par conséquent, Alice sait que le texte original de Bob avant cryptage est 65.

À ce stade, tout le processus de « cryptage-déchiffrement » est terminé.

Nous pouvons voir que si nous ne connaissons pas d, il n’y a aucun moyen de trouver m à partir de c. Comme mentionné précédemment, pour connaître d, il faut décomposer n, ce qui est extrêmement difficile à faire, c'est pourquoi l'algorithme RSA assure la sécurité des communications.

Vous vous demandez peut-être, la clé publique (n,e) ne peut chiffrer qu'un entier m inférieur à n, alors que devez-vous faire si vous souhaitez chiffrer un entier supérieur à n ? Il existe deux solutions : l'une consiste à diviser le message long en plusieurs messages courts et à chiffrer chaque segment séparément ; l'autre consiste à choisir d'abord un « algorithme de chiffrement symétrique » (tel que DES) et à utiliser la clé de cet algorithme chiffrer le message et utilisez ensuite la clé publique RSA pour chiffrer la clé DES.

9. Preuve de décryptage par clé privée

Enfin, nous prouverons pourquoi m peut être obtenu correctement en déchiffrant avec une clé privée. Soit prouver la formule suivante :

c^d ≡ m (mod n)

Car, selon les règles de cryptage

　ｍ^e ≡ c (mod n)

Par conséquent, c peut s'écrire sous la forme suivante :

c = m^e - kn

En substituant c dans la règle de décryptage que nous voulons prouver :

　(m^e - kn)^d ≡ m (mod n)

C'est équivalent à prouver

　m^ed ≡ m (mod n)

Depuis

　ed ≡ 1 (mod φ(n))

donc

ed = hφ( n)+1

Remplacer ed par :

　m^hφ(n)+1 ≡ m (mod n)

Ensuite, prouvez la formule ci-dessus dans deux cas.

(1) m et n sont relativement premiers.

D'après le théorème d'Euler, à cet instant

　m^φ(n) ≡ 1 (mod n)

Obtenir

　(m^φ(n))^h × m ≡ m (mod n)

Original formule Faites vos preuves.

(2) m et n ne sont pas premiers entre eux.

À ce moment, puisque n est égal au produit des nombres premiers p et q, m doit être égal à kp ou kq.

Prenons m = kp comme exemple Considérant que k et q doivent être mutuellement premiers à ce moment, selon le théorème d'Euler, la formule suivante est valable :

　(kp)<.>q-1 ^{≡ 1 (mod q)}

obtient en outre

　[(kp)

q-1^] h(p-1) ^{× kp ≡ kp (mod q)}

c'est-à-dire q)

Réécrivez-le dans l'équation suivante

　(kp)

ed

= tq + kp

A ce moment t doit être divisible par p, c'est-à-dire t=t'p

　(kp)

ed

= t'pq + kp

Parce que m=kp, n=pq, donc

　m^ed ≡ m (mod n)

La formule originale est prouvée.

implémentation de Python

Python puissant a une implémentation dédiée La bibliothèque tierce pycrypto de technologie cryptographique. Cependant, si nous voulons implémenter rsa, nous n'avons pas besoin d'un outil aussi sophistiqué, il nous suffit de charger une bibliothèque tierce de rsa.

vous montrer le code, NON bb :

#实现公钥加密 RSA

import rsa
import time
#计算下时间

start_time = time.time()
key = rsa.newkeys(1024) #数字代表 p * q 产生的存储空间 bit 大小, 也就是密文长度，数字越大，时间越长
privateKey = key[1]
publicKey = key[0]
#print(privateKey)
#print(publicKey)
end_time = time.time()
print("make a key:", end_time - start_time)
#产生公钥和私钥

message = 'Taiyuan is the best city of China.'
message = message.encode()

cryptedMessage = rsa.encrypt(message, publicKey)
print("crypted:", cryptedMessage)
print("length of cryptedMessage：", len(cryptedMessage))
# 加密的过程

decrypetdMessage = rsa.decrypt(cryptedMessage, privateKey)
print("decrypet:", decrypetdMessage)
# 解密的过程

now_time = time.time()
print("crypt and decrypt:", now_time - end_time)

Recommandations associées :

Vous amène à bien comprendre les principes de l'algorithme RSA

Algorithme de cryptage RSA

25 lignes de code pour implémenter l'algorithme RSA complet

Explication détaillée de l'algorithme RSA et de l'implémentation du langage C

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!