Entwickler-Ecke
Delphi Language (Object-Pascal) / CLX - Berechnungen mit großen Zahlen
Markus696 - Do 06.02.14 18:04
Titel: Berechnungen mit großen Zahlen
Hallo,
für ein Schulprojekt muss ich ein Programm entwerfen, welches in der Lage ist eine Information mittels des RSA-Verfahrens zu verschlüsseln. Das Projekt ist theoretisch fertig, bloß in der Praxis scheitert es leider.
Ich muss Berechnungen wie etwa 202122222324252226^64869761 mod 1607202089 vornehmen können und das löst leider immer einen Error aus. Die einziges Nachricht die ich verschlüsseln kann ist 1, denn 1 ist RSA-Verschlüsselt ja immernoch 1 ^^ Sonst liegen alle Berechnungen für mich außerhalb des möglichen. Das ist auch das erste Mal, dass ich beim programmieren mit Zahlen dieser Größenordnung in kontakt komme, folglich fällt es mir sehr schwer damit umzugehen. Kann mir jemand helfen? Ich bitte darum.
Mit freundlichen Grüßen
Markus
Markus696 - Do 06.02.14 19:42
Vielen Dank für die Hilfe! Ich habe mir die BigNum2.pas heruntergeladen und bei uses eingebunden, sowie die entsprechend benötigten Funktionen BM_Power und BM_Modulo zur Berechnung der Verschlüsselung benutzt. Nun bekomme ich leider einen Error aus der BigNum2-Unit, mit dem ich als Laie so gar nichts anfangen kann :(
Lelf - Do 06.02.14 19:55
Hallo Markus696,
Du mußt die Function
BM_PowerMod(Base, Exp, Module: TBigNumber): TBigNumber;
verwenden.
Gruß Lelf
Markus696 - Do 06.02.14 20:07
Danke, das habe ich geändert. Der Error bleibt aber leider derselbe. :(
Martok - Do 06.02.14 20:27
Moin und :welcome:!
Das liegt daran, dass das optimierter 32bit-Assembler ist, du aber vermutlich für eine andere Plattform compilierst. Einfachster Fix: stell das unter Projekt->Projekteinstellungen auf i386 um.
EDIT: man sagt mir grade, dass der 32bit-Compiler dann auch separat installiert und konfiguriert sein muss.
Ist aber an der Stelle egal, du kannst die komplette Funktion Int64divModCar einfach auskommentieren/rauslöschen, soweit ich sehe wird die nirgendwo benutzt.
Grüße,
Martok
Delphi-Laie - Fr 07.02.14 00:08
Markus bzw. Markus696, schau Dir mein Programm "Langzahlentaschenrechner" (auch in diesem Forum zu finden) an, in das habe ich derzeit 8 (soweit ich mich erinnere) verschiedene pascalbasierte Langzahlenbibliotheken integriert. Es sollen noch welche hinzukommen, nur zur Zeit liegt das Projekt brach, wird aber mittelfristig wieder aufgenommen werden.
Auch bignum (genaugenommen bignum2) habe ich dort erfolgreich integriert, allerdings sehr wenige Korrekturen (oder nur eine?) daran vorgenommen. Um eigene Funktionen ergänzt habe ich allerdings alle Langzahlenbibliotheken.
Tranx - Fr 07.02.14 10:52
 Markus696 hat folgendes geschrieben  : |
202122222324252226^64869761
|
Wow, das muss ja schon eine Zahl sein, die selber schon 1.122.611.048 Ziffern hat. Die dann noch modular durch 1.607.202.089 zu teilen, echt, wie lange rechnet selbst ein PC eigentlich daran?
Martok - Fr 07.02.14 11:28
| Tranx hat folgendes geschrieben : |
| Wow, das muss ja schon eine Zahl sein, die selber schon 1.122.611.048 Ziffern hat. Die dann noch modular durch 1.607.202.089 zu teilen, echt, wie lange rechnet selbst ein PC eigentlich daran? |
Mit Mathematica nicht messbar, modulare Arithmetik hat ein paar nette Eigenschaften und nur deswegen funktioniert RSA überhaupt sinnvoll ;)
Quelltext
1:
2:
3:
| In[3]:= AbsoluteTiming[PowerMod[202122222324252226, 64869761, 1607202089]]
Out[3]= {0., 1357487496} |
| Xion hat folgendes geschrieben : |
| Damit sollte man ganze ohne bignum auskommen und es ist vermutlich fies schnell. |
Deswegen sollte man auch bei BigNum2 die PowerMod-Funktion direkt verwenden, die direkt auf dem passenden Ring potenziert.
Nicht immer hat man ja so kleine Zahlen wie hier ;)
Gammatester - Fr 07.02.14 11:56
Mit dem MPArith-Rechner ist die Zeit (incl. parsing) gerade noch meßbar:
Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
| D:\Xtools\MPArith>t_calc.exe
T_CALC using MPArith V1.27.01 (31/32 bit) [mp_calc] (c) W.Ehrhardt 2006-2013
Karatsuba cutoffs: mul/sqr = 16/32, Toom-3 cutoffs: mul/sqr = 32/64
Burnikel/Ziegler div cutoff = 32, MaxBit = 520093696, MaxFact = 22623931
Type "?<enter>" to get some info about commands, "\q" or "quit" to end.
[D]:=> 202122222324252226^64869761 mod 1607202089
Result = 1357487496
[D]:=> .
Time = 0.145 ms |
Selbstverständlich rechnet (wie
Martok schon sagte) man nicht erst die riesige Potenz aus, sondern benutzt sowas wie die schnelle
Binäre modulare Exponentiation [
http://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation#Bin.C3.A4re_modulo-Exponentiation].
Markus696 - Fr 14.02.14 23:53
Vielen Dank, ich hab das Problem jetzt mittels der Moduloexponentation gelöst. Nun hat sich bloß ein weiteres im Zusammenhang mit der Umwandlung eines Strings in ein array of integer (ein feld für jedes char) ergeben. Ich habe dazu folgendes formuliert:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
| type
array_of_int = array of integer;
var
intfeld: array_of_int;
procedure Trsa.b_textzASCIIClick(Sender: TObject);
var txt: string; i: integer;
begin
txt:= m_klartext.text;
for i:=1 to length(text) do
intfeld[ ( i - 1 ) ]:= ord( txt[i] );
end; |
Ich bekomme beim Aufruf der Button-Prozedur immer eine Exception, kann aber beileibe meinen eigenen Denkfehler nicht finden. Gehört nicht mehr ganz zum Thema, aber immernoch zum selben projekt, deswegen stelle ich die Frage hier. Weiß jemand Rat? (External: SIGSEGV)
Moderiert von Martok: Delphi-Tags hinzugefügt
mandras - Sa 15.02.14 02:44
Du mußt vorher die Länge des Feldes festlegen mittels setlength würde ich auf die Schnelle tippen
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 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!