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