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

3
votes
2answers
836 views

Additive ElGamal cryptosystem using a finite field

I'm trying to implement a modified version of the ElGamal cryptosystem as specified by Cramer et al. in "A secure and optimally efficient multi-authority election scheme", which possesses additive ...
0
votes
1answer
31 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 ...
-2
votes
3answers
533 views

How to reverse this hash function?

I have a function that takes an $m$ byte inputs $x_i$ and maps it a 32 byte outputs $y_j$. The hash function is defined as: $$y_j = \sum_{i=1}^{m} (x_i)^{i-1} \pmod {127}$$ The input is restricted ...
3
votes
1answer
71 views

Schnorr signature security level as compared to AES/RSA

As per the Schnorr's original paper (1991), The Security Complexity $2^t$: We wish to choose the parameters $p$, $q$ so that forging a signature or an authentication requires about $2^t$ steps by ...
3
votes
2answers
155 views

How to use the Extended Euclidean algorithm to invert a finite field element?

I was doing some practice on cryptography (I'm new to this topic) and was wondering what the following question even means or what it is asking me to find. I do know how to do Extended Euclidean ...
4
votes
2answers
187 views

What is this “finite field cryptography”?

See RFC 5931 § 2.2.1 which talks about "finite field cryptography" as opposed to elliptic curve cryptography and it looks like it is describing the Diffie-Hellman protocol. But Diffie-Hellman is not a ...
0
votes
2answers
42 views
1
vote
1answer
57 views

multiplicative inverse in galois field $2^8$

I am trying to compute the multiplicative inverse in galois field $2^8$.The question is to find the multiplicative inverse of the polynomial $x^5+x^4+x^3$ in galois field $2^8$ with the irreducible ...
0
votes
2answers
109 views

Algebraic structures in RSA

Why do we need a field for RSA and what are the two operations in this field? Why can't we have a ring or group for example? Because in a group you also have inverse elements.
0
votes
0answers
33 views

Using quadratic residue to learn the sign of a field element

Given $x' \in \{-x, x\} \bmod q$ (where $q$ could be any prime of my choice), $s$ is a random element in the field, $y = x'\cdot s$ and $y' = \pm\sqrt{(x\cdot s)^2}\bmod q$ (i.e., both solutions to ...
3
votes
2answers
53 views

Non primitive lfsr sequence

Given a non-primitive LFSR sequence (i.e number of states is less than $2^n - 1$); how do we find out the the characteristic polynomial? Will Berlekamp-Massey algorithm work in this case? for ...
0
votes
1answer
21 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 ...
1
vote
1answer
60 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 ...
1
vote
1answer
219 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 ...
-1
votes
1answer
101 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.
-4
votes
1answer
36 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?
10
votes
2answers
350 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 ...
1
vote
1answer
66 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 ...
7
votes
0answers
77 views

Default algorithm for scalar multiplication of elliptic curve points by the MIRACL Library

What is the default algorithm used by the MIRACL-Library [1] for elliptic curve cryptography systems to perform scalar-point multiplication with curves of Weierstrass form satisfying the equation : ...
1
vote
1answer
41 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 ...
3
votes
2answers
102 views

Implementation of ECC over binary field

I am supposed to implement ECC over binary field (in C++) for equations of the type - $y^2 + xy = x^3 + ax + b$, as my project. I wish to include the following features : The user will enter a prime ...
3
votes
0answers
35 views

Seeking an implementation of the Satoh algorithm for elliptical curve point counting

I would be very grateful if someone has an implementation of the Satoh algorithm (Fast Elliptic Curve Point Counting). Can someone point me to practical algorithm implementations or provide some ...
3
votes
1answer
104 views

Fast reduction in $GF(2^{128})$ using x86 `PCLMULQDQ`

Modern x86 CPUs support the PCLMULQDQ instruction, which does an XOR-multiply of two 64-bit numbers instead of an add-multiply (i.e. typical arithmetic ...
0
votes
0answers
59 views

Multiplication in GF(2^8)

I am trying to multiply 13 (sub 16) and 11 (sub 16) in $GF(2^8)$. I am given the following irreducible polynomial: P(x) = x^8 + x^4 + x^3 + x +1 Could someone explain to me how to express the ...
3
votes
1answer
61 views

converting finite field elements to octet strings

I need to convert elements of the finite field $GF(p^k)$, where $p$ is an odd prime, to octet strings. To be more precise, I want to include elliptic curve points over $GF(p^2)$ in a Subject Public ...
4
votes
3answers
138 views

Calculating $\mathbb F_{p^2}$-rational points of an elliptic curve defined over $\mathbb F_p$

How can I calculate points on an elliptic curve defined over $\mathbb F_p$, for example $y^2 \equiv x^3 + 1 \pmod p$, with coordinates in $\mathbb F_{p^2}$? (points might have complex number format in ...
4
votes
3answers
549 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 ...
0
votes
1answer
23 views

Lower defree annihilator of function

Suppose $f=x_0x_2(x_1+1)+x_1x_3(x_0+1)$, annihilator is such function $g$, so that $gf=0$ for all $x$ Intuitively solution(for some reason) is obvious - $g=x_0x_1$, which holds true. (Cloud sagemath ...
3
votes
1answer
53 views

Do $v_1=\alpha\cdot r_1$ and $v_2=\alpha\cdot r_2$ leak information about $\alpha$

Please consider we have finite field $\mathbb{F}_p$ for large prime number $p$. We have a fixed field element $\alpha$. By $r_i\leftarrow \mathbb{F}_p$ we mean we pick $r_i$ uniformly random from the ...
1
vote
1answer
125 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, ...
0
votes
0answers
81 views

Multiplicative inverse ($17^{-1} \mod 31$)?

So. Sorry for bothering you with such a simple question, but I can't really get this done. It's just an exam question in which I need to use CRT in order to calculate the RSA signature of a msg ...
3
votes
2answers
131 views

What is the difference between the standard representants of $\mathbb Z/q\mathbb Z$?

The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this ...
1
vote
1answer
51 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
231 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 ...
4
votes
2answers
193 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
366 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 ...
0
votes
0answers
48 views

Discrete log in Galois Extension Field

I was reading 'Pinocchio Coin' paper by Danezis et al. where they have said, "If we use the efficient pairing groups of Pinocchio, computing discrete logarithms in the exponent field $\mathbb{F}_p$ ...
12
votes
1answer
578 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 ...
2
votes
3answers
156 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
128 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
100 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
114 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
124 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
68 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
276 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
89 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
127 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
528 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
472 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 ...
6
votes
2answers
277 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 ...