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.

4
votes
2answers
381 views

Elliptic Curve Isogenies, Frobenius endomorphism relation to characteristic equation

In Schoof's 1995 paper, Counting points on elliptic curves over finite fields, page 236, Proposition 6.1(i) states: Let $\mathbb{E}$ be an elliptic curve over $\mathbb{F}_p$. Suppose that its $j$-...
2
votes
0answers
86 views

How many Affine function can be made from $4 \times 4$ and $8 \times 8$ S-boxes?

The nonlinearity of an S-Box is defined as the non-linearity of its vectorial Boolean Function. Let $F$ be the hamming distance between the set of all non-constant linear combinations of component ...
11
votes
1answer
507 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 ...
5
votes
0answers
181 views

Share Conversion between Different Finite Fields

Let us have any linear secret sharing scheme (LSSS) that works on some field $Z_{p}$, where p is some prime or a power of a prime e.g., Shamir Secret Sharing, Additive secret Sharing. The problem at ...
10
votes
1answer
1k 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 ...
0
votes
2answers
590 views

addition on finite elliptic curves

I tried to calculate the sum of two Points on an elliptic curve in a finite field. The Curve is defined as following: $$y^2 \equiv x^3 + x \mod 257$$ So the curve parameters are $a = 1,b = 0,p = 257$...
2
votes
2answers
792 views

How to apply Pollard's Rho Method on elliptic curves to solve discrete logarithm problem in finite field?

I have ElGamal signature scheme implemented in finite field $\mathbb{F}_p$. The thing is that I need to apply Pollard's Rho Method on elliptic curve $E(\mathbb{F}_p)$ to this scheme, solve discrete ...
-1
votes
1answer
212 views

Abelian groups in Elliptic curves [closed]

Do every elliptic curve defined over a prime field forms an abelian group?
1
vote
0answers
54 views

Efficient proof of linear subspace membership

I am trying to find an efficient method of doing the following: Let $U$ be a $d$-dimensional linear subspace of $\mathbb{F}_q^n$. I want a protocol between a trusted party $T$, a prover $P$ and a ...
2
votes
1answer
113 views

A Question about Irreducible Polynomials [closed]

I am doing some self-study in the area of Cryptography. I am using the Third Edition of the book "Cryptography Theory and Practice" by Douglas R. Stinson. Based upon the information on page 105, in ...
5
votes
2answers
376 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 ...
5
votes
1answer
180 views

Can we have Rijndael s-boxes constructed using reducible polynomials?

Is it necessary for the Rijnael polynomial to be irreducible? Can we have s-boxes constructed using reducible polynomials? If not what is the mathematical property that is obstructing to do so?
7
votes
1answer
970 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 ...
0
votes
1answer
1k 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 $ ...
0
votes
1answer
144 views

Order of an elliptic curve defined over a prime field

I found the following algorithm to find the generator of an elliptic curve: Find the order of the curve - N. Choose any random point on the curve - P. Find the order of that point - n. Calculate co-...
7
votes
1answer
2k 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 ...
1
vote
1answer
2k views

AES MixColumns using L and E lookup tables

I am trying to verify the multiplication by $\mathtt{02}$ in Galois Fields for MixColumns function using the L and E lookup tables. I could verify $\mathtt{D4}\cdot\mathtt{02}=\mathtt{B3}$ by manual ...
2
votes
2answers
539 views

How can I find the generator of a composite group and $Z_p*$?

I was doing some research on elliptic curves. I know how to find the generator of $Z_p$ (this is a prime group). But I came across the term $Z_p*$ (group containing elements that relatively prime to $...
0
votes
1answer
430 views

Multiplication by 2 in the Rijndael Galois field

I was studying the mix column transformation in AES and working through an example. $[\mathtt{02}]\cdot[\mathtt{87}]$ - this multiplication works fine in the polynomial form modulo $x^8+x^4+x^3+x+1$. ...
1
vote
2answers
115 views

Does the generator (base point) is preshared between the sender and receiver in elliptic curve cryptography?

Or the elliptic curve and the generator point are known to everyone?
1
vote
2answers
676 views

Comparing elliptic curves over prime fields against EC over binary fields

In which scenarios we go for prime fields or binary fields? Please indicate why we would choose one over the other.
2
votes
1answer
4k views

How to find the generator of an elliptic curve? [duplicate]

If the elliptic curve has prime order of points, then all of its points are generator. Is this true? If so, how can I find the optimized generator(which generates more number of points) among them?
0
votes
1answer
81 views

Do the elliptic curves over prime fields must always contain prime number of elements (prime order)?

I have gone through one example where i saw a curve defined over some prime number containing non-prime order.
2
votes
1answer
1k views

why are non singular curves used in elliptic curve cryptography?

It is not possible to draw tangent at all the points of a singular curve. What is the specialty of this and how it is related to cryptography and elliptic discriminant?
9
votes
2answers
1k 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 ...
4
votes
1answer
246 views

Elliptic curves with field sizes that not byte-aligned

Why there are abnormal field size like 521, 571, 233, 283 bits in prime and binary fields that are defined by NIST?
2
votes
1answer
346 views

The existence of partial homomorphic additive encryption with bit-wise XOR operation

According to Protocol A that was presented in Section 3.1 paper entitled "Some Efficient Solutions to Yao’s Millionaire Problem" (2013). [1] In that protocol they used an assumption that there is ...
9
votes
2answers
288 views

Advantage of $\operatorname{GF}(2^8)$ over $\mathbb Z/2^8\mathbb Z$ in AES/Rijndael

The Galois Field is used in the mixColumns step of the Rijndael-Algorithm. Over $\operatorname{GF}(2^8)$ (irreducible polynomial: $x^8 + x^4 + x^3 + x + 1$), 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)$, ...
0
votes
1answer
56 views

Commiting to a linear relation over a finite field

Suppose I have some finite field $k$. I am wondering if there exists a way to commit to a linear relation $a_1x_1 + a_2x_2 + \cdots + a_mx_m = b$ over $k$ , such that I can later reveal that a certain ...
2
votes
2answers
425 views

Finding the cycle set of specific polynomial

I have a school assignment where the problem lies in finding the cycle set of two different polynomials. I tried to look up different tools on how to solve these problems, but I have a hard time ...
2
votes
1answer
150 views

How calculation over $GF(2^2)$ is executed?

I was unable to understand the calculation procedure given for $GF(2^m)^2$ in the follwing pdf: http://faculty.washington.edu/manisoma/ee540/EE540finite.pdf In page 21 of the pdf, "Inversion over ...
2
votes
2answers
261 views

How to determine proportion of quadratic residues in elliptic curve group?

I'm using a 'try and increment' method to hash to an Elliptic Curve point, explained below. With security parameter $k$, EC equation $y^2 = x^3 + ax + b \mbox{ mod } q$, we have: $ u = sha256(\mbox{...
1
vote
1answer
262 views

Generating Diffie-Hellman parameters

I'm trying to implement a diffie-hellman key exchange in c++, and I'm struggling with my missing understanding of math / group theory. Let's say I found a large prime number p - how can I find a ...
9
votes
2answers
769 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 ...
3
votes
1answer
461 views

Short Weierstrass equation is non-singular for not 2 or 3 characteristic

Consider a field $K$ of characteristic $p \neq 2,3$. Consider a curve $E$ over $K$ defined by the equation $y^2 = x^3 + ax + b$. How can I show that: $E$ is not an elliptic curve (it is not ...
2
votes
1answer
460 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 ...
4
votes
2answers
2k 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 ...
3
votes
1answer
122 views

How to find irreducible polynomial for Barreto-Naehrig curves?

As described in this paper(section 3) to implement pairing on Barreto-Naehrig curves. The prime in their case is $p=82434016654300679721217353503190038836571781811386228921167322412819029493183$ and ...
1
vote
1answer
561 views

Shamir Secret Sharing GF(p) or GF(2^8)

I'm implementing Shamir's Secret Sharing Scheme, but I've hit a conceptual roadblock. In Shamir's paper "How To Share A Secret" he creates his shares an a finite field of order p, where p is some ...
3
votes
2answers
253 views

In what sense addition modulo $n$ ($n>2$) isn't linear in the field $\mathbb{F}_2$?

I've been reading the Reason why “XOR” is a linear operation, but ordinary “addition” isn’t? question, in which one of the answers states that addition modulo $n$ ($n>2$) is linear in $\mathbb{Z}_n$...
0
votes
1answer
120 views

XOR and bilinear form property

I know that $XOR$ is equivalent to modular addition in the field $\mathbb{F}_2 = \{0,1\}$ (is it right?), and thus should satisfy the following property of a bilinear form: $$\oplus(u+v,w) = \oplus(u,...
4
votes
1answer
1k 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
0answers
173 views

Homomorphic encryption over finite fields

I'm curious on the following question: let $\mathbb{F}_{2^n}$ be a finite field which is an extension of $\mathbb{F}_2$ with order of $n$, is there an encoding scheme $e:=\mathbb{F}_{2^n}\rightarrow \...
0
votes
1answer
93 views

How many field operations are needed when you compute kG in elliptic curves with a multiple additions or the double-ans-add-algorithm?

For an assignment, we have to calculate how many field computations are needed to calculate kG in an elliptic curve. They want us to show this for two different ways of calculating kG. The first way: ...
1
vote
1answer
96 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 ...
-2
votes
3answers
697 views

How to reverse this hash function?

I have a function that takes an $m$ byte inputs $x_i$ and maps it a 32 byte outputs $y_j$. The hash function is defined as: $$y_j = \sum_{i=1}^{m} (x_i)^{i-1} \pmod {127}$$ The input is restricted ...
4
votes
1answer
215 views

Schnorr signature security level as compared to AES/RSA

As per the Schnorr's original paper (1991), The Security Complexity $2^t$: We wish to choose the parameters $p$, $q$ so that forging a signature or an authentication requires about $2^t$ steps by ...
7
votes
2answers
3k 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 ...
3
votes
2answers
1k 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 ...