Berechnungen mit großen Zahlen

Markus696 · Hält's aus hier Beiträge: 7

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

ub60 · Beiträge: 764 Erhaltene Danke: 127

in Delphi:
www.entwickler-ecke....amp;highlight=bignum

Allgemein:
johann.loefflmann.net/de/software/bigal/

Viel Erfolg!
ub60

Markus696 · Hält's aus hier Beiträge: 7

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

Einloggen, um Attachments anzusehen!

Lelf · Beiträge: 42 Erhaltene Danke: 21

Hallo Markus696,

Du mußt die Function
BM_PowerMod(Base, Exp, Module: TBigNumber): TBigNumber;
verwenden.

Gruß Lelf

Markus696 · Hält's aus hier Beiträge: 7

Danke, das habe ich geändert. Der Error bleibt aber leider derselbe.

Martok · Verfasst: Do 06.02.14 20:27

Moin und

!

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.
user defined image

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

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Delphi-Laie · Verfasst: 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.

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Markus696 hat folgendes geschrieben :

Danke, das habe ich geändert. Der Error bleibt aber leider derselbe.

In meinem MPArith-Paket (open source freeware) findest Du eine RSA-Unit mit standardisierten und getesten RSA-Funktionen. Neben den Tests sind im Archiv supptest.zip noch 6 RSA-Beispielprogramme, die RSA-Anwendung und -Attacken demonstieren.

Tranx · Verfasst: 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?

_________________
Toleranz ist eine Grundvoraussetzung für das Leben.

Xion · Verfasst: Fr 07.02.14 11:24

Es gibt deshalb bessere Verfahren dafür
z.B: www.gm.fh-koeln.de/~...isMa/Erg03_DisMa.pdf

Damit sollte man ganze ohne bignum auskommen und es ist vermutlich fies schnell.

_________________
a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)

Martok · Verfasst: 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

markieren

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

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Gammatester · Beiträge: 328 Erhaltene Danke: 101

Mit dem MPArith-Rechner ist die Zeit (incl. parsing) gerade noch meßbar:

markieren

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 user profile icon

Martok schon sagte) man nicht erst die riesige Potenz aus, sondern benutzt sowas wie die schnelle Binäre modulare Exponentiation.

Markus696 · Hält's aus hier Beiträge: 7

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:

markieren

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 · Verfasst: 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

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme