Revisions to How to find the AES branch number?

Commonmark migration

edited Jun 17, 2020 at 8:17

1

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

See the answer to this question for more.

Edit: The Singleton bound states that minimum distance is at least $n-k+1.$ Here $n=8, k=4.$ Such a code is MDS and proving MDS depends on the code structure. Look up MDS codes and Reed Solomon codes.

More concretely, a linear code is the nullspace of its parity check matrix. So if that matrix has all its collections of $d-1$ columns linearly independent (over $GF(2^8)$ here) then its minimum weight codeword must be $d$ or more. Moreover a code is MDS if and only if its dual is MDS so we can just consider the generator matrix and observe all collections of 4columns of $[A| I]$ are indeed linearly independent.So, $d\geq 5.$ But by singleton bound $d\leq 5.$ QED.

See the following link for more details:

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

See the answer to this question for more.

Edit: The Singleton bound states that minimum distance is at least $n-k+1.$ Here $n=8, k=4.$ Such a code is MDS and proving MDS depends on the code structure. Look up MDS codes and Reed Solomon codes.

More concretely, a linear code is the nullspace of its parity check matrix. So if that matrix has all its collections of $d-1$ columns linearly independent (over $GF(2^8)$ here) then its minimum weight codeword must be $d$ or more. Moreover a code is MDS if and only if its dual is MDS so we can just consider the generator matrix and observe all collections of 4columns of $[A| I]$ are indeed linearly independent.So, $d\geq 5.$ But by singleton bound $d\leq 5.$ QED.

See the following link for more details:

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

See the answer to this question for more.

Edit: The Singleton bound states that minimum distance is at least $n-k+1.$ Here $n=8, k=4.$ Such a code is MDS and proving MDS depends on the code structure. Look up MDS codes and Reed Solomon codes.

More concretely, a linear code is the nullspace of its parity check matrix. So if that matrix has all its collections of $d-1$ columns linearly independent (over $GF(2^8)$ here) then its minimum weight codeword must be $d$ or more. Moreover a code is MDS if and only if its dual is MDS so we can just consider the generator matrix and observe all collections of 4columns of $[A| I]$ are indeed linearly independent.So, $d\geq 5.$ But by singleton bound $d\leq 5.$ QED.

See the following link for more details:

replaced http://crypto.stackexchange.com/ with https://crypto.stackexchange.com/

Source Link

edited Apr 13, 2017 at 12:48

Community Bot

1

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

See the answer to this question this question for more.

Edit: The Singleton bound states that minimum distance is at least $n-k+1.$ Here $n=8, k=4.$ Such a code is MDS and proving MDS depends on the code structure. Look up MDS codes and Reed Solomon codes.

More concretely, a linear code is the nullspace of its parity check matrix. So if that matrix has all its collections of $d-1$ columns linearly independent (over $GF(2^8)$ here) then its minimum weight codeword must be $d$ or more. Moreover a code is MDS if and only if its dual is MDS so we can just consider the generator matrix and observe all collections of 4columns of $[A| I]$ are indeed linearly independent.So, $d\geq 5.$ But by singleton bound $d\leq 5.$ QED.

See the following link for more details:

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

See the answer to this question for more.

Edit: The Singleton bound states that minimum distance is at least $n-k+1.$ Here $n=8, k=4.$ Such a code is MDS and proving MDS depends on the code structure. Look up MDS codes and Reed Solomon codes.

More concretely, a linear code is the nullspace of its parity check matrix. So if that matrix has all its collections of $d-1$ columns linearly independent (over $GF(2^8)$ here) then its minimum weight codeword must be $d$ or more. Moreover a code is MDS if and only if its dual is MDS so we can just consider the generator matrix and observe all collections of 4columns of $[A| I]$ are indeed linearly independent.So, $d\geq 5.$ But by singleton bound $d\leq 5.$ QED.

See the following link for more details:

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

See the answer to this question for more.

Edit: The Singleton bound states that minimum distance is at least $n-k+1.$ Here $n=8, k=4.$ Such a code is MDS and proving MDS depends on the code structure. Look up MDS codes and Reed Solomon codes.

More concretely, a linear code is the nullspace of its parity check matrix. So if that matrix has all its collections of $d-1$ columns linearly independent (over $GF(2^8)$ here) then its minimum weight codeword must be $d$ or more. Moreover a code is MDS if and only if its dual is MDS so we can just consider the generator matrix and observe all collections of 4columns of $[A| I]$ are indeed linearly independent.So, $d\geq 5.$ But by singleton bound $d\leq 5.$ QED.

See the following link for more details:

Spelling

Source Link

edited Mar 21, 2017 at 2:37

kodlu

25.7k
2
31
69

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

See the answer to this question for more.

Edit: The Singleton bound states that minimum distance is at least $n-k+1.$ Here $n=8, k=4.$ Such a code is MDS and proving MDS depends on the code structure. Look up MDS codes and Reed Solomon codes.

More concretely, a linear code is the nullspace of its parity check matrix. So if that matrix has all its collections of $d-1$ columns linearly independent (over $Gf(2^8)$$GF(2^8)$ here) then its minimum weight codeword must be $d$ or more. Moreover a code is MDS if and only if its dual is MDS so we can just consider the generator matrix and observe all collections of 4columns of $[A| I]$ are indeed linearly independent.So, $d\geq 5.$ But by singleton bound $d\leq 5.$ QED.

See the following link for more details:

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

See the answer to this question for more.

Edit: The Singleton bound states that minimum distance is at least $n-k+1.$ Here $n=8, k=4.$ Such a code is MDS and proving MDS depends on the code structure. Look up MDS codes and Reed Solomon codes.

More concretely, a linear code is the nullspace of its parity check matrix. So if that matrix has all its collections of $d-1$ columns linearly independent (over $Gf(2^8)$ here) then its minimum weight codeword must be $d$ or more. Moreover a code is MDS if and only if its dual is MDS so we can just consider the generator matrix and observe all collections of 4columns of $[A| I]$ are indeed linearly independent.So, $d\geq 5.$ But by singleton bound $d\leq 5.$ QED.

See the following link for more details:

The AES MixColumns operator ensures that the 8 bytes (4 in the input column 4 in the output column) form the codewords of an MDS code over $GF(2^8)$, which means the minimum weight of the code, which is 5, equals the number of nonzero bytes.

Any nonzer byte contributes 1 to the minimum weight, by definition of Hamming Weight over $GF(2^8)$. A nonzero symbol has weight 1, regardless of how many bits of the eight is nonzero.

See the answer to this question for more.

Edit: The Singleton bound states that minimum distance is at least $n-k+1.$ Here $n=8, k=4.$ Such a code is MDS and proving MDS depends on the code structure. Look up MDS codes and Reed Solomon codes.

More concretely, a linear code is the nullspace of its parity check matrix. So if that matrix has all its collections of $d-1$ columns linearly independent (over $GF(2^8)$ here) then its minimum weight codeword must be $d$ or more. Moreover a code is MDS if and only if its dual is MDS so we can just consider the generator matrix and observe all collections of 4columns of $[A| I]$ are indeed linearly independent.So, $d\geq 5.$ But by singleton bound $d\leq 5.$ QED.

See the following link for more details: