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 ...
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 ...
3
votes
1answer
153 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 ...
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 ...
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 ...
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 ...
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 ...
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
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
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 ...
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
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 ...
9
votes
2answers
514 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 ...
11
votes
3answers
749 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 ...
