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
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{...
Yuri S VB's user avatar
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 ...
user2284570's user avatar
1 vote
0 answers
44 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 ...
Cyth's user avatar
  • 11
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 ...
user avatar
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 ...
Saku's user avatar
  • 101
0 votes
1 answer
139 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:- ...
Melwyn's user avatar
  • 1
1 vote
2 answers
124 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 ...
EngineerMathlover's user avatar
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}_{\...
the thinker's user avatar
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 ...
Insecticide's user avatar
1 vote
0 answers
42 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. $...
Maltoon Yezi's user avatar
2 votes
1 answer
54 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., ...
Dimitri Koshelev's user avatar
0 votes
0 answers
56 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}$.
Sanjai Kumar's user avatar
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 ...
user479610's user avatar
0 votes
1 answer
89 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 ...
Nawras Hussein's user avatar
1 vote
1 answer
173 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 ...
Devanshu Linux's user avatar
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 ...
flinty's user avatar
  • 103
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 ...
immigrantswede's user avatar
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^*...
Eatay Mizrachi's user avatar
3 votes
1 answer
155 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 ...
popeye's user avatar
  • 95
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 ...
tur11ng's user avatar
  • 962
0 votes
0 answers
71 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 ...
user avatar
0 votes
0 answers
77 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 ...
John's user avatar
  • 1
1 vote
1 answer
66 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 ...
Kurious Koder's user avatar
2 votes
1 answer
259 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 ...
X.H. Yue's user avatar
  • 370
2 votes
2 answers
232 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 ...
pacman's user avatar
  • 429
1 vote
1 answer
127 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 ...
Halulu's user avatar
  • 11
0 votes
2 answers
112 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....
CipherNewbie's user avatar
1 vote
1 answer
159 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 ...
user479610's user avatar
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 ...
bobby's user avatar
  • 13
2 votes
1 answer
91 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 ...
ManishB's user avatar
  • 23
1 vote
1 answer
184 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 ...
Sumana bagchi's user avatar
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 ...
Mairon's user avatar
  • 161
1 vote
1 answer
103 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 ...
faust's user avatar
  • 13
1 vote
0 answers
122 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 ...
user109261's user avatar
5 votes
1 answer
337 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 = \...
prairie99's user avatar
3 votes
2 answers
218 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 - ...
LUN's user avatar
  • 119
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 ...
ZhuJerry's user avatar
2 votes
1 answer
104 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{...
vimwitch's user avatar
  • 139
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, \...
user93353's user avatar
  • 2,245
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 + ...
vimwitch's user avatar
  • 139
1 vote
1 answer
95 views

Are you aware of cryptographic contexts (e.g., post-quantum) in which a square root $\sqrt{\cdot}$ must be computed in constant time?

Let $\mathbb{F}_q$ be a finite field of odd characteristic. I know that a constant-time implementation of the square root extraction $\sqrt{\cdot} \in \mathbb{F}_q$ is used in the context of hashing ...
Dimitri Koshelev's user avatar
1 vote
1 answer
38 views

Data fingerprint using multiple multilinear polynomials

Related to this question. I'm trying to find a way to use this fingerprint system without a second pre-image attack. Assume I have a set of elements $V = [v_0, v_1, v_2]$ in $\mathbb{F}_p$. Assume the ...
vimwitch's user avatar
  • 139
2 votes
1 answer
134 views

If SNARKs generally work in finite fields, how are non integer values handled - say fixed point decimal numbers?

In Vitalik Buterin's write-up on SNARKs Quadratic Arithmetic Programs: from Zero to Hero, he writes Note that the above is a simplification; “in the real world”, the addition, multiplication, ...
user93353's user avatar
  • 2,245
4 votes
2 answers
375 views

Should tower field implementations use the x^k element representation?

I'm working on a friendly tower finite field implementation for educational purposes. The library should allow easy building of tower fields from smaller ones - a user may define $\mathbb F_q$ and ...
tk2928's user avatar
  • 41
0 votes
1 answer
104 views

Galois field problem in Cryptography [closed]

This problem is related to Fields in Cryptography, My Question is why there is no multiplicative inverse for 2, isn't it 0.5?? or matters are diffrent if it was related to galois field ? I don't quite ...
Mohamed Mohamed Mourad Abdel W's user avatar
1 vote
1 answer
260 views

Data fingerprint using polynomial and Schwartz-Zippel Lemma

I'm working on a protocol and am looking for a way to fingerprint a set of elements. All elements are evenly distributed across a finite field that is integers modulus $2^{256}$. Assume I have a set ...
vimwitch's user avatar
  • 139
2 votes
1 answer
208 views

multiplicative inverse computations on binary galois fields yield partial result when sampled

I want to compute the multiplicative inverse of 0x2 over $GF(2^{233})$ in hardware. To do so, I compute $a^{-1} = (a^{2^{m-1}-1})^{2}$. Here's the result of that ...
thatbangaloreanguy's user avatar
2 votes
0 answers
71 views

Division, scope finite fields polynomials in general vs. f.f. polynomials in ECC [closed]

A cryptography course covered among others following questions: arithmetic of polynomials over $GF(2^m)$ fields - polynomials division elliptic curves over field $GF(2^m)$ In scope of former point ...
Lilkp2's user avatar
  • 21
1 vote
0 answers
44 views

Is it secure if I disclose an element equals 1 modulo p in Zn?

Let $n = pq$, $p,q$ are two large primes, then $\mathbb{Z}_n^*\cong \mathbb{Z}_p^* \times \mathbb{Z}_q^*$. We disclose $n$ and keep $p, q$ secret. Is it secure if we disclose a random element $a$: $a\...
Bob's user avatar
  • 509
2 votes
1 answer
329 views

Why can't RSA signatures be forged algebraically?

Compute $n = pq$ where p and q are prime. Fix $e$ to be coprime to $\phi(n)$. Compute $d = e^{-1} \pmod n$ and verify $ed \equiv \phi(n) \pmod n$. We sign the (hash of) a message with $s = h^{d}$. A ...
Jeffrey's user avatar
  • 33

1
2 3 4 5
8