26.4 Implementierung von RSA
 
  Ein Blick in die API zeigt, dass in der Klasse BigInteger eine Methode modPow(...) implementiert ist, die die Programmierung von RSA erheblich erleichtert. Sie führt die mathematische Operation

c = me mod n mit m als Originalkode und c Geheimkode

aus.
 
  Dabei entspricht dem exponent in der Parameterliste das e in der Formel, und dem m in der Parameterliste entspricht das n in der Formel. Die Basis m in ist dann das BigInteger-Objekt, für das die Methode aufgerufen wird. Der Rückgabewert, wieder ein BigInteger-Objekt, entspricht dann dem c.
 
Für die am Anfang von Kap.  26.1 RSA verwendeten Werte (n= 2773, e = 17 und m 920), heißt unser Programm
Download:
RSAEnCrypt2.java		 
import info1.*;

import java.math.*;

public class RSAEnCrypt2{

  public static void main(String[] args){

     String n = "2773";

     String e = "17";

     String m = "920";

     BigInteger nBig = new BigInteger(n);

     BigInteger eBig = new BigInteger(e);

     BigInteger mBig = new BigInteger(m);

     BigInteger cBig = mBig.modPow(eBig,nBig);

     String c = cBig.toString();

     System.out.println("Geheimtext: "+c);

  }

}


Ausgabe:

Geheimtext: 948
Download:
RSADeCrypt2.java		 
import info1.*;

import java.math.*;

public class RSADeCrypt2{

  public static void main(String[] args){

     String n = "2773";

     String d = "157";

     String c = "948";

     BigInteger nBig = new BigInteger(n);

     BigInteger dBig = new BigInteger(d);

     BigInteger cBig = new BigInteger(c);

     BigInteger mBig = cBig.modPow(dBig,nBig);

     String m = mBig.toString();

     System.out.println("Geheimtext: "+m);

  }

}
Ausgabe:

Geheimtext: 920
  Wir haben damit alle Voraussetzungen um unsere RSA-Methode

   rsa(String originalText, int n, int e): String

für die Klasse EnCrypt und

   rsa(String geheimText, int n, int d): String

für die Klasse DeCrypt zu implementieren.
 
Download:
EnCrypt.java		 
public static String rsa(String originalText, int n, int e){

  //Das Ensemle (n,e) stellt den public key des RSA-

  //Verfahrens dar.

  String geheimText = "";

  java.math.BigInteger nBig = new java.math.BigInteger(""+n);

  java.math.BigInteger eBig = new java.math.BigInteger(""+e);

  java.math.BigInteger mBig;

  int c;

   

  for (int i = 0; i < originalText.length(); i++){

    mBig = new java.math.BigInteger(""+

                    (int)originalText.charAt(i));

    c = mBig.modPow(eBig,nBig).intValue();

    geheimText += (char)c;

  }

  return geheimText;

}
Bemerkungen Da die Klasse EnCrypt nur in der rsa-Methode das Paket java.math verwendet, wurde dieses Paket nicht durch einen import zur Verfügung gestellt, sondern der Paketname wurde dem Klassenname vorgestellt. Der Konstruktor, den wir für die Erzeugung der BigInteger-Objekte verwenden, verlangt einen String als Übergabeparamter. Deshalb wurde die int-Variablen n und e mit ""+n und ""+e also mit Hilfe einer Konkatenation mit einem leeren String zu String-Objekten. Entsprechend erhalten wir für die rsa(...)-Methode in DeCrypt.
 
Download:
DeCrypt.java		 
public static String rsa(String geheimText, int n, int d){

  //Das Ensemle (n,d) stellt den private key des RSA-

  //Verfahrens dar

  String originalText = "";

  java.math.BigInteger nBig = new java.math.BigInteger(""+n);

  java.math.BigInteger dBig = new java.math.BigInteger(""+d);

  java.math.BigInteger cBig;

  int m;

  for (int i = 0; i < geheimText.length(); i++){

    cBig = new java.math.BigInteger(""+

                    (int)geheimText.charAt(i));

    m = cBig.modPow(dBig,nBig).intValue();

    originalText += (char)m;

  }

  return originalText;

}
TestProgramm
Download:
rsaTest.java		 
public class rsaTest {



  public static void main (String[] args) {

     int n = 2773;

     int e = 17;

     int d = 157;

     String originalText = "Michael Pohlig";

     String geheimText = EnCrypt.rsa(originalText,n,e);

     System.out.println(geheimText);

     String entschluesselt = DeCrypt.rsa(geheimText,n,d);

     System.out.println(entschluesselt);

     

  }

}
Ausgabe:

???┴??®???┴®??

Michael Pohlig
Bemerkungen Geben wir in diesem Programm für n = 2773, e = 17 und für den Originaltext "920" ein, so erhalten wir für den Geheimtext natürlich nicht mehr wie oben "948", den jetzt werden nicht mehr der Wert 920 verschlüsselt, sondern die Bytekodes, die zu den Zeichen 9, 2 und 0 gehören. 
 
Das ist noch nicht alles Nun hat unsere RSA-Verschlüsselung einen gravierenden Nachteil. Da wir immer byte für byte, also Buchstabe für Buchstabe verschlüsselt haben, haben wir unsere Verschlüsselung zu einer monoalphabetischen Substitution degradiert. Mit einer Häufigkeitsanalyse ließe sich der Geheimtext leicht entschlüsseln und alle Mühe war umsonst.  Wir sollten also eine Blocklänge größer als 8 bit wählen. Damit stellt sich aber die Frage nach dem Zusammenhang zwischen der Blocklänge und der Zahl n. Dass dies Frage nicht nebensächlich ist, lässt sich so einsehen: Ist etwa ein Block 8 bit lang, so ist die Anzahl der möglichen Zeichen in diesem Block, also das Alphabet des Originaltextes, durch 28 = 256 begrenzt. Das Alphabet des Geheimtextes muss also mindestens 256 Zeichen enthalten. Wegen c = me mod n muss n mindestens 256 sein, den eine Operation x mod 256 kann genau 256 verschiedene Zeichen liefern. Wählen wir nämlich n kleiner, so gibt es Zeichen m1 ≠ m2 aus dem Originalalphabet, die gleich verschlüsselt werden, also c1=c2. Eine Entschlüsselung wäre somit nicht mehr eindeutig.

In unserem letzten Beispiel hatten wir n = 2773 setzen, so können wir wegen "Anzahl der bit-Blöcke" ≤ log22773 = 11,44 höchstens 11-bit-lange Blöcke verschlüsseln. In der Praxis werden 1024-bit-Blöcke verschlüsselt.
zu 26.5 Übungen und Vertiefung: RSA
zur Startseite www.pohlig.de  (C) MPohlig 2006