# Modulo-Operator versagt bei zu großen Zahlen?



## Tassimmo (12. Mrz 2014)

Hallo, 

ich beschäftige mich grade im Rahmen des Studiums mit Kryptografie und steige da grade erst etwas ein (bitte nich hauen, wenn ich hier irgendwas falsches sag ;( ). 

Ich hab versucht, das RSA-Kryptosystem in Java nachzubaun. Zwar in stark vereinfachter Form (Primzahlen bis 100), stoße aber trotzdem auf ein Problem:
Der codierte Wert berechnet sich ja aus *C=M^e mod N*. 
M= Buchstabe in ASCII, z.B. 65. 
N und e sind die Schlüssel. Sie werden über Math.Random() bestimmt. Wenn ich nun den Schlüsselwert berechne, komme ich bei N=55 und e=3 auf

C = 65^3 mod 55 = *10*. 

So weit, so gut. 
Allerdings macht mir die Modulo-Berechnung Probleme, sobald die Hochzahl e höher als 10 ist. Bei N=1121 und e=17 erhalte ich

C = 65^17 mod 1121 = *421*, während mir der Taschenrechner 981 ausgibt. 

Im Folgenden mal kurz die Methode, die ich dazu geschrieben hab:

```
public void verschluesseln(String m)
	{
		fillPrimArray();
		long n;
		int p,q,e;	
		String c="";
		
		do
		{
			p=pickRandomPrim(); //p ist erste Primzahl des Schlüssels
			q=pickRandomPrim(); //q ist zweite Primzahl des Schlüssels
		}
		while(p==q);
		n=p*q; //N ist erster Teil des public key, RSA-Modul  
		 
		int eulerN = (p-1)*(q-1); //Eulersche Phi-Funktion als Obergrenze für e
		
		do
		{
			e=pickRandomPrim();	//e ist zweiter Teil des public key, 
		}
		while(e>=eulerN||e==p||e==q);
		
		if(ggt(eulerN,e)==1) //e muss teilerfremd zu eulerN sein
		{			
			for(int i=0;i<m.length();i++)
			{
				double Expo = Math.pow(convertToAscii(m.charAt(i)), e);	
				System.out.println(Expo); //Expo wird noch korrekt ausgegeben!
				double Rest = (double) (Expo) % n; 
				System.out.println(Rest);
				c = c+" "+addZeros(Rest);
				System.out.println(c+" ");
			}
		}
		else
		{
			verschluesseln(m);
		}
	}
```
Da mir die Zahl Expo, die ich testweise getrennt berechne, noch korrekt ausgegeben wurde, muss es irgendwie an dem Modulo-Operator liegen. Aber er funktioniert nicht, wenn der Exponent zu hoch ist. Ich bin verwirrt :autsch:

Ich hoffe, ich konnte mein Problem einigermaßen anschaulich schildern. Bereits vielen Dank im Voraus für die Hilfe!

PS: Das Programm wird niemals zum Verschlüsseln von wirklich wichtigen Sachen verwendet werden! Ich könnte auch die Key-Klasse in Java verwenden, möchte aber lediglich den Algorithmus hinter RSA verstehen und nachbauen.


----------



## HD1920 (12. Mrz 2014)

Nimm statt erst M^e zu berechnen die Methode pow_modulo:


```
public static long pow_modulo(long M, long e, long N) {
    if (e % 2 == 1) {
        return M * pow_modulo(M, e-1, N) % N;
    } else {
        return pow_modulo(M * M % N, e/2, N);
    }
}
```


----------



## Tobse (12. Mrz 2014)

warum das passiert:
Alle Zahlen im Quellcode sind 
	
	
	
	





```
int
```
s, solange du nicht anders notierst. 


```
65 ^ 17 = 6599743590836592050933837890625
```

Das übersteigt zwar nicht den Wertebereich von 
	
	
	
	





```
long
```
, wohl aber die Präzision. Sprich, aus 
	
	
	
	





```
6599743590836592050933837890625
```
 wird 
	
	
	
	





```
6.599743590836592 * 10^30
```

Und 
	
	
	
	





```
(6.599743590836592 * 10^30) % 30 = 421
```
 wobei aber 
	
	
	
	





```
6599743590836592050933837890625 % 1121 = 981
```


Was man dagegen tun kann hat mein Vorredner schon gesagt, es geht aber auch mit der Java-API([JAPI]java.math.BigInteger[/JAPI]):

```
BigInteger m = new BigInteger("55421");
BigInteger e = new BigInteger("65535");
BigInteger n = new BigInteger("12354987624687");
BigInteger c = m.modPow(e, n);
```

P.S.: Die Crypto-Bibliothek von Java arbeitet auch mit BigInteger.


----------



## Sen-Mithrarin (13. Mrz 2014)

Tobse hat gesagt.:


> P.S.: Die Crypto-Bibliothek von Java arbeitet auch mit BigInteger.



das glaube ich eher weniger ... weil es zu viel zeit schlucken würde und es auch nur eine kapselung wäre ...
ich geh eher davon aus das in der cypto-lib die bits direkt rumgeschubst werden anstatt sich da noch mal an der api zu bedienen und damit performance zu drücken


----------



## Tassimmo (13. Mrz 2014)

Oke, ich hab jetzt beide Varianten ausprobiert.
@HD1920:
Die Mod_Pow-Methode wird denke ich funktionieren, allerdings fehlt mir die Abbruchbedingung, das e wird nämlich immer immer kleiner (weil e/2), die Methode hört nicht auf -->StackOwerflow. Irgendwas muss die Methode bei e=1 ausgeben, das nicht rekursiv endet. 
@Tobse
Mit den BigInteger könnte ich weiterkommen. Dann muss ich aber auch alle anderen Methoden umschreiben, auch die, die mir eine zufällige Primzahl ausspuckt, da ich meine zwei ints p*q nicht multiplizieren kann, um n zu bekommen. Dadurch funktioniert aber die Random-Funktion nicht mehr korrekt...


----------



## Tobse (13. Mrz 2014)

Tassimmo hat gesagt.:


> da ich meine zwei ints p*q nicht multiplizieren kann, um n zu bekommen.



Und was ist damit?

```
int p = randomPrime();
int q = randomPrime();

int n = p * q;
BigInteger biN = new BigInteger(n);
```

bzw. wenn dus geschickt machen willst:

```
BigInteger p = BigInteger.probablePrime(16, new SecureRandom());
BigInteger q = BigInteger.probablePrime(16, new SecureRandom());
BigInteger n = p.multiply(q);
```


----------



## Tobse (13. Mrz 2014)

Tobse hat gesagt.:


> Und was ist damit?
> 
> ```
> int p = randomPrime();
> ...


[OT]


Sen-Mithrarin hat gesagt.:


> das glaube ich eher weniger ... weil es zu viel zeit schlucken würde und es auch nur eine kapselung wäre ...
> ich geh eher davon aus das in der cypto-lib die bits direkt rumgeschubst werden anstatt sich da noch mal an der api zu bedienen und damit performance zu drücken



Und wie macht sie das? Dann müsste sämtlicher code, der bei der modPow methode passiert in der crypto api nochmal vorhanden sein. Das wiederspricht dem Prinzip der wiederverwendung von code. Und wo da Zeit verloren gehen soll erschließt sich mir nicht direkt. Der Zeitaufwand für [c]BigInteger x = new BigInteger(byte[] data)[/code] ist minimal.[/OT]


----------



## Sen-Mithrarin (14. Mrz 2014)

kann ich soweit verstehen den gedankengang ... aber ich vermute schon das es gewisse algorithmus-spezifische optimierungen geben wird

aber man kann sich ja mal den source für oracles RSA irgendwo her ziehen und nachgucken



...


hmm ok ... muss mich geschlagen geben
hab grade mal im source von sun.security.rsa.RSAKeyPairGeneratorImpl nachgesehen ... es wird wirklich BigInteger genutzt ...


----------



## HD1920 (14. Mrz 2014)

Tassimmo hat gesagt.:


> Die Mod_Pow-Methode wird denke ich funktionieren, allerdings fehlt mir die Abbruchbedingung, das e wird nämlich immer immer kleiner (weil e/2), die Methode hört nicht auf -->StackOwerflow. Irgendwas muss die Methode bei e=1 ausgeben, das nicht rekursiv endet.


Ups, Verbesserung:

```
public static long pow_modulo(long M, long e, long N) {
    if (e == 0) {
        return 1;
    } else {
        if (e % 2 == 1) {
            return M * pow_modulo(M, e-1, N) % N;
        } else {
            return pow_modulo(M * M % N, e/2, N);
        }
    }
}
```


----------



## HD1920 (15. Mrz 2014)

Ach ja: Es wäre ratsam, zuvor zu überprüfen, ob n eine Pseudoprimzahl ist. Wenn ja, schmeißt du dieses n am besten weg, da es sonst im Nu faktorisiert ist.


----------



## Sen-Mithrarin (15. Mrz 2014)

eine primzahl faktorisieren ? oder meinst du das ergebnis was am ende bei raus kommt ?


----------



## Tobse (15. Mrz 2014)

Sen-Mithrarin hat gesagt.:


> eine primzahl faktorisieren ?



Eine pseudo-primzahl faktorisieren.


----------



## Sen-Mithrarin (17. Mrz 2014)

du weist schon was eine primzahl ist oder ?
und wenn du eine prim faktorisieren kannst ist sie nicht prim ... egal ob sie von einem pseudo-random-generator stammt oder nicht ... entweder eine zahl ist prim oder sie ist es nicht ...

das wort "pseudo-prim" drückt doch nur aus das die prim nicht 100% berechnet wurde sondern nur mit einer gewissen wahrscheinlichkeit geschätzt wird ob sie prim ist ... und da wäre es einfacher zu prüfen ob die zahl prim ist in dem man bis sqrt(prim) läuft anstatt zu versuchen sie zu faktorisieren ...



oder was genau meinst du (sorry .. ich habs leider immer noch nich gerallt)


----------



## Tobse (17. Mrz 2014)

Sen-Mithrarin hat gesagt.:


> du weist schon was eine primzahl ist oder ?
> und wenn du eine prim faktorisieren kannst ist sie nicht prim ... egal ob sie von einem pseudo-random-generator stammt oder nicht ... entweder eine zahl ist prim oder sie ist es nicht ...
> 
> das wort "pseudo-prim" drückt doch nur aus das die prim nicht 100% berechnet wurde sondern nur mit einer gewissen wahrscheinlichkeit geschätzt wird ob sie prim ist ... und da wäre es einfacher zu prüfen ob die zahl prim ist in dem man bis sqrt(prim) läuft anstatt zu versuchen sie zu faktorisieren ...


Du wiedersprichst dir selbst. Pseudoprimzahl ? Wikipedia. Es geht ja darum, dass der Modulus den _probabilistischen_ Primzahltest *nicht* besteht. Denn wenn er es tut, ist er eine *Pseudoprimzahl* und damit unsicher.
*Der Modulus kann keine Primzahl sein* denn er wird ja aus zwei Faktoren zusammengesetzt.



Sen-Mithrarin hat gesagt.:


> oder was genau meinst du (sorry .. ich habs leider immer noch nich gerallt)


Gemeinst ist, dass ein Schlüssel dessen Modulus den probabilistischen Primzahltest besteht unsicher ist.


----------



## Sen-Mithrarin (18. Mrz 2014)

achso ... sorry ... hab überlesen das du von N redest ... mein fehler ...


----------

