Python implementiert den RSA-Algorithmus

Das Beispiel in diesem Artikel beschreibt die Implementierung des RSA-Algorithmus in Python. Teilen Sie es als Referenz mit allen:

1. Grundlegende Zahlentheorie

1 >

• Wenn zwei positive ganze Zahlen keine gemeinsamen Faktoren außer 1 haben, sagen wir, dass diese beiden Zahlen eine koprime Beziehung haben (koprime). Beispielsweise haben 15 und 32 keine gemeinsamen Teiler und sind daher gegenseitig prim. Dies zeigt, dass auch Nicht-Primzahlzahlen eine Koprime-Beziehung eingehen können.

2. Euler-Funktion

• Definition: gegeben jede positive ganze Zahl n, Unter den positive ganze Zahlen kleiner oder gleich n, wie viele sind teilerfremd zu n? (Zum Beispiel: Wie viele Zahlen von 1 bis 8 stehen in einer Primzahlbeziehung mit 8?) Die Methode zur Berechnung dieses Werts heißt Euler-Funktion und wird durch φ(n) dargestellt.

• Berechnungsmethode und Eigenschaften der Eulerschen Funktion:

1. Für die Primzahl p, φ(p)=p-1, Für zwei Primzahlen p, q, φ(pq)=pq-1, Die Euler-Funktion ist die Produkt-Sexualfunktion, aber keine vollständige Produktfunktion.

2. Für die Primzahlpotenzzerlegung einer positiven ganzen Zahl N N=P1^q1*P2^ q2* ...*Pn^qn, dann φ(N)=N*(1-1/P1)*(1-1/P2)*…*(1-1/Pn).

3. Außer N=2 sind φ(N) alle gerade Zahlen.

4. Wenn n zerlegt werden kann in zwei Koprime Das Produkt ganzer Zahlen, n = p1 × p2, dann φ(n) = φ(p1p2) = φ(p1)φ(p2)

2 Verschlüsselung

Der erste Schritt besteht darin, zwei ungleiche Primzahlen p und q zufällig auszuwählen.

Alice wählte 61 und 53. (In praktischen Anwendungen ist es umso schwieriger, diese beiden Primzahlen zu knacken, je größer sie sind.)

Der zweite Schritt besteht darin, das Produkt n von p und q zu berechnen.

Alice multipliziert 61 und 53.

　n = 61×53 = 3233

Die Länge von n ist die Schlüssellänge. 3233 ist im Binärformat 110010100001 und hat insgesamt 12 Ziffern, sodass der Schlüssel 12 Ziffern hat. In praktischen Anwendungen beträgt der RSA-Schlüssel im Allgemeinen 1024 Bit, in wichtigen Fällen 2048 Bit.

Der dritte Schritt besteht darin, die Euler-Funktion φ(n) von n zu berechnen.

Nach der Formel:

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

Alice hat berechnet, dass φ(3233) gleich 60×52 ist, also 3120.

Der vierte Schritt besteht darin, eine ganze Zahl e zufällig auszuwählen, die Bedingung ist 1< φ(n) und e und φ(n) sind relativ prim.

Alice war zwischen 1 und 3120 und wählte zufällig 17 aus. (In praktischen Anwendungen wird oft 65537 gewählt.)

Der fünfte Schritt besteht darin, das modulare Umkehrelement d von e in Bezug auf φ(n) zu berechnen.

Das sogenannte „modulo negative Element“ bedeutet, dass es eine ganze Zahl d gibt, die den Rest von ed dividiert durch φ(n) gleich 1 machen kann.

　ed ≡ 1 (mod φ(n))

Diese Formel entspricht

　ed - 1 = kφ(n )

Das Finden des modularen Umkehrelements d bedeutet im Wesentlichen das Lösen der folgenden linearen Gleichung zweier Variablen.

　ex + φ(n)y = 1

Es ist bekannt, dass e=17, φ(n)=3120,

　17x + 3120y = 1

Diese Gleichung kann mit dem „Erweiterten Euklidischen Algorithmus“ gelöst werden, und der spezifische Prozess wird hier weggelassen. Zusammenfassend berechnet Alice eine Reihe ganzzahliger Lösungen als (x,y)=(2753,-15), was d=2753 ist.

Jetzt sind alle Berechnungen abgeschlossen.

Der sechste Schritt besteht darin, n und e in öffentliche Schlüssel und n und d in private Schlüssel zu kapseln.

In Alices Beispiel ist n=3233, e=17, d=2753, also ist der öffentliche Schlüssel (3233,17) und der private Schlüssel ist (3233, 2753).

In tatsächlichen Anwendungen werden die Daten öffentlicher und privater Schlüssel im ASN.1-Format ausgedrückt (Beispiel).

7. Zuverlässigkeit des RSA-Algorithmus

Bei Betrachtung der oben genannten Schlüsselgenerierungsschritte werden insgesamt sechs Zahlen angezeigt:

p
q
n
φ(n)
e
d

Unter diesen sechs Zahlen wird der öffentliche Schlüssel Zwei verwendet (n und e), die restlichen vier Zahlen sind nicht öffentlich. Das kritischste ist d, da n und d den privaten Schlüssel bilden. Sobald d durchgesickert ist, bedeutet dies, dass der private Schlüssel durchgesickert ist.

Ist es also möglich, d abzuleiten, wenn n und e bekannt sind?

　 (1) ed≡1 (mod φ(n)). Nur wenn wir e und φ(n) kennen, können wir d berechnen.

(2)φ(n)=(p-1)(q-1). Nur wenn wir p und q kennen, können wir φ(n) berechnen.

(3) n=pq. Nur durch Faktorisieren von n können wir p und q berechnen.

Schlussfolgerung: Wenn n faktorisiert werden kann, kann d berechnet werden, was bedeutet, dass der private Schlüssel geknackt wurde.

Allerdings ist die Faktorisierung großer Ganzzahlen eine sehr schwierige Sache. Derzeit wurde außer dem Brute-Force-Cracking keine andere wirksame Methode gefunden. Wikipedia schreibt:

„Die Schwierigkeit, eine sehr große ganze Zahl zu faktorisieren, bestimmt die Zuverlässigkeit des RSA-Algorithmus. Mit anderen Worten: Je schwieriger es ist, eine sehr große ganze Zahl zu faktorisieren, desto zuverlässiger ist der RSA.“ Algorithmus ist.

Wenn jemand einen schnellen Faktorisierungsalgorithmus findet, ist die Wahrscheinlichkeit, einen solchen Algorithmus zu finden, sehr gering. Es gibt keine zuverlässige Möglichkeit, den RSA-Algorithmus anzugreifen. Solange die Schlüssellänge lang genug ist, können mit RSA verschlüsselte Informationen nicht geknackt werden.

Sie können beispielsweise 3233 (61×53) faktorisieren. , aber Sie können die folgende ganze Zahl nicht faktorisieren. <🎜>36575187452021997864693899　56474942774063845925192557

　32630345373154826850791702

　61221 4291346167042921 43116

　02221240479274737794080665

　351419597459856902143413


Es ist gleich dem Produkt zweier Primzahlen: 780
02287614711652531743087737
814467999489
227915816434308
　76426760322838157396665112
　792333734 17143396810270092

　798736308917

Tatsächlich ist dies wahrscheinlich die größte ganze Zahl, die Menschen jemals berücksichtigt haben (232 Dezimalstellen, 768 Binärstellen). Größere Faktorisierungen wurden nicht gemeldet, sodass der längste RSA-Schlüssel, der jemals geknackt wurde, 768 Bit beträgt.

8. Verschlüsselung und Entschlüsselung

Mit dem öffentlichen Schlüssel und dem Schlüssel können Sie ver- und entschlüsseln.

(1) Verschlüsselung erfordert öffentlichen Schlüssel (n, e)

Angenommen, Bob möchte verschlüsselte Informationen m an Alice senden, er muss Alices öffentlichen Schlüssel (n, e) verschlüsselt m. Hierbei ist zu beachten, dass m eine Ganzzahl sein muss (die Zeichenfolge kann einen ASCII-Wert oder Unicode-Wert annehmen) und m kleiner als n sein muss.

Die sogenannte „Verschlüsselung“ besteht darin, c nach folgender Formel zu berechnen:

　m^e ≡ c (mod n)

Alices öffentlicher Schlüssel ist (3233, 17) und Bobs m wird mit 65 angenommen, dann kann die folgende Gleichung berechnet werden:

　65¹⁷ ≡ 2790 (mod 3233)

C entspricht also 2790 und Bob sendet 2790 an Alice.

(2) Für die Entschlüsselung ist der private Schlüssel (n, d) erforderlich

Nachdem Alice den von Bob gesendeten 2790 erhalten hat, verwendet sie ihren eigenen privaten Schlüssel (3233, 2753 ) zur Entschlüsselung. Es kann bewiesen werden, dass die folgende Gleichung wahr sein muss:

　c^d ≡ m (mod n)

Mit anderen Worten, c mal d Der Rest, wenn ein Quadrat durch n geteilt wird, ist m. Nun ist c gleich 2790 und der private Schlüssel ist (3233, 2753). Dann berechnet Alice

　2790²⁷⁵³ ≡ 65 (mod 3233)

Daher weiß Alice, dass Bobs Originaltext vor der Verschlüsselung 65 ist.

An diesem Punkt ist der gesamte Prozess der „Verschlüsselung-Entschlüsselung“ abgeschlossen.

Wir können sehen, dass es keine Möglichkeit gibt, m aus c zu finden, wenn d nicht bekannt ist. Wie bereits erwähnt, müssen Sie, um d zu kennen, n zerlegen, was äußerst schwierig ist, sodass der RSA-Algorithmus die Kommunikationssicherheit gewährleistet.

Sie fragen sich vielleicht, dass der öffentliche Schlüssel (n,e) nur eine Ganzzahl m kleiner als n verschlüsseln kann. Was sollten Sie also tun, wenn Sie eine Ganzzahl größer als n verschlüsseln möchten? Es gibt zwei Lösungen: Die eine besteht darin, die lange Nachricht in mehrere kurze Nachrichten aufzuteilen und jedes Segment separat zu verschlüsseln. Die andere besteht darin, zunächst einen „symmetrischen Verschlüsselungsalgorithmus“ (z. B. DES) zu wählen und den Schlüssel dieses Algorithmus zu verwenden Verwenden Sie dann den öffentlichen RSA-Schlüssel, um den DES-Schlüssel zu verschlüsseln.

9. Nachweis der Entschlüsselung mit privatem Schlüssel

Abschließend werden wir beweisen, warum m durch Entschlüsselung mit privatem Schlüssel korrekt erhalten werden kann. Das heißt, die folgende Formel zu beweisen:

c^d ≡ m (mod n)

Denn gemäß den Verschlüsselungsregeln

　ｍ^e ≡ c (mod n)

Daher kann c in der folgenden Form geschrieben werden:

c = m^e - kn

Durch Einsetzen von c in die Entschlüsselungsregel wollen wir beweisen:

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

Es ist gleichbedeutend mit dem Beweisen

　m^ed ≡ m (mod n)

Seit

　ed ≡ 1 (mod φ(n))

also

ed = hφ( n)+1

Ersetzt durch:

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

Beweisen Sie als Nächstes die obige Formel in zwei Fällen.

(1) m und n sind relativ prim.

Nach dem Satz von Euler ist zu diesem Zeitpunkt

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

Get

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

Original Formel Lassen Sie sich beweisen.

(2) m und n sind nicht zueinander prim.

Da n zu diesem Zeitpunkt gleich dem Produkt der Primzahlen p und q ist, muss m gleich kp oder kq sein.

Nehmen Sie m = kp als Beispiel, wenn man bedenkt, dass k und q zu diesem Zeitpunkt gegenseitig prim sein müssen, gilt nach dem Satz von Euler die folgende Formel:

　(kp)^q-1 ≡ 1 (mod q)

erhält weiter

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

d. h. q)

Schreiben Sie es in die folgende Gleichung um

　 (kp)

ed

= tq + kp

Zu diesem Zeitpunkt muss t durch p teilbar sein, d. h. t=t'p

　(kp)

ed

= t'pq + kp

Weil m=kp, n=pq, also

　m^ed ≡ m (mod n)

Die ursprüngliche Formel ist bewiesen.

Python-Implementierung

Leistungsstarkes Python verfügt über eine dedizierte Implementierung Wenn wir jedoch RSA implementieren möchten, benötigen wir kein so ausgefeiltes Tool. Wir müssen lediglich eine RSA-Bibliothek eines Drittanbieters laden.

zeige dir den Code, KEIN 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)

Verwandte Empfehlungen:

Wird Ihnen dabei helfen, die Prinzipien des RSA-Algorithmus gründlich zu verstehen

RSA-Verschlüsselungsalgorithmus

25 Codezeilen zur Implementierung des vollständigen RSA-Algorithmus

Detaillierte Erläuterung des RSA-Algorithmus und der C-Sprachimplementierung

Das obige ist der detaillierte Inhalt vonPython implementiert den RSA-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!