Das Memo, das ich studiert habe. Es gab nicht viele Artikel über die Implementierung von RSA, die mit großen Primzahlen gut funktionieren.
Implementieren Sie eine 256-Bit-RSA-Verschlüsselung mit der minimalen Konfiguration.
Weitere Informationen finden Sie in wikipedia. Schreiben Sie nur den Flow.
Sie sind jetzt bereit. Verschlüsselung ist
Die Entschlüsselung ist mit $ m = c ^ d \ pmod n $ in Ordnung.
Es gibt keine so schwierige Berechnung, aber der Punkt ist
In RSA werden Potenzen mit Hunderten von Ziffern multipliziert, sodass eine exponentielle Multiplikation nicht gehorsam erfolgen kann.
** Schnelle Exponentialberechnung ** macht es schneller.
Da wir außerdem den Überschuss der Dunkelheit und nicht die Dunkelheit selbst finden möchten, können wir auch diesen Punkt optimieren.
Angenommen, Sie möchten den Rest von $ a $ berechnen, der um $ n $ auf die $ b $ -Power erhöht wird. Konvertieren Sie zuerst $ b $ in eine Binärzahl. Jede Ziffer der Binärzahl sei $ b_i $
Wie
Teilen Sie jedes durch $ 21 $ und nehmen Sie zu viel, wenn es während der Berechnung 21 überschreitet.
main.py
def modular_exp(a, b, n):
res = 1
while b != 0:
if b & 1 != 0:
res = (res * a) % n
a = (a * a) % n
b = b >> 1
return res
Anscheinend ist es ziemlich schwierig, Primzahlen direkt zu generieren. Praktisch scheint es einfach zu sein, ** Zufallszahlen zu generieren, bis eine Primzahl erreicht ist **.
Da die Anzahl der Bits angegeben ist, ist es in Ordnung, wenn 0,1 zufällig für diese Anzahl angeordnet sind.
main.py
def gen_rand(bit_length):
bits = [random.randint(0,1) for _ in range(bit_length - 2)]
ret = 1
for b in bits:
ret = ret * 2 + int(b)
return ret * 2 + 1
Die maximalen und minimalen Bits werden stattdessen auf 1 gesetzt. Dies liegt daran, dass das maximale Bit eine ungerade Zahl ist, so dass die Anzahl der Stellen nicht verringert wird. Der Grund, warum es seltsam ist, ist, dass ich jetzt Primzahlen will und gerade Zahlen keine Primzahlen sind.
Ich möchte feststellen, ob die riesige Zufallszahl $ p $ eine Primzahl ist. $ P $ ist so groß, dass es zu langsam ist, es in der richtigen Reihenfolge zu teilen. ** [Mirror-Rabin Prime Number Judgement Method](https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3% 83% A9% E3% 83% 93% E3% 83% B3% E7% B4% A0% E6% 95% B0% E5% 88% A4% E5% AE% 9A% E6% B3% 95) ** Scheint oft benutzt zu werden. Der Algorithmus ist auch auf Wikipedia, also implementieren Sie ihn so wie er ist. Einfach ausgedrückt, wir überprüfen die Anforderungen für Primzahlen viele Male und stellen fest, dass es sich bei allen Passzahlen wahrscheinlich um Primzahlen handelt. Wenn sie nicht einmal eine Passzahl bestehen, handelt es sich um synthetische Zahlen. ** Da dies ein probabilistischer Algorithmus zur Beurteilung von Primzahlen ist, kann er eine zusammengesetzte Zahl als Primzahl beurteilen. ** ** ** Es scheint jedoch, dass das falsch positive Ergebnis in einem Check ungefähr $ \ frac {1} {4} $ ist. Wenn Sie es also Dutzende Male tun, wird es im praktischen Gebrauch fast 0 sein, sodass es kein Problem zu geben scheint.
main.py
def mr_primary_test(n, k=100):
if n == 1:
return False
if n == 2:
return True
if n % 2 == 0:
return False
d = n - 1
s = 0
while d % 2 != 0:
d /= 2
s += 1
r = [random.randint(1, n - 1) for _ in range(k)]
for a in r:
if modular_exp(a, d, n) != 1:
pl = [(2 ** rr) * d for rr in range(s)]
flg = True
for p in pl:
if modular_exp(a, p, n) == 1:
flg = False
break
if flg:
return False
return True
Die Erzeugung von Primzahlen ist also so.
main.py
def gen_prime(bit):
while True:
ret = gen_rand(bit)
if mr_primary_test(ret):
break
return ret
Es spielt keine Rolle, ob es sich um eine Primzahl für $ (p-1) (q-1) $ handelt, daher ist es schnell möglich, daraus eine Primzahl zu machen.
p = gen_prime(128)
q = gen_prime(128)
e = gen_prime(128)
Ich denke, damit gibt es kein Problem. wikipedia gab an, dass $ 65537 $ häufig verwendet wird. Es scheint, dass eine feste Nummer in Ordnung ist.
Sie können die erweiterte euklidische Methode der gegenseitigen Teilung verwenden.
Ursprünglich für natürliche Zahlen $ a, b $
Es ist ein Algorithmus, um $ x, y $ wie z. (gcd ist die maximale Verpflichtung)
Verwenden Sie dies für $ e, (p-1) (q-1) $. Da die maximale Verpflichtung 1 aus der Definition von $ e $ beträgt,
Teilen Sie beide Seiten durch $ (p-1) (q-1) $
main.py
def xgcd(b, n):
x0, x1, y0, y1 = 1, 0, 0, 1
while n != 0:
q, b, n = b // n, n, b % n
x0, x1 = x1, x0 - q * x1
y0, y1 = y1, y0 - q * y1
return b, x0, y0
def gen_d(e, l):
_, x, _ = xgcd(e, l)
return x % l
Der Rest funktioniert, wenn Sie einen einfachen Text vorbereiten.
main.py
bit_length = 128
p = gen_prime(bit_length)
q = gen_prime(bit_length)
e = gen_prime(bit_length)
d = gen_d(e, (p - 1) * (q - 1))
n = p * q
m = 123456789
c = modular_exp(m, e, n) #Geheimtext
m_ = modular_exp(c, d, n) # 123456789
Es funktionierte sogar mit 1024bit. (Es dauerte ungefähr 20 Sekunden) Tatsächlich ist es gefährlich, denselben Klartext viele Male zu verschlüsseln. Es scheint also, dass am Ende eine Zufallszahl hinzugefügt wird (zum Zeitpunkt der Entschlüsselung gelöscht), und wenn m zu klein ist, wird sie aufgefüllt.