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
1 answer
54 views

Carry-less multiplication vs. multiplication in $GF(2^k)$

I implemented carry-less multiplciation using the CLMUL instruction set. This is similarly fast to simple modulo multiplication. But computating the result mod some polynomial is still very slow. I do ...
user avatar
  • 795
8 votes
2 answers
2k views

On what Galois field AES really works?

I'm trying to understand the GF theory, but every time I come across information about AES it all makes no sense. In my opinion $GF(2^8)$ defines any polynomial of the form: $a_{7} x^7 + a_{6} x^6 + ...
user avatar
  • 795
1 vote
0 answers
37 views

Can we solve the ECC DLP if we can distinguish whether the doubling of a public key is accompanied by reduction (modulo n) or not?

Let $E$ be an elliptic curve over a prime or a binary extension field $GF(2^m)$, and let $G(x_g,y_g)$ be a generator point on the curve. Let $Q$ be an arbitrary point $Q = r*G$, with $r$ scalar, and $...
user avatar
4 votes
0 answers
48 views

Can there be identical elliptic curve groups of points from different irreducible polynomials in binary extension fields?

Let $E$ be an elliptic curve over a binary extension field $GF(2^m)$, with constructing polynomial $f(z)$ be an irreducible, primitive polynomial over $GF(2)$, and let $G(x_g,y_g)$ be a generator ...
user avatar
0 votes
0 answers
88 views

Hashing and Password Cracking

I was playing a game on cryptography where I encountered this problem: Hashed Value of password: 24 109 76 35 22 94 83 25 106 104 73 87 56 38 56 50 10 92 58 84 44 88 24 112 125 121 125 43 122 55 106 ...
user avatar
  • 111
0 votes
0 answers
26 views

Algorithm that solves a system of linear equations over finite fields when a parameter is needed

I was reading Kipnis' and Shamir's paper on Cryptanalysis of the HFE Public Key Cryptosystem by Relinearisation and I wanted to implement the example at the end in Octave without using any additional ...
user avatar
  • 1
0 votes
1 answer
85 views

Find multiplicative inverse in Galois field $2^8$ using extended Euclides algorithms

I'm dealing with Galois fields $GF(2^{8})$ and need help finding a polynomial $r^{-1}(x)$ such that $r^{-1}(x) r(x) \equiv 1 \mod m(x)$, where: $m(x) = x^{8} + x^{4} + x^{3} + x + 1$ $r(x) = u(x) - ...
user avatar
3 votes
0 answers
94 views

Given a cycle $x\mapsto x^a$ with start $x_0$. Can other cycle members $x_1,x_2$ be produced without leaking $j$ in $x_1=x_2^{a^j}\mod N$ (non-prime)?

A cyclic sequence can be produced with $$s_{i+1} = s_i^a \mod N$$ with $N = P \cdot Q$ and $P = 2\cdot p+1$ and $Q = 2\cdot q+1$ with $P,Q,p,q$ different primes. and $a$ a primitive root of $p$ and $q$...
user avatar
  • 869
4 votes
1 answer
140 views

Given a cycle $x \mapsto x^a$ with his starting point $x_1$. Can another starting point $x_2$ be transformed to generate the same cycle?

A cyclic sequence can be produced with $$s_{i+1} = s_i^a \mod N$$ with $N = P \cdot Q$ and $P = 2\cdot p+1$ and $Q = 2\cdot q+1$ with $P,Q,p,q$ primes. and $a$ a primitive root of $p$ and $q$. The ...
user avatar
  • 869
2 votes
1 answer
76 views

Any way to find $g,P$ for max cycle size in Blum–Micali with $x_{i+1} = g^{x_i} \mod P $ and $x_0 = g$?

For some $g$ and prime $P$ the sequence $$x_{i+1} = g^{x_i} \mod P $$ $$ x_0 = g$$ can contain all numbers from $1$ to $P-1$ and with this it is a pseudo-random permutation of those numbers (EDIT: ...
user avatar
  • 869
2 votes
1 answer
40 views

How difficult is finding $i$ for sequence $s_{i} = g^{s_{i-1}} \mod P$ with $s_0 = g$ for given value $v\in [1,P-1]$

Assuming we found a constant $g$ and a prime $P$ which is able to produce all values from $1$ to $P-1$ with it's sequence $$s_{i} = g^{s_{i-1}} \mod P$$ $$s_0 = g$$ How many steps are needed to ...
user avatar
  • 869
2 votes
1 answer
66 views

How difficult is finding $i$ in tetration $^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \mod P$ for $v\in[1,P-1]$

EDIT: I messed up something (see comments at answer). This question contains some false statements EditEnd. For tetration modulo prime $P$ $$^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\...
user avatar
  • 869
4 votes
0 answers
69 views

Security of ECDLP using elliptic curves over an extension field

It is known that, for an elliptic curves $E$ defined over a prime field $\mathbb{F}_p$ such that $E(\mathbb{F}_p)$ is a prime number, the best algorithms (beside some specific cases) for solving the ...
user avatar
  • 141
0 votes
1 answer
56 views

Finding collisions of polynomial rolling hashes

A polynomial hash defines a hash as $H = c_1a^{k-1} + c_2a^{k-2} ... + c_ka^0$, all modulo $2^n$ (that is, in $GF(2^n)$). For brevity, let $c$ be a $k$ dimensional vector (encapsulating all the ...
user avatar
2 votes
1 answer
63 views

homomorphic mapping from $F_{p^n}$ to $Z_{p^n}$

Is it possible to have a homomorphic mapping from $F_{p^n}$ to ${\mathbb Z}_{p^n}$ that preserves both the add and multiplication operators? Or if we relax requirement, can we have a homomorphic ...
user avatar
  • 113
2 votes
2 answers
103 views

Cyclic codes as ideals of a quotient ring

I'm finding the algebra behind cyclic codes somewhat tricky. The starting point is easy enough: $C\subseteq \mathbb F_q^n$ is cyclic if any cyclic shift of a codeword $c\in \mathbb F_q^n$ is still in $...
user avatar
1 vote
1 answer
72 views

Understanding the algebra behind GCM's security

I would like to understand the algebra behind GCM's security. Before I ask my questions, let me state my understanding of the math behind GCM. If correct, my questions are at the end; if incorrect, ...
user avatar
0 votes
0 answers
46 views

Secure multi-party computation made simple - questions

The scheme that I refer to is from this paper. A secret $s\in D$ is obtained by splitting s into a random sum. We have (actually linear) for any $k$ this $k$-out-of-$k$ secret-sharing scheme: Select $...
user avatar
1 vote
2 answers
137 views

In AES-256, what exactly forms the extension field $GF(2^8)$?

My question is a little difficult to describe, so let me first start with an analogy In an elliptic curve over a finite field, there are 2 groups - the first group is a finite field over which the ...
user avatar
  • 1,678
2 votes
2 answers
283 views

Program to find the inverse of polynomial [closed]

Can anyone tell me how to find the inverse of a given polynomial using python programming? Ex: input given is to find the inverse of (x^2 + 1) modulo (x^4 + x + 1). the output should be : (x^3 + x + 1)...
user avatar
1 vote
2 answers
112 views

What is the meaning of $F_{p^k}$ and the elliptic curve over it, $E(F_{p^k})$?

In pairing based cryptography, there will be the finite field $F_{p^k}$ where $p$ is prime number and $k$ is an integer. The elliptic curve is constructed on that finite field as $E(F_{p^k})$. For ...
user avatar
0 votes
1 answer
59 views

Structure of composition of permutations

If $P_1, P_2$ are finite permutations, what can we say about $P_3 = P_1 \cdot P_2$? That is, what properties of the composition of permutations can be inferred from the properties of the permutations ...
user avatar
2 votes
2 answers
171 views

A field element as the exponent of a group element

The R1CS constraints are expressed over finite fields. Many proofing systems, such as zk-SNARK, use prover keys such as $g^{\alpha^0}, g^{\alpha^1}, ..., g^{\alpha^n}$ where $\alpha$ is a field ...
user avatar
  • 113
1 vote
1 answer
153 views

How to find integer point of a ec curve in a given range?

I was looking inside the basics of ecc and found the examples from Internet either uses continuous domain curve or use a very small prime number p like 17 in a ...
user avatar
0 votes
0 answers
23 views

Changing Field of MDS Matrix Multiplication

Assume we have an $n \times n$ MDS matrix, whose entries are among $m \times m$ binary matrices. Can we see this matrix as a $n \times n$ matrix with entries from $GF(2^m)$? How can we replace this ...
user avatar
  • 13
1 vote
0 answers
76 views

Proving a function in $\operatorname{GF}(2^n)$ is differentially k-uniform

I want to show that $F(x) = x^{-1}$ in $\operatorname{GF}(2^{n})$ is differentially 4-uniform for even $n$, and is differentially 2-uniform for odd $n$, without looking at the Differential ...
user avatar
  • 13
0 votes
2 answers
68 views

Algebraic Normal Form of a function in $\operatorname{GF}(2^{n})$

Consider the function $f(x)=x^{2k+1}$ in $\operatorname{GF}(2^{n})$ for $n$ odd and $\gcd(k,n)=1$, which is differentially 2-uniform function. For $n=3$, $k=1$, I want to find the Algebraic Normal ...
user avatar
  • 13
2 votes
1 answer
217 views

Poly1305 reuse of r

Poly1305 uses $r, r^2, r^3$ and $r^4$. I understand this if $r$ is a generator of the finite field. But since $r$ can be any random non-zero number, won't its exponents be non-uniform distributed? ...
user avatar
0 votes
1 answer
76 views

Understanding non-linearity in Salsa20 over various rings

In his design of Salsa20, Bernstein writes to ensure non-linearity he chose 32-bit addition (breaking linearity over $Z/2$), 32-bit xor (breaking linearity over $Z/2^32), and constant-distance 32-bit ...
user avatar
1 vote
1 answer
387 views

How to calculate the order of secp256k1?

The elliptic curve secp256k1 is defined as $y^2 = x^3 + 7$. The prime for the field is set to: ...
user avatar
  • 113
3 votes
2 answers
356 views

Recognize whether two random values are raised to the same power

Alice selects two random numbers from a finite field $Z_p$ : $a$ and $b$. Bob does one of the two following steps randomly (sometimes he does step 1; sometimes step 2): He chooses a random number $r$ ...
user avatar
6 votes
1 answer
690 views

How to determine if a point is just a point or a valid public key?

In ECC, specifically over finite fields, in my mind there must be other points that exist that still yield $y^2 \bmod p=x^3 + ax + b \bmod p$ to be true but are never used because the Generator Point (...
user avatar
2 votes
2 answers
115 views

Discrepancy $δ$ in the Berlekamp-Massey Algorithm

I have a question regarding to the Berlekamp–Massey algorithm. Can someone guide me to understand the idea/intuition of this algorithm? According to the explanation in Wikepedia, in each iteration, ...
user avatar
1 vote
0 answers
28 views

A finite group with a threshold functionality

I am trying to find a generator of a finite group that its powers devides the group into two parts. For example look at the last row of this table that shows the powers of 10 in the group Z_19. You ...
user avatar
0 votes
0 answers
119 views

Using random invertible matrices over finite fields to define the hash of a list

This is a follow-up to a prior question Does matrix multiplication of hash digests admit manipulation of the result?; this formulation failed because it admitted singular matrices and therefore ...
user avatar
  • 103
0 votes
0 answers
27 views

Checking whether a particular group has an efficient, faithful representation as a matrix group

There are cryptographic protocols being developed for non-abelian groups. For some protocols it is necessary to know whether the group has an efficient representation as a matrix group (say, a matrix ...
user avatar
11 votes
5 answers
4k views

Why are finite fields so important in cryptography?

I am just getting into cryptography and currently learning by trying to implement some crypto algorithms. Currently implementing the Shamir secret sharing algorithm, what I have noticed is that finite ...
user avatar
  • 121
1 vote
2 answers
83 views

Permutation polynomial

I want to find a linearized polynomial as my permutation polynomial in GF(2^n). I know that the only root should be 0. So, is there any way to find such polynomial instead of choosing a random one and ...
user avatar
  • 53
0 votes
1 answer
102 views

Are Shamir shares independent?

Assume we have a secret $s \in Z_p$. We generate the set of secret shares $\{ (x_i, s_i) \}_{i=1}^{N}$ according to a $(N,k)$ Shamir's scheme. The evaluations are generated according to the following ...
user avatar
1 vote
0 answers
79 views

Multiplication in Tower Field $GF(2^4)^2$

I'm currently reading an article which deals with "Squeezing Polynomial Masking into Tower Fields " for performing an efficient multiplication of elements in $GF(2^8)$. Thereby it is ...
user avatar
4 votes
3 answers
367 views

Pohlig-Hellman: While solving in a subgrp, why is multiplication done mod the parent group's $p$ while the exponent is expanded as per $p_i$ of subgrp

In the Pohlig-Hellman algorithm, we take a Discrete Log Problem (DLP) in a group & solve it in subgroups $p_1^{n_1}$, $p_2^{n_2}$, $p_3^{n_3}$ etc & then combine it with the Chinese Remainder ...
user avatar
  • 1,678
2 votes
3 answers
221 views

Where to apply Montgomery Multiplication in GF(2^n)

I'm optimizing a Reed Solomon decoding library for several polynomials in $\operatorname{GF}(2^k)$, $k\in\{8,10,12\}$. Reading about the Montgomery Multiplication from Çetin K. Koç & Tolga Acar's ...
user avatar
1 vote
2 answers
98 views

Multiparty Computation to calculate addition of shares without revealling individual shares

I have $n$ persons, each holding a secret integer $x_i$ ($i$ from $1$ to $n$) and I'm looking for a way for them to jointly compute the sum of these secrets without revealing to each other their ...
user avatar
  • 13
0 votes
1 answer
111 views

Finding Multiplicative Inverse In Field

Consider the finite set Z_257 of non-negative integers less than 257. The number 257 is a prime, so Z_257 forms a field with addition and multiplication mod 257. How can I use the Extended Euclidean ...
user avatar
2 votes
1 answer
82 views

How does table size impact table lookup speed?

Are there good discussions of how cache pressure impacts large 64k-ish lookup tables used in erasure coding and sometimes signature verification? I'll focus on erasure coding in small characteristic ...
user avatar
  • 1,104
2 votes
1 answer
134 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 "...
user avatar
  • 8,394
0 votes
0 answers
38 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 ...
user avatar
  • 113
5 votes
2 answers
429 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 ...
user avatar
  • 42.9k
2 votes
1 answer
125 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*...
user avatar
4 votes
2 answers
200 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 ...
user avatar

1
2 3 4 5
7