-1

Possible Duplicate:
Finding Byte logarithm

I am implemeting the SAFER+ algorithm, this algorithm uses 16 bytes byte-array and performs the operations on Bytes.

The first phase includes XOR and ADDITON funciton with the Subkeys, no problems to mention here.

The second phase is the nonlinear layer which uses POWER and LOGARITHMS on the bytes' values, the problem here is when we take the log "to base 45" of the Value, the result is a floating point double, and this value should be passed to phase 3 as a byte to be handled in the same way of the phase one.

Community
  • 1
  • 1
Eng. Aws
  • 169
  • 1
  • 2
  • 7
  • Is the question how do you do a log to base 45? Or how to convert the result to a byte (or is it supposed to mean byte array?) – Mike Goodwin Dec 02 '11 at 18:41
  • the question is how to use the result of the log and keep it as a byte so i can move forward with the algorithm, since the result is floating point it will be trunicated when stored in the byte. – Eng. Aws Dec 02 '11 at 18:49
  • Dear Henk, it is not really a duplicate, since i thought that the qustion wasn't clear to all so i tried to clarify the situation. – Eng. Aws Dec 02 '11 at 18:52
  • Surely it has to truncate unless you want to convert each double to a byte array?? – Mike Goodwin Dec 02 '11 at 18:54
  • 1
    @Eng.Aws - the basic idea is that you improve a question, not just post again. See the _edit_ link and the FAQ. – H H Dec 02 '11 at 19:11

2 Answers2

1

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 45exp % 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 = BigInteger.valueOf(45);
BigInteger V257 = BigInteger.valueOf(257);
int[] exp = new int[256];
int[] log = new int[256];
for (int idx = 0; idx < 256; ++idx)
  exp[idx] = V45.modPow(BigInteger.valueOf(idx), V257).intValue() % 256;
for (int idx = 0; idx < 256; ++idx)
  log[exp[idx]] = idx;

With this setup, for example, log45(131) = log[131] = 63, and 4538 = exp[38] = 59.

erickson
  • 265,237
  • 58
  • 395
  • 493
  • Well you don't *need* to use arbitrary precision arithmetic, 32-bit ints will suffice. But you'd have to write you own modPow function. It should only take 10-15 lines. – President James K. Polk Dec 03 '11 at 22:33
  • Yep, you could definitely write your own, but I know that .NET has a `BigInteger` class very similar to the Java I show here. – erickson Dec 04 '11 at 05:20
0

You can do this with a Linq expression as follows

inputBytes.Select(b => b == 0 ? (byte)128 : Convert.ToByte(System.Math.Log(Convert.ToDouble(b), 45))).ToArray();

But this will truncate the double, as it has to do...

Edited after looking at SAFER+, it uses the convention that Log45(0)=128 to avoid numeric overflow.

Mike Goodwin
  • 8,810
  • 2
  • 35
  • 50