RSA - Problem mit den Faktoren mod N

tanj

New member
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:
Code:
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

Moderator
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.
 
Oben