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
1answer
72 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
60 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
63 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
110 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
147 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
48 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
80 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
79 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
88 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
90 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
vote
1answer
122 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
53 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
46 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
46 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
113 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
46 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 ...
5
votes
2answers
187 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
38 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
62 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
108 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
72 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
48 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)$. ...
10
votes
0answers
357 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
79 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
44 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
134 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
114 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
94 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 ...
0
votes
0answers
21 views

What is the difference between these pairings classifications?

I know the basic definitions of bilinear groups. For example, there is a bilinear pairing that uses elliptic curves and has the following properties: For $G_1$, and $G_2$ are cyclic groups of prime ...
3
votes
2answers
482 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
63 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
189 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
73 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
51 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
vote
1answer
96 views

Is there a concept of embedding degree for non-pairing based elliptic curves?

From this post, I learned the concept of embedding degree. Intuitively, if embedding degree of an elliptic curve $E(F_p)$ is $k$, it means there is a way to transform points in $E(F_p)$ to $F_{p^k}$. ...
0
votes
1answer
68 views

Elliptic curve over prime field with high order roots of unity

Suppose I have an elliptic curve defined over a prime field $\operatorname{GF}(p)$ where $p$ is a large prime (e.g. 256-bit). Suppose also that $p = kn +1$, where $n$ is a relatively large power of $2$...
-1
votes
1answer
58 views

Finding a prime field with n-th roots of unity

How can I find the smallest prime $p$, such that field $GF(p)$ has $n$-th roots of unity? For example, I know that for $p=2^{256} - 351 \times 2^{32} + 1$ there exit roots of unity for $n=2^{32}$. ...
2
votes
1answer
123 views

Standard basis representation of elements in binary field

In Remark B.1 from this paper it says: We assume canonical representation for binary fields $\mathbb{F}$, given by an irreducible polynomial and a primitive element $g \in \mathbb{F}$ for it (i.e., ...
1
vote
0answers
93 views

How to find multiplicative inverse of a hexadecimal number in the finite field GF(2^8)? [duplicate]

I am new to cryptography. As I was reading a note regarding S-box construction, I found a step mentioning multiplicative inverse of a number in the finite field GF(2^8). I couldn't understand it!! Can ...
0
votes
1answer
62 views

How to calculate the order of the subgroup?

Given a curve with points over GF(p), a subgroup of prime order q and a co-factor h. How do I calculate the size of q which is ...
1
vote
1answer
42 views

Cost model for different curve models

Is there a cost model for each curve model and their conversions? For example: Take the curve models: Projective, Completed, Extended, Affine. Is there a table which shows how many multiplications, ...
1
vote
0answers
39 views

Efficient fields over arithmetic circuits

What sort of fields is efficient over an arithmetic circuit? Efficient meaning that given a field $\mathbb{F}_p$, reduction (modulo) does not require many multiplications and preferably inversion was ...
0
votes
1answer
73 views

Computing a sextic twist

Let $(x,y) \in E'_{\mathbb{F}_{p^2}}$ be a point of the sextic twist. I am currently trying to compute: $\psi : (x, y) \leftarrow (\mu^2x,\mu^3y)$ with $\mu \in \mathbb{F}_{p^{12}}$ the root of $(Y^...
1
vote
1answer
45 views

ECDSA over $\mathbb{F}_{p^n}$ for $n>1$. How to calculate $r$ and $s$

I'm having some trouble understanding how to calculate $r$ and $s$ as specified in the wikipedia page for ECDSA (https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm) We can see ...
1
vote
1answer
97 views

Is the One Time Pad secure in additive Rings?

Let's assume all operations are done on $\mathbb{Z}_p$ where $p$ is a large non-prime number. To mask a value $a$, we do the following: Pick a uniformly random value: $r$, from the ring. Do as ...
1
vote
1answer
212 views

What is the inverse function of the finite field GF($2^3$) and GF($2^4$)?

I am currently reading a paper Cryptanalysis of a Theorem Decomposing the Only Known Solution to the Big APN Problem. In this paper, they mention that they used $I$ which is the inverse of the finite ...
0
votes
0answers
41 views

Explanation of Gallant-Lambert-Vanstone method / Endomorphism speedups [duplicate]

Can someone explain how the Gallant-Lambert-Vanstone method works (or which literature explains it)? It is also unclear to me how the Frobenius endomorphism can be used in some cases for a speedup. ...
0
votes
0answers
54 views

How can a node establish pairwise shared key with other nodes using its own polynomial share together with other's public values?

A server has a symmetric bivariate polynomial $ F(x, y) = \sum_{{i,j}=0}^{t-1}a_{i,j}x^iy^j$ $\in GF(p)[X, Y] $ of degree $t-1$. For simpliciy, $ F(x, y) = a_{0,0}+a_{1,0} x+a_{0,1}y+ a_{1,1}xy$ mod ...
2
votes
1answer
69 views

What is the difference between the 23 bi-affine and the 39 fully quadratic equations of the rijndael sbox?

In Cryptanalysis of Block Ciphers with Overdefined Systems of Equations Nicolas Courtois and Josef Pieprzyk define 23 so called bi-affine equations (in Appendix A of the paper) between the input x and ...

1 2 3 4 5 6