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
3
votes
2answers
344 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
502 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
29 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
48 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
112 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
41 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
81 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
32 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
109 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
15 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
79 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
74 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
28 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
129 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
90 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
32 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?
1
vote
1answer
76 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
68 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
70 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
147 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
243 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
55 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
81 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
83 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
43 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
140 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 ...
0
votes
1answer
117 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 ...
2
votes
1answer
167 views

Why does curve25519 use a cofactor of 8?

This cofactor (as I understand it) effectively discards valid points that satisfy the curve equation over the finite field. Why would one wish to reduce the number of possible private keys, it seems ...
-1
votes
1answer
74 views

How do I generate the multiplication table for GF(3^2)?

I understood, how this works for arbitrary n and p = 2, but I am struggling with higher prime numbers as a base. In the following, I wanted to use the irreducible polynomial ...
0
votes
1answer
47 views

How can we evaluate a polynomials in a group instead of a field? (verifiable secret sharing on elliptic curves)

I am trying to understand how we can have cryptographic schemes that builds on both secret sharing, which is build on top of a finite field, and bilinear maps, which are built on top of elliptic curve ...
0
votes
0answers
48 views

Difference in elliptic curve order and finite field size [duplicate]

Must the prime finite field, Fp, an elliptic curve is defined over always have a greater number of elements than the cardinality of an elliptic curve. For example, If I have ...
1
vote
1answer
120 views

Why is $S(y) = y^{2^8-2} = y^{254}$ a one-to-one function and a permutation on $GF(2^8)$

I'm taking a course on cryptography and I have some confusions concerning the materials in our notes. Say we have the field $GF(2^8)$, we create a substitution algorithm (the S Box in AES) so we need ...
0
votes
0answers
48 views

Why does using infinite fields leak secrets in Shamirs Secret Sharing Scheme? [duplicate]

There is a similar question here, but the answers as I understand them basically say (1) you can leak the parity of the secret and (2) you can run into over/underflow issues as well as floating point ...
6
votes
2answers
263 views

The definition and origin of Schnorr groups?

Wanting to write something on Schnorr groups in a publication I realised how hard it is to find anything citable about them on the internet. Who can help me with the following questions? What (and ...
1
vote
0answers
42 views

MULalpha and DIValpha operations in SNOW 3G

I'm not able to appreciate the importance of mul alpha and div alpha operations in feedback polynomial of LFSR in SNOW 3G. What problems or weakness do they help in mitigating and how ?
1
vote
1answer
68 views

What does MULx operation in SNOW 3G correspond to?

According to the spec, MULx operation is defined as - MULx maps 16 bits to 8 bits. Let V and c be 8-bit input values. Then MULx is defined: If the leftmost (i.e. the most significant) bit of V ...
1
vote
1answer
205 views

Computational Complexity: ECC multiplication vs Modular multiplication

How does performing scalar multiplication on an elliptic curve compare to exponentiation in a multiplicative group modulo a prime? I.e. on a given elliptic curve of size $|t|$, what's the complexity ...
0
votes
1answer
91 views

Get points of an Elliptic Curve defined over a Finite Field on Twisted Edwards Extended Coordinates

I'm working on a crypto library, and I need to perform some tests for the implementation of: Point Addition. Point Subtraction. Point Doubling. Scalar Mul Point. The operations are performed on ...
1
vote
0answers
50 views

Constructing Low-Density Parity-Check Codes of length $n$ and minimum distance = $\delta n$ over $GF(q)$? [closed]

I am looking for a way to construct an LDPC (Low-Density Parity-Check) Code $C$ of length $n$ and minimum distance $d_C$ that scales linearly to $n$, meaning $d_C = \delta n$ for $\delta \in (0,1)$. ...
11
votes
0answers
387 views

How Significant is the New Quasi-Polynomial-Time Attack on Fixed Characteristic Discrete Logarithms?

There is a new paper by Kleinjung and Wesolowski on eprint that claims and proves a new attack on the discrete logarithm problem in finite fixed characteristic fields in quasi-polynomial time. ...
0
votes
1answer
86 views

Explanation of trace function $\operatorname{Tr}_m(x) = x^{2^{m}} \oplus x$

The following statement is from a paper (Partitions in the S-Box of Streebog and Kuznyechik) about S-Boxes: For all $ x \in \operatorname{GF}(2^{n})$, it holds that $x^{2^{n}} \oplus x = 0$. If $...
1
vote
1answer
87 views

Does any problem arise when the order of an elliptic curve is equal to its prime field modulus? [duplicate]

Regarding cryptographic schemes in elliptic curve cryptography, is there a problem with having the order of an elliptic curve being equal to its prime field modulus? That is, an elliptic curve where $...
3
votes
0answers
187 views

Group Rings on Cryptography

Let $R[G]$ or $RG$ be the group ring where $R=F_q$ and $G$ is any group. Let $Dim(V)=\vert G \vert$. It's clear that $V$ has $\vert R \vert^{\vert G \vert}$ distinct $\vert G \vert$-tuples. This ...
2
votes
0answers
127 views

Solving not so much overdetermined system of multivariate polynomial equations

I'm studying algorithms solving multivariate equations. I'm stuck in solving overdetermined set of quadratic equations. Concretely, with the number $n$ of variables, the number of equations is $m=\...
2
votes
1answer
104 views

Are there any security risks in using Elliptic Curves defined over fields $\mathbf{F}_{p^n}$ where $n>1$

I've recently been studying elliptic curves, and I've found that most of the current implementations use fields $\mathbf{Z_p}$ or in some cases $\mathbf{F}_{2^n}$. All the reasons I've seen for not ...
3
votes
2answers
836 views

How are these AES MixColumn multiplication tables calculated?

I'm using the mul2, mul3, mul9, mul11, mul13 and mul14 tables for the MixColumn and InvMixColumn steps in AES-128. However, I got these off some Github repository, and now I'm looking for an actual ...
3
votes
1answer
64 views

Is inversion always cheap with Twisted Edwards curves?

I'm reading on Jubjub, which is planned for the next upgrade of Zcash. It is based on a Twisted Edwards curve with parameters $a = -1$ and $d = −(10240/10241)$. The reading says Jubjub does not need ...
1
vote
2answers
270 views

Why aren't Complex number fields used in cryptography?

Most of the cryptography is limited to use of real integer fields. Complex numbers are seldom used. Is there any reason for it? Wouldn't complex numbers provide more structure? If there is already ...
0
votes
1answer
88 views

Is the following non-interactive zero-knowledge set membership protocol provable secure?

Given the following Zero-knowledge set-membership protocol https://infoscience.epfl.ch/record/128718/files/CCS08.pdf]. That is given in the following steps (Please refer to page 9). The Verifier -...
-2
votes
1answer
57 views

Given a point $c$ in a field $Z_p$. Can we get another value $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$?

If we have a point in a field $c$. Can we get another value $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$ ?

1
2 3 4 5 6