Come si calcola i logaritmi in crittografia?

Question

Sto cercando di svolgere funzioni non lineari su byte per implementare Safer+. L'algoritmo richiede il logaritmo di calcolo di base-45 sui byte e non capisco come farlo.

tronco d'albero₄₅(201) = 1.39316393

Quando lo assegno a un byte, il valore viene troncato a 1 e non riesco a recuperare il risultato esatto.

Come dovrei gestirlo?

Answer 1

La crittografia spesso usa Field Prime, In questo caso, GF (257). Crea una tabella di esponente Sembra questo:

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

I valori "log" sono 45^Exp % 257. Avrai bisogno di una libreria aritmetica di precisione arbitraria con a modPow Funzione (solleva un numero su un valore di potenza, modulo) per costruire questa tabella. Puoi vedere che il valore per "Exp" 128 è un caso speciale, poiché normalmente il logaritmo di zero non è definito.

Calcola il logaritmo di un numero trovandolo nella colonna "log"; Il valore nella colonna "Exp" di quella riga è il logaritmo.

Ecco uno schizzo dell'inizializzazione:

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;

Con questa configurazione, ad esempio, registro₄₅(131) = log[131] = 63 e 45³⁸ = exp[38] = 59.

(Non ho mai scritto C#; sto solo indovinando dal BigInteger documentazione; È probabile che ci siano errori con i tipi di dati.)

Answer 2

Quindi hai un valore di byte (da 0 a 255) e vuoi ottenere la base di registro 45 e archiviarla in un altro byte? Come altri hanno detto, perderai un po 'di precisione nel farlo. Tuttavia, tu Potere Fai meglio del semplice lancio del double risultato a a byte.

La base di registro 45 di 255 è di circa 1.455675. Puoi archiviarlo in un byte, con una certa perdita di precisione, moltiplicandolo per un fattore costante. Quale fattore costante? Potresti usare 100, il che ti darebbe un valore di 145, ma stai perdendo quasi la metà dell'intervallo di un byte. Poiché il valore più grande che desideri rappresentare è 1.455675, è possibile utilizzare un moltiplicatore costante di 255/log45(255), o circa 175.176.

Quanto funziona bene? Vediamo ...

        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);

Sotto .NET 4 sulla mia macchina, questo mi dà un errore massimo del 2,1419%e un errore medio dell'1,0501%.

È possibile ridurre l'errore medio arrotondando il risultato da Math.Pow. Questo è:

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

Ciò riduce l'errore medio allo 0,9300%, ma aumenta l'errore massimo al 3,8462%.

Answer 3

Mostrarci il codice potrebbe aiutare, ma sospetto che il tuo problema provenga dall'archiviazione del risultato.

Se vuoi archiviare un numero non intellevole non vuoi metterlo in un byte poiché questo lo troncherà (come stai vedendo). Conservare invece il risultato in un doppio o qualcosa di più appropriato:

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

Dovrei aggiungere che non sono sicuro di cosa sia più sicuro+, quindi questa risposta potrebbe non essere utile, ma spero che dovrebbe indicarti nella giusta direzione.

Answer 4

Questa non è davvero una risposta, ma una frazione degli utenti che visualizzano questa domanda sarà probabilmente interrotta nella conversione di un double digitare a a byte[] genere. Ciò che si potrebbe fare è semplicemente:

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

e

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

Questo usa il BitConverter Classe che credo esista inizialmente in .NET.