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.

Filter by
Sorted by
Tagged with
-1
votes
2answers
222 views

LFSR, polynomial , finite field

I'm having a hard time understanding the concept of LFSR, polynomials and finite field and how to solve exercises like picture below. Could anyone give me some pointer on where to start?
1
vote
1answer
165 views

(AES in mind) How can we show two irreducible polynomials have a bit-wise linear isomorphism

This refers to answer 2 on a similar question:Design properties of the Rijndael finite field I am unsure what many of the terms mean in this answer. I think a bit-wise linear isomorphism of ...
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-...
3
votes
1answer
207 views

Why equation Y^2=X^3 +AX+B can't work with finte field of charateristic 2?

I know that we can't define $dx/dy$ with this equation because $2y = 0$ with finite field of charateristic $2$. But with $GF(2^n)$ (has characteristic by $2$) $2=x$ not $0$. Do I misunderstand here?
8
votes
2answers
2k views

Why is x^8 + x^4 + x^3 + x + 1 used in AES's Rcon?

I am not familiar with field theory so please bear with me if this is obvious to you. I was wondering why this particular reducing polynomial $x^8+x^4+x^3+x+1$ is picked for AES' Rcon. Can't it be ...
1
vote
1answer
538 views

how to choose a random secret key for ECDH

I am a beginner, I can understand the basics of ECC and elliptic curve, i can't find where I missed to understand. But I have a great doubt in ECDH regarding below. Could any of you please clarify for ...
8
votes
1answer
909 views

When to use safe prime or Schnorr group

Protocols that use $\mathbb{Z}_{p}^*$ arithmetic often choose $p$ to be a safe prime ($p = 2q + 1$, for prime $q$) or to have the Schnorr group form ($p = rq + 1$, for prime $q$). I understand that ...
2
votes
2answers
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 ...
-2
votes
1answer
138 views

are all elements of ZpxZp in ECC definite over Zp

are all elements of ZpxZp in ECC (elliptic curve) definite over Zp ? otherwise: assume G a base point of ECC and n the order of G. why n is equal or nother to p*p ? (p a prime number). (Think to a ...
2
votes
0answers
312 views

Construction of Isomorphism between Galois Fields

I am trying to create an isomorphism between GF($2^8$) and an extension field in GF($(2^4)^2$). The finite field GF($2^8$) uses the Rijndael(AES) irreducible polynomial.In this field I have found 128 ...
1
vote
1answer
392 views

Shamir's Secret Sharing on non-prime GF

I am implementing Shamir's secret sharing scheme on arbitrary binary files. I don't intend to use this; this is a project to help me explore cryptography. In setting up the finite field arithmetic, ...
4
votes
2answers
576 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$-...
4
votes
1answer
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,...
0
votes
1answer
230 views

trying to understand multiplication + reduction in binary finite fields [duplicate]

The wikipedia.org article on Finite field arithmetic provides an example of multiplying $83$ and $206$ in $\mathbb{F}_{2^8}$ with $x^8+x^4+x^3+x+1$ as the reducing polynomial (in fact it is the ...
7
votes
2answers
775 views

Endomorphism ring of a Elliptic Curve and $j$ invariant

I am reading Schoof's 1995 paper, Counting points on elliptic curves over finite fields, page 236, Proposition 6.1(i). I am trying to understand page 238 (second paragraph) of the proof: if the ...
2
votes
0answers
98 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 ...
3
votes
2answers
967 views

Implementation of ECC over binary field

I am supposed to implement ECC over binary field (in C++) for equations of the type - $y^2 + xy = x^3 + ax + b$, as my project. I wish to include the following features : The user will enter a prime ...
3
votes
1answer
566 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
2answers
1k 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 ...
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 ...
5
votes
1answer
186 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
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 ...
-1
votes
1answer
244 views

Abelian groups in Elliptic curves [closed]

Do every elliptic curve defined over a prime field forms an abelian group?
1
vote
0answers
61 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
124 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 ...
0
votes
1answer
629 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$. ...
0
votes
1answer
174 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-...
33
votes
4answers
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 ...
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 ...
1
vote
2answers
137 views
2
votes
1answer
5k 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?
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 ...
0
votes
1answer
118 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
2k 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?
4
votes
1answer
276 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
388 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
389 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
59 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
596 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 ...
1
vote
1answer
412 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 ...
2
votes
1answer
167 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 ...
3
votes
2answers
452 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{...
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 ...
3
votes
1answer
702 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 ...
3
votes
1answer
138 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
773 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 ...
1
vote
1answer
121 views

How should I define order according to domain parameters in elliptic curve pairing groups?

According to domain parameters, as an example Type 1 pairing domain parameters are ...
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.
3
votes
2answers
434 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$...