Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

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
0 votes
1 answer
69 views

wrting algorithm for torsion group elements

Yesterday,I took an exam. There are two questions I received very low points. I will write the first question in this post. The question says let $E:y^2:x^3+kx+1$ in GF(p) be an elliptic curve where p ...
1 vote
0 answers
43 views

Is a cryptosystem based on hardness of factorization of polynomials, as defined below valid? [closed]

I'm proposing a cryptosystem as defined below: Private Key: $(R, A, R^{-1})$, where $R = \left(\mathbf{r_1}, \cdots, \mathbf{r_n}\right)$ is full-rank, with $n \geq 4$, even; $A = \left(a_1\mathbf{...
0 votes
1 answer
88 views

Finite Field Arithmetic _ Montgomery reduction

In an attempt to understand the mathematical operations related to encryption with elliptic curves, in particular finite field arithmetic (Modular reduction) I found in the Montgomery reduction that ...
3 votes
1 answer
1k views

When incrementing a private key by 1, by how much is the public key Incremented?

If you have a secp256k1 keypair and you increment the private key by 1, then a faster way to compute the new public key is to perform an addition on the previous public key. But by how much? Some ...
1 vote
0 answers
39 views

I want to find the Zero Value Points on SECP256R1 curve... Is there an alternative to Chien's method of finding roots over large Finite Fields?

This PDF explains that on certain elliptic curves, there exists ZVP (Zero Value Points) that cause zero value registers during the scalar-to-point multiplication (i.e during the double operation or ...
0 votes
0 answers
71 views

Why do we use elliptic curves instead of just the discrete logarithm problem?

We have a cyclic field Fp where p is a prime number, a generator g, and an order n. A generator is an element such that $g^n=1$. A random number x has been chosen as the private key, selected from the ...
1 vote
2 answers
123 views

Providing a bound on the field-trace of a specific kind of polynomial to solve the finite-field isomorphism decisional problem

I am currently enrolled in a computer algebra class for engineers, and while I have some background in discrete algebra from a previous course, it's quite limited. I'm seeking assistance with ...
0 votes
1 answer
133 views

How to know if an ECC public key is y or -y

I'm a beginner still learning how ecc works... And i think I understand that in secp256k1 public keys there is something called addictive and negative inverse for example private key:- ...
1 vote
1 answer
183 views

Multi party computation over ring and fields

I am recently reading about multi party computation and its various existing protocols. From what I understand, all the arithmetic operations are performed over a field or a ring such that when two ...
2 votes
2 answers
101 views

Probabilistic proof of multiplying two elements from non-prime finite field

I was reading this paper, and there, they use the ring $\mathbb{Z}_{\large p}[\alpha]/(\alpha^{\large n}+1)$ for all their operations. And that looks like a construction of finite field $\mathbb{F}_{\...
1 vote
1 answer
49 views

Is there any reference about the half-trace when m is even in F(2^m)

There is a algorithm listed in D.1.6, Algorithm 3, it seems that it is used to solve the quadratic equation when $m$ is even in $F(2^m)$. However, I can not find any reference about this algorithm, as ...
1 vote
0 answers
41 views

How to know the number of digits in the decimals place in elliptic curve division result?

$p$ - is the order of the finite field $n$ - is the order of the group. Private keys can range from $1$ (the generator point $G$) to $n - 1$. All the private keys ($Priv$) lie in certain ranges of 2. $...
2 votes
1 answer
52 views

Is it possible to generate an elliptic curve (with the hard discrete logarithm problem) by iterating only a finite field, but not its $j$-invariant?

Let me ask one question. Maybe, you know an answer. Thanks in advance for any response. Let's fix an elliptic curve $E$ over the field $\mathbb{Q}$ of rationals without complex multiplication, i.e., ...
35 votes
4 answers
5k views

What is so special about elliptic curves?

There seems to be sources like this, this also, and some introductions that discuss elliptic curves in general and how they're used. But what I'd like to know is why these particular curves are so ...
2 votes
1 answer
217 views

Ring Learning With Errors : why is it called ring and referred it as Ring LWE

I am curious about the structure of the quotient ring in Ring LWE. So $R=\mathbb Z_q[x]/(x^n+1)$, where q is prime, $x^n+1$ is an irreducible polynomial and $n$ is a power of 2. So, this structure ...
21 votes
3 answers
2k views

Choice of multiplication polynomial in Rijndael s-box affine mapping

The Rijndael specification details the design choices for the s-box in section 7.2. They describe the choice of affine mapping as follows: We have chosen an affine mapping that has a very simple ...
0 votes
0 answers
50 views

How to calculate Cardinality of an Elliptic curve over $\mathbb Z_{23}$

How to calculate Cardinality of an Elliptic curve over $\mathbb Z_{23}$. $E: y^2 = x^3 + x + 1$ defined over $\mathbb Z_{23}$.
1 vote
1 answer
172 views

How to calculate Legendre Symbol in secp256k1 Elliptic Curve

In this answer by fkraiem he proves a property that: $a^{(p-1)/2} = 1$ if and only if $x$ is even But this doesn't seem to work in my test with the secp256k1 Elliptic Curve. Here is my Python 2 ...
0 votes
1 answer
114 views

In multiplicative subgroup Fp* of an elliptic curve does multiplying an element make it leave the subgroup?

In the case of an Elliptic curve over a GF(p) which has order n and multiplicative group of n-1 elements, does multiplication of an element of a subgroup of order q where q is a divisor of n-1 with a ...
0 votes
2 answers
55 views

What weaknesses are worth investigating in this non-linear matrix cipher?

I have an interesting cipher based on matrix products that I've not seen before. Given plaintext bytes $p\in[0,255]$, pad to a perfect square length and write into the entries of an $n\times n$ matrix ...
1 vote
0 answers
99 views

Number of elements in cyclic group that satisfy an exponent

I'm having trouble with solving the following question: Given two distinct prime numbers $p, q$ where $(p-1)$ and $(q-1)$ are not divisible by $3$, define $n=pq$. For how many elements in $\mathbb Z^*...
3 votes
1 answer
149 views

Problem with efficiency of projective coordinates in Elliptic Curve arithmetic

Ok sort of long post incoming. Will go slow to make it as clear as possible I'm trying to build a C library for Elliptic Curve Arithmetic. Since the idea is to learn from the process, I decided to ...
5 votes
2 answers
979 views

Why are binary extension fields preferred for Shamir secret sharing?

It is known that Shamir's secret sharing works over any finite field but I don't get it why binary extension fields are preferred?
3 votes
0 answers
118 views

How do you securely implement a finite field?

I'm not sure if this question belongs here or to StackOverflow. Please flag it if not. I'm trying to implement a standalone library for finite field arithmetic of prime and prime power order as a way ...
0 votes
0 answers
70 views

AES encryption step: calculate the byte substitution process

I am a self learner and tried to learn AES, so I have a book written in my native language. It has some practical examples about finite fields and AES. It has a question that asks me to calculate the ...
2 votes
2 answers
888 views

Carry-less multiplication vs. multiplication in $GF(2^k)$

I implemented carry-less multiplciation using the CLMUL instruction set. This is similarly fast to simple modulo multiplication. But computating the result mod some polynomial is still very slow. I do ...
2 votes
1 answer
103 views

Merkle tree alternating hash and polynomial

I want to get feedback on the security of a modified merkle tree data structure. Using the image above as a reference assume I have a random oracle function $H$. Assume $H$ outputs a value in $\mathbb{...
0 votes
0 answers
76 views

AES SBOX Masking in Python

I am trying to create an AES Sbox masking based on this paper. In the paper, they tried to mask the sbox described in this other paper. The inversion is been done in GF(4). I know that it is mostly ...
1 vote
1 answer
65 views

Near Maximum Distance Separable Code

I want to find the minimum distance of an $[8,4]$ Near MDS code over a finite field F_4 (NMDS Code is a type of linear code). I want to know which programming language has a built-in function that ...
2 votes
1 answer
258 views

Is there an algebra group (or ring) in which computing the inverse element is hard without some trapdoor information?

Specifically, I want an algebra group $G$ (or ring $R$) features: Given elements $g,h\in G$ (or $R$ ), computing $g\cdot h \in G$ (or $R$ ) is easy. Given an element $g \in G$ (or $R$ ), finding the ...
2 votes
1 answer
355 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
2 answers
222 views

Elliptic curves over extension fields

I'm trying to understand which benefits can using of extension fields in elliptic curve cryptography bring over prime fields. Popular curves like secp256k1, curve25519, secp384r1 are defined over a ...
39 votes
5 answers
23k 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
1 answer
123 views

Convert multiplication in $GF(2^{128})$ to bitwise AND?

Suppose we have $GF(2^{128})=F_2[x]/(x^{128}+x^7+x^2+x+1)$ and $a,b,c \in GF(2^{128})$ with $a*b=c$, where * is multiplication in $GF(2^{128})$. Could we convert ...
1 vote
1 answer
156 views

learning with errors

If I talk about efficiency of system of learning with error, is it it fine for q to be composite in Z_q, the ring of integers. As when q would not be prime, Z_q will not be field anymore, won't it ...
0 votes
2 answers
111 views

Query about arithmetic finite fields

I was working on implementing shamir secret sharing in GF(2^256), According to my knowledge multiplication in a finite field is defined as mul(a,b) = (a*b)%mod, where mod is the irreducible polynomial....
1 vote
1 answer
165 views

On the bit security of elliptic curves

My understanding is that an elliptic curve $E$ over a finite field $\mathbf{F}_q$ has a bit security of $\sqrt{q}$ assuming Pollard rho or Baby-step giant-step. In this thread, it is explained that ...
2 votes
1 answer
90 views

Discrete log hardness when secret is multiplied by public value

Given y = g ^ x is discrete log hard on some finite field, is y = g ^ (kx) also equally secure if the value ...
1 vote
1 answer
67 views

How to write monomials in $GF(2^n)$ as a system of equations in $GF(2)$

Let $F = GF(2^n)$ and $P(x) = x^e, P : F \rightarrow F$ be a monomial of degree $e$. How to write each bit of the output of $P$ as a function of input bits? In other words, how to write it as a system ...
1 vote
1 answer
102 views

How does big Galois groups yield better security in NTRU Prime?

I'm still kinda new to Galois theory so I apologize if this question is very obvious to some people. Basically I'm reading this paper by the NTRU Prime team and in section 2.5 it's explaining how ...
1 vote
1 answer
115 views

Is product of two linear combinations over a finite field information hiding?

Suppose we have a 32-bit message $ M=(m_1,..m_{32}) \in \{0, 1\}^{32} $ and we have secrets $ F_{i, b} $ and $ G_{i, b} $ (2x32+2x32=128 secrets in total). $$ \forall 1 \leq i \leq 32, b \in \{0, 1\} :...
1 vote
0 answers
119 views

Feldman Verifiable secret sharing verify [closed]

I recently started to learn about Shamir secret sharing and Feldman's VSS Scheme. I know the concepts But I can't figure out how it works. mostly because many of modulates are with "p" and ...
5 votes
1 answer
333 views

Binary Elliptic Curves Point Doubling Formula - Calculate Lambda from P3

As I am studying ordinary (non-supersingular) binary elliptic curves in the Guide to ECC book by Hankerson (Section 3.1, page 81), for point doubling, the equations presented in the book are: $x_3 = \...
3 votes
2 answers
215 views

"Supported groups" in RFC 8446 (TLS 1.3)

What is meant by "supported groups" in the section 4.2.7. "Supported Groups" of RFC 8446: /* Finite Field Groups (DHE) */ ffdhe2048(0x0100), ffdhe3072(0x0101), etc: Is the digits - ...
2 votes
1 answer
914 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 ...
1 vote
1 answer
44 views

Can some cryptographic conclusions in the prime field be applied to the Galois field?

Such as integer factorization problem and discrete logarithm problem. Assuming a large polynomial is obtained by multiplying two generated polynomials, is it NP hard to decompose it into these two ...
2 votes
2 answers
194 views

Algebraic Normal Form of a function in $\operatorname{GF}(2^{n})$

Consider the function $f(x)=x^{2k+1}$ in $\operatorname{GF}(2^{n})$ for $n$ odd and $\gcd(k,n)=1$, which is differentially 2-uniform function. For $n=3$, $k=1$, I want to find the Algebraic Normal ...
1 vote
1 answer
60 views

Prod Check Gadget in PLONK - any polynomial which satisfies the prod check seems to be the trivial polynomial

In Dan Boneh's PLONK Video - https://www.youtube.com/watch?v=vxyoPM2m7Yg he refers to the Prod Check Gadget $\omega \in F_p$ is a primitive $k$-th root of unity ($\omega^{k-1} = 1$) $H = \{1, \omega, \...
1 vote
1 answer
87 views

Hardening a polynomial checksum scheme

I have a checksum scheme that uses a simple polynomial summation as described here. Basically I'll take a random value $R$ and a set of inputs $[v_0, v_1, v_2]$ and checksum it like $v_0*R + v_1*R^2 + ...
30 votes
2 answers
14k views

How to determine the order of an elliptic curve group from its parameters?

Let $\quad E:\; y^2 = x^3 + ax + b \quad$ be an elliptic curve defined over a finite field $\mathbb F_q$ where $q = p^n$, $a,b \in \mathbb F_q$ and $p \neq 2, 3$. By Hasse's theorem we know that the ...

1
2 3 4 5
8