RSA Verfahren - Erweiterter Euklidischer Algorithmus

[Dagobert]

Ich versuche gerade das RSA-Verfahren mit einer Ausfühlichen Darstellung zu entwickeln, um die Schulergebnisse zu Prüfen.

Doch leider habe ich beim dem Berechnen von d ein Problem und noch viel mehr von der Darstellung.
Ich nenne mal ein Beispiel:
geg: p = 29, q = 41, phi(n)=1120, e= 29
ges: d=?

1120 = 38*29 + 18
29 = 1*18 + 11
18 = 1*11 + 7
11 = 1*7 + 4
7 = 1*4 + 3
4 = 1*3 +1
-> dann muss man das ganze Rückwärts ausgeben:
--> 1 = 4 -1*3
= 1*4-(7-1*4)
= 2*4 - 1*7
= 2*(11-1*7) - 1*7
= 2*11 - 3*7
= 2*11 - 3*(18-1*11)
= 5*11 - 3*18
..............
=309*29 - 8*1120

--> d = 309

nun ist mein Problem, das ich es nicht gebacken bekomme d so auszurechnen mit der obrigen Ausgae (also nur den Rückwärtsteil)

kann mir da wohl jemand unter die Arme greifen weil langsam bin ich da echt am verzweifeln...

mfg. Dagobert

 

[0x7F800000]

joah, an diese elende rechnerei kann ich mich gut erinnern, hab mir dazu auch schon bisschen was geschrieben:

	public static void displayGcdExtended(long a, long b){
		
		String s="%"+String.valueOf(Math.max(a,b)).length()+"d";
		long bezoutA_current=1,bezoutB_current=0,bezoutA_next=0,bezoutB_next=1,q,r;
		long _a=a, _b=b;
		
		System.out.println("calculating gcd("+a+","+b+"):");
		do{
			q=a/b;
			r=a-q*b;
			
			System.out.printf(s+"="+s+"*"+s+"+"+s+"\t\t"+s+"\t"+s+"\n", a,q,b,r,bezoutA_current,bezoutB_current);
			
			long tempA=bezoutA_next, tempB=bezoutB_next;
			
			bezoutA_next=bezoutA_current-q*bezoutA_next;
			bezoutB_next=bezoutB_current-q*bezoutB_next;
			bezoutA_current=tempA;
			bezoutB_current=tempB;
			
			a=b;
			b=r;
		}while(r>0);
		
		String e=s.substring(0,s.length()-1)+"s";
		System.out.printf(s+" "+e+" "+e+" "+e+"\t\t"+s+"\t"+s+"\n", a,"","","",bezoutA_current,bezoutB_current);
		System.out.println("gcd("+_a+","+_b+")="+a+"="+_a+"*"+bezoutA_current+"+"+_b+"*"+bezoutB_current+"\n");
	}

Allerdings hab ich keinen Schimmer Ahnung wieso du die Ausgabe so merkwürdig umgedreht haben willst ???:L Bei meiner version wird's einfach grad aus von oben nach unten ausgegeben, so wie ich das auch normalerweise rechnen würde.

 

[Guest]

Vielen Dank für deinen Code der hat mir sehr weitergeholfen...
Vorallem fande ich diese zwei Zeile sehr interessant

String s="%"+String.valueOf(Math.max(a,b)).length()+"d";
s+"="+s+"*"+s+"+"+s+"\t\t"+s+"\t"+s+"\n",
	        		 a,q,b,r,bezoutA_current,bezoutB_current)

Kannst du mir die einmal genauer erklären, das sieht nach einem Platzhalterprinzip aus? Aber das kenne ich net^^
Gibt es noch eine möglichkeit daraus einfach einen String zu machen? So das ich ihn mit append behandel kann?

mfg. Dagobert

 

[0x7F800000]

öööööh... keine ahnung. Ich hab das mal vor zwei jahren am späten Abend im gestressten zustand zusammengehackt, um damit meine hausis zu prüfen, da habe ich mir nicht zu viel mühe bei der schönen gestaltung des codes gegeben.

s ist einfach nur ein string der gestalt "%Xd" wobei statt "X" die länge der längsten vorkommenden Zahl eingesetzt wird. Das wird dann mehrmals bei printf ausgaben verwendet. Das alles ist eine recht hässliche Krücke, um alle zahlen irgendwie einigermaßen in Spalten auszurichten, damit das alles nur ein wenig geradliniger aussieht. Aber wie gesagt, damals hatte ich keine Zeit um das irgendwie schöner zu machen. Zeitkritisch ist das alles nicht, und funktionieren tut's auch irgendwie... Aber es gibt bestimmt irgendwelche elegantere Möglichkeiten einen String zu formatieren, lies dir in der Literatur deiner Wahl irgendwas zum Thema durch wenn du willst, da findest du schon irgendwas. :toll:

 

[SlaterB]

String.format() statt System.out.printf()