RSA geheimexponent ermitteln

hallo erst mal an alle und danke schon mal für die hilfe.

bin ein ziemlicher neuling was c angeht, mein problem ist folgendes ich möchte ein RSA programm schreiben und ich krieg es einfach nicht hin den Geheimexponenten zu ermitteln wiki und ähnliches hilft mir auch nicht sonderlich, hab allmählich das gefühl das ich zu blöd bin dafür bin :((
hier erst mal mein bisheriger code

void createkey () {
         //Variablendeffinition/ -belegung
         long int p, q;       //Variablen zur speicherung der primzahlen
         long int k;          //RSA - Modul, teil des oeffentlichen schluessels
         long int m;         //eulerische Funktion
         long int s;          //teil des oeffentlichen Schluessels
         long int t;          //geheimer exponent

         int flag;            //einfache entscheidungsvariable

         //p und q mit primzahlen belegen
             p = primzahl();
             //kleine schleife damit p !=q sehr geringe wahrscheinlichkeit muss aber nicht provoziert werden^^
             do {
                 q = primzahl();
             } while(p==q);
         //Test ob es bis hierhin funktioniert
                printf ("%li ist die Primzahl \n", p);
                printf ("%li ist die Primzahl \n", q);
         //RSA-Modul, k ermitteln
             k = p*q;
             printf ("%li ist k \n", k);
         //eulerische funktion anwenden und m ermitteln
             m = ((p-1)*(q-1));
             printf ("%li ist m \n", m);
         //s ermitteln unter zuhilfenahme der funktion ggt
             srand(time(0));                  // es soll ja auch wirklich zuefallig sein
             //s muss teilfremd zu m sein also wird probiert
             do { 
                s = rand()%m+1;
                if (ggt(s,m) == 1) {         //teilfremd von ef
                   flag = 0;
                } else {                      //nicht teilfremd also noch mal 
                   flag = 1;       
                }
             } while(flag == 1);
         //Zwischenbilanz: Oeffentlicher schluessel ist nun vorhanden, weiter zum privaten
         //t ermitteln
             srand(time(0));                  //kennen wir so weit schon von s

	//und ab hier haut es einfach nicht hin 

	//die formel zum erfolg lautet s · t mod m = 1 und das heist wider probieren
             do {
                 t = rand()%k+1;
                 if (((s*t)%m)==1){ //Formel zum erfolg wurde erreicht^^ also weg hier
                    flag = 0;
                 } else {             //fail
                    flag = 1;
                 }
             } while (flag != 0); 
         //Damit haetten wir es eigentich geschafft
         //Dann auf zum probe test
                printf ("%li ist t \n", t);
                printf ("%li ist s \n", s);
                getchar();
         //Hinterlegen der relevanten Daten 
      }

P.S. weiss nicht ob das vorhergehende richtig ist aber das dürfte ja soweit hinhauen.

Hier noch die zwei Funktion die ich oben verwende^^

//Funktion welche eine Primzahl ermittelt unter zuhilfenahme des Both Force III ansatzes
           //Parameter:           keine
           //Rueckgabewert:       long int
    long int primzahl() {
    	//Variablendefinition
    	long int a;          //Hier wird die wahrscheinliche Primzahl gespeichert
    	int i;               //Zaehlvariable
    	int flag;            //einfache flag - variable

        srand(time(0));
    	do {
    		flag = 0;    
    		//Zufallszahl ermitteln 
    		a =rand()%40000+10000;
    		//prüfen ob es eine Primzahl ist 
    		if (a % 2 == 0) {
    	                flag = 1;
    	            }
    	            /* Versuche variable a mit den ungeraden Zahlen
    	               von 3 bis sqrt(a) zu teilen! */ 
    	            for (i = 3; i <= sqrt(a); i = i + 2) {
    	                if (a% i == 0) { //Teilertest
    	                    flag = 1;
    	                }
    	            }
    	}while (flag == 1); //Wenn es hier rausgeht dann ist a eine Primzahl
    	return a;           //Rueckgabe der Primzahl
}

//Funktion ggt, ermittelt den groeßten gemeinsammen teiler
           //Parameter:           long int a; long int b 
           //Rueckgabewert:       long int
    long int ggt( long int a, long int b) {
    	if (a == 0) {                            //Wenn a=0 ist b der größste gemeinsame Teiler laut Definition
            	return b;
        	}
        	while(b != 0) {                      //Solange wiederholen, solange b nicht 0 ist.
            	if (a > b) {
                    	a = a - b;               //Wenn a größer als b subtrahiere b von a.
            	} else {
                    	b = b - a;               //In jedem anderen Fall subtrahiere a von b.
            	}
        	}
        	return a;                            //In a steht jetzt der größste gemeinsame Teiler von a und b.
     }

volkard

Suchst Du den erweiterten euklidischen algorithmus?

wow das ging schnell damit hätte ich nicht gerechnet;)

zu der frage ja der würde mir sehr helfen aber ich krieg das nicht richtig implementiert:((

icarus2

Hier findest du am Ender der Seiten den erweiterten Euklidischen Algorithmus in Java implementiert.

und wie genau krieg ich dadurch jetzt den geheimexponent? Dass ist leider der punkt den ich noch nicht ganz verstanden habe.

Aber nochmals vielen vielen dank

icarus2

murdoc1988 schrieb:

und wie genau krieg ich dadurch jetzt den geheimexponent? Dass ist leider der punkt den ich noch nicht ganz verstanden habe.

Aber nochmals vielen vielen dank

Im Prinzip liefert dir der euklidische Algorithmus fuer zwei natuerliche Zahlen a, b die ganzen Zahlen u,v so dass:
ggT(a,b) = u*a + v*b

Wie du das benutzen kannst um den privaten Schluessel zu berechen ist hier ganz gut erklaert.

Versuche mal zuerst den erweiterten euklidischen Algorithmus zu implementieren. Danach kannst du den direkt fuer die Berechnung des privaten Schluessels verwenden.

ok habs dann auch noch rausbekommen nochmals vielen dank für die schnelle und kompetente hilfe find kein danke buttondarum noch mal so vielen vielen dank

ok hätte dann doch noch ne frage.

Und zwar geht es um folgendes wenn ich den erw. eukl. alg. anwende bekomme ich den gewünschten geheimexponent allerding kann der ja auch negativ sein und das darf ja bei der RSA verschlüsselung nicht der fall sein meine frage ist jetzt muss ich dann noch mal von ganz vorne anfangen bis ich einen posetiven wert bekomme oder gibt es da noch eine andere möglichkeit?

Wie immer vielen Dank

volkard

murdoc1988 schrieb:

ok hätte dann doch noch ne frage.

Und zwar geht es um folgendes wenn ich den erw. eukl. alg. anwende bekomme ich den gewünschten geheimexponent allerding kann der ja auch negativ sein und

nö. :xmas2:

icarus2

murdoc1988 schrieb:

ok hätte dann doch noch ne frage.

Und zwar geht es um folgendes wenn ich den erw. eukl. alg. anwende bekomme ich den gewünschten geheimexponent allerding kann der ja auch negativ sein und das darf ja bei der RSA verschlüsselung nicht der fall sein meine frage ist jetzt muss ich dann noch mal von ganz vorne anfangen bis ich einen posetiven wert bekomme oder gibt es da noch eine andere möglichkeit?

Wie immer vielen Dank

Ja der EEA kann einen negativen Wert liefern fuer das Inverse. Die einfachste Moeglichkeit ist dann einfach solange phi(n) hinzuzuaddieren bis du eine positive Zahl hast.

ok,

frage 1. mit phi(n) meinst du da das RSA Modul (also bei mir k)?

frage 2. haut das echt hin wenn ich einfach phi(n) hinzuaddiere erscheint mir etwas willkürlich?

ipsec

murdoc1988 schrieb:

frage 1. mit phi(n) meinst du da das RSA Modul (also bei mir k)?

frage 2. haut das echt hin wenn ich einfach phi(n) hinzuaddiere erscheint mir etwas willkürlich?

1. Nein, phi(n) ist die Eulersche φ-Funktion.

2. Ja, denn a^φ(n) mod n = 1 (Satz von Euler-Fermat), somit ist a^n ≡ a^n * 1 ≡ a^n * a^φ(n) ≡ a^(n+φ(n)) (mod n)

ok danke