![]() |
Potenzieren mit sehr großen Zahlen ohne modulus?????
Hallo
Ich möchte eine 512-bit zahl mit einer 512-bit Zahl potenzieren ohne modulus operation! Mathematisch ist das natürlich eine so verdammt große Zahl, dass kein Speicher dazu ausreichen würde! die Formel sieht aber so aus a,b,x,y seien 512-bit Zahlen die keinen ggt haben
Code:
d.h
ergebnis = a^x * b^y // Wobei y negativ ist
es entpricht
Code:
Aus theoretischen Überlegungen weiß ich dass das Ergebnis ganz sicher kleiner ist als 512-bit!
ergebnis = a^x / b^y
Kann man das irgendwie berechnen, ohne jeweils extra b^y und a^y berechnen zu müssen?? Danke Grüße Dr.Hackstable |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Mit welchem Datentyp rechnest du eigentlich?
|
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
(a^x)/(a^y) = a^(x-y)
|
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Jetzt hast du die Gleichung umgestellt, und?
Aus der Informatik wissen wir, das sich alle Rechenoperationen aus der Addition zusammensetzen! |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Mach es doch so:
Delphi-Quellcode:
Ungetestet, aber ich potenziere so lange mit a, bis ich nicht mehr darf, oder bis das Zwischenergebnis größer als ein bestimmter Wert ist. Dann wird so lange durch b geteilt, bis ich nicht mehr darf, oder das Zwischenergebnis wieder kleiner als ein Minimalwert ist. Das wird so lange wiederholt, bis nichts mehr zu tun ist.
Function MegaPotenzierer (a,b,x,y : Extended) : Extended;
Const ccZero = 1E-5; // Hab vergessen, wie man floats auf 0 prüft ccMin = 0.000001; // kleinstes Zwischenergebnis ccMax = 100000000; // höchstes Zwischenergebnis Begin Result := a; x:=x-1; Repeat while (x>ccZero) do begin Result := result * a; x:=x-1; if (Result > ccMax) Then Break; // jetzt nicht mehr weiterrechnen End; while (y>ccZero) do begin Result := result / b; y := y - 1; If Result > ccMax Then Break; End; Until (x<ccZero) and (y<ccZero); // Heisst das nicht 'IsZero (x)'? End; |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
a sollte ungleich b sein !
a <> b also klappt das nicht mit (x-y) was gehen würde wäre vielleicht:
Code:
Hilft mir aber auch nicht viel! Ich rechne mit IInteger Zahlen von Decmath!
ergebnis = exp ( x*lna - y*lnb)
Man kann damit beim Exponent bis max_integer rechnen, mehr würde auch keinen Sinn machen! Aber trotzdem müsste es doch eine Lösung für mein Problem geben, da das Ergebnis kleiner ist als 512-bit!?? |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Um dein Problem einmal umzuformulieren:
Du möchtest z.B. 4^9 / 5^7 = 3 ausrechnen, ohne vorher 4^9 (262144) bzw. 5^7 (78125) vollständig ausrechnen zu müssen (ich hab' jetzt mal deine 512 Binärstellen auf 1 Dezimalstelle reduziert, das Ergebnis passt auch in eine Dezimalstelle). Da es sich nach deiner Aussage um teilerfremde Zahlen handelt, wüßte ich dafür keinen Ansatz. Einfacher wäre es natürlich, wenn du mit a*(2^x) und b*(2^y) rechnen würdest - aber das wird wohl nicht gehen. |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Es gäbe da einen Weg:
Berechne die Primfaktorzerlegung von a^x und b^y. Dann kannst du beide Tabellen der Primzahlexponenten jeweils bei gleicher Basis die Exponenten subtrahieren. Das was übrig ist ist die Tabelle der Primzahlexponenten von a^x/b^y und wird einfach ausmultipliziert. In Unit NCombi.pas findest du die Funktionen NPowerTable() und NPrd() die das mit den Faktultäten demonstrieren. Das wäre der einzigste Weg der mir einfällt im Moment um wirklich das Ergebnis aufs letzte Bit exakt ausrechnen zu können. Gruß Hagen |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
hey thx, stimmt:-D wann man das machen kann:-)
NPowerTable() und NPrd() Die zwei Funktionen habe ich nicht ganz kapiert :oops: , könntest du mir ein kleines Beispiel geben wie ich eine Primfaktorzerlegung mit einem IInteger zahl machen kann. Zitat:
|
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Zitat:
Zitat:
|
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Vergesst meinen Vorschlag, habe übersehen das ja auch die Exponenten rießig sein sollen.
Wofür brauchst du das ? Du musst dir nämlich im klaren sein das in den meisten Fällen keine bis aus letzte Bit exakte Lösung möglich sein kann. Die meisten Lösungen ergeben gebrochene Zahlen und viele davon mit unendlichen Nachkommastelen. Du wirst es also in den seltensten Fällen ganz exakt ausrechnen können. Enzigste "Möglichkeit" wäre die Division mit Rest zu machen, nur würde dann der Rest teilweise gigantisch groß werden. Du betonst "ohne modulare division" so stark, hat das einen Grund ? Gruß Hagen |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Zitat:
Dies ist mit kleinen Zahlen noch machbar, aber nicht wenn alle 4 Parameter um die 512 Bit haben sollen, besonders nicht wenn die Exponenten so gigantisch sind. Gruß Hagen |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Es ging um eine Schwachstelle von RSA, unter folgenden Voraussetzungen:
2 offentlich schlüssel: (n,e) (n,f), n sei die selbe und ggt(e,f)=1 Mit dem erweiterten eukl. Algo(e,f) hat man x und y. (1=e*x+y*f) -> eine exakt gleiche Nachricht mit dem selben n wird von beiden verschlüsselt: Ce = m^e (mod n) Cf = m^f (mod n) Dann kann man aus Ce, Cf,x ,y die Nachricht berechnen, was wiederum zu meinem Problem führt: Ce^x * Cf^y = (m^e)^x*(m^f)^y = m^(e*x+y*f) = m^1 = m Ich wollte wiessen, inwieweit das machbar ist:-) und hätte auch einen 512-bit-Fall um das zu testen.... :wink: |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Zitat:
|
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Sag das doch gleich.
Deine Formel Ce^x * Cf^y = (m^e)^x*(m^f)^y = m^(e*x+y*f) = m^1 = m ist unvollständig ! Wir arbeiten beim RSA immer in einem modularem Ring zu N, ergo richtig ist Ce^x * Cf^y == m mod N m = Ce^x * Cf^y mod N m = (ce^x mod N * Cf^y mod N) mod N Kopiere nachfolgenden Source in TestUnit.pas und registriere mit RegisterProc('\RSA\Test', '', Test, vk_F8) diese Procedure. Dann startest du Test.exe und drückst F8. Fertig. Dieser Angriff kann also nur funktionieren weil beide Parteien das gleiche N benutzen und die Message M NICHT mit Zufallsdaten expandiert haben. Es ist also WICHTIG beim RSA die Nachricht M vor der Verschlüsselung immer mit Zufall zu expandieren ! Besonders bei digitalen Signaturen ist dies wichtig. Gruß Hagen
Delphi-Quellcode:
procedure Test;
const KeySize = 256; QSize = KeySize div 2; PSize = KeySize - QSize; var P,Q,U: IInteger; N: IInteger; E1,D1,C1: IInteger; E2,D2,C2: IInteger; M,X,Y: IInteger; begin // bilde RSA Domain, P,Q,N repeat NRnd(P, PSize); NBit(P, PSize -2, True); NMakePrime(P, [1, 2]); repeat NRnd(Q, QSize); NBit(Q, QSize -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) = KeySize; WriteLn('N : ', NStr(N)); // erzeuge public/private Ver/Entschlüsselung Exponenten NDec(P); NDec(Q); NLCM(U, P, Q); repeat repeat NRnd(E1, NLog2(NSize(N)) * 4); NOdd(E1, True); until NGCD1(E1, P) and NGCD1(E1, Q); until NInvMod(D1, E1, U) and (NSize(D1) >= NSize(E1)) and NGCD1(D1, N); repeat repeat NRnd(E2, NLog2(NSize(N)) * 4); NOdd(E2, True); until NGCD1(E2, P) and NGCD1(E2, Q) and NGCD1(E1, E2); until NInvMod(D2, E2, U) and (NSize(D2) >= NSize(E2)) and NGCD1(D2, N); WriteLn('E1 : ', NStr(E1)); WriteLn('E2 : ', NStr(E2)); NSet(M, 'unser Geheimnis', 256); NPowMod(C1, M, E1, N); // verschlüssele M mit E1 NPowMod(C2, M, E2, N); // verschlüssele M mit E2 WriteLn('C1 : ', NStr(C1)); WriteLn('C2 : ', NStr(C2)); NGCD(U, X, Y, E1, E2); // erweiterter GCD() NPowMod(U, NInt([C1, C2]), NInt([X, Y]), N); // U = C1^X * C2^Y mod N WriteLn('M : ', NStr(M, 256)); WriteLn('M'' : ', NStr(U, 256)); // U = M WriteLn; end; |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Zitat:
Es muß sogar so sein, da es ansonsten ja für Primzahlfaktoren[a^x] / Primzahlfaktotren[b^y] = z, für Z keine Primzahlfaktorenzerlegung existieren könnte. Und dies ist unmöglich da wir Potenzen vor uns haben. Im schlechtesten Falle ist a und b eine Primzahl selber und die Primzahlzerlegung wäre a^x = a^x und b^y = b^y, dann wäre die Zerlegung unseres rationalen Produktes exakt a^x * b^-y. Unsere Zahl Z zerlegt sich also in die Primzahlen a und b mit den Primzahlexponenten a^x * b^-y. Gruß Hagen |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Wahrscheinlich stecke ich in diesem Thema nicht tief genug drin. :stupid:
Ich war (bin) halt der Auffassung, dass a^x (x ungleich 0) keine anderen Primfaktoren haben kann als a selbst. Außerdem wüsste ich nicht, dass man eine rationale, nicht ganze Zahl (b^-y) als Primfaktor bezeichnen kann. Zu "Primzahlfaktoren[a^x] / Primzahlfaktotren[b^y] = z": Hier ist das z aber nur das ganzzahlige Ergebnis der Division, oder? Somit kann man doch eigentlich von der Faktorisierung von a^x und b^y keine Schlüsse auf z ziehen. :gruebel: |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
Zitat:
Wenn As{} = Primzahlfaktoren(a^x) ist dann beschreibt logischerweise As{} exakt diese Zahl. Es ergibt sich As{} / Bs{} = a^x / b^y = a^x * b^-y = a^-x * b^y = Z(r). Z ist dabei einfach eine rationale/gebrochene Zahl ein Bruch mit N / D. Man kann diese Zahl also über den Nominator und Denominator sehr wohl auch als "Primfaktorzerlegung" darstellen. Mit As{} / Bs{} sowas wie (2^3 * 3^5 * 5^0) / (2^2 * 3^6 * 5^4) also als Bruch. Nun kann man per einfachen Kürzungen der Exponenten arbeiten was dann (2^1 * 3^0 * 5^0) / (2^0 * 3^1 * 5^4) = (2^1 * 3^-1 * 5^-4) ergäbe. Ob man dann noch matheamtisch von einer Primfaktorzerlegung einer rationalen Zahl reden wird weis ich selber nicht. Gruß Hagen |
Re: Potenzieren mit sehr großen Zahlen ohne modulus?????
@negaH:
oops, hab ich wohl nicht ganz aufgepasst. Mit mod N ist das natürlich kein problem! Klappt jetzt auch wunderbar. thx nochmal für deine Erklärungen. |
Alle Zeitangaben in WEZ +1. Es ist jetzt 13:54 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz