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
1answer
48 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
90 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
67 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
54 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
59 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
2answers
171 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
79 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
97 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 \...
4
votes
1answer
605 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
167 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
47 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
143 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
137 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
108 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
52 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
94 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
91 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
169 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
216 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
64 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
111 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
63 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 ...
3
votes
1answer
239 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
231 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
103 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
371 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
80 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
283 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
104 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
99 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
439 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
71 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
102 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
98 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: ...
1
vote
1answer
161 views

How do we reduce the multiplications in the AES mix column layer using $x^4 +1$

I recently learned AES uses $x^4 +1$ to reduce the multiplications in the MixCol layer. However, I used $p(x) = x^8 + x^4 + x^3 + x + 1$ not knowing it was the wrong polynomial and got the correct ...
1
vote
0answers
183 views

Expressing a given linear transformation in Galois Field GF(256) in terms of another linear transformation with a different reduction polynomial

Before giving a better and detailed description of what I ask, let me first tell why I need what I am looking for: Intel processors already provide instructions (AES-NI) for very efficient AES ...
11
votes
3answers
3k views

What is the main difference between finite fields and rings?

In the course I'm studying, if I've understood it right, the main difference between the two is supposed to be that finite fields have division (inverse multiplication) while rings don't. But as I ...
1
vote
1answer
341 views

Elliptic Curve - Divide by 2

Can anyone tell me the specific equations and steps for dividing a point on an elliptic curve by 2? For instance, I have the point $(P_x, P_y)$, and I would like to find the point $(R_x, R_y)$ which ...
3
votes
2answers
446 views

Verify Points on curve secp256k1

I am trying to verify whether or not these points are on the secp256k1 curve. I am finding several points included below. (I have verified 2*G, 8*G and 10*G with the pycoin script) My Questions are: ...
1
vote
0answers
60 views

Grøstl MixBytes Python implementation

I am trying to find an efficient way to implement the Grøstl matrix multiplication on python3. So far I have managed to get this result : ...
19
votes
5answers
2k views

Are there any (asymmetric) cryptographic primitives not relying on arithmetic over prime fields and/or finite fields?

Trying to figure out if any (asymmetric) cryptographic primitives exists, which do not rely on arithmetic over a prime field and/or arithmetic over a finite field, some people might get lost in ...
0
votes
1answer
412 views

Key size and finite fields in ECC (References)

So somehow I know that the key size in ECC is defined over the number of elements in a finite field or that it is almost equivalent to that (Correct me if I am wrong). However, other than on Wikipedia ...
1
vote
1answer
112 views

Using Hadamard Form of a Matrix in the Block Cipher

Definition: A matrix A of size $2^n$ is a Hadamard matrix, if has the following form $$ A= \left( \begin{array}{cc} U & V \\ V & U \end{array} \right)_{2^n\times 2^n}\, , $$ where $U$ and $V$...
-1
votes
2answers
182 views

LFSR, polynomial , finite field

I'm having a hard time understanding the concept of LFSR, polynomials and finite field and how to solve exercises like picture below. Could anyone give me some pointer on where to start?
1
vote
1answer
2k views

Calculating the multiplicative inverse of a number in $GF(2^n)$ where $n > 8$

Suppose that: We have a polynomial $g(x)$ of degree $n$. $n > 8$. $q$ is the multiplicative inverse of $p$ in $G(2^n)$ modulo $g(x)$. If $p = 0$, then $q = 0$. This could be used: As a non-...
1
vote
1answer
120 views

(AES in mind) How can we show two irreducible polynomials have a bit-wise linear isomorphism

This refers to answer 2 on a similar question:Design properties of the Rijndael finite field I am unsure what many of the terms mean in this answer. I think a bit-wise linear isomorphism of ...
3
votes
1answer
202 views

Why equation Y^2=X^3 +AX+B can't work with finte field of charateristic 2?

I know that we can't define $dx/dy$ with this equation because $2y = 0$ with finite field of charateristic $2$. But with $GF(2^n)$ (has characteristic by $2$) $2=x$ not $0$. Do I misunderstand here?
2
votes
3answers
232 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 ...
7
votes
2answers
1k views

Why is x^8 + x^4 + x^3 + x + 1 used in AES's Rcon?

I am not familiar with field theory so please bear with me if this is obvious to you. I was wondering why this particular reducing polynomial $x^8+x^4+x^3+x+1$ is picked for AES' Rcon. Can't it be ...