Utiliser Python pour implémenter le chiffrement et le déchiffrement RSA

王林
Libérer: 2023-04-14 14:13:03
avant
2905 Les gens l'ont consulté

J'ai vu hier un article en anglais [1], montrant comment utiliser Python pour implémenter l'algorithme RSA. La logique du code est la même que celle de l'article précédent Comprendre l'algorithme RSA. Les amis qui ne sont pas familiers avec RSA peuvent lire l'article. Comprendre l'algorithme RSA, qui explique ce qu'est RSA, les principes mathématiques de RSA, et donne un exemple simple. On peut dire que c'est l'article le plus simple pour comprendre RSA sur Quanzhihu (cela vient des commentaires des lecteurs).

J'ai exécuté le code fourni en anglais et j'ai découvert qu'il ne pouvait pas crypter le chinois. J'ai donc modifié les fonctions de cryptage et de décryptage pour prendre en charge le cryptage et le décryptage du chinois. L'article d'aujourd'hui explique comment utiliser Python pour implémenter le processus de cryptage et de déchiffrement RSA afin de vous aider à établir une compréhension intuitive de RSA. L'algorithme de génération de nombres premiers aléatoires dans le code mérite également d'être appris.

0. Démonstration de l'effet

Jetons d'abord un coup d'œil à l'effet.

Texte original : "Il y a une taupe, mettez fin à la transaction"

Utiliser Python pour implémenter le chiffrement et le déchiffrement RSA

Le texte chiffré ne peut pas être déchiffré du tout :

Utiliser Python pour implémenter le chiffrement et le déchiffrement RSA

Après le décryptage :

Utiliser Python pour implémenter le chiffrement et le déchiffrement RSA

Code complet du compte public "Python Seven" a répondu "rsa" Get.

1. Génération de paires de clés

Idées :

1) Trouvez au hasard deux nombres premiers (nombres premiers) p et q Plus p et q sont grands, plus ils sont sûrs. Ici, nous choisissons un nombre premier de 1024 bits :

p = genprime(1024)
q = genprime(1024)
Copier après la connexion

genprime( ) Ne parlons pas du processus d'implémentation de la fonction.

2) Calculez leur produit n = p * q et la fonction d'Euler lambda_n.

n = p * q
lambda_n = (p - 1) * (q - 1)
Copier après la connexion

3) Sélectionnez au hasard un entier e, à condition que 1 < e < lambda_n, et e et lambda_n soient relativement premiers. Par exemple, si vous sélectionnez 35537, 35537 n'a que 16 bits et doit être plus petit que lambda_n. < e < lambda_n,且 e 与 lambda_n 互质。比如选择 35537,35537 只有 16 位,必然小于 lambda_n。

e = 35537
Copier après la connexion

4) Trouvez un entier d tel que le reste de e * d divisé par lambda_n soit 1, et renvoyez la paire de clés.

d = eucalg(e, lambda_n)[0]
if d < 0: d += lambda_n
return (d, n), (e, n)
Copier après la connexion

eucalg L'implémentation de la fonction sera discutée plus tard.

À ce stade, la fonction de génération de paire de clés est la suivante :

def create_keys():
 p = genprime(1024)
 q = genprime(1024)
 n = p * q
 lambda_n = (p - 1) * (q - 1)
 e = 35537
 d = eucalg(e, lambda_n)[0]
 if d < 0: d += lambda_n
 return (d, n), (e, n)
Copier après la connexion

2. Mise en œuvre du cryptage et du déchiffrement

Le processus de cryptage et de déchiffrement est le même, cryptage à clé publique, déchiffrement à clé privée, et vice versa, privé. cryptage par clé, déchiffrement par clé publique, mais le premier est appelé cryptage et le second est appelé signature.

L'implémentation spécifique de la fonction est la suivante :

def encrypt_data(data,key):
e_data = []
for d in data:
 e = modpow(d, key[0], key[1]) 
 e_data.append(e)
return e_data

## 加密和解密的逻辑完全一样
decrypt_data = encrypt_data
Copier après la connexion

La fonction modpow est utilisée ici, qui est utilisée pour calculer la formule b^e % n = r.

  • S'il s'agit d'un processus de cryptage, alors b est le texte en clair, (n,e) est la clé publique et r est le texte chiffré.
  • S'il s'agit d'un processus de décryptage, alors b est le texte chiffré, (n, d) est la clé privée et r est le fameux texte.

modpow est défini comme suit :

def modpow(b, e, n):
 # find length of e in bits
 tst = 1
 siz = 0
 while e >= tst:
tst <<= 1
siz += 1
 siz -= 1
 # calculate the result
 r = 1
 for i in range(siz, -1, -1):
r = (r * r) % n
if (e >> i) & 1: r = (r * b) % n
 return r
Copier après la connexion

3. Fonction de génération de nombres premiers aléatoires

Fonction de génération de nombres premiers aléatoires, qui utilise la multiplication matricielle et la séquence de Fibonacci, qui montre l'importance des mathématiques pour les algorithmes.

# matrix multiplication
def sqmatrixmul(m1, m2, w, mod):
 mr = [[0 for j in range(w)] for i in range(w)]
 for i in range(w):
for j in range(w):
 for k in range(w):
mr[i][j] = (mr[i][j] + m1[i][k] * m2[k][j]) % mod
 return mr

# fibonacci calculator
def fib(x, mod):
 if x < 3: return 1
 x -= 2
 # find length of e in bits
 tst = 1
 siz = 0
 while x >= tst:
tst <<= 1
siz += 1
 siz -= 1
 # calculate the matrix
 fm = [
# function matrix
[0, 1],
[1, 1]
 ]
 rm = [
# result matrix
# (identity)
[1, 0],
[0, 1]
 ]
 for i in range(siz, -1, -1):
rm = sqmatrixmul(rm, rm, 2, mod)
if (x >> i) & 1:
 rm = sqmatrixmul(rm, fm, 2, mod)

 # second row of resulting vector is result
 return (rm[1][0] + rm[1][1]) % mod

def genprime(siz):
 while True:
num = (1 << (siz - 1)) + secrets.randbits(siz - 1) - 10;
# num must be 3 or 7 (mod 10)
num -= num % 10
num += 3 # 3 (mod 10)
# heuristic test
if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
 return num
num += 5 # 7 (mod 10)
# heuristic test
if modpow(2, num - 1, num) == 1 and fib(num + 1, num) == 0:
 return num
Copier après la connexion

4. Implémentation de la fonction eucalg

L'essence de la fonction est de trouver la solution de l'équation linéaire suivante à deux variables :

e * x - lambda_n * y =1
Copier après la connexion

Code spécifique :

def eucalg(a, b):
 # make a the bigger one and b the lesser one
 swapped = False
 if a < b:
a, b = b, a
swapped = True
 # ca and cb store current a and b in form of
 # coefficients with initial a and b
 # a' = ca[0] * a + ca[1] * b
 # b' = cb[0] * a + cb[1] * b
 ca = (1, 0)
 cb = (0, 1)
 while b != 0:
# k denotes how many times number b
# can be substracted from a
k = a // b
# swap a and b so b is always the lesser one
a, b, ca, cb = b, a-b*k, cb, (ca[0]-k*cb[0], ca[1]-k*cb[1])
 if swapped:
return (ca[1], ca[0])
 else:
return ca
Copier après la connexion

5. :

1), Générez la clé

python test.py make-keys rsakey
Copier après la connexion

La clé publique est stockée dans rsakey.pub et la clé privée est stockée dans rsakey.priv

2), cryptez le contenu du fichier

S'il y a un fichier en texte brut .txt :

python test.py encrypt 明文.txt from rsakey to 密文.txt
Copier après la connexion

générera le texte chiffré .txt

3. Décrypter le contenu du fichier

S'il existe un fichier ciphertext.txt :

python test.py decrypt 密文.txt as rsakey to 解密后.txt
Copier après la connexion

générera le .txt déchiffré

Mots finaux

Cet article partage un simple implémentation de l'algorithme RSA en Python, qui peut aider à comprendre l'algorithme RSA.

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!

Étiquettes associées:
source:51cto.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal