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
20
votes
2answers
7k views

How to determine the order of an elliptic curve group from its parameters?

Let $\quad E:\; y^2 = x^3 + ax + b \quad$ be an elliptic curve defined over a finite field $\mathbb F_q$ where $q = p^n$, $a,b \in \mathbb F_q$ and $p \neq 2, 3$. By Hasse's theorem we know that the ...
0
votes
1answer
545 views

Pollard's Rho - Constructing the random function

Suppose we are aiming to solve the discrete logarithm problem $\alpha^x=\beta$ in some cyclic group $G=<\alpha>$. Then we are looking for a (uniformly) random sequence of elements of the form $\...
1
vote
0answers
45 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
71 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
220 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 ...
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)$. ...
0
votes
1answer
96 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 ...
11
votes
0answers
389 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
98 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 $...
2
votes
0answers
128 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
107 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
933 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
461 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 ...
1
vote
2answers
291 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 ...
3
votes
1answer
67 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 ...
-2
votes
1answer
60 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$ ?
0
votes
1answer
2k views

Understanding elliptic curve point addition over a finite field

I am new to elliptic curve cryptography as well as finite field theory. I am trying to understand point addition in affine coordinates. I understand, that for an elliptic curve $ y^{2}=x^{3}+ax+b $ ...
2
votes
2answers
1k views

Comparing elliptic curves over prime fields against EC over binary fields

In which scenarios we go for prime fields or binary fields? Please indicate why we would choose one over the other.
1
vote
1answer
102 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
85 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
71 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}$. ...
3
votes
1answer
172 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
205 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
72 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 ...
0
votes
1answer
91 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
0answers
42 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 ...
1
vote
1answer
49 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
116 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 ...
6
votes
4answers
1k views

Algorithm for computing square roots in $GF(2^n)$

Short question: is there an algorithm for efficiently computing square roots in $\mathbb{F}_{2^n}$?
1
vote
1answer
431 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
44 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 ...
7
votes
2answers
277 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
74 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 ...
0
votes
1answer
240 views

Does a Finite Field of 36 elements exist? [duplicate]

I'm having a little trouble understanding the finite fields theory, so I'm sorry if my question would seem a little stupid. I wanted to know if a finite field of 36 elements could exist. Basically, I ...
8
votes
1answer
3k views

How to find the order of a generator on an elliptic curve?

I was looking out to find optimum generator for an elliptic curve $E$ over a prime field $\mathbb F_p$. I found the following algorithm: Choose random point $P$ on the curve. Find the order of a ...
1
vote
1answer
163 views

Inverse of an element in a RSA group

Consider a RSA group $Z_N$ for $N=pq$, where $p,q$ are large prime numbers. Under strong RSA assumption, can an adversary efficiently compute the inverse of a random element $z$ from $Z_N$ without ...
7
votes
0answers
163 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 ...
4
votes
1answer
87 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}:\...
3
votes
1answer
243 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 ...
5
votes
2answers
189 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
122 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 ...
10
votes
1answer
344 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: ...
0
votes
1answer
219 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 ...
7
votes
2answers
2k 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 ...
0
votes
0answers
60 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
1
vote
1answer
260 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 ...
-1
votes
1answer
579 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 ...
5
votes
1answer
600 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 ...