Entwickler-Ecke :: Thema anzeigen - größerer Zahlenbereich als Extended/Real?

Entwickler-Ecke

Delphi Language (Object-Pascal) / CLX - größerer Zahlenbereich als Extended/Real?

Florens - So 31.10.10 14:39
Titel: größerer Zahlenbereich als Extended/Real?

Hallo liebe community,
ich bin neu hier und hoffe, dass ihr mir helfen könnt. Zurzeit versuch ich mich an RSA ver- und entschlüsselung, aber bleiben wir erstmal bei der Verschlüsselung. Hier der Algorithmus mit dem ich es bisher probiert habe:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:

procedure TRSA.Button1Click(Sender: TObject);

var i, j, B, RSAC: Integer;
Buchstabe: Char;
BB: Extended;

begin
PublicKey:=StrToFloat(Edit3.Text);
BB:=1;                               //BB ist quasi der Buchstabe nachdem dieser hoch den Public Key genommen wurde
Edit8.visible:=true;
label10.Visible:=true;
label11.visible:=true;
label11.Caption:='';

for i:=1 to 2 do begin
BB:=1;
Buchstabe:=Edit7.Text[i];
B:=Ord(Buchstabe);

for j:=1 to Trunc(PublicKey) do begin
BB:=BB*B;
end;

RSAC:=trunc(BB) mod(n);      //n ist die Zweite Zahl des Public Keys
Label11.Caption:=Label11.Caption+IntToStr(RSAC)+' ';
end;

Edit8.Text:=Label11.Caption;

end;

(Der Auszug gehört nicht zum gesamten Algorithmus).
Nun ist mein Problem, dass Delphi sobald der Public Key größer als 15 ist immer die Fehlermeldung kommt, dass die rechnung keine gültige Gleitkommaoperation wäre. Ich vermute das Die Zahl einfach zu groß wird und Extended dafür nicht mehr ausreicht. Schließlich gehen alle Zahlen darunter wunderbar.
Meine Frage wäre, ob es einen Datentyp gibt, der einen größeren Zahlenbereich abdeckt als Real oder Extended schließlich schafft der Windows-Calculator solche Rechnungen auch ohne Probleme.

jaenicke - So 31.10.10 14:45

Hallo und :welcome:

Florens hat folgendes geschrieben :

schließlich schafft der Windows-Calculator solche Rechnungen auch ohne Probleme.

Der benutzt auch keine Standarddatentypen. Das wirst du schon selbst berechnen müssen. ;-)

Es gibt aber auch fertige Quelltexte für größere Zahlen.

Florens - So 31.10.10 14:55

jaenicke hat folgendes geschrieben :

Der benutzt auch keine Standarddatentypen. Das wirst du schon selbst berechnen müssen. ;-)

Und wie machen das dann Leute die ganze Texte mit 1024bit Schlüsseln verschlüsseln? die werden doch auch nicht jeden einzelnen Buchstaben durchrechnen...
Danke für die Antwort aber so schnell geb ich nciht auf...sitz seit gestern an diesem Programm und wills jetzt zuende führen. Gibt es eine möglichkeit mit meinem Programm auf den Calculator zuzugreifen und dann einfach das Ergebnis rauszukopieren?

jaenicke - So 31.10.10 14:58

Florens hat folgendes geschrieben :

die werden doch auch nicht jeden einzelnen Buchstaben durchrechnen...

Doch, so habe ich das gemacht. ;-)
Es gibt aber wie gesagt auch einiges an fertigem Code dazu.

platzwart - So 31.10.10 15:13

Such mal nach Bignum z.B.

Gausi - So 31.10.10 15:15

Nebenbei wird RSA (und viele andere Verschlüsselungsverfahren) mit Extended oder anderen Gleitkommatypen sowieso nicht funktionieren. Das sind Ganzzahl-Algorithmen. ;-)

Delete - So 31.10.10 15:20

Florens hat folgendes geschrieben :

...Und wie machen das dann Leute die ganze Texte mit 1024bit Schlüsseln verschlüsseln? die werden doch auch nicht jeden einzelnen Buchstaben durchrechnen...

Da wird natürlich mit Blöcken gearbeitet:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

const
cRSACipherBlockSize : array[TLbAsymKeySize] of Word =
    (cBytes128, cBytes256, cBytes512, cBytes768, cBytes1024);
.
.
.
function  EncryptRSA1024(PublicKey : TLbRSAKey; const InBlock : TRSAPlainBlock1024;
            var OutBlock : TRSACipherBlock1024) : Longint;
  { encrypt plaintext block with 1024-bit RSA public key }
begin
  if (PublicKey.KeySize <> aks1024) then
    raise Exception.Create(sRSABlockSize1024Err);
  Result := EncryptRSAEx(PublicKey, @InBlock, @OutBlock, SizeOf(InBlock));
end;

function  DecryptRSA1024(PrivateKey : TLbRSAKey; const InBlock : TRSACipherBlock1024;
            var OutBlock : TRSAPlainBlock1024) : Longint;
  { decrypt ciphertext block with 1024-bit RSA private key }
begin
  if (PrivateKey.KeySize <> aks1024) then
    raise Exception.Create(sRSABlockSize1024Err);
  Result := DecryptRSAEx(PrivateKey, @InBlock, @OutBlock);
end;

Florens - So 31.10.10 15:22

jaenicke hat folgendes geschrieben :

Florens hat folgendes geschrieben :

die werden doch auch nicht jeden einzelnen Buchstaben durchrechnen...

Doch, so habe ich das gemacht. ;-)
Es gibt aber wie gesagt auch einiges an fertigem Code dazu.

HAH! hab nen Datentyp gefunden: Int64. geht von -2^63 bis 2^63-1. jetzt klappt. probiere gerade mal bis wie weit. Na gut zuverlässig funktioniert das nicht. mit nem Public Key 11|187 macht der aus nem F noch zuverlässig eine 60 bei 31|2431 allerdings kommt -2293 raus was ja nicht sein kann bei mod

Gausi - So 31.10.10 15:28

Int64 kann auch nicht größere Zahlen verwalten als Extended. ;-)

Delete - So 31.10.10 15:29

@Florens

Was Du machst, ist total unsinnig.
Das ist nicht verschlüsselt, sondern ausgetauscht...

Florens - So 31.10.10 15:31

Gausi hat folgendes geschrieben :

Int64 kann auch nicht größere Zahlen verwalten als Extended. ;-)

Ja aber wenigstens kamen jetzt keine Fehlermeldungen...(dafür falsche Zahlen ist auch nicht sehr viel besser...). Hat jemand eine Erklärung für die falschen Zahlen? also mein Algorithmus sieht jetzt wie folgt aus(das Wesentliche habe ich rausgefiltert da Sachen wie label11.visible nichts zur Sache tun):

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

procedure TRSA.Button1Click(Sender: TObject);

var i, j, B, RSAC: Integer;
Buchstabe: Char;
BB: Int64;                     //<---geändert

begin
PublicKey:=StrToFloat(Edit3.Text);
BB:=1;                              

for i:=1 to 2 do begin              //hier ist muss ich noch gucken wie ich die Stringlänge ermittle. Vorerst werden nur die ersten beiden Zeichen chiffriert
BB:=1;
Buchstabe:=Edit7.Text[i];
B:=Ord(Buchstabe);

for j:=1 to Trunc(PublicKey) do begin
BB:=BB*B;
end;

RSAC:=BB mod(n);                               //<----Trunc() entfernt da inkompatible Datentypen
end;

end;

Gausi - So 31.10.10 15:36

Die falschen Zahlen kommen durch den Überlauf. Wenn du bei den 2^63-1 angekommen bist, und noch eins draufaddierst, fängt Int64 wieder von vorne an zu zählen, also bei -2^63.

Gammatester - So 31.10.10 15:44

Florens hat folgendes geschrieben :

Und wie machen das dann Leute die ganze Texte mit 1024bit Schlüsseln verschlüsseln? die werden doch auch nicht jeden einzelnen Buchstaben durchrechnen...

Dein Code hat mindestens drei Probleme:

Delphi-Quelltext

1:
2:
3:

for j:=1 to Trunc(PublicKey) do begin
BB:=BB*B;
end;

Hier wird zuerst BB^Publickey berechnet und dann modulo-reduziert, das ergibt dann die zu großen Zahlen. Eine erste Verbessung ist, sofort nach jeder Multiplikation zu reduzieren.

Delphi-Quelltext

1:
2:
3:

for j:=1 to Trunc(PublicKey) do begin
BB:=BB*B mod n;
end;

Ein weiteres Problem wird sein, daß das für größere Zahlen viel zu lange dauert. Dafür gibt es dann die schnelle binäre modulare Exponentation, die mit maximal 2*(Anzahl Bits in Publickey) Multiplikationen auskommt (statt mit PublicKey).

Das dritte Problem, ist die reine Bitgröße. Alles kleiner gleich 64 Bit ist völlig trivial, einigermaßen sicher sind 1024 Bits besser etwas mehr.

Bei meinen Pascal-RSA-Funktionen [http://home.netsurf.de/wolfgang.ehrhardt/mp_intro.html#rsa_functions] findest Du einiges implementiert, inclusive Beispieltestprogramme für die bekannten Angriffe.

Florens - Mo 01.11.10 22:56

WUUUUUUUUUUUUUUUUUUUT!!! Ich hab gerade mal nen rechner geschrieben der 70^1024 locker und schnell rechnet. In meinem RSA verschlüsselungsalgorithmus muss ein anderer Fehler liegen, sodass mir Delphi sagt es sei eine ungültige Gleitkommaoperation >.<. (Mein rechner ist im Anhang genauso).
Der Rechner rechnet nach dem selben Prinzip wie der RSA Algorithmus:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

procedure TForm1.Button1Click(Sender: TObject);  //Der Rechner
var i,x,y :integer;
z: Extended;

begin
Memo1.Lines.Clear;
x:=StrToInt(Edit1.Text);
y:=StrToInt(Edit2.Text);
z:=1;

for i:=1 to y do begin
z:=z*x;
Memo1.Lines.Add(FloatToStr(z));
end;

Edit3.Text:=FloatToStr(z);
end;

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

procedure TRSA.Button1Click(Sender: TObject);  //RSA

var i, j, B, RSAC, x: Integer;
Buchstabe: Char;
BB: Extended;   //BB ist das z im Rechner und ebenfalls Extended

begin
PublicKey:=StrToFloat(Edit3.Text);
BB:=1;
x:=length(Edit7.Text);
Edit8.visible:=true;
label10.Visible:=true;
label11.visible:=true;
label11.Caption:='';

for i:=1 to x do begin
BB:=1;                             //Z wird 1 gesetzt
Buchstabe:=Edit7.Text;
B:=Ord(Buchstabe);

for j:=1 to Trunc(PublicKey) do begin          //das Trunc kann ich beim Rechner seltsamerweise wegnehmen. Ich wer hier Public Key gleich mal als Integer definieren
BB:=BB*B;                                      //Z * die alte Zahl PublicKey-Mal. Die Zahl wird also offensichtlich nciht zu groß
end;

RSAC:=trunc(BB) mod(n);
Label11.Caption:=Label11.Caption+IntToStr(RSAC)+' ';
end;

Edit8.Text:=Label11.Caption;

end;

Trunc entfernen hat nichts gebracht. ebenfalls mein Verdacht, dass mod mit dem E bei extended nciht klarkommt (4,7827E15) ist ebenfalls falsch nachdem der Rechner das rechnen konnte...)

Flamefire - Mo 01.11.10 23:43

Dann solltest du mal lesen, was hier geschrieben wird: RSA ist GANZzahlig. Warum also Floating point verwenden? Gibt nur hässliche Rundungsfehler. Einziger Vorteil ist der etwas größere Zahlenbereich. Aber halt ungenau!
Und sich einzubilden damit 70^1024 exakt zu berechnen ist quark...
BigNum ist eine Lösung, die das kann.

BenBE - Di 02.11.10 04:53

Zumal BigNum das auch recht schnell rechnen kann - und vor allem korrekt. Und die Modulo-Operationen sind dort beim Potentieren sogar gleich in optimierter Form drinnen, so dass das nicht unnötig bremst.

Gib uns doch mal bitte dein vollständiges "exaktes" Ergebnis für 70^1024.

Zur Kontrolle: Die letzten Stellen, die nicht 0 sind: 4401

Florens - Di 02.11.10 20:46

Flamefire hat folgendes geschrieben :

1. Habs mit meinem Rechner probiert und mit dem Windows Calculator überprüft...Die Ergebnisse für modolu sind identisch also nix da mit Rundungsfehlern (Extended macht ja 19 Stellen nach dem Komma also schätz ich mal schreibt der das nur Beispielsweise 1,[16Stellen]E15 wenn man die Zahl in einen String konvertiert. Die richtige Zahl scheint das Programm aber im Cache zu behalten.
mal nen Beispiel: Mein Rechner->70^1024=2,40100450320503E1889 ->2,40100450320503E1889 mod 187=Okaaay gestern hats noch geklappt jetzt gibt er mir hier ebenfalls ungültige
gleitkommaoperation aus....Der Windows Calculator sagt es soll 69 rauskommen

2. Wie verwende ich BigNum? Ist das ein Datentyp? Bei Google kommt immer nen Rechner den man sich runterladen kann und irgendwelche Mailinglists etc.

3. Das Beispiel bei erstens ist wirklich seltsam...hab gerade bei meinem Rechner sowohl k als auch f mal als Extended gesetzt und 2^50 was ebenfalls mit nem E ausgegeben wird macht der modolu nur die monströse 70^1024 Zahl nicht

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

procedure TForm1.Button2Click(Sender: TObject);
var
k,f: Extended;
begin
f:=StrToFloat(Edit5.Text);
Memo1.Lines.Add(FloatToStr(f));
k:=trunc(z) mod(trunc(f));
Edit6.Text:=FloatToStr(k);
end;

BenBE hat folgendes geschrieben :

Gib uns doch mal bitte dein vollständiges "exaktes" Ergebnis für 70^1024.

Zur Kontrolle: Die letzten Stellen, die nicht 0 sind: 4401

Wie soll ich das machen wenn er die letzten Zeilen vor mir versteckt mit nem E

jaenicke - Di 02.11.10 20:54

Florens hat folgendes geschrieben :

Wie soll ich das machen wenn er die letzten Zeilen vor mir versteckt mit nem E

die versteckt er nicht, die hat er schlicht nicht. Das ist eben die interne Darstellung von Gleitkommazahlen...
Eine gewisse Anzahl Stellen und den Rest dann als "Anzahl Nullen", sprich der Exponent.

Flamefire - Di 02.11.10 21:02

richtig. 1,265E12 heißt 1,265*10^12
und BigNum ist eine Klasse/Unit, die du hier im Forum findest. Ist von BenBE, jaenicke und mir (in der Reihenfolge)

Florens - Di 02.11.10 21:02

jaenicke hat folgendes geschrieben :

Florens hat folgendes geschrieben :

Wie soll ich das machen wenn er die letzten Zeilen vor mir versteckt mit nem E

die versteckt er nicht, die hat er schlicht nicht. Das ist eben die interne Darstellung von Gleitkommazahlen...
Eine gewisse Anzahl Stellen und den Rest dann als "Anzahl Nullen", sprich der Exponent.

Mal der Versuch wiedermal mit meinem Rechner: 17^13=9,90457803290594E15
9,90457803290594E15/17(sollte j eine ganze Zahl rauskommen)=582622237229761 (was der Fall ist)

zum Bignum-> Sooo hab jetzt jemanden gefunden der ebenfalls an RSA gescheitert war aber mit BigNum offensichtlich gut geholfen wurde(http://www.delphi-forum.de/viewtopic.php?t=97227&highlight=bignum). Ich versteh nur noch nicht, wie ich Units in Delphi einfüge und wozu diese überhaupt da sind. Soweit sind wir in Info noch nicht. Morgen hab ich wieder Info dann werd ich einfach mall meinen Lehrer zu BigNum und Units ausquetschen. Insofern 51 92 66 112 84 76 119 142 126 76 92 48 48 76 144 96 84 76 30 96 48 119 84 (Private Key zum entschlüsseln-> (23|187))

jaenicke - Di 02.11.10 21:05

Da ist die Anzahl der Stellen noch ausreichend. Aber bei größeren Zahlen eben nicht mehr.

Und wie schon gesagt wurde: RSA ist doch sowieso ein Algorithmus für ganze Zahlen. Da kannst du also mit Kommazahlen ohnehin nichts anfangen. :nixweiss:

Florens - Mi 03.11.10 00:43

jaenicke hat folgendes geschrieben :

Ja hab Extended genommen weil das ja nen deutlich größeren Zahlenberreich abdeckt und da theoretisch nie eine Kommazahl auftauchen sollte dachte ich geht das so klar. wusste vorher nicht das Extended son Mist mit E macht :(...naja wie gesagt danke für die Hilfe werd mich mal morgen weiter drüber informieren

jaenicke - Mi 03.11.10 00:52

Florens hat folgendes geschrieben :

wusste vorher nicht das Extended son Mist mit E macht :(

Naja, von wegen Mist, überlege dir einmal was das bedeuten würde, wenn tatsächlich bei jeder Rechenoperation im PC so viele Stellen berechnet würden und wenn tatsächlich jede einzelne Zahl so viel Speicherplatz belegen würde...

BenBE - Mi 03.11.10 08:01

Also laut bc:

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:

> 70^1024
24010045032050349897829336107043933679229334992146423448220412706814\
86868333082578133553340069205286132534414845589161753348714754578045\
19913023923040798194920932800692355650641054232396253129068445435369\
41723091486523991681201549497347474723369238537239398448533730166852\
73873475557422978613901632684409113877957960151237467027431685232930\
56361832212379885224076470705304125310144400609642143220058640070479\
26903363200774773090161548101986899212144457593188071000306099306660\
19023382024715071177943534402431729924601868354489109512017545582889\
12781989100521238070890182973235750852695687229936318528420599581058\
89930981042642294753980764858987312531838913768491434961191337287366\
40554486896215426975373615422025826630061312541589124041975789541267\
44601068669647115256265062986820369746907134530167547320977398680045\
69451463199475681447759527781060339101392487014401000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
00000000000000000000000000000000000000000000000000000000000000000000\
000000000000000000000000000000000000000000000000000000
> 70^1024%187
69
> l(70^1024)/l(256)
784.54822616895570628108
> 17^13
9904578032905937
> 17^13/17
582622237229761
> 17^13%17
0

Die Funktion l() bei bc berechnet den Logarithmus Naturalis, die Division durch LN von 256 rechnet in Bytes um. Oder anders ausgedrückt: Das Ergebnis braucht in Binärform 785 Bytes. Extended bietet aber nur 80 Bit, wobei sogar nur 64 Bit Mantisse sind, ein Bit Sign sowie 15 Bit Exponent. Oder anders ausgedrückt: Das kann rein technisch bei Dir schon nicht klappen mit Floats ;-)

BTW: Bignum kann nativ keine Gleitkommazahlen, man kann es aber Reibungslos implementieren, wenn man weiß, was man tut. Nur braucht man für die wenigsten Algorithmen, die solche Zahlen präzise brauchen irgendwelche Gleitkommazahlen, und ansonsten gibt es Abwandlungen dieser Algorithmen, die mit Ganzzahlen rechnen können.

Für RSA jedenfalls reicht BigNum(2) vollkommen aus. Beispiel hattest Du ja bereits verlinkt. Zum Verwenden der Unit diese einfach in dein Projektverzeichnis legen und bei Delphi Unit verwenden sagen. Danach die zusätzlichen Funktionen, die diese Unit bereitstellt verwenden, nachdem Du die Unit in deine Uses-Klausel aufgenommen hast. Rest dazu sagt die Hilfe.

P.S.: Bei Verwendung von BigNum2 möchte ich mindestens eine Namensnennung haben, egal wo, bevorzugt aber im About oder der gepflegten Dokumentation.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!