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 ...
11
votes
3answers
750 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 ...
9
votes
2answers
515 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 ...
6
votes
1answer
129 views
Solving hard problems in $\mathbb Z_{p}^{*}$ when $\mathbb p$ is close to $\mathbb 2^{n}$
Suppose, for some security parameter $n$ you choose a prime $p$ such that $p = 2^n+c$ for some relatively small $|c| < 2^m << 2^n$. I have seen such primes being called Pseudo-Mersenne Primes ...
5
votes
1answer
275 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
0answers
159 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 ...
3
votes
5answers
822 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 ...
3
votes
1answer
154 views
Understanding Feldman's VSS with a simple example
I'm trying to understand Feldman's VSS Scheme. The basic idea of that scheme is that one uses Shamir secret sharing to share a secret and commitments of the coefficients of the polynomial to allow the ...
3
votes
1answer
209 views
Best choice of finite field for AES on a 4-bit microcontroller?
As the finite field of $GF(2^8)$ are isomorphic to $GF((2^4)^2)$, $GF((2^2)^4)$ and $GF(((2^2)^2)^2)$,
which of the fields is best suited and most efficient for 4-bit MCU and why? Would it be ...
3
votes
2answers
281 views
Finding the LFSR and connection polynomial for binary sequence.
I have written a C implementation of the Berlekamp-Massey algorithm to work on finite fields of size any prime. It works on most input, except for the following binary GF(2) sequence:
$0110010101101$ ...
2
votes
3answers
201 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.
Thank you
2
votes
2answers
216 views
Additive ElGamal cryptosystem using a finite field
I'm trying to implement a modified version of the ElGamal cryptosystem as specified by Cramer et al. in "A secure and optimally efficient multi-authority election scheme", which possesses additive ...
1
vote
1answer
90 views
inverse element in Paillier cryptosystem
As I know, in Paillier cryptosystem, the encryption $c$ of a message $m$ is calculated as $c=g^m r^n \bmod n^2$.
Now, I am wondering if I can derive $g^m \bmod n^2$ given that I know $c$, $r$, and ...
-2
votes
2answers
218 views
Factoring a polynomial over a GF [closed]
I have the following question:
What polynomial, when factored over the field $GF (2^8)$ based on the irreducible polynomial that is used in Rijndael, will factor into all the polynomials in the ...
