# 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.

229 questions
1answer
109 views

### How should I define order according to domain parameters in elliptic curve pairing groups?

According to domain parameters, as an example Type 1 pairing domain parameters are ...
1answer
52 views

### Probability of generating same master secret key in Identity-based Encryption

Suppose multiple servers use same IBE domain parameters (I mean same curve description parameters and field) for master secret key setup. Is there any possibility for generating the same system ...
1answer
646 views

### How to perform AES MixColumns as matrix multiplication in GF(2) (boolean values)?

AES MixColumns is done by multiplying a $4 \times 4$ matrix and a column of the AES state (a vector). Addition and multiplication are done in $\operatorname{GF}(2^8)$. In the paper White-box AES, the ...
1answer
124 views

### How to find roots of equation $f(x)=0 \pmod p$, where $p$ is prime number?

$f(x)$is any nth degree equation $n>0$, how to find roots of $f(x)$ over prime modulo.
1answer
159 views

### Computing inverses in a binary field

Please suggest how can i solve the below question What is the inverse of {03} in GF (2^8) with the irreducible polynomial x8+x4+x3+x+1?
1answer
217 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 ...
1answer
121 views

### Elliptic ElGamal Public Key Cryptosystem doubt

I need an example of Elliptic ElGamal Public Key Cryptosystem. I have been trying with some values but I don't get the right solution. I have $p=13$, the elliptic curve $E:y^2=x^3+11x+7$ and a point ...
1answer
309 views

3answers
493 views

### How does $g$ being a generator imply Diffie-Hellman's correctness?

In the Diffie-Hellman protocol for key exchange over an unsecured channel, we choose $p$ and $g$, where $g$ is a generator of $\mathbf{Z}_p^*$. However I want to know why this assumption makes the ...
1answer
226 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 ...
1answer
522 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$ ...
2answers
387 views

### In a group, is it hard to calculate the base $g$ given $g^a$ and $a$?

Discrete logarithm, that is: calculate $a$ given $g$ and $g^a$, is assumed to be a hard problem in some groups. Is it also hard to calculate $g$ given $g^a$ and $a$?
2answers
279 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 ...
1answer
135 views

### Applications of GF(p) polynomials

A Galois field of the type $GF(p)$, where $p$ is prime, is normally expressed as the ring of integers modulo $p$. If my understanding is correct, it is also possible to represent its elements as a ...
1answer
291 views

### What is the difficulty of DLP in GF(P^Q) with a subgroup with a prime order of L

Given a finite field GF(P^Q), having a subgroup with a prime order of L (P,Q,L are all primes), how difficult is it to find the discrete log, is it related to P and Q or is it related to L, or to both....
3answers
458 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 ...
1answer
3k views

### How to calculate AES logarithm table?

I would like to know how to find multiplicative inverses in $\mathrm{GF}(2^8)$. I know how to multiply two elements of $\mathrm{GF}(2^8)$ (for example, I know that ...
2answers
1k views

### Solving Quadratic equations in Galois Field (2^163)

Hello I am working on implementing a message to elliptic curve point mapping hardware circuit I have done some research and found out the koblitz mapping method: I will be using a field of binary ...
3answers
1k views

### Does RSA operate over a Finite Field (Galois Field)?

Is it correct to say that RSA operates over a Finite Field (Galois Field)? In this case GF(p)? I do understant that the modulo in RSA is not itself a prime number, but all the operations (...
1answer
284 views

### Elliptic curve trapdoor function without modular arithmetic?

From what I understand, an elliptic contains a set points satisfying the equation $y^2=x^3 + ax + b$ together with the point at infity. It seems clear how multiplication with a scalar and a point ...
1answer
452 views

1answer
115 views

### Does $i^n=j^n$ for $i, j \in GF(2^q)$ and $i \neq j$ for some $n<2^q-1$

Let $i, j \in GF(2^q)$ and $i \neq j$ and $i,j\neq0$. Is that possible that $i^n=j^n$ for some $n$ such that $0 < n < 2^q-1$? I am looking for a proof if the answer is no, or for a method to ...
1answer
187 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 ...
1answer
267 views

### Sextic twist of BN pairing parameters vs security

I've previously asked questions on BN pairing parameters. Here's one more. In the BN construction, one is working in a subgroup of a curve over an extension field $\mathbf{F}_{p^{12}}$ for some ...
1answer
498 views

### Sextic twist optimization of BN pairing - cubic root extraction required?

I found the following paper really interesting: http://www.researchgate.net/publication/220378229_A_family_of_implementation-friendly_BN_elliptic_curves/file/79e4150b3a773beecd.pdf It allows ...
1answer
882 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 ...
3answers
482 views

### Generating bilinear pairing parameters - running time of finding member of p-torsion group

Update: Question completely rephrased. I want to create the parameters for a bilinear pairing (the Tate pairing in this case). In case you're interested I'm following this thesis, specifically the ...
1answer
1k views

### Why do we use 1024 / 160 bit primes in DSA?

I am looking at DSA's parameter generation and don't understand why for $p$ a 1024 bit prime is needed if $q$ is chosen as a $160$ bit prime. I thought that the security of DSA relates on the discrete ...
2answers
420 views

### Choice of reduction polynomial in Whirlpool's internal cipher

Whirlpool is an interesting little hash function in the Miyaguchi-Preneel family. In my mind, it's most interesting feature is the design of internal cipher W, where the distinction between key and ...
2answers
631 views

### Secure degree reduction for Shamir's secret sharing

I understand the basic Shamir Secret Sharing protocol, and when two shares are multiplied, the degree of the polynomial increases. I've seen in a number of papers a reference to a degree reduction ...