Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
1answer
56 views

Difficulty of forging MACs based on linear functions over $GF\left(2^n\right)$

This is a homework question, therefore I'm not expecting full solutions, just general guidance. I want to build a one-time MAC using universal hashing. I defined my hash functions as: $h_{a,b}:\...
2
votes
1answer
53 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 ...
2
votes
2answers
46 views

Why does libSTARK use binary fields as opposed to prime fields for zk-SNARKs?

zk-STARKs make use of FRI for low degree testing of polynomials. The zk-STARKs paper states on page 11: we stress that ZK-STARK could also operate over prime fields but we have not realized this ...
1
vote
1answer
77 views

What is the difference between subtracting the modulus from a scalar field element and reducing it?

When implementing a Field element, we define the necessary operations on the data structure. One function that I see is a "scalar reduce" function, which effectively reduces a random scalar so that ...
0
votes
0answers
46 views

Prove I know a value v in a set s.t. K = H(v) [duplicate]

Is it possible to prove that I know a value v in a finite set, such that the hash of the value v is K. Where v is private and K is public
9
votes
1answer
181 views

how does BearSSL's GCM modular reduction work?

BearSSL (in src/hash/ghash_ctmul.c) seems to be doing a modular reduction that I don't completely understand. Here's the code: ...
-1
votes
0answers
59 views

Secp256k1 Base Point in the Real Set

It is given that the base point of secp256k1 is ...
0
votes
1answer
56 views

Why only non-prime order fields have small subgroup attacks?

Why don't prime-order curves have small subgroup attacks? It seems that I can choose a Generator such that it has a small order, maybe 2 points, and so an attack could generate all of the points in ...
1
vote
1answer
40 views

For an elliptic curve, what is the difference between the base field modulus $Q$ and subgroup $r$

What is the difference between the basefield modulus $Q$ and a subgroup of prime order $r$? They are all fields, but what is their relevance to the curve they are defined upon? How does this relate ...
6
votes
0answers
88 views

GCM with reversed poly

These slides talk about how GCM can be sped up if one uses $x^{128}+x^{127}+x^{126}+x^{121}+1$ as the reduction polynomial instead of $x^{128}+x^7+x^2+x^1+1$. When one is doing that one needs to ...
-1
votes
1answer
36 views

find additive inverse of modular arithmetic [closed]

For a set to be called as a ring, it should have the following properties closed commutative associative Identity existence Inverse existence but how is Z7 a ring, as there aren't any inverse ...
7
votes
2answers
404 views

Should we use IANA groups 14 (MODP), 25, and 26 (ECP)?

By looking at SonicWall Knowledge Base article Key exchange (DH) Groups Supported - Site to Site VPN: It appears that our firewall supports DH group 25, and 26. Almost everywhere I've seen, they've ...
5
votes
1answer
523 views

Why doesn't the GCM spec use a more efficient multiplication algorithm?

NIST SP 800-38D § 6.3 Multiplication Operation on Blocks describes a multiplication algorithm that, in my testing, appears to be a good amount slower then algorithm 2.40 (arbitrary reduction ...
1
vote
1answer
44 views

GHASH with a finite field multiplication algorithm in reverse order

NIST SP 800-38D § 6.4 GHASH Function describes the GHASH algorithm thusly: Prerequisites: block $H$, the hash subkey. Input: bit string $X$ such that len($X$) = $128m$ for some positive ...
0
votes
1answer
38 views

modular reduction algorithm over $F_{2^m}$ doesn't seem to work when order of polynomial being reduced is small

I was considering algorithm 2.40 (arbitrary reduction polynomials) in the Guide to Elliptic Curve Cryptography and... it doesn't appear to work when the order of the polynomial you're trying to ...
3
votes
1answer
75 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^...
0
votes
1answer
59 views

Multiplication and squaring the binary polynomials

I have tried to calculate $trace$ of a coordinate $X$ of EC in binary representation. Before that I tried to pre-calculate traces of the various bits of $X$ using formula: $$Tr(X) = Tr(\sum_{i = 0}^{...
2
votes
0answers
44 views

Pre-computing a log and exp table for a primitive polynomial in $GF(2^8)$ [duplicate]

I'm new on the topic of finite fields, specifically $GF(2^8)$. I've come across the information that it's possible to implement multiplication using logarithm and exponential tables. But how are ...
2
votes
0answers
53 views

Numerical Algebraic geometry in the finite fields

Does the numerical algebraic geometry method work in the finite fields? I am working on this method to find a solution for a low-degree proximity testing problem. Would you please guide me how they ...
6
votes
1answer
78 views

Algorithm for computing modular inverse in MPC

Is there any known algorithm for calculating $a^{-1} \pmod{q}$, where $ q < p$ and $F_{p}$ is the prime field of the MPC, in a linear secret sharing scheme ? I have tried using the standard ...
2
votes
1answer
70 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 ...
3
votes
2answers
78 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
193 views

Finding the n-th root of unity in a finite field

I'm trying to find the n-th root of unity in a finite field that is given to me. n is a power of 2. The finite field has prime ...
1
vote
1answer
80 views

How Elliptic-Curve affects the Server Key Exchange parameters

In Finite Field DHE, the server sends the following parameters in the server key exchange message: $p$: prime $g$: group $g^b$: the server's public DH key In DHE_RSA (non anonymous DHE), the server ...
0
votes
1answer
31 views

Given paramaters of an Edward's curve and x, determine a y value if it exists

I'm making a demonstration cryptosystem using ECC ElGamal. I've currently got a working implementation of Edward's Curve operations and a basic ElGamal implementation (Encrypts only points on the ...
1
vote
2answers
94 views

How to calculate Trace function for a point on an elliptic curve

I encountered trouble with calculating Tr (trace function) for points on an elliptic curve in polynomial basis ( $GF(2^m), m = 431$). Maybe there are any assumptions that can simplify and allow ...
1
vote
0answers
73 views

How to use Galois LFSR to find multiplicative inverses

My question is how can a Galois Linear Feedback Shift Register be used to discover multiplicative inverses of polynomials? This is a homework assignment. Here is a list of things I did before asking ...
4
votes
1answer
104 views

questions about modular reduction algorithm over $F_{2^m}$

So I'm trying to understand algorithm 2.40 (arbitrary reduction polynomials) from the Guide to Elliptic Curve Cryptography and have some questions. The very first sentence of this section says this: ...
1
vote
0answers
14 views

Legendre conditions on the factors of the fundamental negative discriminant to minimize the 2-Sylow subgroup of the class group

If we know the prime factorisation of the fundamental negative discriminant $\Delta_K$, say $\Delta_K=p_1\cdot p_2 \cdots p_n$, then we are guaranteed that at least $2^{n-1}\mid h_K$, the class number ...
2
votes
1answer
43 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?
1
vote
2answers
65 views

powers of g in $GF(256)$

The finite field $GF(256)$ is usually implemented $mod$ 0x11b to keep the numbers inside that field. I understand that 0x11b was ...
1
vote
1answer
53 views

Galois Field multiplication instead of Diffie Hellmans discrete logarithm

I am wondering if the inversion of multiplication of polynomials is equally hard as the discrete logarithm problem used for key exchange. Or are there algorithms that weaken such an usage. I ...
2
votes
2answers
120 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
1answer
123 views

Questions about the Curve25519-donna implementation

I'm trying to understand the implementation of the following function: Please note questions in comments. ...
1
vote
1answer
58 views

Computations in extended finite field p^2

I would like to construct a distortion map from a point $\in \mathbb{F}_p$ to $\mathbb{F}_{p^2}$. If I have an elliptic curve $Y^2 = X^3 + 1$ over $\mathbb{F}_p$ and a distortion map $\phi(x,y) \...
1
vote
1answer
77 views

How to use Frobenius for finding Square Roots in $GF(2^m)$

Given a polynomial $x$ with degree $n$ in $GF(2^m)$, $1 < n < m$, will any generator of $GF(2^m)$ suffice when applying the Frobenius automorphism to determine the square root of $x$ as ...
1
vote
1answer
46 views

How to handle points in extended finite field

Following the response to my previous question, I would like to know if you could give me some information or give me a link on how to perform arithmetic operations once I changed a point from the ...
0
votes
0answers
71 views

Understanding creation of distortion map

I'm trying to implement a distortion map but I have a problem. I know the basics and I read some questions like this one and asked some questions here. If I have an elliptic curve $E : y^2 = x^3 + 1$ ...
2
votes
1answer
86 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 ...
0
votes
0answers
107 views

Cube root modulo prime

I make research about big numbers in finite fields and I need to calculate a cube root modulo prime P for the number N: ...
3
votes
0answers
73 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.
5
votes
1answer
326 views

Why does a Galois field have to have an order of $p^n$ where $p$ is prime?

I was reading about this in a cryptography book last night. I have a hunch about this, but I can't quite put my finger on it. I think this is a similar situation to an affine cipher, where the ...
1
vote
1answer
75 views

What hash functions can be (efficiently) computed over GF(2^m)?

Given an arithmetic circuit over a finite field of characteristic 2, what families of cryptographic hash functions can be efficiently computed with this circuit? Can standard hash functions be ...
0
votes
1answer
208 views

Using the encryption matrix from AES, how do you compute the decryption matrix?

So I don't want the answer but somewhere to start with this problem, first I want to know if my logic and thinking is on the right path before I dive right into computing the decryption matrix so here ...
1
vote
1answer
87 views

do koblitz curves over $\mathbb{F}_{P}$ as generalized in SEC2 always have $a$ as 0?

I reviewed all the curves in http://www.secg.org/SEC2-Ver-1.0.pdf . All the secp*k* curves have the $a$ parameters as 0 and those are the only ones with the $a$ as 0. Is this a defining requirement ...
0
votes
2answers
84 views

Difference between $F_2^n$ and $\Bbb F_2^n$ for a field

I am confused between the notation $F_2^n$ and $\Bbb F_2^n$ for a field in regards to codes. I thought that $F_2^n$ and $\Bbb F_2^n$ were both fields composed by codes of length n and entries in mod ...
0
votes
2answers
183 views

How does wNAF work with prime finite fields?

According to wikipedia, in the precomputation step of the w-ary non-adjacent form (wNAF) point multiplication method you do $d \bmod 2$ and, later, $d \gets \frac{d}2$. The mod operation doesn't make ...
2
votes
1answer
44 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 ...
1
vote
1answer
72 views

AES S-Box: How is value for 01 mapped to 7c?

If irreducible polynomial $m(x) = x^8+x^4+x^3+x+1$ is chosen, or even for any other value, the multiplicative inverse will not exist for $01$, as $0000 0001$ will perfectly divide $m(x) = 100011011$ ...
3
votes
1answer
86 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: ...