# RSA - Eigener Quelltext



## Iome (11. Feb 2006)

Bei uns an der Schule sollen wir als Schüler fast alles neu erfinden, was es schon in Java gibt. Es soll dazu dienen, dass wir Java lernen. So sollen wir auch das Kryptologie-Verfahren von RSA selbst schreiben.

Vorgegeben wurde uns: http://de.wikipedia.org/wiki/RSA-Kryptosystem

ich hab mich daran mal versucht, hab aber das Problem, dass sich mein Programm beim dekodieren manchmal aufhängt.


```
import java.math.*;
import java.util.*;

public class rsa {

  static int prim=0;

  public static void main(String[] args) {

    //Schritt 1: Eine Zahl eingeben, die codiert werden soll:
    BigInteger code = new BigInteger("9999");

    //Schritt 2: Das Programm ermittelt zwei Zufallszahlen:
    int p=0;
    int q=0;
    while(q==0){  //Solange ausführen, bis beide Vaiablen mit einer Zahl belegt sind
      Primzahlen(1000); //1000=Primzahl darf nicht größer als 1000 sein
      if(!(prim==0) && !(prim==p)){
        if(p==0){
          p=prim;
        }else{
          q=prim;
        }
      }
    }

    //Schritt 3: Das Primzahlprodukt (N) bilden :
    int N=p*q;

    //Schritt 4: Wert der Eulerfunktion berechnen:
    int n=(p-1)*(q-1);

    //Schritt 5: Den öffentlichen Exponenten ermitteln (nötig zum codieren):
    int e=(p*q)-n;

    //Schritt 6: Den privaten Exponenten ermitteln (nötig zum decodieren ):
    int d=0;
    for(;true;d++){
      if(((e*d)%n==1)){
        break;
      }
    }

    System.out.println("Oeffentliche Keys:");
    System.out.println("N="+N);
    System.out.println("e="+e+"\n");
    System.out.println("Private Keys:");
    System.out.println("N="+N);
    System.out.println("d="+d+"\n");

    System.out.println("Die zu kodierende Zahl: "+code);
    System.out.println("kodiert: "+kryp(code,""+N,e));
    System.out.println("dekodiert: "+dekryp(kryp(code,""+N,e),""+N,d));

  }
  //Schritt 2... Primzahlengeneration
  public static void Primzahlen(int bereich){
    Random rand = new Random();
    for(int i=10;i<=bereich; i++){
      int tmp=0;
      for(int j=2; j<10; j++){
        if(i%j==0 && !(i==j)){
          tmp++;
        }
      }
      if(tmp==0){
        //Ziehe eine Primzahl aus allen möglichen Zahlen aus dem Wertebereich
        if((1 + Math.abs(rand.nextInt()) % 500)>480){
          prim=i;
          //Wenn eine Zahl gezogen wurde, beende die Primzahlermittlung
          i=bereich;
        }
      }
    }
  }

  public static BigInteger kryp(BigInteger zahl, String zahl2, int exp){
   //Lösungsidee nach de.wikipedia.org/wiki/rsa-Kryptosystem

   //Cn = Kn^e mod N   für n=1,2,3(,...)
   //C1 = 230911^1721 mod 263713
   //C1 = 001715

    BigInteger modulo = new BigInteger(zahl2);
    BigInteger temp;
    BigInteger lsg;

    temp = zahl.pow(exp);         //Exponentialrechnung
    lsg = temp.remainder(modulo); //Rest Ermittel

    return lsg;
  }

  public static BigInteger dekryp(BigInteger zahl, String zahl2, int exp){
   //Lösungsidee nach de.wikipedia.org/wiki/rsa-Kryptosystem

   //Kn = Cn^d mod N   für n=1,2,3(,...)
   //K1 = 001715^1373 mod 263713
   //K1 = 230911

    BigInteger modulo = new BigInteger(zahl2);
    BigInteger temp;
    BigInteger lsg;

    temp = zahl.pow(exp);         //Exponentialrechnung
    lsg = temp.remainder(modulo); //Rest Ermittel

    return lsg;
  }
}
```

Was ich vielleicht noch sagen sollte: Je größer die zu kodierende Zahl ist, um so größer muss auch das Primzahlprodukt sein (ist mir nur so aufgefallen).

Irgendwas scheint bei Schritt 6 falsch zu sein.

Machnmal klappt es, machmal streikt er aber auch und hängt sich in Schritt 6 auf, weil er keinen ganzzahligen privaten Exponenten findet.

Ich wäre euch dankbar, wenn ihr mir sagen könntet was alles falsch ist und wo man Sachen verbessern könnte.


----------



## clemson (11. Feb 2006)

ich hab mal in der schule so ein programm schreiben müssen, vielleicht hilfts dir ja weiter...


```
import java.math.*;
import javax.swing.*;
import java.io.*;
import java.lang.Character;

import javax.swing.*;

/**
 *Diese Klasse Verschlüsslet einen eingegebenen Text mittels der RSA Methode.
 *
 *@author clemson
 *@version 2.0
 *@date 12. Februar 2005 | 12:30
 */
public class RSA extends JFrame
{
	
	// Elemente des Frames deklarieren
	private javax.swing.JLabel NLabel;
    private javax.swing.JTextField NTextField;
    private javax.swing.JLabel TextLabel;
    private javax.swing.JTextField TextTextField;
    private javax.swing.JButton codeButton;
    private javax.swing.JLabel codedLabel;
    private javax.swing.JTextField codedTextField;
    private javax.swing.JLabel eLabel;
    private javax.swing.JTextField eTextField;
    private javax.swing.JPanel jPanel1;
	// Ende der Element-Deklaration
	
	
	
	/**
	 *Verschlüsselt den übergebenen Zahlenwert T mit den Parametern N und e nach
	 *der RSA Methode
	 *
	 *@param T zu kodierender Text
	 *@param N Produkt aus den beiden Primzahlen p und q
	 *@param e öffentlicher Schlüssel e
	 *
	 *@return den verschlüsselten Text
	 */
	public static BigInteger kodier(int nr, BigInteger N, int e)
	{
		BigInteger T = BigInteger.valueOf(nr);
		
		return ( T.pow(e) ).mod(N);
	}
	
	
	/**
	 *Gibt den chiffrierten Text zurück
	 *
	 *@param Text Text, welcher verschlüsselt werden soll
	 *@param N öffentlicher Schlüssel N
	 *@param e öffentlicher Schlüssel e
	 *
	 *@return verschlüsselter Text
	 */
	public static String getChiffredText( String Text, BigInteger N, int e )
	{
		// Länge des zu verschlüsselnden Textes bestimmen
		int laenge = Text.length();
		
		// ASCII Nummer
		int nr;
		
		// Character
		char c;
		
		// Ausgangsstring festlegen
		String codiert = "";
		
		// Schleife über die ganze Länge des Textes laufen lassen
		for (int i = 0; i<laenge; i++)
		{
			// einzelnenen Character der i.ten Position holen
			c = Text.charAt(i);
			
			// ASCII Nummer des Characters holen
			nr = Character.getNumericValue(c) - 9;
			
			// Wenn der Character ein Kleinbuchstabe ist, soll er verschlüsselt werden
			if ( (0<nr) & (nr<27) )
			{
				// Character verschlüsseln
				codiert += kodier( nr, N, e ).toString();
				
				// Wenn das Ende noch nicht erreicht wurde, soll ein Trennzeichen eingefügt werden			
				if ( i != laenge-1 )
				{
					codiert += "-";
				}
			}
			
			
	    }
		
		// verschlüsselten Text zurückgeben
		return codiert;
	}
	


	public static void main(String[] args)
	{

		new RSA();

	}
	
	
	public RSA()
	{
		initComponents();
		
		pack();
		
		setResizable(false);
		
		setLocation(200,200);
		
		setSize(300, 150);
		
		setVisible(true);		
				
	}
	
	
	/**
	 *initialisiert das Frame und fügt alle Komponenten und Listener
	 *hinzu.
	 */
	private void initComponents()
	{
		eLabel = new javax.swing.JLabel();
        eTextField = new javax.swing.JTextField();
        NLabel = new javax.swing.JLabel();
        NTextField = new javax.swing.JTextField();
        TextLabel = new javax.swing.JLabel();
        TextTextField = new javax.swing.JTextField();
        codedLabel = new javax.swing.JLabel();
        codedTextField = new javax.swing.JTextField();
        jPanel1 = new javax.swing.JPanel();
        codeButton = new javax.swing.JButton();

        getContentPane().setLayout(new java.awt.GridLayout(5, 2));

        setTitle("RSA-Verschl\u00fcsselung");
        setCursor(new java.awt.Cursor(java.awt.Cursor.DEFAULT_CURSOR));
        setFont(new java.awt.Font("Algerian", 0, 10));
        addWindowListener(new java.awt.event.WindowAdapter() {
            public void windowClosing(java.awt.event.WindowEvent evt) {
                exitForm(evt);
            }
        });

        eLabel.setLabelFor(eTextField);
        eLabel.setText("e");
        eLabel.setHorizontalTextPosition(javax.swing.SwingConstants.RIGHT);
        eLabel.setOpaque(true);
        getContentPane().add(eLabel);

        eTextField.setText("7");
        getContentPane().add(eTextField);

        NLabel.setText("N");
        NLabel.setHorizontalTextPosition(javax.swing.SwingConstants.RIGHT);
        getContentPane().add(NLabel);

        NTextField.setText("33");
        getContentPane().add(NTextField);

        TextLabel.setText("zu verschl\u00fcsselnder Text");
        TextLabel.setHorizontalTextPosition(javax.swing.SwingConstants.RIGHT);
        getContentPane().add(TextLabel);

        TextTextField.setText("Text");
        getContentPane().add(TextTextField);

        codedLabel.setText("verschl\u00fcsselter Text");
        codedLabel.setHorizontalTextPosition(javax.swing.SwingConstants.RIGHT);
        getContentPane().add(codedLabel);

        getContentPane().add(codedTextField);

        getContentPane().add(jPanel1);

        codeButton.setText("Text verschl\u00fcsseln");
        codeButton.addActionListener(new java.awt.event.ActionListener() {
            public void actionPerformed(java.awt.event.ActionEvent evt) {
                codeButtonActionPerformed(evt);
            }
        });

        getContentPane().add(codeButton);
	}
	
	
	/**
	 *Wenn der CodeButton gedrückt wurde, dann wird der Text verschlüsselt
	 *und im codedTextField angezeigt
	 */
	private void codeButtonActionPerformed(java.awt.event.ActionEvent evt)
	{
		// Versuch, die folgenden Befehler auszuführen
		try
		{
			// öffentlichen Schlüssel N aus dem TextField holen
			BigInteger N = new BigInteger( NTextField.getText() );
			
			// öffentlicher Schlüssel e aus dem TextField holen
			int e = Integer.parseInt( eTextField.getText() );
			
			// zu verschlüsselnden Text holen
			String Text = TextTextField.getText();
			
			// den kodierten Text im codedTextField setzen
			codedTextField.setText( getChiffredText( Text, N, e) );
		}
		catch (Exception ex)
		{
			codedTextField.setText("Error occured!");
		}
		
		
	}
	
	
	/**
	 *Diese Methode wird bei einem Klick auf das X aufgerufen
	 */
    private void exitForm(java.awt.event.WindowEvent evt)
    {                          
        System.exit(0);
    }
	
}
```


----------



## Iome (11. Feb 2006)

Dein Prog hilft mir leider gar nicht. Bei deinem Programm muss man ja selbst irgendwie das Primzahlprodukt und den Exponenten errechnen. Mein Programm soll diese Sachen aber selbst erzeugen können.

im eigentlichen ist ja dein Quelltext:

```
public static BigInteger kodier(int nr, BigInteger N, int e)
   {
      BigInteger T = BigInteger.valueOf(nr);

      return ( T.pow(e) ).mod(N);
   }
```

so in etwa sieht auch meins aus. 

*-> Mein Problem ist ja eher die Erzeugung der Exponenten.*


----------



## Iome (24. Feb 2006)

habt ihr nicht vll noch nen kleinen hinweis für micht was die exponenten beim rsa-verfahren anbelangt *bitte ... fleh*


----------



## Bleiglanz (26. Feb 2006)

kannst du mal die Frage genauer Stellen

p und q musst du auwändig durch probieren und raten erzeugen

e nimmt man immer 3 oder 65537 oder sowas?!


----------

