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.
64
questions
13
votes
3answers
10k views
Multiplicative inverse in $\operatorname{GF}(2^8)$?
I know how to do multiplication over ${\rm GF}(2^8)$:
...
34
votes
4answers
19k 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 ...
10
votes
2answers
4k 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 ...
28
votes
3answers
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 ...
21
votes
2answers
2k 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 ...
20
votes
2answers
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,...
20
votes
2answers
8k 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 ...
10
votes
2answers
948 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 ...
18
votes
1answer
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 ...
6
votes
1answer
4k 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 ...
3
votes
1answer
209 views
Standard basis representation of elements in binary field
In Remark B.1 from this paper it says:
We assume canonical representation for binary fields $\mathbb{F}$, given by an irreducible polynomial and a primitive element $g \in \mathbb{F}$ for it (i.e., ...
4
votes
2answers
331 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 ...
4
votes
2answers
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 ...
3
votes
1answer
764 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 ...
1
vote
1answer
124 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 ...
23
votes
3answers
3k 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 ...
15
votes
1answer
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 ...
4
votes
1answer
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?)
...
3
votes
1answer
1k views
Choosing finite field size in Shamir's Secret Sharing Scheme
The Wikipedia article on Shamir's Secret Sharing says to that to have information theoretical security the splitting algorithm should be evaluated using finite field arithmetic on the field $\rm{GF}(p)...
10
votes
1answer
372 views
how does BearSSL's GCM modular reduction work?
BearSSL (in src/hash/ghash_ctmul.c) seems to be doing a modular reduction that I don't completely understand. Here's the code:
...
8
votes
3answers
3k views
Complexity of arithmetic in a finite field?
I am wondering what the complexities are of adding/subtracting and muliplying/dividing numbers in a finite field $\mathbb{F}_q$. I need it to understand an article I am reading.
5
votes
1answer
79 views
Relationship between generating elements given by cycles in Cayley graph
The strong RSA assumption is that the following problem is hard to solve.
"Given a randomly chosen RSA modulus $n$ and a random $z \in \mathbb{Z}_n^*$, find $r>1$ and $y \in \mathbb{Z}_n^*$ such ...
5
votes
2answers
6k views
Find the generators of multiplicative group of units efficiently?
Say you're give some prime numbers $p_{1},p_{2},p_{3}, p = 2p_{1}p_{2}p_{3} + 1$ (which is assumed to be also prime) and a list of numbers $L$ and you're asked to find the generators of the ...
7
votes
2answers
1k views
What is the importance of Rcon in Rjindael's key expansion from a security prespective?
I do not see why the Rcon function is important, it looks like a waste of cycles.
$$\operatorname{Rcon}(i) = 2^{i-1} \bmod p(x)$$ is in $\operatorname{GF}(2^8)$, ...
4
votes
1answer
134 views
How does Montgomery reduction work?
I want to reduce a multi-precision integer $x$ modulo a prime $p$, very fast. Performing the traditional Euclidean division for only calculating the modulo, is inefficient and modular reduction is at ...
10
votes
2answers
1k views
Is the additive discrete Logarithm problem always easy in Fields?
While thinking about additive DH key exchanges, I somehow had the idea that additive DH key exchange may always be easy to break, if we are in a field.
So here's (directly) the question:
In any ...
7
votes
1answer
1k views
Is it necessary for the Rijndael polynomial to be primitive?
I am working on selecting a S-box for my Cipher (Similar to AES). I found out there are 30 irreducible polynomials and over 16 primitive polynomials of degree 8. Is it necessary to choose a primitive ...
7
votes
2answers
2k views
Should we use IANA groups 14 (MODP), 25, and 26 (ECP)?
By looking at SonicWall Knowledge Base article Key exchange (DH) Groups Supported - Site to Site VPN:
It appears that our firewall supports DH group 25, and 26. Almost everywhere I've seen, they've ...
6
votes
4answers
1k views
Algorithm for computing square roots in $GF(2^n)$
Short question: is there an algorithm for efficiently computing square roots in $\mathbb{F}_{2^n}$?
5
votes
1answer
469 views
Why does a Galois field have to have an order of $p^n$ where $p$ is prime?
I was reading about this in a cryptography book last night. I have a hunch about this, but I can't quite put my finger on it. I think this is a similar situation to an affine cipher, where the ...
4
votes
2answers
569 views
Non primitive lfsr sequence
Given a non-primitive LFSR sequence (i.e number of states is less than $2^n - 1$); how do we find out the the characteristic polynomial? Will Berlekamp-Massey algorithm work in this case?
for example;...
2
votes
1answer
297 views
Cryptographic properties of field multiplication
While reading about AES-GCM, I discovered there is a multiplication over $\operatorname{GF}(2^{128}$). My question is about its cryptographic properties, such as:
Take a random element $X$ from $\...
1
vote
1answer
2k views
Calculating Multiplicative Inverse for Rijndael S-box using EEA
I am currently learning, and I'm stuck on something that I thought is very simple. On many academic sources they suggest using Extended Euclidean Algorithm to calculate the multiplicative inverse for ...
20
votes
5answers
2k views
Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?
Trying to figure out if any (asymmetric) cryptographic primitives exists, which do not rely on arithmetic over a prime field and/or arithmetic over a finite field, some people might get lost in ...
15
votes
1answer
605 views
Security of pairing-based cryptography over binary fields regarding new attacks
In the last week, the discrete logarithm problem was broken for the binary fields $\mathbb{F}_{2^{(14 \times 127)}}$ and $\mathbb{F}_{2^{(27 \times 73)}}$.
Pairing-based cryptography using binary ...
11
votes
3answers
601 views
Mapping between subgroups and the integers
This question is a companion to the equivalent question on elliptic curves.
Preliminaries
Diffie-Hellman, Elgamal, DSA, etc. are examples of protocols that work in the integers modulus a large prime $...
8
votes
1answer
27k 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 ...
1
vote
1answer
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-...
11
votes
1answer
777 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 ...
10
votes
1answer
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 ...
9
votes
2answers
2k views
Why are elliptic curves constructed using prime fields and not composite fields?
I come across this:
Numbers mod composite number does not form a field rather it forms a ring
and
every number has a multiplicative inverse under integer mod prime
Maybe these are the reasons ...
8
votes
2answers
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 ...
7
votes
1answer
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)$?
...
4
votes
1answer
233 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,...
3
votes
2answers
429 views
Constant time multiplication in GF(2^8)
I am trying to implement AES in C; I would like to make it resistant to side-channel attacks but I can't implement the multiplication in constant time. My current code:
...
3
votes
1answer
525 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 ...
8
votes
1answer
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 ...
6
votes
2answers
507 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 ...
5
votes
2answers
624 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 ...
2
votes
1answer
226 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 ...
