11
votes
Accepted
Advantages of Montgomery Ladder-based Scalar Multiplication
Synthetically, the advantages of the Montgomery ladder are that it is simple and fast.
If you look at X25519, the Diffie-Hellman algorithm applied to Curve25519 and described in RFC 7748, you will see ...
- 84.7k
7
votes
Accepted
Why does AES use a Binary Field?
Well, there would be two possible ways to use modular arithmetic:
You could do the arithmetic modulo $2^n$. However, that has some nasty properties (not all elements have multiplicative inverses, ...
- 132k
6
votes
Accepted
How do Käsper and Schwabe's Bitsliced AES Mixcolumns work?
Slide #8 in the presentation you linked to describes the way Käsper and Schwabe pack the bits of the AES data blocks into CPU registers.
According to the slide, what they're doing is processing eight ...
- 44.4k
6
votes
Accepted
What is the branch number of this matrix?
The matrix is not MDS over $GF(2)$; No binary MDS codes exist and non nonbinary (over $GF(2^n)$ MDS codes would have this generator whose scalar entries are in the field $GF(2)$). Over $GF(2^n)$ The ...
- 16.4k
5
votes
Accepted
Prove the branch of number of Advanced Encryption Standard
The dear user @kodlu has answered to the similar question with excellent discussion but I want to answer with linear algebra argument.
We have two definitions for MDS (Maximum Distance Separable) ...
- 304
4
votes
Accepted
How to calculate active s-boxes from branch number?
Khazad has an $8\times 8$ MDS matrix $A$ used as the diffusion layer. The augmented matrix $[I|A]$ generates a $[n,k,d]=[16,8,9]$ MDS code over $GF(2^8).$ The implications are:
The minimum number of ...
- 16.4k
4
votes
Accepted
How do we reduce the multiplications in the AES mix column layer using $x^4 +1$
The $x^4+1$ is implicit in the matrix.
What you are doing is that you consider formal sums $z_0 + z_1 \alpha + z_2 \alpha^2 + z_3 \alpha^3$ for $z_i$ elements of the field $\mathbb{F}_{256}$, and a ...
- 84.7k
4
votes
How can I get the binary form of AES's MDS matrix in MixColumns tranformation?
Concretely, given an element $x \in$ GF($2^8$), to multiply it by 2, we simply do a left shift and xor with 0b100011011 if the result of the shift gets above 0b11111111 (255). To multiply by 3, we ...
- 121
4
votes
What is the time complexity of the basic components of a symmetric cipher?
I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above
You wont really find anything because those components are generally not described that ...
- 12.7k
4
votes
How to check that an $km \times km$ block-binary matrix is an MDS matrix in $k$-bit words over $\operatorname{GF}(2)$
Let $\bf A$ be an $n \times n$ binary matrix. Let we want to check that whether $\bf A$ is an MDS matrix over the finite field $\mathbb{F}_{2^k}$ for some $k$?
The necessary condition is that $k\mid n$...
- 233
3
votes
What is the time complexity of the basic components of a symmetric cipher?
You may need to specify your model of computation to make your question answerable.
In some models bitwise XOR is ${\rm O}(n)$ in the number of bits being XORed; it others it can be ${\rm O}(1)$, ...
- 44.4k
3
votes
Accepted
How can I get the binary form of AES's MDS matrix in MixColumns tranformation?
Here is a Sage code that creates the MDS matrix over $F_2$.
...
- 80
3
votes
How can I get the binary form of AES's MDS matrix in MixColumns tranformation?
This question can be used to get what you want.
There we use bytes (so expand those to bits) and you have to use extra XOR's (i.e. binary additions) to get the field multiplications.
- 3,772
3
votes
Why are $\{0,1\}$-matrices almost-MDS only when n is 2, 3, or 4?
From the article on page 5;
Theorem 1 Let $A:{GF(2^m)}^n \to {GF(2^m)}^n$ be an $n\times n \{0,1\}$-matrix over $GF(2^m)$. Then the branch number of $A$ is at most $\frac{2n+4}{3}$.
Let $A$ be the ...
- 2,285
3
votes
Hill Cipher question
You would need (at least) 3 pairs of vectors in order to determine the 3*3 matrix.
- 1,312
3
votes
Accepted
How to calculate the branch number of a linear mapping?
As explained in the answer to the question here
the branch number of a linear mapping
$$
A:F_q^n \rightarrow F_q^n, \quad x\mapsto A\cdot x
$$
is the minimum weight of the linear code generated by the ...
- 16.4k
3
votes
Accepted
Questions on LWE with a repeated secret matrix S
The distinguishing problem with a single sample $x$ is impossible.
This is because for any non-zero $x$ and any $u$ there exists an $S$ such that $Sx=u$.
ETA 20220405:
For the broader question of ...
- 10.5k
2
votes
Accepted
How to perform AES MixColumns as matrix multiplication in GF(2) (boolean values)?
Assume that we have to compute $M\times x$, where $M$ is a $n\times n$ matrix, and $x$ is a $n\times 1$ vector, all entries of $M$ and $x$ are in $GF(2^8)$.
We have:
$$
M\times x = M \times \left( \...
- 233
2
votes
Affine transformation in AES: Matrix representation
In literature there are 2 ways to show the affine transform for a given polynomial, and that depends on the location of the MSB in the input as a polynomial.
The polynomial representation of the full ...
- 12.7k
2
votes
Direct sum of Binary numbers In Mixcolumns
You misunderstand $(02) \cdot 10000100$; it is not integer multiplication (resulting in a 9 bit integer); instead, it is multiplication in $GF(2^8)$ (which results in an element in $GF(2^8)$, which ...
- 132k
2
votes
Accepted
Matrix Trapdoor AB+BA
How difficult is it to find $b$?
If the matrices within $R$ are of dimension $n \times n$, then we can express the equation $u = a \cdot b + b \cdot a$ as $n^2$ linear equations over the finite field ...
- 132k
2
votes
Accepted
How difficult is inverting a non-square matrix?
As far as I know, there is no well-behaved and canonical topology on finite fields that would enable a consistent and useful definition of pseudoinverse. The main point in computing pseudoinverses ...
- 16.4k
2
votes
Accepted
Found a mistake in a proof about when GGH will decrypt incorrectly
Okay, this was a really stupid mistake by me. I got confused because some sources use notation where $R$ and $B$ have the basis vectors as rows. However Goldreich, Goldwasser and Halevi have the basis ...
2
votes
Optimal MDS matrix - circulant or recursive?
my answer is extension to circulant and recursive.
one property measure to the optimal implementation of MDS matrix in cryptography is the cost of xor (number of xors required to fully implement the ...
- 1,990
2
votes
Accepted
UOV signature scheme, how does the affine transformation work? What does the composition of the core map and the affine map yield?
The secret polynomials are multivariate polynomials whose oil-oil terms have coefficient zero. You can represent it as a sum of terms, or as a vector-matrix-vector product. Take for example the ...
- 1,370
2
votes
Accepted
What is the time complexity of the basic components of a symmetric cipher?
I assume a cipher has a total time complexity. Where can I find the time complexities of a given cipher, especially DES, PRESENT and AES? And is there available time complexities per round of these ...
- 43.4k
2
votes
Simple question about the branch number of the matrix
Yes, its branch number is 2, which is the minimal possible branch number.
Note that every permutation matrix (that is, one element per row or column is one, all others are zero) has branch number 2.
- 334
2
votes
Simple question about the branch number of the matrix
Yes. This a degenerate matrix that provides no mixing and has minimal branch number.
- 16.4k
2
votes
Accepted
Problem while decrypting Hill cipher
These modular equations are not uniquely solvable:
$$\begin{bmatrix}7&2\\ 10& 20\end{bmatrix}, \begin{bmatrix}7&2\\ 23& 7\end{bmatrix}, \begin{bmatrix}20&15\\ 10& 20\end{...
- 3,772
Only top scored, non community-wiki answers of a minimum length are eligible