Zodiac密码算法的多维零相关线性分析

程 璐，魏悦川，潘晓中，李安辉

(1.武警工程大学 电子技术系,西安 710086; 2.网络与信息安全武警部队重点实验室,西安 710086)

Zodiac密码算法的多维零相关线性分析

程 璐1,2*，魏悦川1,2，潘晓中1,2，李安辉1,2

(1.武警工程大学 电子技术系,西安 710086; 2.网络与信息安全武警部队重点实验室,西安 710086)

(*通信作者电子邮箱18302972151@163.com)

分组密码算法Zodiac支持3种密钥长度，分别为Zodiac-128、Zodiac-192、Zodiac-256。利用零相关线性分析方法评估了Zodiac算法的安全性，首先根据算法的结构特性，构造了一些关于Zodiac算法的10轮零相关线性逼近，然后对16轮Zodiac-192进行了多维零相关分析。分析结果显示：攻击过程中一共恢复了19个字节的密钥，其数据复杂度约为2124.40个明密文对，计算复杂度为2181.58次16轮加密。由此可得：16轮(即全轮)192 bit密钥的Zodiac算法(Zodiac-192)对于零相关线性分析方法是不安全的。

分组密码；Zodiac密码算法；线性掩码；线性逼近；零相关线性分析

0 引言

Zodiac是分组密码算法的代表之一，由韩国专家Lee等[1]于2000年为韩国公司SoftForum所设计。Zodiac算法是典型的Feistel结构，共有16轮迭代。其明文分组长度为128 bit，密钥长度有三种128 bit、192 bit、256 bit，分别可记作Zodiac-128、Zodiac-192、Zodiac-256[12]。目前针对Zodiac的分析有不可能差分分析、积分分析和中间相遇分析等。

目前对Zodiac最好的分析结果是不可能差分分析， Shakiba等[2]利用2个13轮的不可能差分，攻击全轮Zodiac算法，时间复杂度为271.3次全轮加密，数据复杂度为271.28个选择明文；张鹏等[3]利用Zodiac的等价结构找到了两个新的9轮Square区分器，利用新的区分器攻击了全轮Zodiac，其时间复杂度为2189.5次全轮加密，数据复杂度为212.6个选择明文；孙兵等[4]构造了一个16轮的不可能差分以及一个9轮的积分区分器，并在此区分器前面增加1轮，后面增加6轮，实现对全轮Zodiac算法的积分攻击，其时间复杂度为2190次全轮加密，数据复杂度为216个选择明文；……