We’re rewarding the question askers & reputations are being recalculated! Read more.
67

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


28

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


23

Braid cryptography? Knapsack cryptosystems, like Nasako–Murikami? Lattice-based cryptography tends to work in polynomial rings or modules with coefficients in finite fields, but whose higher-level structure is not a field. Also: don't forget RSA! RSA works in a ring, not a field.


22

Since you specified finite fields and other answers didn't talk about it, I am adding the following: Fields are rings which are commutative and in which all nonzero elements have multiplicative inverse. But finite fields have another important property that distinguish them from rings: every finite field is completely specified by its order, because they ...


21

There is a rather deep polynomial-time algorithm for counting the $\mathbb F_q$-rational points of an elliptic curve published by René Schoof in 1985 (with subsequent improvements by Noam Elkies and A. O. L. Atkin). It is based on two core ideas: The number of points is closely linked to a functional equation $$ \varphi^2-t\varphi+q = 0 \qquad\in\...


20

In general rings do not have inverse multiplication, as you claimed. Think for example about the integers modulo $4$. In this case, $2$ is not invertible as there is no element that multiplied by $2$ gives you $1$ (the unit of the ring). You can check this easily by exhausting the possibilities: $$0\cdot 2 \equiv 0 \bmod 4, \ \ \ 1\cdot 2 \equiv 2 \bmod 4, \...


19

There are three important points here to consider. 1. We work in $\mathbb{F}_2[X]$. This means that we do additions and multiplications of binary polynomials, i.e. polynomials whose coefficients are 0 or 1. The addition of two polynomials is then a bitwise XOR; there is no carry propagation. Similarly, the multiplication is called a "carry-less" ...


17

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


16

For the GCM mode polynomial, it's likely that they simply looked it up in a table. Low-weight irreducible polynomials over ${\rm GF}(2)$ are useful enough that people have spent time compiling lists of them; the one I linked to above (Seroussi 1998) is fairly often cited, and indeed contains the GCM polynomial. Of course, this just changes the question to ...


14

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


14

Cryptography over quasi-fields (which are not field, but where non-invertible elements are hard to find) is very common. This includes many cryptosystems such as RSA, but also Rabin, Goldwasser-Micali, Benaloh, Okamoto-Uchiyama, Naccache-Stern, Paillier, Damgard-Jurik, BCP, and many other related cryptosystems. This also includes all works based on composite-...


13

The standard method for doing multiplication (and multiplicative inverses) in $\operatorname{GF}(2^8)$ is using a log and antilog table. Each table takes up only 255 bytes; hence it is much smaller than a full $256 \times 256$ multiplication table, and it is much faster than the multiplication procedure you give above. To create such tables, we need to ...


12

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


12

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


12

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


12

The polynomial $x^8+x^4+x^3+x+1$ is the minimal irreducible binary polynomial of degree 8, in the sense that: it has the smallest possible number of terms for an irreducible binary polynomial of that degree, and among all the irreducible binary polynomials with the same degree and number of terms, it has the smallest exponents. In particular, it is the ...


11

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


11

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 $n\...


11

I will call the field elements "points" (as an analogy with elliptic curves). We can thus add points together and multiply points together. We can also multiply a point with an integer with a double-and-add algorithm (which will be reasonably efficient), and, similarly, raise a point to some integer power with a square-and-multiply algorithm. Your additive ...


10

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


10

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


10

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


10

(Note: I'm using hexadecimal numbers to denote AES field elements and decimal numbers to denote integers.) First of all, you have to fix a generator of the AES field's multiplicative group. There's quite a lot of them: 0x03 0x05 0x06 0x09 0x0b 0x0e 0x11 0x12 0x13 0x14 0x17 0x18 0x19 0x1a 0x1c 0x1e 0x1f 0x21 0x22 0x23 0x27 0x28 0x2a 0x2c 0x30 0x31 0x3c 0x3e ...


10

Question: Given $n$ values $v_1=\alpha \cdot r_1 \bmod p,..., v_n=\alpha \cdot r_n \bmod p$ for a large $n$ can the adversary learn the value $\alpha$? Answer: assuming that the $r_i$ values are random (that is, equidistributed and uncorrelated), then the attacker gets absolutely no information about $\alpha$ (other than whether or not it's 0). We can see ...


10

Is it necessary to choose a primitive polynomial for an S-Box? Actually, it is not necessary (and, as the polynomial they actually use in AES, $x^8 + x^4+ x^3 + x + 1$, is not primitive, and so it's a good thing that it's not necessary). The polynomial must be irreducible (if it isn't, the multiplication operation isn't invertible in general, and hence you ...


10

My question is... why? There are a number of different algorithms that perform $GF(2^{128})$ multiplication, all with different trade-offs (speed on specific platforms, program size, memory usage, complexity, side channel resistance, etc). NIST doesn't care which one you use, as long as you get the expected result at the end. As for why NIST decided to ...


9

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


9

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


8

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


8

There are two ways to solve a discrete log problem over $Z^*/p$, that is, given $g$ and $h$, find $x$ with $h \equiv g^x \bmod p$: If the point $g$ generates a subgroup of size $q$, use a general Discrete Log algorithm (such as Pollard Rho) to recover $x$ in $O( \sqrt{q})$ time. Use the Number Field Sieve algorithm to attack the discrete log problem in $Z^*/...


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