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
197 views

Cryptographic Arithmetic Toolbox/Software [closed]

This term I have many cryptography courses treating finite fields. I was wondering if there is any good software that could help doing basic operations in galois fields etc. I already googled but ...
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 "...
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*...
2
votes
0answers
83 views

Pre-computing a log and exp table for a primitive polynomial in $GF(2^8)$ [duplicate]

I'm new on the topic of finite fields, specifically $GF(2^8)$. I've come across the information that it's possible to implement multiplication using logarithm and exponential tables. But how are ...
2
votes
0answers
352 views

Construction of Isomorphism between Galois Fields

I am trying to create an isomorphism between GF($2^8$) and an extension field in GF($(2^4)^2$). The finite field GF($2^8$) uses the Rijndael(AES) irreducible polynomial.In this field I have found 128 ...
2
votes
0answers
101 views

How many Affine function can be made from $4 \times 4$ and $8 \times 8$ S-boxes?

The nonlinearity of an S-Box is defined as the non-linearity of its vectorial Boolean Function. Let $F$ be the hamming distance between the set of all non-constant linear combinations of component ...
1
vote
1answer
256 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 ...
1
vote
1answer
880 views

Elliptic Curve - Divide by 2

Can anyone tell me the specific equations and steps for dividing a point on an elliptic curve by 2? For instance, I have the point $(P_x, P_y)$, and I would like to find the point $(R_x, R_y)$ which ...
1
vote
1answer
849 views

Shamir Secret Sharing GF(p) or GF(2^8)

I'm implementing Shamir's Secret Sharing Scheme, but I've hit a conceptual roadblock. In Shamir's paper "How To Share A Secret" he creates his shares an a finite field of order p, where p is some ...
1
vote
1answer
126 views

Subscript R notation for the finite fields

I'm trying to understand the notation used in the literature for Pairing-based cryptography. I know (and I hope I've understood it well) from Wikipedia that $\mathbb{Z}_p$ is the finite field of prime ...
1
vote
3answers
597 views

Random Galois fields

Note: I have now answered this by my own research and can generate random fields up to G(2^9) in reasonable time. I would need to find more speedups for larger fields. At this time G(2^8) takes a few ...
1
vote
2answers
161 views

Is it possible to use structures other than finite fields?

I have some difficulties to understand why we are using finite fields in cryptography. Why do we use field? Why not ring or group? Is that really necessary that the field is finite? Why not real ...
1
vote
3answers
3k views

Lagrange Interpolation for finite field GF(2^8), for Secret Reconstruction

I'm using Lagrange's Interpolation technique to reconstruct the secret from a set of point pairs (x,y). Since I only need the secret, not the whole polynomial, I have simplified the reconstruction ...
1
vote
1answer
541 views

Solving a discrete logarithm using GDlog

I am trying to calculate an $x$, such that $t = g^x \pmod p$ in order to crack a weak ElGamal encryption for university. I found GDlog, but I cant figure out how I can use the input to calculate my $...
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
1answer
580 views

how to choose a random secret key for ECDH

I am a beginner, I can understand the basics of ECC and elliptic curve, i can't find where I missed to understand. But I have a great doubt in ECDH regarding below. Could any of you please clarify for ...
1
vote
1answer
383 views

How to split up $GF(2^{128})$ into smaller fields?

I've heard that it's possible to split up $GF(2^{128})$ into copies of several smaller fields like $GF(4)$ so as to make the math easier in some cases. How do you do that? I know how it works for ...
1
vote
1answer
2k views

Calculating Multiplicative Inverse for Rijndael S-box using EEA

I am currently learning, and I'm stuck on something that I thought is very simple. On many academic sources they suggest using Extended Euclidean Algorithm to calculate the multiplicative inverse for ...
1
vote
1answer
210 views

How do I express each element in a field F as a power of a primitive element?

I have a field $\mathbb F_{2^4}$, and it is represented as a residue ring of the polynomials over $\mathbb F_2$ modulo the polynomial $\beta^4 + \beta^3 + \beta^2 + \beta + 1$. I want to express ...
1
vote
2answers
504 views

Factoring a polynomial over a GF [closed]

I have the following question: What polynomial, when factored over the field $GF (2^8)$ based on the irreducible polynomial that is used in Rijndael, will factor into all the polynomials in the ...
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 ...
1
vote
1answer
163 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
129 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 ...
1
vote
2answers
400 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 ...
1
vote
1answer
136 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
203 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 ...
1
vote
2answers
422 views

How to calculate Trace function for a point on an elliptic curve

I encountered trouble with calculating Tr (trace function) for points on an elliptic curve in polynomial basis ( $GF(2^m), m = 431$). Maybe there are any assumptions that can simplify and allow ...
1
vote
2answers
250 views

powers of g in $GF(256)$

The finite field $GF(256)$ is usually implemented $mod$ 0x11b to keep the numbers inside that field. I understand that 0x11b was ...
1
vote
1answer
143 views

do koblitz curves over $\mathbb{F}_{P}$ as generalized in SEC2 always have $a$ as 0?

I reviewed all the curves in http://www.secg.org/SEC2-Ver-1.0.pdf . All the secp*k* curves have the $a$ parameters as 0 and those are the only ones with the $a$ as 0. Is this a defining requirement ...
1
vote
1answer
277 views

How do we reduce the multiplications in the AES mix column layer using $x^4 +1$

I recently learned AES uses $x^4 +1$ to reduce the multiplications in the MixCol layer. However, I used $p(x) = x^8 + x^4 + x^3 + x + 1$ not knowing it was the wrong polynomial and got the correct ...
1
vote
1answer
478 views

Generate Finite Field power of g

consider the field $\mathbb{F}_{2^4}$, defined by using polynomial representation with the irreducible polynomial $f(x) = x^4 + x + 1$. Given element $g = (0010)$ as a generator for the field, How ...
1
vote
1answer
1k views

simple multiplication in GF(8)

I am trying to do multiplication in the GF($2^3$) defined by the irreducible minimum binary polynomial $X^3+X^2+1$. I want to multiply $A(x) * B(x)$ where $A(x) = x$ and $B(x) = x^2$. The ...
1
vote
1answer
474 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= ...
1
vote
1answer
591 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 ...
1
vote
1answer
150 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 ...
1
vote
1answer
309 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
vote
1answer
268 views

How Elliptic-Curve affects the Server Key Exchange parameters

In Finite Field DHE, the server sends the following parameters in the server key exchange message: $p$: prime $g$: group $g^b$: the server's public DH key In DHE_RSA (non anonymous DHE), the server ...
1
vote
1answer
192 views

Galois Field multiplication instead of Diffie Hellmans discrete logarithm

I am wondering if the inversion of multiplication of polynomials is equally hard as the discrete logarithm problem used for key exchange. Or are there algorithms that weaken such an usage. I ...
1
vote
1answer
153 views

How to use Frobenius for finding Square Roots in $GF(2^m)$

Given a polynomial $x$ with degree $n$ in $GF(2^m)$, $1 < n < m$, will any generator of $GF(2^m)$ suffice when applying the Frobenius automorphism to determine the square root of $x$ as ...
1
vote
1answer
91 views

What hash functions can be (efficiently) computed over GF(2^m)?

Given an arithmetic circuit over a finite field of characteristic 2, what families of cryptographic hash functions can be efficiently computed with this circuit? Can standard hash functions be ...
1
vote
1answer
4k views

Calculating the multiplicative inverse of a number in $GF(2^n)$ where $n > 8$

Suppose that: We have a polynomial $g(x)$ of degree $n$. $n > 8$. $q$ is the multiplicative inverse of $p$ in $G(2^n)$ modulo $g(x)$. If $p = 0$, then $q = 0$. This could be used: As a non-...
1
vote
1answer
203 views

(AES in mind) How can we show two irreducible polynomials have a bit-wise linear isomorphism

This refers to answer 2 on a similar question:Design properties of the Rijndael finite field I am unsure what many of the terms mean in this answer. I think a bit-wise linear isomorphism of ...
1
vote
1answer
436 views

Shamir's Secret Sharing on non-prime GF

I am implementing Shamir's secret sharing scheme on arbitrary binary files. I don't intend to use this; this is a project to help me explore cryptography. In setting up the finite field arithmetic, ...
1
vote
1answer
2k views

AES MixColumns using L and E lookup tables

I am trying to verify the multiplication by $\mathtt{02}$ in Galois Fields for MixColumns function using the L and E lookup tables. I could verify $\mathtt{D4}\cdot\mathtt{02}=\mathtt{B3}$ by manual ...
1
vote
2answers
139 views

Does the generator (base point) is preshared between the sender and receiver in elliptic curve cryptography?

Or the elliptic curve and the generator point are known to everyone?
1
vote
1answer
1k views

Modular reduction for NIST prime P256— understanding the data

I am working on a project where I need to implement elliptic curve cryptography, I am struggling from a long time in order to understand the working and the process. Modular finite field arithmetic, ...
1
vote
1answer
116 views

Degenerate discrete logarithm in binary field

Given a field $\mathbb{F}_{2^n}$, are there any choices of primitive element $g$ that make the discrete logarithm easier for that generator? That is, are there any degenerate cases? For example, if I ...
1
vote
1answer
273 views

What is the polynomial to use in the Massey-Omura cryptosystem?

The Massey-Omura cryptosystem uses "multiplication over the finite field $GF(2^n)$. I'm just starting understand the idea of multiplying polynomials and I've searched for online calculators to use for ...
1
vote
1answer
767 views

Finding $x$'s parity in the discrete log problem

Suppose $p$ is prime, and $g, a\in\mathbb F_p$ are given elements with $g$ a primitive root. The discrete log problem poses the task of finding an integer $x$ such that $g^x=a$. Show that even if $x$ ...
1
vote
2answers
332 views

Usage of GF(p^m) fields, where p != 2

$GF(2^m)$ Galois fields are widely used in different cryptographic algorithms, for example, in Rijndael. However, $GF(p^m)$ fields are possible with any prime $p$, not only 2, but $GF(2^m)$ fields ...