2022 Developer Survey is open! Take survey.
26 votes
Accepted

How to determine the order of an elliptic curve group from its parameters?

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....
user avatar
  • 10.9k
23 votes
Accepted

Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

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 ...
user avatar
23 votes

What is the main difference between finite fields and rings?

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 ...
user avatar
21 votes
Accepted

What is the main difference between finite fields and rings?

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$ ...
user avatar
  • 3,707
19 votes
Accepted

how does BearSSL's GCM modular reduction work?

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 ...
user avatar
17 votes
Accepted

Why are finite fields so important in cryptography?

One particularly important topic for this question is that of the encoding size. This comes from the following "trivial fact": For an infinite set $A$, there does not exist some $s\in \...
user avatar
  • 8,424
16 votes
Accepted

How was the GCM polynomial found?

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 ...
user avatar
16 votes

Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

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,...
user avatar
13 votes
Accepted

Why is x^8 + x^4 + x^3 + x + 1 used in AES's Rcon?

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 ...
user avatar
13 votes

Constant time multiplication in GF(2^8)

In C, multiplication in the field $\operatorname{GF}(2^8)$ with reduction polynomial $x^8+x^4+x^3+x+1$ can be coded as one of these three functionally equivalent functions: ...
user avatar
  • 122k
12 votes

In a group, is it hard to calculate the base $g$ given $g^a$ and $a$?

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 ...
user avatar
  • 10.9k
11 votes
Accepted

Does RSA operate over a Finite Field (Galois Field)?

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&...
user avatar
  • 10.9k
11 votes
Accepted

Algorithm for computing square roots in $GF(2^n)$

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 ...
user avatar
  • 131k
11 votes
Accepted

Is the additive discrete Logarithm problem always easy in Fields?

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-...
user avatar
11 votes
Accepted

On what Galois field AES really works?

No, in AES the $a_i$ are not bytes. They are bits. The 8 bits $a_i$ together form a byte, and are considered a single element of the Galois Field ${\operatorname{GF}\left(2^8\right)}$, also noted $\...
user avatar
  • 122k
10 votes

Algorithm for computing square roots in $GF(2^n)$

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 ...
user avatar
  • 7,904
10 votes
Accepted

How to calculate AES logarithm table?

(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 ...
user avatar
  • 10.9k
10 votes
Accepted

Do $v_1=\alpha\cdot r_1$ and $v_2=\alpha\cdot r_2$ leak information about $\alpha$

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 ...
user avatar
  • 131k
10 votes
Accepted

Is it necessary for the Rijndael polynomial to be primitive?

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 ...
user avatar
  • 131k
10 votes
Accepted

Finding the n-th root of unity in a finite field

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 ...
user avatar
10 votes
Accepted

Why doesn't the GCM spec use a more efficient multiplication algorithm?

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, ...
user avatar
  • 131k
9 votes

Random Galois fields

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 ...
user avatar
9 votes
Accepted

Advantage of $\operatorname{GF}(2^8)$ over $\mathbb Z/2^8\mathbb Z$ in AES/Rijndael

One important property of the mixColumns step is that it is Maximum Distance Separable (MDS). That is, if $M$ is our multiplication matrix, if you take any two distinct input vectors $V$ and $V'$, ...
user avatar
  • 131k
9 votes

What is the main difference between finite fields and rings?

Take a set $S$ and an operation, let's call it $\oplus$. Also take another operation, say $\odot$. Also fix an element $\mathcal O\in S$ such that $\forall s\in S: \mathcal O\oplus s=s$ and fix ...
user avatar
  • 44.6k
9 votes
Accepted

Need help understanding math behind Rijndael S-Box

The code is using the fact that the Rijndael's* Galois field has the following generators†: 3 5 6 9 11 14 17 18 19 20 23 24 25 26 28 30 31 33 34 35 39 40 42 44 48 49 60 62 63 65 69 70 71 72 73 75 76 ...
user avatar
  • 43.1k
8 votes

Choosing finite field size in Shamir's Secret Sharing Scheme

Actually, you can do Shamir Secret Sharing over any finite field $GF(p^k)$, for any prime $p$ and any integer $k$. If $k=1$, you have the $GF(p)$ field you mentioned; however it works on extension ...
user avatar
  • 131k
8 votes

How to determine the order of an elliptic curve group from its parameters?

As yyyyyyy mentioned for counting number of points on elliptic curve over $\mathbb F_p$ we can use Elkies method. But for extension of fields use of this theorem make it so easy: Theorem : Let $E$ ...
user avatar
8 votes

What is this "finite field cryptography"?

"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 ...
user avatar
  • 44.6k
8 votes
Accepted

Find the generators of multiplicative group of units efficiently?

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 $...
user avatar
  • 122k

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