24 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 ...
Hilder Vitor Lima Pereira's user avatar
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 ...
Squeamish Ossifrage's user avatar
23 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$ ...
Daniel's user avatar
  • 3,952
20 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 ...
Thomas Pornin's 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 \...
Mark Schultz-Wu's user avatar
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 ...
Ilmari Karonen's 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,...
Geoffroy Couteau's user avatar
14 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 ...
Thomas Pornin's user avatar
14 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: ...
fgrieu's user avatar
  • 141k
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 ...
Ilmari Karonen's user avatar
12 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-...
Thomas Pornin's 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 $\...
fgrieu's user avatar
  • 141k
10 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$ ...
Meysam Ghahramani's user avatar
10 votes
Accepted

Why are elliptic curves constructed using prime fields and not composite fields?

For a prime $p$ and an integer $n\geq1$, the ring $\mathbb{Z}/p^n\mathbb{Z}$ is a field if and only if $n=1$. There are fields with $p^n$ elements, usually denoted $\mathbb{F}_{p^n}$ or $\operatorname{...
CurveEnthusiast's user avatar
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 ...
poncho's user avatar
  • 147k
10 votes
Accepted

Elliptic Curve - Divide by 2

There are two strategies to do what you want. The first one being to find the group order $q$ and then compute $i=2^{-1}\bmod q$. When you then multiply your point $P$ by $i$ you get $Q=[i]P$ with $[...
SEJPM's user avatar
  • 46k
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, ...
poncho's user avatar
  • 147k
10 votes
Accepted

How does Montgomery reduction work?

In 1985, Montgomery introduced a new clever way to represent the numbers $\mathbb{Z}/n \mathbb{Z}$ such that arithmetic, especially the modular multiplications become easier. Peter L. Montgomery; ...
kelalaka's user avatar
  • 48.5k
10 votes

Why are binary extension fields preferred for Shamir secret sharing?

The main reason is that there is no disadvantage to using a binary extension field. Since the computing and communications infrastructure already runs over binary, this is the simplest and most ...
kodlu's user avatar
  • 22.5k
9 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 ...
SEJPM's user avatar
  • 46k
9 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 $...
fgrieu's user avatar
  • 141k
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'$, ...
poncho's user avatar
  • 147k
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 ...
SEJPM's user avatar
  • 46k
9 votes
Accepted

Why only non-prime order fields have small subgroup attacks?

In Group theory, it is known that if $G$ is a finite group and $q$ is a prime number dividing the order of $G$ (the number of elements in $G$), then $G$ contains an element of order $q$ (Cauchy's ...
Changyu Dong's user avatar
  • 4,178
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 ...
kelalaka's user avatar
  • 48.5k
9 votes

Why are finite fields so important in cryptography?

I will try to give generic answer to this. A Finite Field denoted by ${F_p}$, where p is a prime number, works well with cryptographic algorithms like AES, RSA , etc. because of the following reasons: ...
SSA's user avatar
  • 640
8 votes

why are non singular curves used in elliptic curve cryptography?

Not-so-useful answer: An elliptic curve is by definition a non-singular curve. Therefore by definition we use non-singular curves in elliptic-curve cryptography. Why not use singular curves? It turns ...
CurveEnthusiast's user avatar
8 votes
Accepted

How to find the order of a generator on an elliptic curve?

Due to the Pohlig-Hellman algorithm, the hardness of discrete logarithms is dominated by the largest prime factor $\ell$ of the group order $n$. In particular, one typically works in a subgroup of ...
yyyyyyy's user avatar
  • 12.1k
8 votes
Accepted

representing binary finite fields in ASN.1

For a binary field $\mathbb{F}_{2^m}$, the polynomial necessarily has degree $m$ (otherwise the field would not have cardinal $2^m$), and its least significant coefficient must be $1$, not $0$ (...
Thomas Pornin's user avatar

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