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
2
votes
1answer
59 views

Constant Time algorithms for $\mathbb{Z}/m\mathbb{Z}$, $\mathbb{Z}/m\mathbb{Z}[x]$, and $\mathbb{Z}/m\mathbb{Z}[x] / (f(x))$?

I want to implement some (lattice based) protocols to better familiarize myself with a programming language (Rust). These tend to do arithmetic over rings like $\mathbb{Z}/m\mathbb{Z}$, or "...
0
votes
0answers
23 views

Pedersen commitment on binary field $GF(2^n)$

I am curious whether one can do Pedersen commitment on $GF(2^n)$. One method I thought of was to get a prime order multiplicative subgroup of $GF(2^n)$. But for efficiency and security, what would be ...
5
votes
2answers
269 views

Must a line hitting two points on the elliptic curve over a finite field hit another point by continuation?

The Arstechnica article title as "A (relatively easy to understand) primer on elliptic curve cryptography" claims this; In fact, you can still play the billiards game on this curve and dot ...
2
votes
1answer
91 views

Problem with the signature of message using ECDSA over GF(2^m)

I'm trying to set up an ECDSA with Elliptic Curves over $\operatorname{GF}(2^m)$ with an example of toy with the following values: Using the Weierstrass equation on binary finite fields. $$E: y^2 + x*...
4
votes
2answers
115 views

Doubt on elliptic curve over a finite field and binary representation

I'm a programmer, i.e. agnostic to the mathemathics behind most of cryptographic scheme, but I'm trying to remediate. I'm writing this premise for any possible error or imprecision that I probably put ...
0
votes
0answers
38 views

Matrix multiplicative inverse

How to determine the inverse multiplicative matrix of the following two irreducible polynomials GF(2^8) x^8 + x^5 + x^3 + x^2 + 1 and x^8 + x^5 + x^4 + x^3 + x^2 + x +1
1
vote
2answers
102 views

Question about the proof of the change of base formula for the discrete logarithm

I was looking at the proof of a change of base formula for the discrete logarithm in this paper (page 6, 4th bullet indent). In the intruduction, the paper states: Let $F_q$ be a finite field of order ...
0
votes
0answers
38 views

Generalization of Bezout Identity for Polynomials

Let $i \in \{1,\ldots, n\}$, $f_i(x)$ be a univariate polynomial, and $g(x) = \mathsf{GCD}(f_1(x), \ldots,f_n(x))$. According to Bezout identity, there exists $a_i(x)$ such that: $$\sum_{i \in [n]}a_i(...
4
votes
1answer
182 views

Why Abstract Algebra in Cryptography?

I come from an engineering background, but not from computer science or anything to do with pure math. I studied applied math in college--never abstract algebra, number theory, or discrete math, ...
1
vote
1answer
116 views

Solving Diffie-Hellman vs DLP

I'm wondering what is the current knowledge regarding the difficulty of solving the Diffie-Hellman problem (DHP). Obvisously solving the DLP (discrete log) is at least as hard as solving the DH ...
0
votes
0answers
22 views

How fast compute high degree power in finite field?

We need find y for some x on elliptical curve in cases: decompressing public key restoring public key from signature for given message hash, r and s. This algorithm uses power twice: first it is y1 =...
0
votes
1answer
19 views

On the hardness of addition when the elements of a field is represented by the powers of generator and possible any existant scheme

We can represent elements of a finite field $F$ in various ways polynomial basis and normal basis. There is one other; generator-based representation and this is based on the fact that the ...
2
votes
2answers
209 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 ...
6
votes
2answers
905 views

Need help understanding math behind Rijndael S-Box

in Rijndael SubBytes() step all bytes of input block are substituted based on a lookup table S-Box. S-Box is initialized by taking all elements of $GF(2^8)$, ...
0
votes
0answers
45 views

Cryptographic properties of field multiplication (Continued)

This question follows-up from this question/comment. Suppose, you are given $X \odot Y$, where $X~(\neq 0) \in \operatorname{GF}(2^{128})$ is random, $Y~(\neq 0) \in \operatorname{GF}(2^{128})$ is ...
2
votes
1answer
297 views

Cryptographic properties of field multiplication

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 $\...
5
votes
2answers
166 views

Why use prime number $q$ such $q$| $(p-1)$ in discrete logarithm based schemes?

In discrete logarithm based schemes on finite field we have a prime number $q$ that divides $p-1$ and $q$ is to specify a subgroup with the order $q$. But why do we do that? Why do not we work on the ...
4
votes
1answer
138 views

How does Montgomery reduction work?

I want to reduce a multi-precision integer $x$ modulo a prime $p$, very fast. Performing the traditional Euclidean division for only calculating the modulo, is inefficient and modular reduction is at ...
3
votes
2answers
451 views

Distribution of the Difference of Uniformly Random Elements

In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (...
2
votes
1answer
178 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 ...
2
votes
1answer
635 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 ...
14
votes
0answers
189 views

The aftermath and considerations of the new record of 30750-Bit Binary Field Discrete Logarithm - 2020

Granger et al. recently published a paper about breaking a record for discrete logarithm on the Binary field Computation of a 30 750-Bit Binary Field Discrete Logarithm, Robert Granger and Thorsten ...
3
votes
2answers
450 views

Constant time multiplication in GF(2^8)

I am trying to implement AES in C; I would like to make it resistant to side-channel attacks but I can't implement the multiplication in constant time. My current code: ...
7
votes
1answer
521 views

How do client and server agree on the values of p and g during DHE exchange?

How do the communicating parties using Finite Field DHE agree on the values of the $p$ and $g$ variables? Are their values fixed for each DHE group? Reading through the TLS 1.3 RFC (8446), the client ...
0
votes
0answers
33 views

Finding the relationship given by the generating elements of a non-abelian group (for a maximum case) where they correspond to finding cycles

Let $G=(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes_{\phi} \mathbb{Z}_q$, where $p$ and $q$ are odd distinct primes. Let $G$ be generated by the elements $s=(g_1,e_q)$ and $t=(e_p,g_3)$, $g_1,e_p \in \...
0
votes
1answer
55 views

In a secret image sharing scheme, what are the advantages of Galois field $\mathrm{GF}(p^m)$ over finite field $ F_p$?

Shamir's Secret Sharing Scheme uses arithmetic in a finite field of prime order. In a secret image sharing scheme, what are the advantages of Galois field $\mathrm{GF}(p^m)$ over finite field $ F_p$?
4
votes
1answer
139 views

Itoh Tsuji algorithm

I'd like to use the Itoh-Tsujii algorithm for a dynamic substitution table, but I do not get the following line: $$r\ \gets\ (p^m - 1)\,/\,(p - 1)$$ And why can $r$ be used to calculate the ...
1
vote
1answer
51 views

RSA assumption and relationship given by generating elemts of a Cayley graph

I have read a very interesting description of computation related to the RSA group as follows. "By the Chinese remainder theorem, we have that: $$(\mathbb{Z}/pq\mathbb{Z})^* \cong (\mathbb{Z}/p\...
3
votes
1answer
121 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 ...
1
vote
0answers
33 views

Determining order of the group for an elliptic curve defined over a finite field

I need to find out the order of the group for an elliptic curve. See the image for the question. The inequality condition after simplification leads to $-2 \sqrt{p} \leq m \leq2 \sqrt{p}.$ Also, the ...
4
votes
1answer
117 views

Distinguishing between a Polynomial and a Laurent Polynomial

Let $f(x) \in \mathbb{Z}_p[x]$ (for a prime $p \gg d$) be a polynomial of degree $d$, and let $g(x)$ be a Laurent polynomial with the same degree and only the first negative exponent term ($g(x) = \...
0
votes
0answers
21 views

A related question to “relationship between generating elements given by cycles in Cayley graphs”

I am writing this question with reference to the post at Relationship between generating elements given by cycles in Cayley graph When considering the generating elements $g_qg_p$, does it have the ...
2
votes
1answer
98 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 ...
4
votes
1answer
81 views

Relationship between generating elements given by cycles in Cayley graph

The strong RSA assumption is that the following problem is hard to solve. "Given a randomly chosen RSA modulus $n$ and a random $z \in \mathbb{Z}_n^*$, find $r>1$ and $y \in \mathbb{Z}_n^*$ such ...
0
votes
1answer
31 views

Decoding in Reed solomon codes

I have code encoded in GF(7) with primitive 5 Сf(4,1,0,4,5,5). (last four symbols is redundancy) While decoding using DFT we use formula $$ С_k=N^{-1}*c(z^{-kj}) $$ example: $$ C_1 = c(5^{-1*j})/6 ...
1
vote
1answer
315 views

Prime fields vs non-prime fields

I was watching this class about AES in this LINK and I was trying to grasp the concept of prime fields, which is a finite field with prime order $p$. The non-prime field part (order is $p^n$) is ...
3
votes
1answer
97 views

Inversion in $GF(2^{10})$ Using Composite Fields

I'm designing a circuit that uses many $GF(2^{10})$ inverters. Normally for this sort of thing I use lookup tables. (Itoh-Tsujii is not efficient for these smaller fields.) This application is for ...
0
votes
0answers
35 views

How to Solve Discret Log Computation Problem

Given $g^a$ in $Z_p$, it is hard to get the solution $a$. Everyone says yes, I wonder why it is hard. Could anyone give a specific mathematical way to show it is indeed hard?
4
votes
1answer
309 views

Prove that the $x^8+x^4+x^3+x+1$ is irreducible over $\mathbb{Z}_2[x]$

I am new to this field. I am doing some cryptography course and have encountered $\text{GF}(2^8)$ in the famous AES algorithm. Although I do not have a strong relevant math background with this stuff(...
1
vote
1answer
78 views

How to make this cipher strong?

Suppose I have an arbitrary 256 bit number $m$ another secret number $k$ of the same bit length, and then I multiply them both modulo a 256 bit prime number $p$ to get $c$ as follows: $$ c = (m\cdot k)...
1
vote
0answers
69 views

Looking for a group where multiplicative inverse is hard but calculating multiple pairwise inverses is easy

I have an equation that comes up in trying to do an Attribute Based Encryption scheme, where users have certificates that sign off on attributes that are also watermarked. I perform a division to ...
2
votes
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 ...
3
votes
1answer
201 views

In a shamir secret sharing scheme, why can't the secret be a middle coefficient and only the first or the last?

In the shamir secret sharing scheme, the Secret s is set as the constant in the equation $ y_p = s+ \sum_{i=0}^{i = t-1} a_i * x_p^i$ s can only be the constant term or the last coefficient or the ...
1
vote
1answer
465 views

Diffie-Hellman key exchange protocol with finite field GF(2^5)

In a Diffie-Hellman key exchange protocol, the system parameters are given as follows: finite field $GF(2^5)$ defined with irreducible polynomial $f(x) = x^5 + x^2 + 1$ and primitive element $\alpha= ...
0
votes
1answer
56 views

Understanding simplification steps when solving complicated equations in Galois Field

I just encountered a problem when I tried to understand a basepoint conversion from x25519 to ed25519. I can't really wrap my head around how the value of $x$ can be the stated value below? Can ...
3
votes
2answers
84 views

Size of $E$ over $\mathbb{F}_p$ contains $p+1$ points

I am struggling to prove this claim: I proved that the map $x\mapsto x^3+1$ is a bijection from $\mathbb{F}_p$ to itself if we have that $p\equiv 2\bmod{3}$. We have to use this fact to prove that ...
1
vote
2answers
85 views

Generating Private Keys [closed]

First of all I want to say that I have exactly 0 knowledge how I can write something in Python. But I have some knowledge in math especially finite fields. That's why I want to learn more in writing ...
0
votes
1answer
44 views

Question about algorithm

https://www.shoup.net/ntb/ntb-v2.pdf, page 523, algortithm IPT I don't get the for loop, since "k" isn't used anywhere inside the loop. What am i missing?
0
votes
1answer
207 views

Order of subgroups formed by Elliptic Curves with a Cofactor

In this question: Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation? The answer indicates that the order of all points on the curve over the finite field ...
1
vote
1answer
160 views

Choice of finite fields for use in elliptic curves

this is maybe a basic question but I'm trying to better understand elliptic curve cryptography at a fundamental level. I understand that a finite field is required in order to define a boundary for ...

1
2 3 4 5 6