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

learn more… | top users | synonyms

0
votes
0answers
26 views

Curve41417 example

I have done an example, attached as image file, of the algorithm in Curve41417 by Daniel J. Bernstein et al. but my answer is not correct. I have checked it multiple times but couldn't find the ...
0
votes
1answer
65 views

Choosing finite field size in Shamir's Secret Sharing Scheme

The Wikipedia article on Shamir's Secret Sharing says to that to have information theoretical security the splitting algorithm should be evaluated using finite field arithmetic on the field ...
11
votes
1answer
358 views

Choice of multiplication polynomial in Rijndael s-box affine mapping

The Rijndael specification details the design choices for the s-box in section 7.2. They describe the choice of affine mapping as follows: We have chosen an affine mapping that has a very simple ...
1
vote
3answers
102 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 ...
0
votes
0answers
56 views

Affine transformation in finite field SubBytes

Can anyone please explain how this computation was done? I picked it up from How are the AES S-Boxes calculated? The affine transformation is as follows. The input bits are multiplied against the ...
1
vote
1answer
43 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 ...
3
votes
2answers
160 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$?
1
vote
1answer
72 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
64 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 ...
0
votes
1answer
47 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 ...
0
votes
3answers
224 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 ...
0
votes
1answer
65 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 ...
0
votes
2answers
103 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 ...
0
votes
1answer
161 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 ...
3
votes
2answers
262 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 ...
2
votes
2answers
236 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 ...
5
votes
2answers
197 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 ...
0
votes
0answers
49 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 ...
0
votes
1answer
106 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 ...
3
votes
1answer
351 views

Why does FIPS 186-4 require specific sizes for keys?

In FIPS 186-4, page 32, about FFC crypto it is required that the length of $p$ will be exactly 1024 bit and the length of $q$ will be exactly 160 bit. Why is the requirement not stated in terms of ...
5
votes
1answer
1k views

AES mixcolumn stage

I'm studying AES, and am having problems with the "mixcolumn" stage. I read about finite fields, but I still don't know. How do I construct $GF(2^8)$? ...
1
vote
1answer
88 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 ...
4
votes
3answers
174 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
315 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
150 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
1answer
46 views

Question about block erasure codes

I have a question about linear block erasure codes that are described in this paper. I briefly describe the idea behind the linear erasure codes and then I ask my question. Given a set $d=\langle x_i ...
3
votes
1answer
89 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 ...
1
vote
2answers
695 views

Finding the LFSR and connection polynomial for binary sequence. [closed]

I have written a C implementation of the Berlekamp-Massey algorithm to work on finite fields of size any prime. It works on most input, except for the following binary GF(2) sequence: $0110010101101$ ...
2
votes
1answer
109 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 ...
3
votes
2answers
146 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 ...
10
votes
3answers
370 views

Mapping between subgroups and the integers

This question is a companion to the equivalent question on elliptic curves. Preliminaries Diffie-Hellman, Elgamal, DSA, etc. are examples of protocols that work in the integers modulus a large prime ...
1
vote
0answers
74 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 ...
3
votes
1answer
122 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 ...
1
vote
1answer
268 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 ...
1
vote
1answer
137 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 ...
2
votes
3answers
223 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 ...
0
votes
2answers
2k views

Multiplicative inverse in $GF(2^8)$?

I know how to do multiplication over $GF(2^8)$. Logic is... ...
12
votes
1answer
478 views

Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use?

A recent paper by Göloğlu, Granger, McGuire, and Zumbrägel: Solving a 6120-bit DLP on a Desktop Computer seems to "demonstrate a practical DLP break in the finite field of $2^{6120}$ elements, using ...
2
votes
1answer
424 views

How Multiplication Table is generated for GF(2^2) field

I was unable to solve the multiplication table given in the book for $\mathrm{GF}(2^2)$.However, I have managed to solve the addition table. Acoording to the Book multiplication is the AND operation, ...
1
vote
0answers
82 views

Can you provide an example in relation to Hidden Field Equations Multivariate?

I'm reading about Hidden Field Equations Multivariate scheme. My lecture states that the central map is a univariate polynomial $$P(X)=\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}p_{ij}x^{q^i+q^j} \in K[X]$$ ...
15
votes
3answers
902 views

What is so special about elliptic curves?

There seems to be sources like this, this also, and some introductions that discuss elliptic curves in general and how they're used. But what I'd like to know is why these particular curves are so ...
3
votes
2answers
933 views

Why does Shamir's Secret Sharing Scheme need a finite field?

I read ampersand's question "Necessity for finite field arithmetic and the prime number p in Shamir's Secret Sharing Scheme", where he asked why Shamir's Secret Sharing Scheme uses arithmetic in a ...
12
votes
1answer
408 views

Security of pairing-based cryptography over binary fields regarding new attacks

In the last week, the discrete logarithm problem was broken for the binary fields $\mathbb{F}_{2^{(14 \times 127)}}$ and $\mathbb{F}_{2^{(27 \times 73)}}$. Pairing-based cryptography using binary ...
1
vote
3answers
733 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 ...
5
votes
1answer
4k views

Multiplication/Division in Galois Field (2^8)

I'm attempting to implement multiplication and division in $GF(2^8)$ using log and exponential tables. I'm using the exponent of 3 as my generator, using instructions from here. However I'm having ...
6
votes
1answer
248 views

Why use variable p, q, g for Diffie-Hellman?

In the book Cryptographic Engineering, it is said that fixing p, q, g for a key negotiation protocol based on DH is a bad idea (page 228 1st ed). But allowing for flexible p, q and g requires a lot ...
2
votes
1answer
429 views

Solve a system of non linear equations over GF

I have the following set of equations: $$M_{1}=\frac{y_1-y_0}{x_1-x_0}$$ $$M_{2}=\frac{y_2-y_0}{x_2-x_0}$$ $M_1, M_2, x_1, y_1, x_2, y_2,$ are known and they are chosen from a $GF(2^m)$. I want ...
5
votes
1answer
350 views

What do recent announcements about solving the DLP in $GF(2^{6120})$ mean for RSA

After just reading the post Do recent announcements about solving the DLP in $GF(2^{6120})$ apply to schemes proposed for cryptographic use? I was a bit confused. DSA, ElGamal and others are based on ...
16
votes
3answers
1k views

How robust is discrete logarithm in $GF(2^n)$?

"Normal" discrete logarithm based cryptosystems (DSA, Diffie-Hellman, ElGamal) work in the finite field of integers modulo a big prime p. However, there exist other finite fields out there, in ...
3
votes
1answer
408 views

Understanding Feldman's VSS with a simple example

I'm trying to understand Feldman's VSS Scheme. The basic idea of that scheme is that one uses Shamir secret sharing to share a secret and commitments of the coefficients of the polynomial to allow the ...