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:
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.
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:
Java:
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);
}
}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.
