Primzahlen und Kryptographie - Geheime Nachrichten
RSA-Algorithmus
RSA ist ein asymmetrisches Kryptosystem zur Verschlüsselung geheimer Daten oder zur digitalen Signatur. RSA ist ein zahlentheoretisches Codierungsverfahren, das auf dem kleinen Fermatschen Satz gründet. RSA beruht auf der Möglichkeit, relativ leicht grosse Primzahlen zu erzeugen, und auf der praktischen Unmöglichkeit, große zusammengesetzte Zahlen in Primfaktoren zu zerlegen. RSA wurde 1978 von R.L.RIVEST, A.SHAMIR und L.ADLEMAN vorgeschlagen.
Das Verfahren lässt sich so beschreiben:
1. Nachricht transformieren: Die Nachricht wird in eine Ziffernfolge verwandelt, zum Beispiel mit A=11, B=12, .... Die Art der Transformation ist für die Sicherheit des Verfahrens irrelevant. Wir nehmen diese Tabelle:
| ij | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | ||||||||||
| 1 | SP | A | B | C | D | E | F | G | H | I |
| 2 | J | K | L | M | N | O | P | Q | R | S |
| 3 | T | U | V | W | X | Y | Z | a | b | c |
| 4 | d | e | f | g | h | i | j | k | l | m |
| 5 | n | o | p | q | r | s | t | u | v | w |
| 6 | x | y | z | . | , | : | ; | ' | " | |
| 7 | ! | @ | # | $ | % | ^ | & | * | - | + |
| 8 | ( | ) | [ | ] | { | } | ? | / | < | > |
| 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
2. RSA-Schlüssel bilden: Wir nehmen zwei grosse Primzahlen p und q und bilden das Produkt N = p * q. Dann wählen wir eine zu φ(N)=(p-1)*(q-1) teilerfremde natürliche Zahl c > 1 und bestimmen ein natürliches d mit der Eigenschaft, dass c * d ≡ 1 (mod φ(N)). Nach Vorraussetzung ist die Kongruenz eindeutig mod φ(N) lösbar. Jetzt haben wir einen
- öffentlichen Schlüssel: (c, N) mit dem man Nachrichten chiffriert, und einen
- geheimen Schlüssel: (d, N) mit dem man die chiffrierte Nachrichten dechriffiert.
3. RSA-Chiffrieren: Alice möchte Bob eine Nachricht x senden. Er nimmt den öffentlichen Schlüssel (c, N) von Bob und sendet:
y ≡ xc mod N
4. RSA-Dechiffrieren: Bob erhält von Alice die verschlüsselte Nachricht y. Er nimmt seinen geheimen Schlüssel (d, N) und bildet:
x ≡ yd mod N
Jeder, der d kennt, kann die Nachricht lesen. Dafür muss man aber φ(N)=(p-1)*(q-1) kennen, d.h. die Primzahlen p und q kennen. Das RSA-Verfahren gilt in sofern als sicher, weil eine Primfaktorzerlegung von Zahlen mit hinreichend grossen Primfaktoren nach dem aktuellen Stand zahlentheoretischer Forschung und der aktuellen Computer Technologie i.a. eine Programmlaufzeit von Millionenen von Jahren haben kann.