Der Modulo-Operator (%) liefert ein unterschiedliches Ergebnis für verschiedene .NET-Versionen in C #

89

Ich verschlüssele die Benutzereingabe zum Generieren einer Zeichenfolge für das Kennwort. Eine Codezeile führt jedoch in verschiedenen Versionen des Frameworks zu unterschiedlichen Ergebnissen. Teilcode mit Wert der vom Benutzer gedrückten Taste:

Taste gedrückt: 1. Variable asciiist 49. Wert von 'e' und 'n' nach einiger Berechnung:

e = 103, 
n = 143,

Math.Pow(ascii, e) % n

Ergebnis des obigen Codes:

  • In .NET 3.5 (C #)

    Math.Pow(ascii, e) % n

    gibt 9.0.

  • In .NET 4 (C #)

    Math.Pow(ascii, e) % n

    gibt 77.0.

Math.Pow() gibt in beiden Versionen das richtige (gleiche) Ergebnis.

Was ist die Ursache und gibt es eine Lösung?

Rajiv
quelle
12
Natürlich sind beide Antworten in der Frage falsch. Die Tatsache, dass Sie sich nicht darum zu kümmern scheinen, ist besorgniserregend.
David Heffernan
34
Sie müssen mehrere Schritte zurückgehen. "Ich verschlüssele die Benutzereingaben zum Generieren einer Zeichenfolge für das Kennwort" Dieser Teil ist bereits zweifelhaft. Was möchten Sie eigentlich tun? Möchten Sie ein Passwort in verschlüsselter oder gehashter Form speichern? Möchten Sie dies als Entropie verwenden, um einen zufälligen Wert zu generieren? Was sind Ihre Sicherheitsziele?
CodesInChaos
49
Während diese Frage ein interessantes Problem mit der Gleitkomma-Arithmetik darstellt, halte ich es nicht für eine gute Idee, eine eigene Verschlüsselung zu verwenden, wenn das Ziel des OP darin besteht, "die Benutzereingaben zum Generieren einer Zeichenfolge für das Kennwort zu verschlüsseln" tatsächlich eine der Antworten implementieren.
Harrison Paine
18
Schöne Demonstration, warum andere Sprachen die Verwendung von %Gleitkommazahlen verbieten .
Ben Voigt
5
Obwohl die Antworten gut sind, beantwortet keiner von ihnen die Frage, was sich zwischen .NET 3.5 und 4 geändert hat und was das unterschiedliche Verhalten verursacht.
Msell

Antworten:

160

Math.Powarbeitet mit Gleitkommazahlen mit doppelter Genauigkeit; Daher sollten Sie nicht mehr als das erwartenDaher ersten 15 bis 17 Stellen des Ergebnisses korrekt sind:

Alle Gleitkommazahlen haben auch eine begrenzte Anzahl von signifikanten Stellen, wodurch auch bestimmt wird, wie genau sich ein Gleitkommawert einer reellen Zahl annähert. Ein DoubleWert hat eine Genauigkeit von bis zu 15 Dezimalstellen, obwohl intern maximal 17 Stellen beibehalten werden.

Für die Modulo-Arithmetik müssen jedoch alle Ziffern genau sein. In Ihrem Fall berechnen Sie 49 103 , deren Ergebnis aus 175 Ziffern besteht, wodurch die Modulo-Operation in beiden Antworten bedeutungslos wird.

Um den richtigen Wert zu ermitteln, sollten Sie eine Arithmetik mit beliebiger Genauigkeit verwenden, wie sie von der BigIntegerKlasse bereitgestellt wird (eingeführt in .NET 4.0).

int val = (int)(BigInteger.Pow(49, 103) % 143);   // gives 114

Bearbeiten : Wie von Mark Peters in den Kommentaren unten ausgeführt, sollten Sie die BigInteger.ModPowMethode verwenden, die speziell für diese Art von Operation vorgesehen ist:

int val = (int)BigInteger.ModPow(49, 103, 143);   // gives 114
Douglas
quelle
20
+1 für den Hinweis auf das eigentliche Problem, nämlich dass der Code in der Frage einfach falsch ist
David Heffernan
36
Es ist erwähnenswert, dass BigInteger eine ModPow () -Methode bereitstellt, die (in meinem Schnelltest gerade) für diesen Vorgang etwa fünfmal schneller ausgeführt wird.
Mark Peters
8
+1 Mit der Bearbeitung. ModPow ist nicht nur schnell, es ist auch numerisch stabil!
Ray
2
@maker Nein, die Antwort ist bedeutungslos , nicht ungültig .
Cody Gray
3
@ makerofthings7: Ich stimme dir grundsätzlich zu. Die Gleitkomma-Arithmetik ist jedoch mit Ungenauigkeiten verbunden, und es wird als praktischer angesehen, von Entwicklern zu erwarten, dass sie sich der Risiken bewusst sind, als den Betrieb im Allgemeinen einzuschränken. Wenn man wirklich "sicher" sein möchte, muss die Sprache auch Gleitkomma-Gleichheitsvergleiche verbieten, um unerwartete Ergebnisse wie die 1.0 - 0.9 - 0.1 == 0.0Auswertung von zu vermeiden false.
Douglas
72

Abgesehen von der Tatsache, dass Ihre Hashing-Funktion nicht sehr gut ist * , besteht das größte Problem mit Ihrem Code nicht darin, dass er je nach .NET-Version eine andere Nummer zurückgibt, sondern in beiden Fällen eine völlig bedeutungslose Nummer: Die richtige Antwort auf das Problem lautet

49 103 mod 143 = ist 114. ( Link zu Wolfram Alpha )

Mit diesem Code können Sie diese Antwort berechnen:

private static int PowMod(int a, int b, int mod) {
    if (b == 0) {
        return 1;
    }
    var tmp = PowMod(a, b/2, mod);
    tmp *= tmp;
    if (b%2 != 0) {
        tmp *= a;
    }
    return tmp%mod;
}

Der Grund, warum Ihre Berechnung ein anderes Ergebnis liefert, ist, dass Sie zur Erstellung einer Antwort einen Zwischenwert verwenden, der die meisten signifikanten Ziffern der Zahl 49 103 löscht: Nur die ersten 16 der 175 Ziffern sind korrekt!

1230824813134842807283798520430636310264067713738977819859474030746648511411697029659004340261471771152928833391663821316264359104254030819694748088798262075483562075061997649

Die restlichen 159 Ziffern sind alle falsch. Die Mod-Operation sucht jedoch ein Ergebnis, bei dem jede einzelne Ziffer korrekt sein muss, einschließlich der allerletzten. Daher würde selbst die kleinste Verbesserung der Genauigkeit Math.Pow, die möglicherweise in .NET 4 implementiert wurde, zu einem drastischen Unterschied Ihrer Berechnung führen, der im Wesentlichen zu einem beliebigen Ergebnis führt.

* Da es in dieser Frage darum geht, Ganzzahlen im Zusammenhang mit dem Passwort-Hashing auf hohe Potenzen zu bringen, ist es möglicherweise eine sehr gute Idee, sie zu lesen diesen Antwortlink , bevor Sie entscheiden, ob Ihr aktueller Ansatz durch einen potenziell besseren geändert werden soll.

dasblinkenlight
quelle
20
Gute Antwort. Der eigentliche Punkt ist, dass dies eine schreckliche Hash-Funktion ist. OP muss die Lösung überdenken und einen geeigneteren Algorithmus verwenden.
david.pfx
1
Isaac Newton: Ist es möglich, dass der Mond genauso von der Erde angezogen wird wie der Apfel von der Erde? @ david.pfx: Der eigentliche Punkt ist, dass dies eine schreckliche Art ist, Äpfel zu pflücken. Newton muss die Lösung überdenken und vielleicht einen Mann mit einer Leiter einstellen.
JWG
2
@jwg Davids Kommentar hat aus einem bestimmten Grund so viele positive Stimmen erhalten. Die ursprüngliche Frage machte deutlich, dass der Algorithmus zum Hashing von Passwörtern verwendet wurde, und es ist in der Tat ein schrecklicher Algorithmus für diesen Zweck - es ist äußerst wahrscheinlich, dass er zwischen Versionen des .NET-Frameworks bricht, wie bereits gezeigt wurde. Jede Antwort, die nicht erwähnt, dass das OP seinen Algorithmus ersetzen muss, anstatt ihn zu "reparieren", tut ihm einen schlechten Dienst.
Chris
@ Chris Danke für den Kommentar, den ich bearbeitet habe, um Davids Vorschlag aufzunehmen. Ich habe es nicht so stark formuliert wie Sie, weil das OP-System ein Spielzeug oder ein Wegwerfcode sein kann, den er zu seiner eigenen Unterhaltung erstellt. Vielen Dank!
Dasblinkenlight
27

Was Sie sehen, ist ein doppelter Rundungsfehler. Math.Powfunktioniert mit double und der Unterschied ist wie folgt:

.NET 2.0 und 3.5 => var powerResult = Math.Pow(ascii, e);gibt Folgendes zurück:

1.2308248131348429E+174

.NET 4.0 und 4.5 => geben var powerResult = Math.Pow(ascii, e);Folgendes zurück:

1.2308248131348427E+174

Beachten Sie die letzte Ziffer zuvor E, die den Unterschied im Ergebnis verursacht. Es ist nicht der Moduloperator (%) .

Habib
quelle
3
Heilige Kuh, ist dies die EINZIGE Antwort auf die Frage der OP? Ich las alle Meta "bla bla Sicherheit falsche Frage, ich weiß mehr als Sie n00b" und fragte mich immer noch "warum die konsequente Diskrepanz zwischen 3,5 und 4,0? Haben Sie jemals Ihren Zeh auf einen Felsen gestoßen, während Sie auf den Mond schauten, und gefragt" welche Art von Felsen ist das? "Nur um zu sagen" Ihr eigentliches Problem ist es, nicht auf Ihre Füße zu schauen "oder" Was erwarten Sie, wenn Sie nachts hausgemachte Sandalen tragen? !!! "DANKE!
Michael Paulukonis
1
@ Michael Paulukonis: Das ist eine falsche Analogie. Das Studium von Felsen ist eine legitime Beschäftigung; Das Ausführen von Arithmetik mit beliebiger Genauigkeit unter Verwendung von Datentypen mit fester Genauigkeit ist einfach falsch. Ich würde dies mit einem Software-Personalvermittler vergleichen, der fragt, warum Hunde beim Schreiben von C # schlechter sind als Katzen. Wenn Sie ein Zoologe sind, könnte die Frage einen gewissen Wert haben. für alle anderen ist es sinnlos.
Douglas
24

Die Gleitkommapräzision kann von Maschine zu Maschine und sogar auf derselben Maschine variieren .

Das .NET erstellt jedoch eine virtuelle Maschine für Ihre Apps ... es gibt jedoch Änderungen von Version zu Version.

Daher sollten Sie sich nicht darauf verlassen, um konsistente Ergebnisse zu erzielen. Verwenden Sie für die Verschlüsselung die vom Framework bereitgestellten Klassen, anstatt Ihre eigenen zu rollen.

Joe
quelle
10

Es gibt viele Antworten darüber, wie schlecht der Code ist. Warum ist das Ergebnis jedoch anders?

Intels FPUs verwenden intern das 80-Bit- Format, um mehr Präzision für Zwischenergebnisse zu erzielen. Wenn sich also ein Wert im Prozessorregister befindet, erhält er 80 Bit, aber wenn er in den Stapel geschrieben wird, wird er bei 64 Bit gespeichert .

Ich gehe davon aus, dass die neuere Version von .NET einen besseren Optimierer in der JIT-Kompilierung (Just in Time) hat, sodass ein Wert in einem Register gespeichert wird, anstatt ihn in den Stapel zu schreiben und dann vom Stapel zurückzulesen.

Es kann sein, dass die JIT jetzt einen Wert in einem Register anstatt auf dem Stapel zurückgeben kann. Oder übergeben Sie den Wert in einem Register an die MOD-Funktion.

Siehe auch Frage zum Stapelüberlauf Was sind die Anwendungen / Vorteile eines 80-Bit-Datentyps mit erweiterter Genauigkeit?

Andere Prozessoren, z. B. der ARM, liefern für diesen Code andere Ergebnisse.

Ian Ringrose
quelle
6

Vielleicht ist es am besten, es selbst mit nur ganzzahliger Arithmetik zu berechnen. Etwas wie:

int n = 143;
int e = 103;
int result = 1;
int ascii = (int) 'a';

for (i = 0; i < e; ++i) 
    result = result * ascii % n;

Sie können die Leistung mit der Leistung der BigInteger-Lösung vergleichen, die in den anderen Antworten angegeben ist.

Ronald
quelle
7
Das würde 103 Multiplikationen und Modulreduzierungen erfordern. Man kann es besser machen, indem man e2 = e * e% n, e4 = e2 * e2% n, e8 = e4 * e4% n usw. berechnet und dann das Ergebnis = e * e2% n * e4% n * e32% n * berechnet e64% n. Insgesamt 11 Multiplikationen und Modulreduzierungen. Angesichts der Größe der beteiligten Zahlen könnte man ein paar weitere
Modulreduzierungen
2
@supercat Schöne Mathematik, aber in der Praxis nur relevant, wenn Sie dies auf einem Toaster ausführen.
Alextgordon
7
@alextgordon: Oder wenn man plant, größere Exponentenwerte zu verwenden. Das Erweitern des Exponentenwerts auf z. B. 65521 würde ungefähr 28 Multiplikationen und Modulverringerungen erfordern, wenn man eine Festigkeitsverringerung verwendet, gegenüber 65.520, wenn man dies nicht tut.
Supercat
+1 für eine zugängliche Lösung, bei der genau klar ist, wie die Berechnung durchgeführt wird.
JWG
2
@ Supercat: Du hast absolut Recht. Es ist einfach, den Algorithmus zu verbessern, was relevant ist, wenn er entweder sehr oft berechnet wird oder die Exponenten groß sind. Die Hauptbotschaft ist jedoch, dass sie mit ganzzahliger Arithmetik berechnet werden kann und sollte.
Ronald