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.
Jetons d'abord un coup d'œil à l'effet.
Texte original : "Il y a une taupe, mettez fin à la transaction"
Le texte chiffré ne peut pas être déchiffré du tout :
Après le décryptage :
Code complet du compte public "Python Seven" a répondu "rsa" Get.
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)
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)
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
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)
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)
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
La fonction modpow est utilisée ici, qui est utilisée pour calculer la formule b^e % n = r.
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
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
L'essence de la fonction est de trouver la solution de l'équation linéaire suivante à deux variables :
e * x - lambda_n * y =1
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
1), Générez la clé
python test.py make-keys rsakey
2), cryptez le contenu du fichier
python test.py encrypt 明文.txt from rsakey to 密文.txt
générera le texte chiffré .txt
3. Décrypter le contenu du fichier
python test.py decrypt 密文.txt as rsakey to 解密后.txt
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!