Umkehren, dass Math-Funktion

Ich muss eine Funktion mit harten Math-Operationen umkehren, ich frage hier zu prüfen, ob es sogar möglich ist, schließlich für Hilfe.Umkehren, dass Math-Funktion

public static UInt32 Func_4(UInt32 P, UInt32 X, UInt32 G) 
    { 
     UInt64 result = 1; 
     UInt64 mult = G; 
     if (X == 0) 
      return 1; 
     while (X != 0) 
     { 
      if ((X & 1) != 0) 
       result = (mult * result) % P; 
      X = X >> 1; 
      mult = (mult * mult) % P; 
     } 
     return (UInt32)result; 
    }

Mit "Umkehren" Ich meine dies: Ich weiß, G, ich weiß, P, ich weiß, das Ergebnis. Ich brauche X.

Ich habe versucht, es heute Morgen wieder zu übersetzen, während meine Meinung klar war, aber ich habe versagt. Ist es überhaupt möglich?

Vielen Dank im Voraus.

Quelle

2009-04-24 Ivan Prodanov

Was sind Ihre erwarteten Eingaben zur Umkehrung? Welche von P, X und G suchst du zurück? –

Es würde helfen, wenn Sie den Algorithmus zeigen, den Sie hoffen zu tun. Wenn Sie das Ergebnis kennen und X nicht kennen, warum sollten Sie dann X weitergeben? Übergeben Sie das Ergebnis als Parameter. –

James: Ich denke, er hat r = f (p, x, g) und will eine Funktion x = h (p, r, g). –

Es ist wie Ihre Func_4() Funktion sieht berechnet G ^X mod P. Was Sie fordern, ist eine Lösung für das discrete logarithm Problem, aber kein effizienter Algorithmus ist bekannt.

Quelle

2009-04-24 04:40:17

+14

Allerdings, wenn das Plakat dieses Problem löst, habe ich dieses RSA-System Ich versuche zu brechen ... –

der "Mod" ist das Problem. Du wirst das niemals brechen. 5 Mod 2 hat das gleiche Ergebnis wie 7 Mod 2 und 9 Mod 4 und so weiter. Sie können die Eingabe nicht anhand der Ausgabe ermitteln. Es gibt unendlich viele Eingabekombinationen, die zu der gewünschten Ausgabe führen. Geh schlafen. –

Genau. Du solltest X nicht bekommen. Du solltest überprüfen, ob der Klient * das korrekte x kannte, indem du ihm ein anderes G und P schickst und prüfst, ob ihre Ergebnisse mit deinen übereinstimmen. Aber zu keinem Zeitpunkt soll x übertragen werden. –

Es sieht aus wie i = (g ** x) mod p. Das heißt, es kann mehr als ein X

Quelle

2009-04-24 04:40:48

Ja, X = X << 1, jedes Mal, wenn Sie die Schleife durchlaufen. Bedeutet das, dass es unmöglich ist? –

Nicht unmöglich, nur dass es mehrere Antworten gibt (und nicht wegen der <<, sondern wegen der%). Ist das schnell genug für Sie? ... x = 0; do {if (Func_4 (P, x, G) == I) und dann x zurückgeben; x ++; } while (x! = 0); –

gut,

durch diese Arbeiten von Hand für:

P = 5, X = 0b0000 1110 G = 7

P = 5, X = 0b0001 1110 G 7 =

P = 5, X = 0b0011 1110 G 7 =

P = 5, X = 0b0111 1110 G 7 =

etc, ich denke, dass Sie das Muster sehen

haben alle den gleichen Rückgabewert für Ergebnis (4) ...

daher jeder Versuch, dies rückgängig zu machen um einen Wert zu erhalten für X mehrere mögliche Werte für X haben würde ..

je nachdem, was Sie tatsächlich aus dieser Sache brauchen, diese Angelegenheit nicht wirklich kann ...

was ist der Zusammenhang dieser Sache?

Quelle

2009-04-24 05:29:54

Da der Modulo-Operator im Spiel ist, können Sie sofort erkennen, dass die Funktion nicht bijektiv ist: Für ein festes P und G können verschiedene x das gleiche Ergebnis liefern.

Aber die Funktion ist bijektiv für eine begrenzte Domäne von x. Genau wie atan, asin, sqrt, ... erzeugen Sie eine ganze Menge von Werten, wenn Sie die Domäne begrenzen, können Sie die richtige auswählen.

Auf den ersten Blick, was die Funktion tut, für eine sehr große P ist,

Das Produkt von G ^{(2i * x [i])}, wobei x [i] ist der i-te Bit von x (beginnend mit Bit 0 als am wenigsten signifikant).

Dies bedeutet, dass bei einem großen P (größer als Prod (G ²ⁱ) für x = 0x1111 ... 111) die Funktion umgekehrt werden kann. Es scheint auch, dass die Funktion entworfen nicht für kleinere Ps reversibel sein soll.

Quelle

2009-04-24 08:30:08 xtofl

Ich glaube ernsthaft, dass Sie diesen Algorithmus missbrauchen. Aus Ihrer Beschreibung und aus dem Blick auf den Algorithmus ist es ziemlich klar, dass dies nur vorwärts gehen soll. Denken Sie daran als eine Prüfsumme von X Rechentasten P und G.

Quelle

2009-04-27 23:52:57

pseduo Algorithmus

R = pow (G, X) mod P

ie) existiert ein Q, das unter Verwendung von R + P * Q = pow (G, X)

In umgekehrter Richtung, Überprüfen Y für alle Q von 0 bis UINT32 ((MAXUINT32-R)/P),

Y = log (R + P * Q)/log (G)

und wenn der Wert Y tut keine Brüche haben, dann sind sie der Satz von mehreren "X" Antworten auf Ihr Problem.

Angenommen X1 ist der erste X-Wert, der keine Brüche hat und X2 ist der zweite X-Wert, der keine Brüche hat. Dann kann die Menge aller X in der Gleichung X (S) = X1 + (X2-X1) * S angegeben werden, wobei S = 0 bis UINT32 ((MAXUINT32-X1)/(X2-X1)).

Das ist, wenn 1 = Pow (G, T) mod P und dann Pow (G, X + T) mod P = Pow (G, X) mod P * Pow (G, T) mod P was ist auch Pow (G, X) mod P. Also X, X + T, X + 2T, X + 3T ... alle werden die gleichen Werte haben.

Quelle

2009-04-29 11:55:02 lakshmanaraj

Antwort

Verwandte Themen