I have trouble understanding how Reed-Solomon coding can produce same number of output bits than the input was.

Twofish uses this technique. I've read the paper, but still can't quite understand how the flattening works. In my understanding, RS should add redundant bits, and the output must be larger than the input. What am I missing?

In addition, how is the MDS matrix constructed from RS coding? It seems that it was constructed using clever heuristics.


1 Answer 1


In crypto diffusion layer design the MDS matrix is usually used in the following form:

$$ X_{n+1}=M X_n,$$

where the actual codewords are $(X_n | X_{n+1}).$ So it's a rate $1/2$ MDS code. It need not be Reed Solomon, and optimisations with respect to speed and other considerations are made. This is done in Twofish as well.

In particular $X_n$ is made up of the 4 words that are the outputs of sboxes $(S_0,S_1,S_2,S_3)$ and $X_{n+1}$ is the result of multiplying this vector with the MDS matrix $M$.

See the answer to this question as well.

  • $\begingroup$ Would it be possible to illustrate this with an example? I'm still not quite seeing it. $\endgroup$
    – Sam_hai
    Jul 28, 2017 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.