Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm attempting to implement multiplication and division in $GF(2^8)$ using log and exponential tables. I'm using the exponent of 3 as my generator, using instructions from here.

However I'm having trouble getting the expected answer for some of these trivial multiplications.

For $2 · 4$ this works:

$$ \begin{align*} \log_3(2) &= 25 \\ \log_3(4) &= 50 \\ 25 + 50 &= 75 \\ \exp_3(75) &= 8 \Rightarrow \text{ expected answer} \end{align*}$$

However for $7 · 11$ this breaks down:

$$\begin{align*} \log_3(7) &= 198 \\ \log_3(11) &= 104 \\ 198 + 104 &= 302. \\ \text{Mod it by 255, gives us 47.}\\ \exp_3(47) &= 49 \end{align*}$$ instead of the expected 77.

From what I understand, we use modulus 255 because the 3 generator 'wraps around' on the 255th power (so the pattern repeats after that) thus we only need 0~254. Even if I'm wrong in this, $302 \bmod 256$ still doesn't give us $70$, where $\exp_3(70) = 77$ (the expected answer)

My observation for both multiplication and division is that it works fine until the result of addition/subtraction goes out of range of 0~255.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

In GF(28), 7 × 11 = 49. The discrete logarithm trick works just fine.

Your mistake is in assuming that Galois field multiplication works the same way as normal integer multiplication. In prime-order fields this actually is more or less the case, except that you need to reduce the result modulo the order of the field, but in fields of non-prime order the multiplication rules are different.

Let's do 7 × 11, for example. Noting that 7 = 1112 and 11 = 10112, we can calculate 7 × 11 in binary as:

    111 ×
   1011 =
   ------
    111 +
   1110 +
 111000 =
 --------

So far, everything works the same as in ordinary integer multiplication. But whereas in the integers we'd propagate carries while doing the addition, and thus end up with

      1112 + 11102 + 1110002 = 101012 + 1110002 = 10011012 = 77,

in GF(2n) addition is done bitwise without carries (i.e. GF(2n) addition is the same as bitwise XOR), and thus we get

      1112 + 11102 + 1110002 = 10012 + 1110002 = 1100012 = 49.

(Of course, if the result exceeded the group order, we'd also have to reduce it modulo the reduction polynomial, but in this case that doesn't happen for n ≥ 7.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.