11
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 that for an n-bit Montgomery curve, multiplying a point with an n-bit scalar, you will need to compute about 10n multiplications of field elements. In more ...
7
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, higher order bits do not affect lower order ones), and while you could get around these issues, it would require significant changes to AES.
You could do the ...
7
One observation is that if we modify the problem so that $M, A, B$ are random invertible matrices, then it is easy to prove the security of the system. In fact, we can prove that the system is informationally secure; that is, for any observed $C_1, C_2$ pair, for any possible value of $K$, there is a unique set of values of $A, B, M$ that yield that $K$ (...
6
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 128-bit AES blocks in parallel, using eight 128-bit XMM registers to store them. They're not doing basic "naïve bitslicing", which would involve using 128 $n$-...
6
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 branch number, which is the minimum weight of the corresponding linear code is 4, in $GF(2^n)$ for all $n$. This covers all possible fields of interest for ...
5
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) Matrix:
First definition: A matrix $M$ of order $n$ is an MDS matrix if and only if every sub-matrix of $M$ is non-singular.
Second definition: A matrix $M_{n\...
4
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 active Sboxes, i.e., the minimum branch number across 2 rounds is $9,$ the minimum weight of the MDS code.
MDS codes have a fully known weight distribution, so ...
4
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 multiply by 2 and add the input.
Those two multiplications can be described with 8x8 binary matrices. The easiest way to find the matrices is to think how those ...
4
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$ which means $n=km$ for some integer $m$.
Now Let $\bf A$ be $km \times km$ binary matrix. The first step is that to consider the matrix $\bf A$ as a block ...
3
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 formal value $\alpha$ which is not in $\mathbb{F}_{256}$, but is such that $\alpha^4+1 = 0$. You can add and multiply such elements, always keeping the result in ...
3
Here is a Sage code that creates the MDS matrix over $F_2$.
mds = matrix(GF(2), [
[0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0],
[0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0],
[0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0],
[1,0,0,0,1,0,0,0,1,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,...
3
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
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 almost-MDS matrix. So its branch number is $n$. Using above theorem we have
$$n \leq \frac{2n+4}{3} $$
So $n=2,3$ or $4$.
The size of matrix is a tool for ...
3
You would need (at least) 3 pairs of vectors in order to determine the 3*3 matrix.
3
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 way. There are simply too many ways of implementing each component in hardware and software on multiple platforms, and they do not always obey the rules of big-...
3
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 matrix
$$
G=[~I~|~A].
$$
For an arbitrary matrix $A$ this problem is NP hard, i.e., very hard. For structured matrices like the MDS matrix in AES the answer is ...
2
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( \begin{matrix} x_0 \\ x_1 \\ \vdots \\x_{n-1}\end{matrix}\right)
= M \times \left( \begin{matrix} x_0 \\ 0\\ \vdots \\ 0\end{matrix}\right)
\oplus M \times \...
2
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 transformation, in the format of the original Rijndael paper, is:
$b(x) = a(x)(x^7 + x^6 + x^5 + x^4 + 1) + (x^7 + x^6 + x^2 + x) ~~mod~~ x^8 + 1$
Where $a(x)...
2
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 can be represented in 8 bits).
AES uses a polynomial representation of $GF(2^8)$, using the polynomial $x^8 + x^4 + x^3 + x + 1$; what this means is that ...
2
Let $k=\left(\begin{array}{cc}k_0 & k_1\\k_2 & k_3\end{array}\right)$ be the key. And I'll assume the transformation $a=0$, $b=1$, and so on.
So you know $k\left(\begin{array}{c}0\\1\end{array}\right)=\left(\begin{array}{c}c_0\\c_1\end{array}\right)$ where you know $c_0$ and $c_1$.
Thus $c_0=0k_0+1k_1$ and $c_1=0k_2+1k_3$. So that is two equations, ...
2
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 the matrices are over; a simple minded Gaussian Elimination would recover $b$ in $O(n^6)$ steps.
If $u$ is specified explicitly in the public key or the ...
2
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 over the complex or real field is that they minimize some second moment error functional, since there is no unique inverse defined.
However, and I may regret this,...
2
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 vectors as columns so
$$B=RU\implies U=R^{-1}B.$$ Hence the matrix is unimodular and the proof works. Sorry about the inconvience.
2
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 MDS matrix ) , depth (number of stages) and the field size (usually 4 or 8 )
according to this paper MDS Matrices with Lightweight Circuits, the native ...
2
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 polynomial of your example, $F_0(x_0, \ldots, x_5) = x^2_0 − 4x_0x_1 − 4x^2_1 + 8x_0x_2 + 11x_2^2 − 2x_0x_3 − x_1x_3 + 9x_2x_3 + 12x^2_3 + 7x_0x_4 − 11x_1x_4 − ...
2
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.
2
Yes. This a degenerate matrix that provides no mixing and has minimal branch number.
2
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)$, because all those bits can be processed in parallel. In some models the answer can even depend on the relationship between the number of bits being XORed and the ...
2
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{bmatrix}, \begin{bmatrix}20&15\\ 23& 7\end{bmatrix}$$
are all the $2 \times 2$ matrices over $\mathbb{Z}_{26}$ would transform 'monday' to IKTIWM, the ...
Only top voted, non community-wiki answers of a minimum length are eligible