1
$\begingroup$

$GF(2^m)$ Galois fields are widely used in different cryptographic algorithms, for example, in Rijndael.

However, $GF(p^m)$ fields are possible with any prime $p$, not only 2, but $GF(2^m)$ fields are, as Wikipedia puts it, "especially popular choices for applications", because arithmetic operations in $GF(2^m)$ are much easier to implement that, say, in $GF(5^m)$: polynomials in the former can be expressed as simple binary numbers, and addition and subtraction are simply bitwise $xor$, which gives a great performance boost.

The question is: are there any cases where a $GF(p^m)$ with $p \neq 2$ would be preffered over a $GF(2^m)$ field? Or do such fields have only theoretical value?

I'm asking this because part of my cryptography homework involves calculations with such fields, and the last two tasks are to calculate a message encrypted with ElGamal, and to calculate an ElGamal signature, using a $GF(31^3) = \mathbb Z_{31}[x]/(29*x^3+14)$ field. Is this an example of a practice that has some benefits (besides the "security through obscurity" principle)?

$\endgroup$
1
$\begingroup$

There have been some research in Optimal Extension Fields (OEF), introduced at Crypto'98 by Bailey and Paar paper.

The idea is to work in a field $GF(p^n)$ with $p$ prime and of the form $2^{32}\pm c$ with small $c$ for 32-bit CPUs ($2^{64}\pm c$ for 64-bit CPUs), so that they can leverage on CPU's ALU for most computations, therefore OEF based systems are very fast in SW.

That said, I don't believe they had any real adoptions in crytosystems.

$\endgroup$
  • $\begingroup$ Thank you, I wasn't aware of the OEF research. Looks like an interesting read. $\endgroup$ – Mints97 Jan 31 '15 at 9:06
1
$\begingroup$

Yes, cryptosystems like ElGamal or Shnorr based on the intractability of Dlog Problem are are indicated to be implemented on finite field, which is not the case of the RSA for which a model was proposed in the early $80^{ies}$, and immediatly broken. As you know, a finite field is denoted by $GF(q)$ where $q=p^m$ and p would be any Prime. But in the case there is no special advantage to use such q with $p\neq 2$, because the arithmetic on this field is a bit more complicated, and each party would beforehand agree on using the same irreducible polynomial for building the corresponding splitting field.

However, other applications could use these fields for specific attacks, as the MOV attack which was introduced to reduce the Dlog Problem on supersingular curves.

$\endgroup$
  • $\begingroup$ I see. However, isn't the MOV attack using elliptic curves, not polynomials? $\endgroup$ – Mints97 Jan 30 '15 at 4:49
  • 1
    $\begingroup$ @Mints97 What do you think an elliptic curve is? It's a set of points $(x,y)$ where $x$ and $y$ are elements of some field. This field is very often $\mathbf{F}_{p^k}$ with $p > 2$ and $k > 1$. This is the case in particular for the MOV algorithm. $\endgroup$ – fkraiem Jan 31 '15 at 13:57
  • $\begingroup$ @fkraiem: ah, thank you very much, I get it now. It's just that I am not really familiar with elliptic curves yet... $\endgroup$ – Mints97 Jan 31 '15 at 14:06
  • 1
    $\begingroup$ @Mints97: I've mentionned the MOV case to only give example of working over fields of the form $GF(p^{k})$. Succintly speaking, MOV attacks reduces Dlog problem from EC to Dlog problem in $GF(p^{k})$, and the aim of this attack is to preventsof using some kind of curves for specific crypto applications. Despite their relative complexity there is othes applications in crypto, such as the SATO & all variants, introduced in the begin of 2000, for counting cardinality of EC over fields of small characteristics. Methods a little bit complex to be exposed here. $\endgroup$ – Robert NACIRI Jan 31 '15 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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