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
vote
1answer
121 views

Using Hadamard Form of a Matrix in the Block Cipher

Definition: A matrix A of size $2^n$ is a Hadamard matrix, if has the following form $$ A= \left( \begin{array}{cc} U & V \\ V & U \end{array} \right)_{2^n\times 2^n}\, , $$ where $U$ and $V$...
-1
votes
2answers
197 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
3k 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-...
1
vote
1answer
128 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 ...
3
votes
1answer
203 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?
2
votes
3answers
265 views

How can I get the binary form of AES's MDS matrix in MixColumns tranformation?

I need to write a procedure for calculating the MixColumns's operation result in the following form: $M*X^T,$ where $M$ is a 128x128 binary matrix, $X$ is a 128-bit vector (the state). My question ...
7
votes
2answers
1k 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
425 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
763 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
1answer
118 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
250 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
306 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, ...
0
votes
1answer
143 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 ...
4
votes
1answer
211 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,...
7
votes
2answers
606 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 ...
4
votes
2answers
473 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
94 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
563 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 ...
6
votes
0answers
205 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
3answers
727 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
907 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
232 views

Abelian groups in Elliptic curves [closed]

Do every elliptic curve defined over a prime field forms an abelian group?
1
vote
0answers
58 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
118 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
443 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
181 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 ...
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
153 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-...
8
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 ...
4
votes
2answers
695 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
467 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
120 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
821 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
91 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
270 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
363 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
321 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
57 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
465 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
161 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
322 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
284 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 ...
10
votes
2answers
855 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 ...