Explanation on step $\rho$ of the SHA-3 algorithm

Question

I'm working on implementing SHA-3 in a PIC microcontroller.

In the block permutation, I don't quite understand step $\rho$:

Bitwise rotate each of the 25 words by a different triangular number 0, 1, 3, 6, 10, 15, …. To be precise, $a[0][0]$ is not rotated, and for all $0 \le t \le 24$, $a[i][j][k] = a[i][j][k−\frac{(t+1)(t+2)}{2}]$, where $${i \choose j} = \left(\begin{matrix}3&2\\1&0\end{matrix}\right)^t {0 \choose 1}$$

I understand the textual explanation and can write the needed code for that, if I assume that $i$ and $j$ are iterated like they form a 2-digit number in base 5, when the number equals $t$. I think that's what the formula below the text says, but I am not sure if this is so and if my assumption is correct.

I am familiar with the $n\choose{}m$ notation, but have never worked with matrices before. It came to my mind that $i\choose{}j$ and $0\choose1$ might be matrices as well instead of 'n choose m', like $\left(\begin{matrix}3&2\\1&0\end{matrix}\right)$ is.

Can someone explain the formula to me?

Answer 1

They are column vectors. This is an iterative formula. It means that:

• For $t=0$, you have $i=0$ and $j=1$.
• For $t=1$, you have $\left(\begin{matrix}3&2\\1&0\end{matrix}\right)\left(\begin{matrix}0\\1\end{matrix}\right) = \left(\begin{matrix}2\\0\end{matrix}\right)$ so $i=2$ and $j=0$.
• For $t=2$, you have $\left(\begin{matrix}3&2\\1&0\end{matrix}\right)^2\left(\begin{matrix}0\\1\end{matrix}\right) = \left(\begin{matrix}3&2\\1&0\end{matrix}\right)\left(\begin{matrix}2\\0\end{matrix}\right) =\left(\begin{matrix}6\\2\end{matrix}\right)$ so $i=6$ and $j=2$.
• And so on.

As you see above, if you iterate over $t$ then you don't have to implement the matrix power operation, since you can just multiply once - the matrix times the previous result vector.

You can look at the Wikipedia article Matrix multiplication for the general case, but for a 2x2 matrix multiplied by a 2x1 vector, the formula is $\left(\begin{matrix}a&b\\c&d\end{matrix}\right)\left(\begin{matrix}e\\f\end{matrix}\right) =\left(\begin{matrix}ae+bf\\ce+df\end{matrix}\right)$.

Edit: In fact, this is a mathematician's way to write the following code:

$i_{\text{new}} := 3i_{\text{prev}} + 2j_{\text{prev}}$

$j_{\text{new}} := i_{\text{prev}}$

Since you have only 25 different values of $t$, essentially you have constant values of $i$ and $j$ depending on the iteration. So, from the point of view of coding on a PIC, it might be faster to skip the matrix multiplication, and just calculate it (i.e. with a quick Python program) and write the constant lookup tables in your code. But maybe the above iterative formula is also fast. Up to you.