Potenzieren mit sehr großen Zahlen ohne modulus?????

[negaH]

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

[negaH]

Zitat von Flocke:

Zitat von Dr.Hackstable:

a,b,x,y seien 512-bit Zahlen die keinen ggt haben

Zitat von negaH:

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.

Welche gleiche Basis ?

Die Basen der Primfaktorzerlegungen. Im Grunde hat man zwei Tabellen wie "2^e1 * 3^e2 * 5^e3 ..." für jeweils a^x und b^-y. Nun geht man diese Tabelle durch und subtrahiert jeweils die Exponenten aller gleichen Basen. Also wenn für a^x -> 2^e1 * .... und für b^y = 2^d1 *... gilt dann wird einfach 2^(e1-d1).... berechnet. Dies ist das endgültige Ergebniss als Primzahlfaktorzerlegung und muß dann nur noch ausmultipliziert werden.
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

[Dr.Hackstable]

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....

[Flocke]

Zitat von Dr.Hackstable:

a,b,x,y seien 512-bit Zahlen die keinen ggt haben

@Hagen: Ich habe deinen Beitrag schon verstanden. Ich wollte nur darauf hinweisen, dass er das bei teilerfremden Zahlen nicht anwenden kann (-> keine gemeinsamen Primfaktoren -> keine gemeinsamen Basen).

[negaH]

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;

[negaH]

Zitat von Flocke:

Zitat von Dr.Hackstable:

a,b,x,y seien 512-bit Zahlen die keinen ggt haben

@Hagen: Ich habe deinen Beitrag schon verstanden. Ich wollte nur darauf hinweisen, dass er das bei teilerfremden Zahlen nicht anwenden kann (-> keine gemeinsamen Primfaktoren -> keine gemeinsamen Basen).

wenn der ggT() = 1 ist dann heist dies nicht das zwangsläufig bei der Primfaktorzerlegung der Potenzen nicht gemeinsamme Basen existieren. Und selbst wenn dann heist dies dann nur das in der "subtrahierten" Primzahlfaktorization diese nicht gemeinsammen Basen wieder auftauchen. Entweder als b^x oder b^-y.

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

[Flocke]

Wahrscheinlich stecke ich in diesem Thema nicht tief genug drin.

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.

[negaH]

Zitat:

Zu "Primzahlfaktoren[a^x] / Primzahlfaktotren[b^y] = z": Hier ist das z aber nur das ganzzahlige Ergebnis der Division, oder?

Nein es beschreibt quasi als rationale Primfaktorzerlegung exakt Z.

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

[Dr.Hackstable]

@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.