Autor Beitrag
g1o2k4
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 493



BeitragVerfasst: Mo 05.05.08 16:01 
hi

ich hab den rsa algorithmus implementiert aber leider dauert das verschlüsseln mit großen zahlen extrem lang...

das rsa prinzip lautet ja einfach:
ausblenden Delphi-Quelltext
1:
nachricht^schlüssel modulo n					

wobei n das schlüssel modul ist.

im moment sieht das bei mir noch so aus:

für große exponenten:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
  e := 1;
  for i := 1 to y do        // (x^y) mod z = e.
    e := (e*x) mod z;
  result := e;


bzw für kleinere eponenten:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
  e := 1;
  for i := 1 to y do        // (x^y) mod z = e.
    e := (e*x);

  e := e mod z;
  result := e;


für exponenten über 10000 dauert die erste variante mehr als 10 sekunden für 5 chars...
sind hier zufällig kryptologen oder mathematiker, die mir sagen können wie ich den algorithmus verfeinern kann, damit es schneller läuft ?

z.b. sowas wie:
e := 1;

e := e*x;
e := e*e;
e := e*e;

so kommt man ja nach z.b.
ausblenden Delphi-Quelltext
1:
2:
3:
4:
e := 1*2;
e := 2*2;   //2^1*2^1
e := 4*4;   //2^2*2^2
e := 16*16//2^4*2^4


was ja theoretisch schneller ist als jeden schritt der potenz also x*x*x*x*x*x... einzeln zu schreiben oder ? und an geeigneten stellen modulo z rechnen.

aber wie bekommt man dieses schema in einen algorithmus ? der exponent muss ja kleiner als der schlüssel bleiben und da der exponent ungerade ist muss man ja noch ein paar schritte mehr machen...
Sirke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 208
Erhaltene Danke: 2



BeitragVerfasst: Mo 05.05.08 16:39 
Im Studium haben wir Square & Multiply gelernt (genau das was du dort an sich beschreibst), was jedoch recht umständlich zu implementieren ist.
Rechnungen wie 17^300 sind damit aber im "Kopf" bzw mit einfachem Taschenrechner möglich!

Dagegen lässt sich folgende Funktion leichter einbinden: Diskrete Exponentialfunktion
g1o2k4 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 493



BeitragVerfasst: Mo 05.05.08 17:27 
ja square und multiply sieht perfekt aus...

aber wie ich das aus anhieb implementieren müsste wüsste ich jetzt auch nicht.
haste da zufällig nen delphi example code ?
Jakob_Ullmann
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1747
Erhaltene Danke: 15

Win 7, *Ubuntu GNU/Linux*
*Anjuta* (C, C++, Python), Geany (Vala), Lazarus (Pascal), Eclipse (Java)
BeitragVerfasst: Mo 05.05.08 17:33 
Benutze doch einfach die Funktion power.
g1o2k4 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 493



BeitragVerfasst: Mo 05.05.08 17:37 
user profile iconJakob_Ullmann hat folgendes geschrieben:
Benutze doch einfach die Funktion power.


ich benutze kein integer sondern bigints. da ist power zu lahm. wie gesagt das sind potenzen im 10k+ bereich...

könnte mir das jemand in delphi code hinschreiben ? ich check den code von der seite nicht so ganz...


was ist das delphi synonym für folgenden c code ?
if ( x & 1 )
Jakob_Ullmann
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 1747
Erhaltene Danke: 15

Win 7, *Ubuntu GNU/Linux*
*Anjuta* (C, C++, Python), Geany (Vala), Lazarus (Pascal), Eclipse (Java)
BeitragVerfasst: Mo 05.05.08 17:55 
Ich verstehe den Code auch nicht wirklich, aber wahrscheinlich sieht das dann so aus:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
for i := 1 to n do
begin
  res := res * res mod m;
  if b_i = 1 then
    res := (res * a) mod m;
end;
Sirke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 208
Erhaltene Danke: 2



BeitragVerfasst: Di 06.05.08 00:46 
Das Porblem an Square & Multiplay ist, dass man den Exponenten als Binärzahl von vorne nach hinten lesen muss (das sind diese b_i). Das ist aber sehr umständlich, da man zuvor die Zahl binär verkehrt herum aufschreiben müsste. Die zweite von mir gepostete Funktion dagegen beruht auf Square & Multiply nur ist wesentlich einfacher ;-)
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
function expmod( b, x, m : Integer) : Integer;
begin
  Result := 1;
  while ( x > 0 ) do
  begin
    if (x mod 2) > 0 then
      Result := ( Result * b ) mod m;
    b := ( b * b ) mod m;
    x := x div 2;
  end;
end;


Das ganze kann man natürlich auch als Funktion von die BigNum Unit oder ähnlichem umschreiben!
g1o2k4 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 493



BeitragVerfasst: Di 06.05.08 06:32 
danke. aber die hatte ich schon selbst implementieren können... tictech.wordpress.co...se-zahlen-in-delphi/

aber beim square und multiply würde man nochmal die hälfte weniger durchläufe brauchen, das wäre es mir schon wert, auch wenn die disk. exp.funktion schon gute dienste tut :P

könntest du mir vielleicht die variablen beim schnellen potenzieren algo von wikipedia erklären ? vielleicht bekomm ichs dann selbst hin.
was genau ist for i=1..n ? bzw was ist n ?
Sirke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 208
Erhaltene Danke: 2



BeitragVerfasst: Di 06.05.08 15:02 
Bei Square & Multiplay muss man den Exponenten in Binär darstellen und dann von vorne nach hinten durchlafen. Das macht die For-Schleife in dem Pseudocode! Dabei ist dann n die Bitlänge des Exponenten. Die Pseudovariable b_iist dann das i-te Bit des Exponenten. Hoffe das ist verständlich ;-)

Problem ist eben, dass man den Exponenten Bit für Bit durchlaufen muss. Mich würde es sehr interessieren, welches Verfahren man gut und vorallem schnell implementieren könnte!

Welche Bibliothek benutzt du für die großen Zahlen? Kannst du mal n link posten bitte, dann würde ich das mit der mal testen!
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Di 06.05.08 15:25 
Ich benutz meine BigNum2-Biblio dafür ... die nutzt übrigens bei ExpMod (Exponentation Modulo) Square & Multiply und da hab ich ehrlichgesagt keine Probleme mit der Performance (das hängt bei meiner Lib eher wo anders ;-)) ... Z.B. am fehlenden Karatsuba :P

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Sirke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 208
Erhaltene Danke: 2



BeitragVerfasst: Di 06.05.08 15:51 
Hast du mal einen Link dazu? Ich habe noch nie mit so großen Zahlen gearbeitet, weil ich noch nie Praxisnahe mit Delphi RSA oder änliches rechnen musste - würde das aber gerne mal testen!

Musste dazu bisher immer Java verwenden, was mir durch mein Studium aufgezwungen wurde :?
g1o2k4 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 493



BeitragVerfasst: Di 06.05.08 16:00 
user profile iconBenBE hat folgendes geschrieben:
Ich benutz meine BigNum2-Biblio dafür ... die nutzt übrigens bei ExpMod (Exponentation Modulo) Square & Multiply und da hab ich ehrlichgesagt keine Probleme mit der Performance (das hängt bei meiner Lib eher wo anders ;-)) ... Z.B. am fehlenden Karatsuba :P



ich find die ExpMod funktion nicht, haste ne neuere version geschrieben ?
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Di 06.05.08 16:19 
Scheint so, ich muss mal die aktualisiertere Fassung hochladen ... U.U. gleich unter Open Source Units ...

Aber bis dahin: Siehe im Anhang von www.delphi-forum.de/....php?p=246388#246388, Funktion BM_Power:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
Function BM_Power(Base, Exp: TBigNumber): TBigNumber;
Var
    X: Integer;
Begin
    SetLength(Result, 1);                                                       //Set 1 as the Result
    Result[0] := 1;

    For X := Length(Exp) * 8 - 1 Downto 0 Do
    Begin
        BM_Assign(Result, BM_Multiply(Result, Result));

        If Exp[X Div 8And ($01 Shl (X Mod 8)) <> 0 Then
            BM_Assign(Result, BM_Multiply(Result, Base));
    End;
End;


Dort noch an den beiden nötigen Stellen das Module einzubauen, sollte eigentlich nicht das Thema sein ;-)

BTW: Es reicht, das Modulo nach jedem Schleifendurchlauf auszuführen - nach jeder Multiplikation hält zwar die Zahlen kleiner, frisst dafür aber u.U. auf Grund der Division mehr Rechenzeit.

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
g1o2k4 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 493



BeitragVerfasst: Di 06.05.08 16:57 
user profile iconBenBE hat folgendes geschrieben:
U.U. gleich unter Open Source Units ...


wäre super ! denn die unit gehört in jede standard lib sammlung :P

schade das sowas nicht standardmäßig im delphi sprachumfang ist...oder im sprachumfang von anderen sprachen...man braucht sowas zwar selten, aber ich finde es blöd auch nur ansatzweise eingeschränkt zu werden....
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Di 06.05.08 20:02 
Bei Java hast Du einen BigInteger gleich in der Standard-Bibliothek ...

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
Sirke
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 208
Erhaltene Danke: 2



BeitragVerfasst: Di 06.05.08 20:11 
Ich habe Square & Multiply mal implementiert, sodass folgende Funktion dabei herausgekommen ist:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
function SquareAndMultiply( B, X, M: TBigNumber ): TBigNumber;
const C: array [0..7of Byte = ( $01$02$04$08$10$20$40$80 );
var i, j   : Integer;
begin
  Result := BMD_StrToBigNum( '1', false );
  for i := High(X) downto 0 do
  begin
    for j := 7 downto 0 do
    begin
      Result := BM_Modulo( BM_Multiply( Result, Result ), M );
      if (X[i] AND C[j] ) > 0 then
        Result := BM_Modulo( BM_Multiply( Result, B ), M );
    end;
  end;
end;


Für große Zahlen liefert das momentan die besten Zeiten, ist aber sicherlich noch ausbaufähig!
g1o2k4 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 493



BeitragVerfasst: Di 06.05.08 22:26 
ich hab bei der disk exp funktion jetzt leider ein problem...

das bitweise verschieben hatte ich so gelöst:
ausblenden Delphi-Quelltext
1:
keystring := inttostr(strtoint(keystring) shr 1);					


im keystring war der schlüssel (exponent), dieser ist jetzt aber leider so groß, dass er nicht mehr in nen string konvertiert werden kann.
wie shifte ich das jetzt nach rechts ? oder wie löse ich den vorgang mit Tbignumber ?
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Di 06.05.08 23:36 
SHR kannst Du dir schnell selber über den Direktzugriff auf die Einzelbytes des BigNums implementieren ...

Für SHL 2 einfach Mul 2 rechnen (Geht aber ähnlich wie SHR auch linear zu implementieren ...)

Einfach vom MSB zum LSB alle Bytes um 1 Bit shiften und merken, ob das LSb gesetzt war, um dies ggf. in der nächsten Stelle als MSb einzutragen ... Werd ich aber ggf. gleich in's Release mit aufnehmen ...

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
g1o2k4 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 493



BeitragVerfasst: Mi 07.05.08 13:47 
wäre echt klasse. sag bescheid wenn dein release da ist.
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Sa 17.05.08 18:47 
k, Release gibt's jetzt an prominenter Stelle bei den OpenSource-Units. Dort hab ich 2 Units von mir angehängt,einmal BigNum2, zum anderen eine SEHR alte Unit BigNum_Lib, die OOP arbeitet, allerdings in Bezug auf Primzahlen ein paar kleinere Vorteile hat ;-)

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.