Benutzer-Werkzeuge

Webseiten-Werkzeuge


info10:aufgaben:rsa

Das RSA-Kryptosystem

Das RSA-Verfahren ist eines der bekanntesten Public-Key-Kryptosysteme zur Verschlüsselung von Nachrichten. In diesem System gibt es für jeden Teilnehmer einen öffentlichen Schlüssel (N, e) zur Verschüsselung und einen privaten Schlüssel (N, d) zur Entschlüsselung. N, e und d sind jeweils große ganze Zahlen. Will eine Person A einer zweiten Person B eine Botschaft senden, die effektiv nur B verstehen kann, so verschlüsselt A diese Botschaft mit B's öffentlichem Schlüssel. B kann dann mit seinem privaten Schlüssel die Nachricht entziffern.

Die Schlüssel können wie folgt berechnet werden:

  1. Bestimme zufällig zwei „große“ Primzahlen p und q mit k Dezimalziffern. Etwa 100 Ziffern (entspricht etwa 333 Binärziffern) sind nötig, um eine gute Sicherheit zu erreichen. In der Praxis verwendet man sogenannte Pseudo-Primzahlen, die wesentlich leichter zu bestimmen sind.
  2. Berechne $n = p * q$, den sogenannten Modulus.
  3. Berechne $ф(n) = (p - 1) * (q - 1)$.
  4. Wähle e zufällig so, daß $1 < e < n$ und daß e und ф(n) relativ prim sind, d.h. $ggT(e,ф(n)) = 1$.
  5. Berechne d so, daß $e * d = 1 (\mod ф(n))$

Implementieren Sie Klassen RSAKey und RSAKeyPair zur Erzeugung und Verwaltung der benötigten Schlüssel. Benutzen Sie dazu die Klasse math. BigInteger, die alle nötige Funktionalität besitzt. (Verwenden Sie z.B. für Schritt (a) einen passenden Konstruktor und für (d) die Methode modInverse).

Die Verschlüsselung eines Strings m erfolgt dann so:

  1. Wandle m in eine numerische Folge x um.
  2. Zerteile x in Blöcke $x_i$ der Länge l Bits, so daß $2^l < n$.
  3. Berechne für alle $x_i$ die Verschlüsselung $c_i$ gemäß $c_i=x_i^d (\mod n)$

Zur Entschlüsselung geht man umgekehrt vor:

  1. Entschlüsselung der Blöcke gemäß $x_i = c_i^d (\mod n)$
  2. Zusammensetzen der Blöcke $x_i$ und Konversion in einen String.

Implementieren Sie eine Klasse RSA, die folgende Klassen-Methoden zum Ver- und Entschlüsseln von Nachrichten anbietet:
public static BigInteger [] encode (RAKey publicKey, String message) ;
public static String decode (RSAKey privateKey, BigInteger [] cipherText);

Verwenden Sie zur Zerlegung eines Strings in eine numerische Folge die Methode getBytes der Klasse String.

Implementieren Sie eine Klasse RATest, die die Verwendung Ihrer Implementierung demonstriert.

info10/aufgaben/rsa.txt · Zuletzt geändert: 2023/01/14 19:29 von Ulrich Schneider