5
$\begingroup$

Recently, when I studied the permutation cipher, I saw a matrices structure which is same as permutation cipher. This method was so simple and interesting for me.

Let $m$ be $n$-bit plain text and $P=[p_1,...,p_n]$ be the permutation secret key such that $P(m_i)=m_{p_i}$.

For example, let $m=5={(101)}_2$ and $P=[2,1,3]$. So $P(5)={(011)}_2=3$. In mathematical points of view, we can do this method with matrices multiplication as fallow:

$P(m)=\left(\begin{array}{ccc}m_1&m_2&m_3\end{array}\right)\cdot\left(\begin{array}{ccc}0&1&0\\1&0&0\\0&0&1\end{array}\right)=\left(\begin{array}{ccc}m_2&m_1&m_3\end{array}\right).$

In general case, instead of using $P$ as $1\times n$ vector, we can use $n\times n$ matrices with $0,1$ elements, such that there exist only one $1$ in each column( in the position $p_i$).

This equivalent presentation make analysis and attacks so easier. Is there exist similar mathematical method for substitution cipher?

$\endgroup$
4
$\begingroup$

Well, at least two representations come to my mind, but I'm afraid you will not find them too useful. In general, S-boxes are designed with the goal in mind that such "mathematical" representations do not help in exposing any more structure than just writing down the table does.

  • If we are talking about bit strings, i.e., an S-box $S\colon\{0,1\}^n\to\{0,1\}^n$, we can interpret $\{0,1\}^n$ as a finite field $\mathbb F_{2^n}$. Over any field, polynomial interpolation works, thus there exists a unique polynomial of degree at most $2^n$ over $\mathbb F_{2^n}$ that describes the substitution $S$.
  • Similarly to your permutation matrix example, any map $f\colon A\to B$ of finite sets can be written as a matrix: Let $A=\{a_1,\dots,a_n\}$ and $B=\{b_1,\dots,b_m\}$ (note this fixes an order on the sets), and define $F$ to be the binary $m\times n$ matrix which has $1$ in the entry labelled $i,j$ and only if $f(a_i)=b_j$. Then $F$ applied to the $i$th unit vector gives back the $j$th unit vector, where $b_j=f(a_i)$.

Note how both representations have size exponential in the bit length of the input.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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