RSA - Problem mit den Faktoren mod N

[tanj]

Hallo,

ich darf fuer die Uni mich am RSA-Verfahren versuchen. Folgendes Problem: Alle Schluessel sind bekannt, mein Programm zum berechnen funktioniert auch fuer kleine Zahlen. Fuer grosse hingegen nicht.
Das Programm ist in Java geschrieben, hier mal der wesentliche Ausschnitt:

public long [] faktoren(long zahl, long N, String potenz)
	{
		if (potenz.length() > 0)
		{
			long [] fac = new long[potenz.length()];
			
			fac[0] = zahl;
			
			for(int i = 1; i < fac.length; i++)
			{
				fac[i]= ((fac[i-1] % N) * (fac[i-1] % N)) % N;
				System.out.println("FAC["+i+"] "+ fac[i]);
			}
			return fac;
		}
		return null;
	}

Hier wird die Tabelle berechnet damit das Potenzieren schneller geht. Fuer kleine Zahlen in Ordnung, fuer grosse hingegen, kommen negative Werte heraus. z.B. fuer zahl = 1210034980, N = 4111577933 und potenz ist 10000101100001110100011001000111.

Fuer fac[7] kommt jetzt -1911990465 raus. Ich denke mal das ist ein Speicherproblem, dass es da irgendwo zu einem Pufferueberlauf kommt oder so.

Hat wer eine Idee, wie ich das loesen koennte?

 

[Elderan]

Hallo,
int kann nur Zahlen bis max. 2,1 Mrd. fassen. Wenn ein Zwischenergebnis größer wird, stimmt die Rechnung nicht mehr und man bekommt u.U. auch negative Ergebnisse.

Lösung: BigInteger Classe von Java nutzen. Dort dürfen die Zahlen beliebig groß werden.

 

[tanj]

Danke.

 

[Darkslide]

Schau dir zur Berechnung mal den Square and Multiply Algorithmus an.