![]() |
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 01:40 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 by Thomas Breitkreuz