# Tag Info

16

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

15

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

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

6

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

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

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

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

6

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

5

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

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

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

5

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

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

The simplest answer is probably to give an example of information leaked when using Shamir's secret sharing over the integers. Assume that we construct a low degree example, defining $q$ to be a linear polynomial with $q(0)=D$ and $q(1)=a_1$. By interpolation you find that: $$q(x)=(a_1-D)x+D.$$ Assume that you are given the share corresponding to ...

4

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

3

There are several questions hidden in your question. You'll have to distinguish between the polynomial ring $\mathbb Z_2[X]$, and the factor field $GF(2^8) = \mathbb Z_2[X]/F$ (where $F$ is any irreductible polynomial of degree 8). In $\mathbb Z_2[X]$, the only polynomial which is a factor of all others is the trivial polynomial $1$. (In general, in a ...

3

There have been extensive comments by the OP on this question as well as a related one and its answers and the consensus don't seem to be converging at all to anything sensible. Broadly speaking, the field in which we are operating influences the answer to the question of whether a system of equations has solutions or not to some extent, but not in ...

3

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

3

The complexity of the number field sieve can be obtained from the expected size of the coefficients of the polynomial $f(x) = x^d + c_{d-1} x^{d-1} + \ldots + c_0$: if $c_i \le N^{\epsilon/d}$, then the expected runtime is $$\exp\left(\left(\left(\frac{32(1 + \epsilon)}{9}\right)^{1/3} + o(1)\right) (\log N )^{1/3} (\log \log N)^{2/3}\right),$$ or simply ...

3

While I haven't read the paper, I believe I can answer these questions: I'm not sure if the implied modulus of each operation is $q$, as I added myself to the above formulas. Could someone please clarify this? The paper omits it... No, the arithmetic is done modulo $p$. Remember, you're working in a subgroup of size $q$ of $\mathbb{Z}^*_{p}$; ...

3

As far as I can tell from your description, the modulus is p. To multiply two group elements, you compute x*y (mod p); because the generator g you choose has period q it'll all work out fine. No, p, q, and g can (and must) all be public. This is ElGamal, not RSA we're talking about - the security comes from the (presumed) hardness of taking discrete ...

3

I now see your problem; it's more fundamental than what my previous answer assumed. You state: Now the same method should work for finite field GF(2^8) as long as the arithmetic are replaced with finite field arithmetic. However this is not the case where you interpret "should work" as "coming up with the exact same answer". Actually, that's not the ...

2

While $GF(2^8)$ is indeed isomorphic to $GF((2^4)^2)$ (and to the other fields you have mentioned), if you use the latter you will need a conversion routine to change the field representation from and to $GF(2^8)$. This will probably defeat any performance gain with the alternative representation (and I'm not sure there would be any). Another related issue ...

2

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

2

Ok so you probably know that fields are interesting structures to study...they are places where arithmetic works nicely. Most cryptosystems depending heavily on numbers usually must take the numbers from some field in order for things to work out. Now there are many fields with infinitely many elements, $\mathbb{Q}, \mathbb{R}, \mathbb{C}...$, but what ...

2

In addition to some of the other answers, what has helped me the most in understanding finite fields, or any algebraic structure for that matter is playing with them. For this, I have found Sage to be indispensible. So, looking at Galois Fields in Sage goes something like this: sage: f = GF(2^8, 'x') sage: f Finite field in x of size 2^8 sage: ...

2

Finite fields are a fascinating subject, but it's not really something you can understand from a forum. I really recommend you take a book about number theory and spend some time with it. It will help you greatly for the rest of your life. For instance, I like "A Computational Introduction to Number Theory and Algebra" by Victor Shoup. The whole book is ...

2

The reason that a field must be used in Shamir's reconstruction scheme is that the calculations used in the reconstruction need to divide one "number" by another, and division is not defined in $\mathbb Z$, the set of integers: $\frac{m}{n}$ is not necessarily a member of $\mathbb Z$. So, why not use $\mathbb R$, or $\mathbb Q$ which can be "implemented" in ...

2

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

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