Algebraic properties of the operations used in block cipher idea

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Uygulamalı Matematik Enstitüsü, Türkiye

Tezin Onay Tarihi: 2007

Öğrenci: HAMDİ MURAT YILDIRIM

Danışman: ERSAN AKYILDIZ

Özet:

In this thesis we obtain several interesting algebraic properties of the operations used in the block cipher IDEA which are important for cryptographic analyzes. We view each of these operations as a function from $\mathbb Z_{2}^n \times \mathbb Z_{2}^n \to \mathbb Z_{2}^n$. By fixing one of variables $v(z)=\mathbf Z$ in $\mathbb Z_{2}^n \times \mathbb Z_{2}^n$, we define functions $\mathbf {f}_z$ and $\mathbf {g}_z$ from $\mathbb Z_{2}^n$ to $\mathbb Z_{2}^n$ for the addition $\BIGboxplus$ and the multiplication $\BIGodot$ operations, respectively. We first show that the nonlinearity of $\mathbf {g}_z$ remains the same under some transformations of $z$. We give an upper bound for the nonlinearity of $\mathbf {g}_{2^k}$, where $2\leq k < n-1$. We list all linear relations which make the nonlinearity of $\mathbf {f}_z$ and $\mathbf {g}_z$ zero and furthermore, we present all linear relations for $\mathbf {g}_z$ having a high probability. We use these linear relations to derive many more linear relations for 1-round IDEA. We also devise also a new algorithm to find a set of new linear relations for 1-round IDEA based on known linear relations. Moreover, we extend the largest known linear class of weak keys with cardinality $2^{23}$ to two classes with cardinality $2^{24}$ and $2^{27}$. Finally, we obtain several interesting properties of the set $ \{ ({\mathbf X},{\mathbf X} \BIGoplus {\mathbf A}) \in \mathbb Z_2^n \times \mathbb Z_2^n \,I\, (\mathbf {X}\BJoin {\mathbf Z})\BIGoplus( ({\mathbf X} \BIGoplus {\mathbf A} ) \BJoin \mathbf {Z} ) = {\mathbf B} \}$ for varying ${\mathbf A}, {\mathbf B}$ and ${\mathbf Z}$ in $\mathbb Z_2^n$, where $\BJoin \in \{ \BIGodot,\BIGboxplus \}$. By using some of these properties, we present impossible differentials for 1-round IDEA and Pseudo-Hadamard Transform.