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 1a8635884769d8e38da4b4734041e1f1936575187452021997864693899　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!