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 reading through the XEX mode spec, and I want to make sure I've understood the $\alpha^j$ step correctly:

$X = E_K(I) \oplus \alpha^j$

$C = E_K(M \oplus X) \oplus X$

where:

  • $M$ is the plaintext message
  • $I$ is the number of the sector
  • $\alpha$ is the polynomial $2^n$ over the finite field $GF(2^{128})$
  • $j$ is the block index within the sector

So, to compute $\alpha^j$, assuming that my language has native 128-bit int support, I envision something like this:

UInt128 a_j = 1 << (j % 128);

Is this literally it, or am I missing a key point here?

share|improve this question
2  
I suggest you take a look at this. In short, it is not $1<<(j\ \%\ 128)$. –  mikeazo Jul 14 at 16:45
    
@mikeazo If you look, that question you linked was asked by me. –  Polynomial Jul 15 at 8:49
    
Surely $2^n$ over $GF(2^{128})$ is equal to $2^n\ mod\ 2^{128}$? –  Polynomial Jul 15 at 8:51
    
:) My apologies. I hadn't realized you had asked that other question. No, $2^n$ is not equal to $2^n\bmod{2^{128}}$ in $GF(2^{128})$. The only integers (using polynomial representation) in $GF(2^{128})$ are $0$ and $1$. –  mikeazo Jul 15 at 11:22

1 Answer 1

$GF(2^{128})$ is a finite field with $2^n$ elements. There are a number of ways to represent this field. For example, a binary vector of length 128, or polynomials of degree 127 where the coefficients are 0 or 1. You could even choose to represent them as integers between $0$ and $2^{128}-1$. These are the elements of the finite field. In addition to the elements you need two operations, call them $\boxplus$ and $\boxdot$ (we often call them addition and multiplication). To be a field, the elements must be closed under both operations, associative under both operations, commutative under both operations, there must exist an additive and multiplicative identity, there must exist additive and multiplicative inverses for every element, and multiplication must distribute over addition (see this for additional details).

So for a given representation, you must specify what $\boxplus$ and $\boxdot$ mean and show that the properties I just listed hold.

It is very tempting to want to think of $GF(2^{128})$ as simply the integers modulo $2^{128}$ ($\mathbb{Z}_{2^{128}}$). Part of this probably comes from the fact that $\mathbb{Z}_p$ where $p$ is prime, is in fact a finite field. It turns out that $\mathbb{Z}_{2^{128}}$ is not a finite field. In other words, using integer addition and multiplication modulo $2^{128}$ does not get us all the properties listed above.

So, $\alpha^j\neq 1<<j\ \%\ 128$. You could represent $\alpha$ as a 128 bit integer, but the operations to compute $\alpha^j$ would be very different from simple integer arithmetic. I'd suggest using a finite field library. For more details on the arithmetic, see the other question you asked.

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.