Schon gewusst...

dass Sie mit CrypTool-Online Barcodes generieren können?

 

RSA

Dieses Modul demonstriert schrittweise die Ver- und Entschlüsselung mit dem RSA-Verfahren. Der Sender verwendet dabei zum Verschlüsseln den öffentlichen Schlüssel des Empfängers; der Empfänger verwendet zum Entschlüsseln seinen zugehörigen privaten Schlüssel.

Primfaktoren

Die Sicherheit von RSA basiert darauf, dass es zwar einfach ist, das Produkt n zweier großer Primzahlen p und q zu berechnen. Es ist jedoch sehr schwer, nur aus dem Produkt n die beiden Primzahlen zu bestimmen, die das Produkt ergeben. Dieses Zerlegen nennt man auch das Faktorisieren von n.

Als Ausgangspunkt für RSA wählt man zwei Primzahlen p und q.

p ist keine Primzahl!
q ist keine Primzahl!
p und q sind nicht verschieden!

Damit der Algorithmus funktioniert, müssen die beiden Primzahlen verschieden sein.

Zur Demonstration beginnen wir mit kleinen Primzahlen. Um die Faktorisierung schwierig zu gestalten, müssen die Primzahlen möglichst groß gewählt werden. Aktuell werden für eine sichere Kommunikation Werte von n mit mehreren tausend Binärstellen verwendet.

( Bit)

Öffentlicher Schlüssel

Das Produkt n wird im RSA-Verfahren auch Modul genannt. Der öffentliche Schlüssel besteht neben dem Modul n noch aus einem Exponenten e.

e und n sind nicht teilerfremd.

Dieses e kann sogar vorab gewählt werden und für alle Teilnehmer gleich sein.

Geheimer Schlüssel

RSA benutzt für die Berechnung des geheimen Schlüssels die Eulersche φ-Funktion von n. Diese ist definiert als

Hier wird ausgenutzt, dass p und q verschieden sind. Andernfalls würde sich die φ-Funktion anders berechnen.

Wichtig ist für RSA, dass der Wert der φ-Funktion teilerfremd zu e ist (der größte gemeinsame Teiler also 1 ist).

Um den Wert von φ(n) zu bestimmen, reicht es nicht aus n zu kennen. Nur mit der Kenntnis von p und q kann man φ(n) effizient bestimmen.

Der geheime Schlüssel besteht ebenfalls aus n und einem d mit der Eigenschaft, dass e × d ein Vielfaches von φ(n) plus eins ist.

In Formeln ausgedrückt, muss gelten:

e × d = 1 (mod φ(n))

Dabei ist mit dem mod-Ausdruck die Gleichheit bezüglich einer Restklasse gemeint. Es ist genau dann x = y (mod z), wenn es ein ganzzahliges a gibt mit xy = z × a.

Für die gewählten Werte von p, q und e ergibt sich d als:

Dieses d kann immer bestimmt werden, wenn e mit der oben beschriebenen Einschränkung gewählt wurde – bspw. mit dem erweiterten Euklidischen Algorithmus.

Ver- und Entschlüsseln

Grundsätzlich werden bei diesem Verfahren keine Texte, sondern nur Zahlen ver- und entschlüsselt, die zwischen 0 und n liegen.

Um eine Nachricht m mit dem öffentlichen Schlüssel (n, e) zu verschlüsseln, wird

m' := me (mod n)

berechnet.

Das Entschlüsseln mit dem privaten Schlüssel (n, d) erfolgt analog mit

m'' := m'd (mod n).

Damit ist

m'' = me × d (mod n).

RSA nutzt nun die Eigenschaft aus, dass

xa = xb (mod n)

wenn

a = b (mod φ(n))

e und d wurden passend gewählt damit

m'' = m.

Die Reihenfolge spielt keine Rolle. Man könnte auch erst eine Nachricht mit dem privaten Schlüssel potenzieren, und das Ergebnis dann mit dem öffentlichen Schlüssel potenzieren – das verwendet man bei RSA-Signaturen.

Nachrichten

In den folgenden zwei Textboxen können Sie sehen, wie das Ver- und Entschlüsseln für konkrete Eingaben (Zahlen)funktioniert.

Die Klartextzahl ist zu groß. Der maximale Wert ist . Bitte wählen Sie größere Primzahlen.
Die Geheimtextzahl ist zu groß. Der maximale Wert ist . Bitte wählen Sie größere Primzahlen.

Verwendete Bibliothek

Diese Seite verwendet für die Rechnung mit großen Zahlen die Bibliothek BigInteger.js.

Dadurch kann man auch in JavaScript mit beliebig großen Zahlen rechnen, also auch solchen, die real bei RSA-Anwendungen verwendet werden.

CTOAUTHORS: Timm Knape (Dank an Bernhard Esslinger für das Review)

Die Sicherheit von RSA beruht darauf, dass es nach heutigem Stand nicht möglich ist, das Produkt von zwei großen Primzahlen in einer sinnvollen Zeit zu faktorisieren. Dies ist jedoch nur eine begründete Annahme, aber keine gesicherte Erkenntnis: Es ist bisher lediglich noch kein schnelles Verfahren bekannt. Wir wissen nicht, ob die Faktorisierung mindestens so schwer ist wie andere schwere Probleme, ob sie also NP-vollständig ist.

Angriff mit Quantencomputern

Prinzip-bedingt kann ein Quantencomputer mit hinreichend vielen verschränkten Quanten-Bits (Qbits) eine Faktorisierung schnell durchführen, da er parallel jeden möglichen Faktor gleichzeitig ausprobieren kann. Bisher gibt es jedoch keinen bekannten Quantencomputer, der eine auch nur annähernd große Rechenkapazität hat. Damit bleiben effektive Quantencomputer momentan ein Mythos, der wohl auch in den nächsten Jahren noch nicht serienreif werden wird. Es kann jedoch sein, dass die Faktorisierung in 20 Jahren gelöst ist und RSA damit seine Sicherheit verliert.

Größe der Primfaktoren

Je größer die verwendeten Primfaktoren sind, desto länger benötigen aktuelle Algorithmen und desto mehr Qbits werden in zukünftigen Quantencomputern benötigt. Momentan sollte das Produkt aus mindestens 4096 Binärstellen bestehen, um sicher zu sein.

Wiederverwendung von Primzahlen

Primzahlen dürfen nicht wiederverwendet werden! Wenn man zwei Produkte aus je zwei Primzahlen hat und weiß, dass eine der verwendeten Primzahlen die gleiche ist, dann kann diese sog. Shared Prime mit dem Euklidischen Algorithmus schnell ermittelt werden. Und durch Divison der Produkte durch diese "shared" Primzahl erhält man jeweis die andere Primzahl.

Frühe Implementierungen von RSA haben diesen Fehler begangen, um die Zeit für das aufwändige Finden einer Primzahl zu reduzieren. Auch auf Ressourcen-beschränkten Geräten kam es in neuerer Zeit aufgrund von mangelndem Zufall dazu. Aktuelle Implementierungen sollten diesen Fehler nicht mehr begehen.

Wahl der Primzahlen

Grundsätzlich müssen die Primzahlen zufällig genug ausgewählt werden. Wenn für eine n-bit Zahl nur n/2-bit Zahlen herangezogen werden, reduziert das den Suchraum für Angreifer erheblich. Es darf aber auch keine der beiden Primzahlen zu klein sein, um bei einem Brute-Force-Angriff mit allen Primzahlen nicht zu einem frühen Treffer zu kommen. Eine geschickte Wahl zwischen beiden Extremen ist notwendig und nicht trivial. Die beiden Primzahlen sollten also nicht zu nah beieinander liegen, aber auch nicht zu weit ausenander.

Weitere RSA-Implementierungen im Browser

https://www.cs.drexel.edu/~jpopyack/Courses/CSP/Fa17/notes/10.1_Cryptography/RSAWorksheetv4e.html

Hier sieht der Nutzer, wie (N, e, d) gewählt werden kann (so wie bei uns auch), aber es ersetzt zusätzlich Textnachrichten in Zahlen.

https://www.cs.drexel.edu/~jpopyack/Courses/CSP/Fa17/notes/10.1_Cryptography/RSA_Express_EncryptDecrypt_v2.html

Hier kann man die Nachricht als Text eingeben (es wird angenommen, dass der Benutzer N, e und d schon gewählt hat).

Beide Implementierungen sind aus 2012, nur in Englisch, benutzen keine Langzahl-Arithmetik-Bibliothek (sondern pures Java Script), und sehen didaktisch sehr gut aus.

Quellen

 

 

Go To Top