Wie berechne ich Logarithmen in der Kryptographie?

Question

Ich versuche, nichtlineare Funktionen auf Bytes auszuführen, um Safer+zu implementieren. Der Algorithmus erfordert die Berechnung von Basis-45-Logarithmus auf Bytes, und ich verstehe nicht, wie es geht.

Protokoll₄₅(201) = 1.39316393

Wenn ich dies einem Byte zuordne, wird der Wert auf 1 abgeschnitten, und ich kann das genaue Ergebnis nicht wiederherstellen.

Wie soll ich damit umgehen?

Answer 1

Kryptographie verwendet oft Prime Fields, In diesem Fall GF (257). Erstellen Sie eine Exponentiationstabelle Das sieht so aus:

exp | log
----+----
  0 |   1
  1 |  45
  2 | 226
  3 | 147
... | ...
128 |   0
... | ...
255 |  40
---------

Die "Protokoll" -Werte sind 45^Exp % 257. Sie benötigen eine willkürliche Präzisions -Arithmetikbibliothek mit a modPow Funktion (erhöhen Sie eine Zahl auf eine Leistung, modulo etwas Wert), um diese Tabelle zu erstellen. Sie können sehen, dass der Wert für "Exp" 128 ein Sonderfall ist, da normalerweise der Logarithmus von Null undefiniert ist.

Berechnen Sie den Logarithmus einer Zahl, indem Sie das IT in der Spalte "Protokoll" finden. Der Wert in der Spalte "Exp" dieser Zeile ist der Logarithmus.

Hier ist eine Skizze der Initialisierung:

BigInteger V45 = new BigInteger(45);
BigInteger V257 = new BigInteger(257);
byte[] exp = new byte[256];
for (int idx = 0; idx < 256; ++idx)
  exp[idx] = BigInteger.ModPow(V45, new BigInteger(idx), V257) % 256;
byte[] log = new byte[256];
for (int idx = 0; idx < 256; ++idx)
  log[exp[idx]] = idx;

Mit diesem Setup zum Beispiel Protokollieren₄₅(131) = log[131] = 63 und 45³⁸ = exp[38] = 59.

(Ich habe noch nie C#geschrieben; Ich rate nur aus dem BigInteger Dokumentation; Es gibt wahrscheinlich Fehler bei den Datentypen.)

Answer 2

Sie haben also einen Bytewert (von 0 bis 255) und möchten die Protokollbasis 45 erhalten und in einem anderen Byte speichern? Wie andere gesagt haben, werden Sie dabei etwas Genauigkeit verlieren. Aber du kann tun besser, als nur das zu werfen double Ergebnis zu a byte.

Die Protokollbasis 45 von 255 beträgt ungefähr 1,455675. Sie können das in einem Byte mit einem gewissen Genauigkeitsverlust aufbewahren, indem Sie es mit einem konstanten Faktor multiplizieren. Welcher konstante Faktor? Sie könnten 100 verwenden, was Ihnen einen Wert von 145 ergibt, aber Sie verlieren fast die Hälfte des Reichweite eines Byte. Da der größte Wert, den Sie darstellen möchten, 1,455675 ist, können Sie einen konstanten Multiplikator von verwenden 255/log45(255), oder ca. 175.176.

Wie gut funktioniert das? Mal schauen ...

        var mult = 255.0 / Math.Log(255, 45);
        Console.WriteLine("Scaling factor is {0}", mult);
        double errMax = double.MinValue;
        double errMin = double.MaxValue;
        double errTot = 0;
        for (int i = 1; i < 256; ++i)
        {
            // Get the log of the number you want
            var l = Math.Log(i, 45);

            // Convert to byte
            var b = (byte)(l * mult);

            // Now go back the other way.
            var a = Math.Pow(45, (double)b / mult);

            var err = (double)(i - a) / i;
            errTot += err;
            errMax = Math.Max(errMax, err);
            errMin = Math.Min(errMin, err);
            Console.WriteLine("{0,3:N0}, {1,3:N0}, {2}, {3:P4}", i, b, a, err);
        }
        Console.WriteLine("max error = {0:P4}", errMax);
        Console.WriteLine("min error = {0:P4}", errMin);
        Console.WriteLine("avg error = {0:P4}", errTot / 255);

Unter .NET 4 auf meiner Maschine gibt ich einen maximalen Fehler von 2,1419%und einen durchschnittlichen Fehler von 1,0501%.

Sie können den durchschnittlichen Fehler reduzieren, indem Sie das Ergebnis von abrunden Math.Pow. Das ist:

var a = Math.Round(Math.Pow(45, (double)b / mult));

Dies reduziert den durchschnittlichen Fehler auf 0,9300%, erhöht jedoch den maximalen Fehler auf 3,8462%.

Answer 3

Das Zeigen des Codes könnte helfen, aber ich vermute, dass Ihr Problem aus der Speicherung des Ergebnisses entsteht.

Wenn Sie eine Nichtteger-Nummer speichern möchten, möchten Sie sie nicht in ein Byte einfügen, da dies sie abschneidet (wie Sie sehen). Speichern Sie stattdessen das Ergebnis zu einem doppelten oder etwas besseren: besser:

double result = math.log(154,45);

Ich sollte hinzufügen, dass ich nicht sicher bin, was sicherer+ ist, daher ist diese Antwort möglicherweise nicht hilfreich, aber hoffentlich sollte sie Sie in die richtige Richtung zeigen.

Answer 4

Dies ist nicht wirklich eine Antwort, aber ein Bruchteil der Benutzer, die diese Frage anzeigen double Geben Sie zu a byte[] Typ. Was getan werden könnte, ist einfach:

double theDouble = 78.24435;
byte[] theResult = BitConverter.GetBytes(theDouble);

und

byte[] theByteArray = new byte[]{0, 4, 2, 3}; //for example
double theCorrespondingDouble = BitConverter.ToDouble(theByteArray);

Dies verwendet die BitConverter Klasse, von der ich glaube, dass sie in .NET initialy existiert.