RSA verschlüsselung

[NicNacMan]

hi,

ich suche eine function/komponente, mit der ich eine zahl mit rsa verschlüsseln kann.
ich hab schon mehrere komponenten gefunden und ausprobiert,
aber die waren alle zu komplex, oder funktionierten nicht.
ich hab schon public keys, brauche also nichts, um gültige keys zu generieren.

kennt ja jemand was?
thx schonmal

[Olli]

Hagen fragen!

... oder nach DEC suchen ;)

[NicNacMan]

hab mir das DEC runter geladen, aber nichts mit rsa gefunden. :gruebel:
oder ist das da nur unter nem anderen namen enthalten (habs nicht so mit verschlüsselungen)?

thx nicnacman

[Phistev]

Soweit ich weiß, sind beim DEC auch Funktionen zum Rechnen mit großen Zahlen dabei. Damit kann man sich die RSA-Verschlüsselung selber bauen

[NicNacMan]

jo, aber da hab ich sonst auch schon welche (u.a. von den kompos, die ich schon ausprobiert hab).
das problem ist bei mir aber, dass ich nicht so die ahnung von rsa hab.
ich weiß zwar inzwischen, wie das funzt, aber immer wenn ich das mal selbst probiert hab, kam was anderes raus^^

[generic]

turbopower bei sf suchen...

http://sourceforge.net/projects/tplockbox/

[NicNacMan]

thx, lockbox hatte ich schon probiert.
ich habs aber nicht hinbekommen, meinen eigenen key verwenden zu können,
er hat immer welche generiert.

edit: habts mit den beispielen, und der hilfe versucht, aber nichts darüber gefunden.
gibt es vll noch weitere beispiele mit turbopower?

[Jan]

Also wenn du die Keys schon hast (3 Werte) dann ist das ganz einfach...

erstmal die RSA Verschlüsselung als Java-Programm:

Code:

import java.math.BigInteger;
import java.util.Random;
public class RSA {
   private BigInteger n,e,d;
   private int pubkey, privkey;
   RSA(){
      BigInteger p = BigInteger.probablePrime(512, new Random());
      BigInteger q = BigInteger.probablePrime(512, new Random());
      n=p.multiply(q);
      BigInteger f = p.multiply(q).subtract(p).subtract(q).add(BigInteger.ONE);
      e=new BigInteger("3");
      while(f.gcd(e).doubleValue()!=1.0)
         e=new BigInteger(String.valueOf(prim(e.intValue()+1)));
      d=e.modInverse(f);
   }

   public BigInteger encode(BigInteger t){
      return t.modPow(e,n);
   
   }
   
   public BigInteger decode(BigInteger c){
      return c.modPow(d,n);
   }

      private int prim(int a) {
         boolean isprim=true;
         for(int i=a;i<10000;i++){
            for(int j=2;j<i;j++){
               if(i%j==0)
                  isprim=false;
            }
            if(isprim)
               return i;
            isprim=true;
         }
         return 0;
      }
}

vielleicht kannst du da was mit anfangen.

Anosnten musst du nur wissen, dass zur verschlüsselung von werten mit dem RSA-public key du nichts anderes machen musst
als deinen Wert mit E potenzieren und MOD N nehmen musst. Welches davon die werte sind, die du brauchst, musst du wissen, du hast ja die Schlüssel.
Zum entschlüsseln das gleiche allerdings mit dem privaten Teil des Schlüssels D.
also:

X (zu entschlüsselnder Wert) mit D potenzieren und MOD N nehmen.

Das wars.

Gruß
Jan

[NicNacMan]

erstmal danke für den code.
muss gleich mal sehen wie ich den gebrauchen kann.

also die public keys sind:
N = 26967259745684484909271072928592253020339168682042 2133286759
e = 5456431

wenn ich jetzt als code c z.b. 123456 nehme,
dann müsste ich ja c^e mod N rechnen, oder?

ich werds mal probieren, sonst komm ich wieder^^
thx soweit

[negaH]

Im offiziellen DEC sind keine asymmetrischen Algos enthalten, ich habe aber hier http://www.delphipraxis.net/internal...ct.php?t=14699 meinen inoffiziellen Part II des DEC gepostet.
Damit kannst du schon mal mit sehr großen Zahlen rechnen. Du lädst dir dort deine benötigte Version runter -> D5,D6 oder D7.

Um nun mit deinem Beispiel zu rechnen erweiterst du folgendes im Test Projekt

Delphi-Quellcode:

unit TestUnit;

interface

uses Windows, ConsoleForm.....;

implementation

.....blabla

procedure TestRSA;
var
  N,E,M,C: IInteger;
begin
// Zuweisungen
  NSet(N, '269672597456844849092710729285922530203391686820422133286759');
  NSet(E, '5456431');
  NSet(M, 123456);

// modular Potenzieren
  NPowMod(C, M, E, N);  // C = M^E mod N -> CipherText = Message^Exponent mod Modulus  

// Ausgabe
  WriteLn('N: ', NStr(N));
  WriteLn('E: ', NStr(E));
  WriteLn('M: ', NStr(M));
  WriteLn('C: ', NStr(C));
end;


initialization
  RegisterProc('\Test\RSA', '', TestRSA, vk_F8);

....blabla
end.

dann kompilierst du das Projekt, startest das Projekt und drückst F8, in der Console sollten dann deine Ausgaben stehen.

Gruß Hagen

[negaH]

Wenn du das geschafft hast kopierst du die Procedure RSA aus dem gleichen Thread und baust sie wie oben in das Test Projekt ein.

Delphi-Quellcode:

procedure RSA; 
// RSA 1024 Bit verschlüsselung 
var 
  P,Q: IInteger; 
  N: IInteger;    
  E,D: IInteger;  
  U,Dp,Dq: IInteger; 
  M,C: IInteger;    
  X,Y: IInteger;    
begin 
// Schüssel Erzeugung 
// 1. Primzahlen P,Q erzeugen, jeweils 512 Bit groß, N=P*Q erzeugen
  repeat 
    NRnd(P, 512); 
    NBit(P, 512 -2, True); 
    NMakePrime(P, [1, 2]); 
    repeat 
      NRnd(Q, 512); 
      NBit(Q, 512 -2, True); 
      NMakePrime(Q, [1, 2]); 
    until NCmp(P, Q) <> 0; 
    if NCmp(P, Q) < 0 then NSwp(P, Q);    
    NMul(N, P, Q); 
  until NSize(N) = 1024; 
// 2. Exponenten E und D erzeugen
  NDec(P); 
  NDec(Q); 
  NLCM(U, P, Q);   // Phi   
  repeat 
    repeat 
      NRnd(E, NLog2(NSize(N)) * 4);    
      NOdd(E, True); 
    until NGCD1(E, P) and NGCD1(E, Q); 
  until NInvMod(D, E, U) and (NSize(D) >= NSize(E)) and NGCD1(D, N); 
// 3. Hilfsvariablen des privaten Keys erzeugen um die Entschlüsselung 400% zu beschleunigen
  NMod(Dp, D, P);    
  NMod(Dq, D, Q);    
  NInc(P); 
  NInc(Q); 
  NInvMod(U, P, Q);  

// privater und öffentlicher RSA Schlüssel sind nun fertig 
// N,E ist der öffentliche Schlüssel 
// N,D der private Schlüssel, wobei 
// U,Dp,Dq,P,Q dazu gehören damit wir die Entschlüsselung um Faktor 4 beschleunigen können 


// verschlüssele M den PlainText zu CipherText C = M^E mod N 
  NSet(M, 'Unser Geheimnis', 256); 
  NPowMod(C, M, E, N);          

// entschlüssele C per Chinese Remainder Theorem ca. 4 mal schneller als normale Variante 
  NPowMod(X, C, Dp, P); 
  NPowMod(Y, C, Dq, Q); 
  NCRT(Y, NInt([X, Y]), NInt([Dp, Dq]), NInt([U])); 

// Y = M entschlüsselt 
// Ausgabe

  WriteLn('Schlüssel');
  WriteLn('P  : ', NStr(P));
  WriteLn('Q  : ', NStr(Q));
  WriteLn('N  : ', NStr(N));
  WriteLn('E  : ', NStr(E));
  WriteLn('D  : ', NStr(D));
  WriteLn('U  : ', NStr(U));
  WriteLn('Dp : ', NStr(Dp));
  WriteLn('Dq : ', NStr(Dq));
  WriteLn(#13, 'Verschlüsselung');
  WriteLn('M  : ', NStr(M, 256));
  WriteLn('M  : ', NStr(M));
  WriteLn('C  : ', NStr(C));
  WriteLn(#13, 'Entschlüsselung');
  WriteLn('Y  : ', NStr(Y, 256));
  WriteLn('Y  : ', NStr(Y));
  WriteLn(#13'fertig'#13);
end;

Gruß Hagen

[NicNacMan]

respect! :spin2:

hat alles super gefunzt, danke :thumb:

[NicNacMan]

ich hab gestern nacht mal 6-stelligen zahlen mit den public keys e und N verschlüsselt
und dann mit der musterlösung verglichen (das ganze is so ne art test):
24540494168278770214786214883175221254310871335534 1721279658
aber davon stimmte kein wert.

kann es sein, dass man verschiedene lösungen erhält, je nachdem wie man etwas verschlüsselt.
ich hab das soweit verstanden, dass man nicht die ganze zahl hoch e nimmt und dann mod N,
sondern in stückchenweise.
aber kommt dann auch das gleiche raus?

[negaH]

Hi,

ich verstehe deine Frage nicht zu 100%. Anscheinend hast du Musterlösungen poste doch ein par hier. Fakt ist das die Verschlüsselung beim RSA exakt C = M^E mod N ist und nicht anders. Das ist natürlich nur rein mathematisch gesehen korrekt den technologisch werden nun darüber die verschiedenen Protokolle drübergestülpt. Und exakt diese Protokolle beschreiben wie zb. die Zahlen Formate aussehen, wie eine lange Message in Teilstücken zu zerlegen ist, welche zusätzlichen Daten in die Message vor der Verschlüsselung einzuarbeiten ist usw. usw. Es könnte also duchaus sein das deine Testcases schon solchen Regeln unterworfen wurde. Sage mir doch mal was in diesen Testcases und Aufgabenstellungen alles für Randbedingungen existieren.

Eines kann ich dir aber absolut garantieren: mit DECMath wird alles korrekt berechnet falls man die Inputdaten auch im richtigen Format übergibt. Seit Veröffentlichung des DECMaths hier wurde bisher nur ein Fehler in den Funktionen gefunden, übrigens in einer kryptographisch sehr unwichtigen Funktion.

Als ersten Test würde ich mal mit NStr(C, 16) die Ausgabewerte in HEX anzeigen lassen. Dann nimmst du die angeblich korrekte Lösungszahl und zeigst sie mit NSet(L, '12345....123423434'); WriteLn(NStr(L, 16)); ebenfalls in HEX an. Eine zweite Ausgabe von L dann so NSwp(L, piBit); WriteLn(NStr(L, 16)); Dabei wird die Reihenfolge der Bits in L von Litte Endianess in Big Endianess umgewandelt. Ich empfehle das weil ich weis das ein großer "Anfängerfehler" bei solchen Sachen immer wieder die interne Darstellung der Zahlen ist. Es gibt verschiedene math. Libraries die intern in Big Endian speichern und es zulassen das bei der Ausgabe dieser Zahl nicht die math. korrekte Zahl ausgegeben wird.

Gruß Hagen

[NicNacMan]

also das ganze kommt von der seite www.i-nerds.com
man kann halt verschiedene aufgaben "hackits" lösen und bekommt dann punkte dafür.
ich hab mich an "Be a millionaire" versucht, wo man versuchen muss eine online überweisung zu fälschen. (natürlich keine echte *g*)
zuerst braucht man eine gültige pin, mit der kann man dann die tan anfordern, ...

die tan bekommt man per email zugeschickt:
[spoiler]
Sehr geehrter Herr Brathering,

vielen Dank für die Nutzung unseres Online-Transaktionsmanagers.
Um den Transaktionsmanager nun in dem vollen Umfang nutzen zu können, benötigen Sie neben der PIN (Persönliche Identifikations Nummer), auch eine 6 stellige TAN (Trans Aktions Nummer).
Um Ihre hundertprozentige Sicherheit während der Online-Transaktion zu gewährleisten, wurde die TAN mittels "RSA" verschlüsselt.
Benutzen Sie zum entschlüsseln Ihren privaten Schlüssel, den Sie bei der Konto-Eröffnung von uns erhalten haben, und geben die dechiffrierte TAN in dem dafür vorgesehenem Feld ein.

Mit freundlichen Grüßen, Ihre Deutsche Bank... ;)

Ihre verschlüsselte TAN lautet: 24540494168278770214786214883175221254310871335534 1721279658

Special 3 - www.i-nerds.com - /* © 2003 by z3r0x */
[/spoiler]

die public keys bekommt man dann, wenn man einen (nachgebauten) htaccess passwortschutz "geknackt" hat^^:
[spoiler]
RSA Public Key 'N': 26967259745684484909271072928592253020339168682042 2133286759
RSA Public Key 'e': 5456431
[/spoiler]

da ich keinen private key hab, musste ich alle möglichen tans (also alle 6 stelligen zahlen) mit den public keys verschlüssel.
die hab ich dann mit der verschüsselten tan verglichen, aber nichts gefunden.
keine der 999.999 tans passt. :(
aber zum glück hat das mit deiner hilfe nur 59 sekunden gedauert alle tans zu verschlüsseln :thumb:

da ich jetzt aber keine übereinstimmung gefunden hab, bin ich mal wieder ratlos.
ich hatte mir bei den zahlreichen komponenten, die ich schon getestet hatte ein paar mal genauer angeguckt und rausgefunden, dass die rechnung schrittweise gerechnet wird.
999999^5456431 ist auch nicht gerade die kleinste zahl.

ich werd das mit der hexadezimal darstellung gleich mal versuchen.
thx&cu nicnacman

[negaH]

Sie schicken dir eine Liste von möglichen TANs und eine davon soll die richtige sein ?
Wie passt aber nun der öffentliche RSA Schlüssel ins Bild ?
Ich vermute mal eher das du mit dem Privaten Schlüssel des öffentlichen RSA Schlüssel eine beliebige TAN mit einer gültigen digitalen Signatur versehen musst. D.h. du musst zur TAN die du verschickt eine digitale Unterschrift erzeugen. Dazu benötigst du aber den privaten Teil deines RSA Schlüssel's den du nicht in der nötigen Form besitzt. Denn du besitzt N das aus P*Q errechnet wird, du benötigst nun P und Q um den korrekten Entschlüsselungs-Exponenten D erzeugen zu können. Dieser wird dann samt P,Q benötigt um eine digitale Unterschrift zu erzeugen. Nun, deine Aufgabe ist es aus N die beiden Primzahlen P,Q zu errechnen, per Faktorization. Das ist mit < 128 Bit N eventuell noch auf deinem PC möglich, aber bei N mit mehr als 128 Bits sehe ich echt schwarz. Es sei denn die Primzahlen P,Q in N sind von sehr schlechter Qualität, also einfach zu finden.

Gruß Hagen

[NicNacMan]

ich denke mal das mit dem öffentlichen schlüssel aus der email (den man bei der kontoeröffnung bekommen haben soll) ist nur show.
wenn man weiß, dass die tan aus 6 zahlen besteht, dann ist es doch deutliche einfacher alle zu verschlüsseln und zu gucken was rauskommt, als N in p und q zu zerlegen um D rauszubekommen, oder?

ich hab jetzt alle nochmal in hex verglichen und mit der anderen bit reihenfolge, aber wieder nichts gefunden. :roll:

wenn ich es jetzt versuchen würde N in p und q zu zerlegen,
dann müsste ich doch für p alle primzahlen bis sqrt(N) nehmen und gucken, ob N mod p = 0 ist.
soweit ich das verstanden habe darf diese hilfszahl z = (p-1) * (q-1) kein vielfaches von e sein
und e * D mod z muss 1 sein.
:gruebel:

[negaH]

Ja das ist alles richtig. Du musst nicht bis N^0.5 suchen, es gibt weit weit bessere Faktorisierungsverfahren. Denoch, bei großem N, hast du keine wirkliche Chance das N zu zerlegen, es ist einfach viel zu groß. Es sei denn P,Q wurden absichtlich so schlecht gewählt das du eine Chance im Spiel absichtlich bekommen hast. (was ich nicht glaube).

Meine Vermutung ist eher das das Spiel anders verläuft, sprich N,E für andere Aufgaben benötigt wird. Leider habe ich nichts darüber gefunden was man im Spiel eigentlich machen soll. Und ehrlich gesagt interessiert mich das auch nicht so wirklich.

Gruß hagen

[NicNacMan]

ok danke.

wäre auch zu schön gewesen, wenn das so einfach wäre.

thx&cu nicnacman

[gammatester]

Mit diesen Werten

"also die public keys sind:
N = 26967259745684484909271072928592253020339168682042 2133286759
e = 5456431"

kommt man nicht ohne Multipräzisionszahlen aus. Wenn Du DEC nicht benutzen kannst/willst, findest Du auf meiner Seite <http://home.netsurf.de/wolfgang.ehrhardt/misc_de.html#mpint> das mpint_2006-03-12.zip. Darin sind zwei kleine Beispielprogramme zum RSA.

Gruß
Wolfgang

[gammatester]

Sorry,

der vorherige Beitrag war gedacht für

Brauch dringend Hilfe zur RSA-Verschlüsselung !!!
http://www.delphipraxis.net/internal...ct.php?t=79256

Wolfgang