# Tagged Questions

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

59 views

### In what sense addition modulo $n$ ($n>2$) isn't linear in the field $\mathbb{F}_2$?

I've been reading the Reason why “XOR” is a linear operation, but ordinary “addition” isn’t? question, in which one of the answers states that addition modulo $n$ ($n>2$) is linear in $\mathbb{Z}_n$...
28 views

87 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 ...
243 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 ...
217 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 ...
76 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 ...
122 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.
34 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 ...
77 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 example;...
35 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 ...
93 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 ...
261 views

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 $\rm{GF}(p)... 1answer 104 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 42 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? 2answers 455 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 ... 1answer 73 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 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 ... 2answers 135 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 ... 0answers 36 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 ... 1answer 133 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 ... 0answers 70 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 ... 1answer 63 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 ... 3answers 142 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 ... 3answers 605 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 24 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 ... 1answer 56 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 ... 1answer 169 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, ... 0answers 85 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 m=101(... 2answers 149 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 ... 1answer 52 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 ... 1answer 282 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 ... 2answers 196 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$? 1answer 372 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$...
50 views

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$ ...
616 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 ...
164 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 ...
143 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 ...
109 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 ...
### 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$ ...
$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 ...