# Tag Info

26

The $GF$ in $GF(p^n)$ is not a function — it just stands for "Galois field (of $p^n$ elements)". As for what a Galois field is, it's a finite set of things (which we might represent e.g. with the numbers from $0$ to $p^n-1$), with some mathematical operations (specifically, addition and multiplication, and their inverses) defined on them that let us ...

18

Elliptic curves are not the only curves that have groups structure, or uses in cryptography. But they hit the sweet spot between security and efficiency better than pretty much all others. For example, conic sections (quadratic equations) do have a well-defined geometric addition law: given $P$ and $Q$, trace a line through them, and trace a parallel line ...

11

Discrete logarithms in $\mathbb{F}_{p}$ share the same asymptotic complexity as integer factorization for general numbers: $L_p[1/3,1.923]$ for general integers, $L_p[1/3,1.587]$ for special integers. Discrete logarithms in $\mathbb{F}_{p^n}$ have the same asymptotic complexity as factoring special integers, i.e. $L_{p^n}[1/3, 1.587]$, via the Function ...

10

The quoted recommendations do little to prevent fields that are subject to the recent developments. Take the $\mathbb{F}_{2^{6120}}$ example: it clearly passes the field size criterion, but also the subgroup rule, as the group order $2^{6120} - 1$ has one $1536$-bit prime factor. Not all binary fields are affected equally, however. Both Göloğlu et al and ...

10

It depends. If the order $m$ of $g$'s group is known and $a$ has an inverse modulo $m$ (which is the case if and only if $a$ is coprime to $m$), then it is easy: Calculate the inverse $b:=a^{-1}\bmod m$ (for instance, using the Euclidean algorithm), and compute the power $(g^a)^b$. By Lagrange's theorem, this equals $g$. However, there are cases for which ...

9

I think there are some gaps and some misunderstandings in what you say. A finite field or Galois field $GF(p^n)$ is a collection of $p^n$ $n$-dimensional vectors. Here, $p$ is a prime, and each coordinate in a vector is an integer in the range $[0,p-1]$; that is, an element of $GF(p)$. Thus, $$\mathbf A = (a_0, a_1, \ldots, a_{n-1}), ~~ a_i \in GF(p)$$ is ...

7

There is no reason in Shamir's scheme for the finite field $\mathbb F$ to have a prime number $p$ of elements; the field can have $p^m$ elements for suitable prime $p$ and integer $m \geq 1$. So, using $F_{2^8}$, the field with $2^8$ elements is perfectly all right. However, choosing $m = 1$ has the advantage that calculations in $\mathbb F_p$ can be done ...

7

For $p = 2q+1$, one can note that elements of $\mathbb{G}_q$ are exactly the non-zero quadratic residues modulo $p$: Since $p$ is prime, $\mathbb{Z}_p$ is a field. Hence, the polynomial $X^q-1$, being of degree $q$, cannot have more than $q$ roots in $\mathbb{Z}_p$. So $\mathbb{G}_q$ contains all the $q$ values of order $1$ or $q$. If $x$ is a non-zero ...

7

Let $n = \lceil \log q \rceil$ (with "$\log$" being the base-2 logarithm, so $n$ is the size, in bits, of $q$). If $q$ is a prime integer (i.e. $\mathbb{F}_q$ is the field of integers modulo $q$), then classical implementations will have cost $O(n)$ for addition and subtraction, $O(n^2)$ for multiplications and divisions. The cost of multiplications can be ...

7

What is Rijndael's finite field? Rijndaels finite field is $F=\mathrm{GF}(2^8)$ with minimal polynomial $f(x)=x^8 + x^4 + x^3 + x + 1$. Formally, we have $F=\mathbb F_2[x] / (f)$ but don't worry about that. So what does this mean? Well, elements of $F$ should be thought of as polynomials over $\mathbb{F}_2$, with the added fact that the minimal polynomial ...

6

Antoine Joux very kindly sent me the following on the topic: People worry that [logarithms over fields with composite exponent] might be easier, this is why they use prime exponent. For some factorization of the exponent, viewing the finite field as a tower of extensions $(p^{n_1})^{n_2}$ indeed makes things easier. See "The function field sieve ...

6

Well, if $q$ is a prime (and not $p^n$ with $n>1$), then addition, subtraction and multiplication can be performed by doing the traditional operations modulo $q$, that is: $a +_{\mathbb{F}_q}b \equiv (a+b) \bmod q$ $a -_{\mathbb{F}_q}b \equiv (a-b) \bmod q$ $a \times_{\mathbb{F}_q}b \equiv (a\times b) \bmod q$ As such, addition and subtraction can be ...

6

For security of ECC, the choice of the irreducible polynomial is unimportant, because all finite fields with the same cardinal are isomorphic to each other (and the isomorphisms are easy to compute); this is why we can say "the finite field $GF(2^{163})$" even though there are many irreducible polynomials of degree $163$ over $GF(2)$. So the algebraic ...

6

Antoine Joux announced the computation of discrete logarithm over $\mathbb{F}_{2^{257 \times 24}}$, which is now pretty close to what was being used in pairing-based cryptography. According to Joux, "a direct consequence of this record is that supersingular curves (of genus 1 or 2) defined over GF(2^257) cannot be used securely for pairing-based ...

6

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 ...

6

The process is pretty simple. As you say, each party multiplies their two shares. They then use Shamir secret sharing to share the resulting value with the other parties. Once they have received a "subshare" from each other party, each party simply runs Lagrangian interpolation on the subshares they received (plus their own subshare). The result is a share ...

6

Yes, there is an algorithm for efficiently computing square roots in $GF(2^n)$. I don't know if this is the most efficient known, but the existence of an efficient algorithm can be shown by observing that squaring within $GF(2^n)$ is a bitwise linear operation, hence it is equivalent to taking the bit representation of the value, and multiplying it by an ...

6

No, RSA encryption and signature is performed in (the multiplicative semigroup of) the factor ring $\mathbb Z/n\mathbb Z$ which is not a field since the non-zero elements $kp+n\mathbb Z$ (for $0<k<q$) and $kq+n\mathbb Z$ (for $0<k<p$) do not have multiplicative inverses. (However, one easily observes that all other non-zero elements are ...

6

GF$(2^8)$ or $\mathbb F_{2^8}$ can also be viewed as the vector space $\mathbb F_2^8$ of $8$-bit vectors (or bytes) over GF$(2)$ or $\mathbb F_2$. Suppose $\{\beta_0, \beta_1, \cdots, \beta_7\}$ is a basis of $\mathbb F_2^8$ over $\mathbb F_2$, that is, the sum $$a_0\beta_0 \oplus a_1\beta_1 \oplus \cdots \oplus a_7\beta_7, ~ a_i \in \mathbb F_2$$ equals ...

6

It does not; the equation holds for any element $g$. The fact that $g$ is a generator means only that every element of the group can be obtained a key. This is not at all necessary for the protocol.

5

$((g \mod p)^{(p-1)/q})^{142363323} = (t \mod p)^{(p-1)/q}$ Equivalently, $(g \mod p)^{362274084216648467976382636880} = (t \mod p)$ That is, $362274084216648467976382636880 = 142363323 \mod \frac {p-1}q$

5

Göloğlu, Granger, McGuire, and Zumbrägel broke the DLP in the Galois finite field with $2^n$ elements for $n=6120$, and Antoine Joux did it for $n=6168$, with modest computing power. These recent announcements directly imply that cryptosystems (if any) based on the DLP in a field with $2^n$ elements are no longer secure, including for $n$ big enough that ...

5

For the second case, mapping numbers from $\mathbb{Z}_q$ to $\mathbb{G}_q$ and back when: $p=aq+1$ with an $a$ such that, e.g., |p|=1024 and |q|=160 It appears an efficient subgroup encoding/decoding scheme does not exist. Although it has not been proven that one cannot exist, notable cryptographers have conjectured it in the literature. For example, ...

5

Actually, the choice of irreducible polynomial is unimportant in AES; for any polynomial representation of $GF(2^8)$, you can modify the affine tranformation (and the MixCollumn) operation to come up with a block cipher that is equivalent to AES (meaning that any break to that can be translated to a break on the original AES). The key observation here is ...

5

Elliptic curves have a number of nice features that make them good for cryptography. One could write a whole book on the topic (as some have), so I'll highlight a few points. The points on an elliptic curve over a finite field forms a group. The same is not true for the ideas you mentioned. Discrete log on many of these EC groups is hard. In fact, there ...

5

Actually, the answer is "such an $n$ exists iff neither $i, j$ are 0". We have $x^{2^q-1} = 1$ for $x \ne 0$ (because multiplication in $GF(2^q)$ over the nonzero elements forms a group of order $2^q-1$), hence if $i, j \ne 0$, $n=2^q-1$ is one answer (if not necessarily the minimal one). If we add the simple observation that if one of $i, j$ is 0, then ...

5

To complete poncho's answer, if you know some Galois theory. The map $\sigma: x\mapsto x^2$ from $\mathbf{F}_{2^n}$ to itself is simply the Frobenius automorphism (relative to $\mathbf{F}_2$). It generates the Galois group $\mathrm{Gal}\left(\mathbf{F}_{2^n}/\mathbf{F}_2\right)$, which is cyclic of order $n$, and so its inverse (which is, by definition, the ...

4

To complete @Samuel's answer, there are a few shortcuts that can be used when n is composite; however, they only contribute small constant factors, hence they do not change the asymptotic behavior: If n can be divided by r, then one can first solve the discrete logarithm in the subfield GF(2r). In a sieve-based algorithm, this can provide up to half the ...

4

The Handbook on Applied Cryptography (link to the pdf version is on Alfred's webpage) has some of the known techniques to do finite field arithematic. If you are doing arithmetic to implement Elliptic Curve Cryptography (note the comment made by Paulo), then there are methods that depends on whether you are doing it in Jacobian or Projective plane (inverse ...

4

Probably the easiest solution for the case a=2 is to map $m\in\{1\ldots q\}$ to $(m/p)m$ where $(m/p)$ is the Legendre symbol. The inverse can be obtained by mapping a quadratic residue $x\in Z/(pZ)^*$ either to x or -x depending on which of the two residue classes contains an integer in $\{1\ldots q\}$. This is of course a well know solution, but I can't ...

Only top voted, non community-wiki answers of a minimum length are eligible