# Tag Info

## Hot answers tagged finite-field

31

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

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

18

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

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

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

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

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

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

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 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 ... 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 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 (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 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 ... 9 In a finite field of size$q$, the multiplicative subgroup has order$q-1$(i.e. all elements are invertible except$0$). If$n$is relatively prime to$q-1$, then there is only one$n$-th root of unity, i.e.$1$itself. If$n$divides$q-1$, then there are$n$roots of unity. In the remainder of this answer, I assume that you are in that case, i.e.$n$... 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^*/...

8

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

8

It has to do with which modulus you use. You did all your arithmetic modulo 11. However, when using Feldman's VSS, you gotta use two different moduli (using each one in the appropriate spot). In your example, you shouldn't do all arithmetic modulo 11. Instead, you should be doing some arithmetic modulo 11, and some arithmetic modulo 5 (the order of $g$ ...

8

"Finite field cryptography" is fancy language for group-based cryptography done over the integers modulo a prime (instantiating a field) to distinguish this more "classic" approach from the new fancier elliptic curve cryptography. Example: Finite Field Diffie-Hellman: Diffie-Hellman done in $\mathbb F_p$.

8

For any $g$ in the set $\mathbb Z_p^*=\{1,2,\dots,p-1\}$, consider the function $F_g$ over that set defined by $F_g(x)\;=\;g\cdot x\bmod p$. Since $p$ is prime, by Fermat's little theorem, iterating $F_g$, starting from $1$, $p-1$ times, cycles back to $1$. By definition, $g$ is a generator of $\mathbb Z_p^*$ if and only if that cycling does not occur ...

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