Zum Hauptinhalt springen

⭐ RSA Algorithmus

Der RSA Algorithmus ist der aktuell am weitesten verbreitete asymmetrische Verschlüsselungsalgorithmus und wird etwa für die SSL/TLS Verschlüsselung beim HTTPS-Protokoll verwendet. Der Algorithmus wurde 1977 von Ronald Rivest, Adi Shamir und Leonard Adlerman unter dem Namen RSA entwickelt und publiziert1.

Funktionsweise

Die Funktionsweise basiert darauf, dass es leicht ist, c=memodnc = m^{e}\: mod\: n zu berechnen, aber praktisch unmöglich, ohne den privaten Schlüssel d die Umkehr­funktion zu berechnen.

n

öffentliche Zahl
e

öffentlicher Schlüssel des Empfängers

d

privater Schlüssel des Empfängers
m<nm<n

Klartext
c

Geheimtext

Verschlüsselung

Zur Verschlüsselung berechnet Bob den Geheimtext c:

c=memodnc=m^{e} \: mod \: n

Wobei mod der Ganzzahlige Rest bei der Division mit n darstellt. Beispiel: 13mod4=113 \: mod \: 4=1, da 134=3Rest1\frac{13}{4} = 3\: Rest\: 1.

Die Zahl nn ist das Produkt von zwei ver­schiedenen Primzahlen pp und qq, diese sind geheim. Wie können pp und qq geheim sein, wenn doch n=pqn = p\cdot q öffentlich ist? Dies beruht nur darauf, dass die Primfaktor­zerlegung von nn zu rechen­aufwendig ist, da nn sehr gross ist (z.B. 1024 Bit lang).

Für die Zahl e muss gelten

ggt(e,ϕ(n))=1ggt(e, \phi(n)) = 1

Hierbei ist

ϕ(n)=(p1)(q1)\phi(n) = (p-1)(q-1)

die Anzahl der zu n teiler­fremden Zahlen, die kleiner als n sind.

Entschlüsselung

Der Empfänger hat als privaten Schlüssel eine Zahl dd mit

demodϕ(n)=1d\cdot e\: mod\: \phi(n) = 1

daher

de=kϕ(n)+1d\cdot e = k\cdot \phi(n) + 1

für irgend ein kNok \in \N_{o}.

Ist n=pqn = pq, so gilt nach einem Satz von Euler für alle Zahlen mm mit m<nm < n und für alle natürlichen Zahlen kk:

mkϕ(n)+1modn=mmk\cdot\phi(n)+1\: mod\: n = m

Zur Ent­schlüsselung berechnet der Empfänger also

cdmodn=mdemodn=mkϕ(n)+1modn=m\begin{aligned} c^{d}\: mod\: n &= md\cdot e\: mod\: n \\ &= mk\cdot \phi(n) + 1\: mod\: n \\ &= m \end{aligned}

und erhält damit den Klartext mm.

⭐️ RSA Schlüssellänge

Die RSA Schlüssel haben standardmässig 1024 oder 2048 bits, wobei Schlüssel mit 1024 bits mittelfristig als knackbar erachtet werden, so dass die Industrie heute oft mindestens 2048 bits voraussetzt.

RSA in Python

Schlüsselerzeugung:

Als erstes wählt man zwei Primzahlen pp und qq und berechnet daraus

n=pqn = p \cdot q

und

φ(n)=φ(p)φ(q)=(p1)(q1)\varphi(n) = \varphi(p) \cdot \varphi(q) = (p-1) \cdot (q-1)

p = 11
q = 13
n = p * q
phi = (p-1) * (q-1)
print(n, phi)

Nun muss man ein Zahlenpaar ee und dd finden, die bezüglich φ(n)\varphi(n) multiplikativ invers zueiunander sind. Das bedeutet, dass gilt:

demodϕ(n)=1d \cdot e \mod \phi(n) = 1

Das Zahlenpaar findet man mit dem sogenannten erweiterten euklidschen Algorithmus:

p = 11
q = 13
n = p * q
phi = (p-1) * (q-1)
### PRE
def euclidExtended(e, N):
x1, x2, x3 = 1, 0, N
y1, y2, y3 = 0, 1, e
while True:
if y3 == 0:
print('Existiert nicht!')
return None
if y3 == 1:
return y2 % N
q = x3//y3
t1, t2, t3 = x1-q*y1, x2-q*y2, x3-q*y3
x1, x2, x3 = y1, y2, y3
y1, y2, y3 = t1, t2, t3

Erster Versuch: 3 hat kein multiplikatives inverses bezüglich φ(n)\varphi(n)

p = 11
q = 13
n = p * q
phi = (p-1) * (q-1)
def euclidExtended(e, N):
x1, x2, x3 = 1, 0, N
y1, y2, y3 = 0, 1, e
while True:
if y3 == 0:
print('Existiert nicht!')
return None
if y3 == 1:
return y2 % N
q = x3//y3
t1, t2, t3 = x1-q*y1, x2-q*y2, x3-q*y3
x1, x2, x3 = y1, y2, y3
y1, y2, y3 = t1, t2, t3
### PRE
e = 3
d = euclidExtended(e, phi)

Zweiter Versuch: 5 hat auch kein multiplikatives inverses bezüglich φ(n)\varphi(n)

p = 11
q = 13
n = p * q
phi = (p-1) * (q-1)
def euclidExtended(e, N):
x1, x2, x3 = 1, 0, N
y1, y2, y3 = 0, 1, e
while True:
if y3 == 0:
print('Existiert nicht!')
return None
if y3 == 1:
return y2 % N
q = x3//y3
t1, t2, t3 = x1-q*y1, x2-q*y2, x3-q*y3
x1, x2, x3 = y1, y2, y3
y1, y2, y3 = t1, t2, t3
### PRE
e = 5
d = euclidExtended(e, phi)

Dritter Versuch: 7 hat ein multiplikatives inverses bezüglich φ(n)\varphi(n).

(Nebenbei: Der Grund, warum es mit 3 und 5 nicht geklappt hat: Die Zahlen müssen zu φ(n)\varphi(n) teilerfremd sein, aber 120 ist durch 3 und 5 teilbar)

p = 11
q = 13
n = p * q
phi = (p-1) * (q-1)
def euclidExtended(e, N):
x1, x2, x3 = 1, 0, N
y1, y2, y3 = 0, 1, e
while True:
if y3 == 0:
print('Existiert nicht!')
return None
if y3 == 1:
return y2 % N
q = x3//y3
t1, t2, t3 = x1-q*y1, x2-q*y2, x3-q*y3
x1, x2, x3 = y1, y2, y3
y1, y2, y3 = t1, t2, t3
### PRE
e = 7
d = euclidExtended(e, phi)
print(d)# => 103

Kurze Überprüfung: Ist das Produkt von ee und dd modulo φ(n)\varphi(n) tatsächlich 1?

phi = 120
d = 103
e = 7
### PRE
print(e * d) # => 721
print((e * d) % phi) # => 1

Verschlüsselung

Der öffentliche Schlüssel besteht nun aus den Zahlen ee und nn. Diesen darf jeder wissen.

Der private Schlüssel besteht aus den Zahlen dd und nn. Dieser muss geheimgehalten werden.

Mit dem RSA-Verfahren lassen sich nun Zahlen von 0 bis (n-1) verschlüsseln.

Um eine Nachricht mm zu verschlüsseln, muss man folgendes berechnen:

c=memodnc = m^e \mod n

Resultat ist eine verschlüsselte Nachricht cc

e = 7
n = 143
### PRE
m = 141
c = m**e % n
print(c) # => 15

Entschlüsseln

Um die verschlüsselte Nachricht cc zu entschlüsseln, muss man folgendes berechnen:

m=cemodnm = c^e \mod n

d = 103
n = 143
c = 15
### PRE
print(c**d % n) # => 141

Praktische Anwendung: Text mit RSA verschlüsseln:

Um einen Text mit RSA zu verschlüsseln hat man nun zahlreiche Möglichkeiten. Hier ist nur ein Beispiel:

Zunächst wandeln wir jeden Buchstaben der Nachricht 'HALLO' in eine Zahl um:

alphabet = 'abcdefghijklmnopqrstuvwxyz'
for buchstabe in 'hallo':
print(alphabet.find(buchstabe), end=',')

Mit der Python-Funktion bin machen wir daraus Binärzahlen in Form eines strings, allerdings brauchen wir die zwei ersten Zeichen 0b, die Python vor jede Binärzahl schreibt, nicht und zwacken diese ab. Ausserdem füllen wir die Binärzahl mit zfill (für englisch "Zero Fill") immer mit Nullen auf 5 Stellen auf. Warum 5 Stellen? Weil man für 26 Buchstaben mindestens 5 Bit (= 32 Möglichkeiten) braucht:

print(bin(7)) # das 0b brauchen wir nicht
print(bin(7)[2:].zfill(5)) # abzwacken und mit 0 füllen

for number in [7, 0, 11, 11, 14]:
print(bin(number)[2:].zfill(5), end=' ')

Aus diesen 5-Stelligen Binärzahlen machen wir 7-Stellige Binärzahlen, indem wir die Bits einfach der Reihe nach lesen. Falls es nicht aufgeht, hängen wir einfach noch Nullen dran.

Warum 7 Bit? Weil für dieses Beispiel n=pq=1113=143n = p \cdot q = 11 \cdot 13 = 143 ist, worin 127 (grösste Zahl mit 7 bit) gerade Platz hat. Das Resultat sind 4 Zahlen:

for number in ['0011100', '0000101', '1010110', '1110000']:
print(int(number, 2), end=', ')

Diese vier Zahlen werden nun einzeln RSA-Verschlüsselt:

e = 7
n = 143
for number in [28, 5, 86, 112]:
print(number**e % n, end=', ')

Am anderen Ende können die Zahlen wieder einzeln entschlüsselt werden:

d = 103
n = 143
for number in [63, 47, 70, 18]:
print(number**d % n, end=', ')

Die Zahlen werden wieder binär umgewandelt, diesmal auf 7 Stellen mit Nullen gefüllt:

for number in [28, 5, 86, 112]:
print(bin(number)[2:].zfill(7), end=' ')

Aufgeteilt in 5-Stellige Binärzahlen erhalten wir die ursprünglichen Zahlen und daraus die ursprünglichen Buchstaben:

for number in ['00111', '00000', '01011', '01011', '01110']:
print(int(number, 2), end=',')
alphabet = 'abcdefghijklmnopqrstuvwxyz'
for number in [7, 0, 11, 11, 14]:
print(alphabet[number], end=' ')

Sicherheit

Warum ist dies sicher? Dieses Beispiel wäre natürlich nicht sicher, weil die Primzahlen viel zu klein sind, aber bei grossen Primzahlen pp und qq würde es viel zu lange dauern, diese Teiler nur aus nn zu bestimmen.

Um dies zu verdeutlichen hier eine naive Funktion factors, die die Teiler einer Zahl zurückgibt, falls sie exisiteren. In der Zelle darunter wird diese Funktion benutzt, um Primzahlen zu finden indem einfach eine Zahl nach der anderen durchprobiert wird. Wird eine Primzahl gefunden, verdoppeln wir unseren Kandidaten und suchen von dort aus weiter.

Am Anfang geht das ganze recht schnell, aber schon bald dauert es ewig lange, um die nächste Primzahl zu finden. Einerseits, weil es immer weniger Primzahlen gibt, aber andererseits wird die factors-Funktion immer langsamer.

from browser import timer
i = 1

def factors(n):
for i in range(2, n):
if n % i == 0:
return i, n // i

def check_next():
global i
if factors(i) is None:
print(i, end=', ')
i = i * 2
i = i + 1

LIMIT = 200

for q in range(LIMIT):
print(q)
timer.set_timeout(check_next, 0.1)

Footnotes