Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
I wish I could give you an extra +1 for the link with writing code ;) thanks a lot, this is a very clear explanation! –  Camil Staps Apr 19 '13 at 8:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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