Rsa verfahren Primfaktorzerlegung

[SurTana]

Hi Leute

hab da ein Problem beim RSA verfahren.

ich soll für Informatik einen Algorythmus schreiben der den Öffentlichen schlüssel N in die beiden Primzahlen p und q zerlegt habe aber keine ahnung wie man das macht. habe auch schon versucht über google was zu finden bin aber auf keine lösung gestoßen.

ich weiss zwar wie man eine zahl in ihre Primfaktoren zerlegt aber das bringt mir nichts weil man dabei auf eine vielzahl von primzahlen stößt ich muss aber wissen wie man von einer Zahl genau 2 primfaktoren bekommt.

ich hoffe ihr versteht mein problem.

und wenn jemand das kann, ich soll den algorythmus in Java machen, aber mir würde die mathematische funktion auch schon reichen den rest würde ich vielleicht selber hinbekommen, auch wenn ich ncihtmal mehr weiss wie man ein grundgerüst macht ^^

vielen dank

SurTana

[kingofbrain]

Du kannst doch nicht jede Zahl in genau zwei Primzahlen zerlegen. Sonst gäbs ja die Primfaktorzerlegung nicht mit n Primzahlen.

Peter

[SurTana]

es ist ja so das ich den öffentlich schlüssel (N) vom RSA verfahren habe und der wird ja aus 2 primzahlen zusammengesetzt ( p * q ). Die Zahl die ich abfrage ist also auf jedenfall eine Zahl mit 2 primzahlen. ich will ja ganricht jede Zahl zerlegen nur eine bestimmte die auf diese weise entstanden ist.

[Whatever]

Du kannst doch nicht jede Zahl in genau zwei Primzahlen zerlegen. Sonst gäbs ja die Primfaktorzerlegung nicht mit n Primzahlen.

Peter

Nein, aber ich wette das es genau einen Fall gibt wo es nur zwei Primfaktoren gibt...und genau die sucht man ja.

/: So aus dem groben heraus würde ich es so machen:

p = 2

q = 2

do {

 p = nextPrim(p)

 do {

  q = nextPrim(q)

  if(p*q == N) {

   //gefunden

  }

 } while (q < N)

} while(p < N)

//nextPrim liefert jeweils die nächste Primzahl

Anders als schlichtes durchprobieren geht nicht, das is ja der Trick an der Sachen mit Primfaktoren

(Natürlich ist das da oben total unoptimiert und mir fallen auch schon wieder 2 Sachen ein wie man eine MENGE Iterationen sparen könnte, aber das machst du schön selbst )

[kingofbrain]

Ok, das wusste ich nicht, dass dieser Schlüssel aus zwei Primzahlen gefertigt wird.

Die Bruteforce-Methode ist natürlich jetzt, durch die Primzahlen zu iterieren und versuchen, die Zahl damit mit einem Modulo-Teiler auf das Ergebnis 0 zu bringen. In welchem Zahlenraum bewegen wir uns denn dann? Soll heissen, welche mögliche Anzahl Primzahlen gibt es in diesem Raum?

@Whatever: das glaube ich nicht. Es gibt ganz viele Fälle, wo eine Zahl aus genau zwei Primzahlen gebildet wurde. Mir war nur nicht bekannt, das bei diesem Schlüssel diese Voraussetzung zutrifft.

Peter

[SurTana]

irgendwie funktioniert das nicht so ganz. erstens habe ich keine methode nextprim. hab mal versucht eine zu finden aber das klappt nicht. der sagt bei p*q == N das Wert erforderlich ist aber Variable gefunden Wurde.

ich verzweifel hier volkommen weil es einfach nicht klappt

so sieht mein programm aus

import java.io.*;

import java.awt.*;

import java.awt.event.*;




/**

 * <p>Überschrift: </p>

 *

 * <p>Beschreibung: </p>

 *

 * <p>Copyright: Copyright (c) 2006</p>

 *

 * <p>Organisation: </p>

 *

 * @author unbekannt

 * @version 1.0

 */

public class Main extends Frame implements ActionListener

{

    int p,q,N;

    int x=1;

    long prim;

    Button calc;

    Button quit;

    Label nfo;

    TextField input, output;


    public Main()

    {

           setLayout(null);

     setSize(600,500);

     setTitle("Primfaktorzerlegung");

     setBackground(Color.gray);

     calc=new Button("Berechnen");

     calc.setBounds(50,400,200,50);

     calc.addActionListener(this);

     add(calc);

     quit=new Button("Schliessen");

     quit.setBounds(300,400,200,50);

     quit.addActionListener(this);

     add(quit);

     nfo=new Label(" Geben Sie hier die zu berechnende Zahl ein:");

     nfo.setBounds(50,70,300,50);

     add(nfo);

     input=new TextField();

     input.setBounds(50,150,200,20);

     add(input);

     output=new TextField();

     output.disable();

     output.setBounds(50,250,200,20);

     add(output);

     show();


    }


     public void actionPerformed (ActionEvent ae)

     {

     if (ae.getSource()==quit)

        System.exit(0);

     if (ae.getSource()==calc)

        prim(prim);


     }


    /* public void textValueChanged(TextEvent te)

     {


     }

         */

    public long prim(long prim)

    {


       String N = input.getText();

       prim=Integer.parseInt(N);

       // N = 2773;

        p = 2;

        q = 2;

        do {

            p = nextprim();

                do

            {

                q = nextprim();

                    if( p * q = N)

                    {

                        System.out.println(p);



                } while (q < N);

            }while(p < N);

        }while (p*q == N);



        return p;

    }


    /**

     * nextPrim

     *

     * @param p int

     * @return int

        */


  static int nextprim()


  {


    do


    {


      //Primzahlen ausschliesslich ungerade (ab 3)


      x += 2;


    }


    while (!(isprim(x)));


    //Kommentar kann zu Testzwecken entfernt werden.


    //Ausgabe nur um zu zeigen, dass das Programm arbeitet


    //System.out.println(x);


    return x;


  }




  //normaler Algorithmus: Ueberpruefung, ob eine Zahl von n/2


  //bis 1 n teilt => keine Primzahl (sehr lange Rechenzeit)


  //deshalb wird hier ein sehr viel schnellerer Algorithmus


  //verwendet


  static boolean isprim(int n)


  {


    int k = bisqrt(n);


    //stellt sicher, dass k ungerade ist


    k = k + 1  + (k%2);


    return (!(isdiv(k,n)));


  }




  //Ueberprueft, ob eine Zahl von k bis 1 n teilt


  static boolean isdiv(int k, int n)


  {


    int t = 3;


    boolean b = false;




    while (t <= k)


    {


      if ((n % t) == 0)


      {


        b = true;


        break;


      }


      t += 2;


    }


    return b;


  }




  //rekursive Berechnung der ganzzahligen Quadratwurzel von n


  static int bisqrt(int n)


  {


    int l=0;




    if (n == 0)


      return 0;


    else


    {


      l = 2 * bisqrt(n/4) +1;


      if (l*l <= n)


        return l;


      else


        return l-1;


    }


  }



    public static void main(String[] args) {

        Main main = new Main();


    }

}

[kingofbrain]

Servus,

Du solltest erst mal Deine Compilerfehler bereinigen, die nichts mit dem Problem zu tun haben. Dann könntest Du Deinen Code um unwichtige Teile erleichtern, da ich keine Zeit habe, 229 Zeilen zu lesen und nachzuvollziehen, wenn das Problem vielleicht in 5 Zeilen steckt.

Die Fehler, die der Compiler bis jetzt schmeisst, sind im if in Zeile 84, da solltest Du vielleicht mit "==" statt mit "=" prüfen. Danach kommen drei Fehler in den Zeilen 89, 90 und 91, wo Du Strings mit "<" oder "==" vergleichen willst. Und in einer statischen Methode (nextprim) kannst Du natürlich keine nichtstatischen Attribute der Klasse ansprechen (Zeilen 114, 118, 126).

Das sind jetzt alles wirkliche Anfängerfehler, die Dir der Compiler erklärt und die Du beim nächsten Mal bitte bereinigst, bevor Du Code anbietest.

Bis nachher!

Peter

[etreu]

Das Verfahren ist doch bei Wikipedia gut erklaert: http://de.wikipedia.org/wiki/RSA-Kryptosystem#Entschl.C3.BCsselung

Das, was noch fehlt ist der public key.