How do I compute logarithms in cryptography?

Question

I am trying to perform non-linear functions on bytes to implement SAFER+. The algorithm requires computing base-45 logarithm on bytes, and I don't understand how to do it.

log₄₅(201) = 1.39316393

When I assign this to a byte, the value is truncated to 1, and I can't recover the exact result.

How am I supposed to handle this?

Answer 1

Cryptography often uses prime fields, in this case, GF(257). Create an exponentiation table that looks like this:

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

The "log" values are 45^exp % 257. You'll need an arbitrary precision arithmetic library with a modPow function (raise a number to a power, modulo some value) to build this table. You can see that the value for "exp" 128 is a special case, since normally the logarithm of zero is undefined.

Compute the logarithm of a number by finding the it in the "log" column; the value in the "exp" column of that row is the logarithm.

Here's a sketch of the initialization:

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;

With this setup, for example, log₄₅(131) = log[131] = 63, and 45³⁸ = exp[38] = 59.

(I've never written C#; I'm just guessing from the BigInteger documentation; there are likely to be errors with the data types.)