# Questions tagged [finite-field]

A finite field is a mathematical construct based on a set of axioms which are held to be true. A number of interesting and useful properties arise from finite fields that makes them particularly suitable for use in cryptography, notably in block ciphers. Questions concerning finite fields should use this tag. Your question may concern finite fields if you are asking about AES, block ciphers or modular arithmetic.

56 questions
Filter by
Sorted by
Tagged with
10k views

### Multiplicative inverse in $\operatorname{GF}(2^8)$?

I know how to do multiplication over ${\rm GF}(2^8)$: ...
18k views

### Galois fields in cryptography

I don't really understand Galois fields, but I've noticed they're used a lot in crypto. I tried to read into them, but quickly got lost in the mess of heiroglyphs and alien terms. I understand they're ...
3k views

### Why does Shamir's Secret Sharing Scheme need a finite field?

I read ampersand's question "Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme", where he asked why Shamir's Secret Sharing Scheme uses arithmetic in a ...
3k views

### What is so special about elliptic curves?

There seems to be sources like this, this also, and some introductions that discuss elliptic curves in general and how they're used. But what I'd like to know is why these particular curves are so ...
1k views

### Choice of multiplication polynomial in Rijndael s-box affine mapping

The Rijndael specification details the design choices for the s-box in section 7.2. They describe the choice of affine mapping as follows: We have chosen an affine mapping that has a very simple ...
4k views

### Design properties of the Rijndael finite field?

So we've already had a question on replacing the Rijndael S-Box. My question is - can we use a different finite field other than the one given by $x^8 + x^4 + x^3 + x + 1$ in $GF(2^8)$. In other words,...
7k views

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

Let $\quad E:\; y^2 = x^3 + ax + b \quad$ be an elliptic curve defined over a finite field $\mathbb F_q$ where $q = p^n$, $a,b \in \mathbb F_q$ and $p \neq 2, 3$. By Hasse's theorem we know that the ...
804 views

### Secure degree reduction for Shamir's secret sharing

I understand the basic Shamir Secret Sharing protocol, and when two shares are multiplied, the degree of the polynomial increases. I've seen in a number of papers a reference to a degree reduction ...
1k views

### Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use?

A recent paper by GĆ¶loÄlu, Granger, McGuire, and ZumbrĆ¤gel: Solving a 6120-bit DLP on a Desktop Computer seems to "demonstrate a practical DLP break in the finite field of $2^{6120}$ elements, using ...
3k views

### How to calculate AES logarithm table?

I would like to know how to find multiplicative inverses in $\mathrm{GF}(2^8)$. I know how to multiply two elements of $\mathrm{GF}(2^8)$ (for example, I know that ...
326 views

### What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$?

The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this ...
2k views

### How to use the Extended Euclidean algorithm to invert a finite field element?

I was doing some practice on cryptography (I'm new to this topic) and was wondering what the following question even means or what it is asking me to find. I do know how to do Extended Euclidean ...
682 views

### How to perform the modular reduce of Rijndael's finite field

I am trying to understand how to calculate the modular reduction of Rijndael's finite field. The example on this page says that {53} ā¢ {CA} = {01}, because ...
118 views

### Subscript R notation for the finite fields

I'm trying to understand the notation used in the literature for Pairing-based cryptography. I know (and I hope I've understood it well) from Wikipedia that $\mathbb{Z}_p$ is the finite field of prime ...
2k views

### How robust is discrete logarithm in $GF(2^n)$?

"Normal" discrete logarithm based cryptosystems (DSA, Diffie-Hellman, ElGamal) work in the finite field of integers modulo a big prime $p$. However, there exist other finite fields out there, in ...
3k views

### Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme

Shamir's original paper (PDF, 197kb) describing a threshold secret sharing scheme states: To make this claim more precise, we use modular arithmetic instead of real arithmetic. The set of ...
2k views

### Elliptic curve and embedding degree

I am new to ECC. I am confused about what the embedding degree in an elliptic curve group represents and what is the impact of its values on the curve and security (small values or large values?) ...
1k views

25k views

### Multiplication/Division in Galois Field (2^8)

I'm attempting to implement multiplication and division in $GF(2^8)$ using log and exponential tables. I'm using the exponent of 3 as my generator, using instructions from here. However I'm having ...
4k views

### Calculating the multiplicative inverse of a number in $GF(2^n)$ where $n > 8$

Suppose that: We have a polynomial $g(x)$ of degree $n$. $n > 8$. $q$ is the multiplicative inverse of $p$ in $G(2^n)$ modulo $g(x)$. If $p = 0$, then $q = 0$. This could be used: As a non-...
702 views

### Why are elliptic curves over a field of characteristic 2 or 3 insecure?

The following is a quotation from my cryptography course: Recent results on the discrete logarithm raise big concerns on the security of elliptic curves over a binary field. What are these ...
2k views

### How was the GCM polynomial found?

As far as I understand, there is no general way to enumerate irreducible polynomials in a particular finite field, which are similar in nature to prime numbers over the integers. The GCM mode finite ...
4k views

### What is this “finite field cryptography”?

See RFC 5931 Ā§ 2.2.1 which talks about "finite field cryptography" as opposed to elliptic curve cryptography and it looks like it is describing the Diffie-Hellman protocol. But Diffie-Hellman is not a ...
2k views

### AES mixcolumn stage

I'm studying AES, and am having problems with the "mixcolumn" stage. I read about finite fields, but I still don't know. How do I construct $GF(2^8)$? ...
229 views

### representing binary finite fields in ASN.1

In SEC 2: Recommended Elliptic Curve Domain Parameters two types of finite fields are utilized - $\mathbb{F}_p$ and $\mathbb{F}_{2^m}$. In the case of sect193r1, $\mathbb{F}_{2^m}$ is the finite field,...
437 views

### How to optimise a finite field multiplication?

I'm currently trying to optimise the finite field multiplication in $\operatorname{GF}(2)[x]/(p)$, where $p = x^8 ā x^7 ā x^6 ā x ā1 ā \operatorname{GF}(2)[x]$. The thing is that I have to multiply ...
3k views

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

I was looking out to find optimum generator for an elliptic curve $E$ over a prime field $\mathbb F_p$. I found the following algorithm: Choose random point $P$ on the curve. Find the order of a ...
589 views

### LED (AES like) algorithm Decryption-Mixcolumn

I want to program decryption algorithm for the LED cipher. The lightweight block cipher LED(Jian Guo, Thomas Peyrin, Axel Poschmann, Matt Robshaw:CHES 2011). All the things is routine except the ...
482 views

### Choice of reduction polynomial in Whirlpool's internal cipher

Whirlpool is an interesting little hash function in the Miyaguchi-Preneel family. In my mind, it's most interesting feature is the design of internal cipher W, where the distinction between key and ...
1k views

### Solve a system of non linear equations over GF

I have the following set of equations: $$M_{1}=\frac{y_1-y_0}{x_1-x_0}$$ $$M_{2}=\frac{y_2-y_0}{x_2-x_0}$$ $M_1, M_2, x_1, y_1, x_2, y_2,$ are known and they are chosen from a $GF(2^m)$. I want ...
166 views

### Why does curve25519 use a cofactor of 8?

This cofactor (as I understand it) effectively discards valid points that satisfy the curve equation over the finite field. Why would one wish to reduce the number of possible private keys, it seems ...
143 views

### How to use Frobenius for finding Square Roots in $GF(2^m)$

Given a polynomial $x$ with degree $n$ in $GF(2^m)$, $1 < n < m$, will any generator of $GF(2^m)$ suffice when applying the Frobenius automorphism to determine the square root of $x$ as ...
2k views

### Understanding elliptic curve point addition over a finite field

I am new to elliptic curve cryptography as well as finite field theory. I am trying to understand point addition in affine coordinates. I understand, that for an elliptic curve $y^{2}=x^{3}+ax+b$ ...
588 views

### Sextic twist optimization of BN pairing - cubic root extraction required?

I found the following paper really interesting: http://www.researchgate.net/publication/220378229_A_family_of_implementation-friendly_BN_elliptic_curves/file/79e4150b3a773beecd.pdf It allows ...
### Does $i^n=j^n$ for $i, j \in GF(2^q)$ and $i \neq j$ for some $n<2^q-1$
Let $i, j \in GF(2^q)$ and $i \neq j$ and $i,j\neq0$. Is that possible that $i^n=j^n$ for some $n$ such that $0 < n < 2^q-1$? I am looking for a proof if the answer is no, or for a method to ...