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
3
votes
2answers
2k views

Solving Quadratic equations in Galois Field (2^163)

Hello I am working on implementing a message to elliptic curve point mapping hardware circuit I have done some research and found out the koblitz mapping method: I will be using a field of binary ...
3
votes
1answer
118 views

Is there a multiplicative group of integers modulo p in which the discrete logarithm is easy?

The complexity of computing discrete logarithms in a multiplicative group modulo a prime $p$ is assumed to be sub-exponential time. The complexity is determined by $q$, the biggest factor of the group ...
3
votes
1answer
208 views

Standard basis representation of elements in binary field

In Remark B.1 from this paper it says: We assume canonical representation for binary fields $\mathbb{F}$, given by an irreducible polynomial and a primitive element $g \in \mathbb{F}$ for it (i.e., ...
3
votes
1answer
263 views

Elliptic curves on finite fields

I've been reading: https://github.com/bellaj/Blockchain/blob/6bffb47afae6a2a70903a26d215484cf8ff03859/ecdsa_bitcoin.pdf On page 22 it shows an eliptic curve over F17. I have added the orange lines ...
3
votes
2answers
119 views

Finding Nonlinear boolean functions

Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements. I wonder if there is any known algorithm/construction that, given any $n\geq 1$, returns a boolean function $f:\mathbb{F}^n_2\rightarrow \...
3
votes
1answer
524 views

How to optimise a finite field multiplication?

I'm currently trying to optimise the finite field multiplication in $ \operatorname{GF}(2)[x]/(p)$, where $p = x^8 ⊕ x^7 ⊕ x^6 ⊕ x ⊕1 ∈ \operatorname{GF}(2)[x] $. The thing is that I have to multiply ...
3
votes
1answer
761 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
315 views

Sextic twist of BN pairing parameters vs security

I've previously asked questions on BN pairing parameters. Here's one more. In the BN construction, one is working in a subgroup of a curve over an extension field $\mathbf{F}_{p^{12}}$ for some ...
3
votes
2answers
184 views
+100

Must a line hitting two points on the elliptic curve over a finite field hit another point by continuation?

The Arstechnica article title as "A (relatively easy to understand) primer on elliptic curve cryptography" claims this; In fact, you can still play the billiards game on this curve and dot ...
3
votes
1answer
187 views

In a shamir secret sharing scheme, why can't the secret be a middle coefficient and only the first or the last?

In the shamir secret sharing scheme, the Secret s is set as the constant in the equation $ y_p = s+ \sum_{i=0}^{i = t-1} a_i * x_p^i$ s can only be the constant term or the last coefficient or the ...
3
votes
1answer
211 views

converting finite field elements to octet strings

I need to convert elements of the finite field $GF(p^k)$, where $p$ is an odd prime, to octet strings. To be more precise, I want to include elliptic curve points over $GF(p^2)$ in a Subject Public ...
3
votes
1answer
1k views

Why does FIPS 186-4 require specific sizes for keys?

In FIPS 186-4, page 32, about FFC crypto it is required that the length of $p$ will be exactly 1024 bit and the length of $q$ will be exactly 160 bit. Why is the requirement not stated in terms of ...
3
votes
1answer
68 views

Is inversion always cheap with Twisted Edwards curves?

I'm reading on Jubjub, which is planned for the next upgrade of Zcash. It is based on a Twisted Edwards curve with parameters $a = -1$ and $d = −(10240/10241)$. The reading says Jubjub does not need ...
3
votes
1answer
109 views

Is Finite Field Multiplication Distributive? Moving Affine Transform in AES

In AES the output of the SubBytes step is equal to: $a_{0-15} = d*c_{0-15}^{-1}+b$ where $d$ is a constant 8x8 matrix and b is a constant 8x1 matrix both in $GF(2)$. The inversion is done in $GF(2^...
3
votes
1answer
143 views

Primitive root in a finite field

Wen-Her Yang and Shiuh-Pyng Shieh proposed two password authentication schemes by employing smart cards, one is timestamp-based and the other one is nonce-based. Their scheme consists of 3 phases: ...
3
votes
1answer
145 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 ...
3
votes
1answer
84 views

Question about block erasure codes

I have a question about linear block erasure codes that are described in this paper. I briefly describe the idea behind the linear erasure codes and then I ask my question. Given a set $d=\langle x_i ...
3
votes
0answers
213 views

Group Rings on Cryptography

Let $R[G]$ or $RG$ be the group ring where $R=F_q$ and $G$ is any group. Let $Dim(V)=\vert G \vert$. It's clear that $V$ has $\vert R \vert^{\vert G \vert}$ distinct $\vert G \vert$-tuples. This ...
3
votes
0answers
155 views

How to map the points of an elliptic curve cyclic group to $\mathbb{Z}_q$ using a hash function?

Let $E$ be an elliptic curve defined over $\mathrm{GF}(q)$, where $q=p^r$. Let $G$ be a cyclic group of points of $E$. Then how we can map points of $G$ into $\mathbb{Z}_q$ using a hash function.
3
votes
0answers
203 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 \...
2
votes
3answers
465 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 ...
2
votes
1answer
297 views

Cryptographic properties of field multiplication

While reading about AES-GCM, I discovered there is a multiplication over $\operatorname{GF}(2^{128}$). My question is about its cryptographic properties, such as: Take a random element $X$ from $\...
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?
2
votes
1answer
96 views

Diffie-Hellman with Galois field

I Google around and can't find any page mentioning Diffie-Hellman with Galois field $GF(p^n)$ with $n>1$. Is there a reason for this? For example, wouldn't Diffie-Hellman with $GF(2^n)$ be ...
2
votes
2answers
1k 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
396 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 ...
2
votes
2answers
203 views

How to find the co-efficients of a function within Zp[x]?

I am a newbie in Finite Field arithmetic and while trying to implement an Elliptic Curve Cryptography based ABE scheme in a programming language, I am unable to understand how to implement function ...
2
votes
1answer
226 views

Why does curve25519 use a cofactor of 8?

This cofactor (as I understand it) effectively discards valid points that satisfy the curve equation over the finite field. Why would one wish to reduce the number of possible private keys, it seems ...
2
votes
1answer
109 views

Are there any security risks in using Elliptic Curves defined over fields $\mathbf{F}_{p^n}$ where $n>1$

I've recently been studying elliptic curves, and I've found that most of the current implementations use fields $\mathbf{Z_p}$ or in some cases $\mathbf{F}_{2^n}$. All the reasons I've seen for not ...
2
votes
1answer
545 views

Questions about the Curve25519-donna implementation

I'm trying to understand the implementation of the following function: Please note questions in comments. ...
2
votes
3answers
571 views

Generating bilinear pairing parameters - running time of finding member of p-torsion group

Update: Question completely rephrased. I want to create the parameters for a bilinear pairing (the Tate pairing in this case). In case you're interested I'm following this thesis, specifically the ...
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
6k 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?
2
votes
1answer
9k views

multiplicative inverse in galois field $2^8$

I am trying to compute the multiplicative inverse in galois field $2^8$.The question is to find the multiplicative inverse of the polynomial $x^5+x^4+x^3$ in galois field $2^8$ with the irreducible ...
2
votes
1answer
155 views

Complexity of Gaussian Elimination over a Finite Field

I read somewhere that the complexity of solving a Linear $n\times n$ system over a Finite Field $\Bbb F_q$ using Gaussian Elimination is $\mathcal{O}(n^3)$ operations in $\Bbb F_q$. What's the role of ...
2
votes
1answer
76 views

Finding subgroup in elliptic curve over finite field $ \mathbb{F}_{11}$

For elliptic curve $ y^2 = x^3 +3x+7$ I found the finite group $ E(\mathbb{F}_{11})= \left\{ \mathcal{O}, (1,0),(5,2),(5,9),(8,2),(8,9),(9,2),(9,9),(10,5),(10,6) \right\}$. I have to find a ...
2
votes
2answers
321 views

AES alternate equation for the S-Box affine transformation

The Wikipedia article for the AES S-Box gives an alternate equation for the affine part of the S-Box transformation: $$b_{out} = (b_{in} \times 31_d) \operatorname{mod} 257_d \oplus 99_d$$ 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 ...
2
votes
1answer
168 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
3k views

Finding the LFSR and connection polynomial for binary sequence. [closed]

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
1answer
484 views

Multiplicative inverse in ${GF}(2^4)$

I want to create a $4\times4$ multiplicative inverse table in $GF(2^4)$. The primitive polynomial given is $P(x)= x^4+x+1$ (NOTE: the values in the table need to be in hexadecimal format, hence I'll ...
2
votes
1answer
298 views

Computational Complexity: ECC multiplication vs Modular multiplication

How does performing scalar multiplication on an elliptic curve compare to exponentiation in a multiplicative group modulo a prime? I.e. on a given elliptic curve of size $|t|$, what's the complexity ...
2
votes
1answer
75 views

What is the difference between the 23 bi-affine and the 39 fully quadratic equations of the rijndael sbox?

In Cryptanalysis of Block Ciphers with Overdefined Systems of Equations Nicolas Courtois and Josef Pieprzyk define 23 so called bi-affine equations (in Appendix A of the paper) between the input x and ...
2
votes
1answer
76 views

choices for k in binary finite field modular reduction algorithm

In the Guide to Elliptic Curve Cryptography there's this algorithm: My question is... what is $k$? Is it just some random value we pick? If so are some numbers better than others?
2
votes
1answer
152 views

AES S-Box: Possible options for constant to calculate S-Box values

To calculate the values of S-Box in AES, I came across a lot of resources where constant {63} was chosen. It is said that {63} satisfies the condition of S-Box that it should not have any fixed points ...
2
votes
1answer
128 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 ...
2
votes
1answer
898 views

How to perform AES MixColumns as matrix multiplication in GF(2) (boolean values)?

AES MixColumns is done by multiplying a $4 \times 4$ matrix and a column of the AES state (a vector). Addition and multiplication are done in $\operatorname{GF}(2^8)$. In the paper White-box AES, the ...
2
votes
1answer
370 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
1answer
135 views

Decoding a message on elliptic curve

Let's say I have an elliptic curve $E$ $y^2=x^3 + 486662x^2 + x$ over a prime field $GF(2^{255} - 19)$. My algorithm for computing $E(m)$ is as follows: I take the bits 1 through 32 of the message ...
2
votes
1answer
196 views

Cryptographic Arithmetic Toolbox/Software [closed]

This term I have many cryptography courses treating finite fields. I was wondering if there is any good software that could help doing basic operations in galois fields etc. I already googled but ...