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.

294 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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., ...
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 ...
119 views

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: ...
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 ...
84 views

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 ...
297 views

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 $\... 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? 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 ... 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. 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 ... 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 ... 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 ... 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 ... 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. ... 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 ... 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 ... 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? 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 ... 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 ... 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 ... 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 ... 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 ... 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 ... 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$... 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 ... 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 ... 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 ... 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? 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 ... 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 ... 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 ... 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$...
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 ...