一种新的实用安全加密标准算法——Camellia算法

摘要：介绍了ＮＥＳＳＩＥ标准中的分组密码算法——Ｃａｍｅｌｌｉａ算法的加、解密过程，并对其在各种软、硬件平台上的性能进行了比较，结果表明Ｃａｍｅｌｌｉａ算法在各种平台上均有着较高的效率。Ｃａｍｅｌｌｉａ算法与其它技术相结合将在信息安全领域产生更广泛的应用。 关键词：ＮＥＳＳＩＥ 分组密码 Camellia 算法 加密 继２０００年１０月美国推出二十一世纪高级数据加密标准ＡＥＳ后，２００３年２月欧洲最新一代的安全标准ＮＥＳＳＩＥ（Ｎｅｗ Ｅｕｒｏｐｅａｎ Ｓｃｈｅｍｅｓ ｆｏｒ Ｓｉｇｎａｔｕｒｅｓ、Ｉｎｔｅｇｒｉｔｙ ａｎｄ Ｅｎｃｒｙｐｔｉｏｎ）出台。ＮＥＳＳＩＥ是欧洲ＩＳＴ（Ｉｎｆｏｒｍａｔｉｏｎ Ｓｏｃｉｅｔｙ Ｔｅｃｈｎｏｌｏｇｉｅｓ）委员会计划的一个项目。Ｃａｍｅｌｌｉａ算法以其在各种软件和硬件平台上的高效率这一显著特点成为ＮＥＳＳＩＥ标准中两个１２８比特分组密码算法之一（另一个为美国的ＡＥＳ算法）。 Ｃａｍｅｌｌｉａ算法由ＮＴＴ和Ｍｉｔｓｕｂｉｓｈｉ Ｅｌｅｃｔｒｉｃ Ｃｏｒｐｏｒａｔｉｏｎ联合开发。作为欧洲新一代的加密标准，它具有较强的安全性，能够抵抗差分和线性密码分析等已知的攻击。与ＡＥＳ算法相比，Ｃａｍｅｌｌｉａ算法在各种软硬件平台上表现出与之相当的加密速度。除了在各种软件和硬件平台上的高效性这一显著特点，它的另外一个特点是针对小规模硬件平台的设计。整个算法的硬件执行过程包括加密、解密和密钥扩展三部分，只需占用８．１２Ｋ ０．１８μｍ ＣＯＭＳ工艺ＡＳＩＣ的库门逻辑。这在现有１２８比特分组密码中是最小的。 １ Ｃａｍｅｌｌｉａ算法的组成 Ｃａｍｅｌｌｉａ算法支持１２８比特的分组长度，１２８、１９２和２５６比特的密钥与ＡＥＳ的接口相同。本文以１２８比特密钥为例对Ｃａｍｅｌｌｉａ算法进行详细介绍。 Ｃａｍｅｌｌｉａ算法１２８比特密钥的加、解密过程共有１８轮，采用Ｆｅｉｓｔｅｌ结构，加、解密过程完全相同，只是子密钥注入顺序相反。而且密钥扩展过程和加、解密过程使用相同的部件。这使得Ｃａｍｅｌｌｉａ算法不论是在软件平台还是硬件平台只需更小的规模和更小的存储即可。 （１）Ｃａｍｅｌｌｉａ算法所采用的符号列表及其含义 Ｂ ８比特向量 Ｗ ３２比特向量 Ｌ ６４比特向量 Ｑ １２８比特向量 ｘｎ 比特向量 ｘＬ 向量ｘ的左半部分 ｘＲ 向量ｘ的右半部分 ＜＜＜ 比特循环左移 ｜｜ 两个操作数的连接  比特的异或操作 ｘ 比特位取补操作 ∪ 比特位的或操作 ∩ 比特位的与操作 （２）Ｃａｍｅｌｌｉａ算法所采用的变量列表及其含义 Ｍ１２８ １２８比特明文组 Ｃ１２８ １２８比特密文组 Ｋ 主密钥 ｋｗｔ６４ ｋｕ６４ ｋｌｖ６４ 子密钥 （３）Ｃａｍｅｌｌｉａ算法所采用的变换函数 %26;#183;Ｆ变换 Ｆ变换（见式（１））是Ｃａｍｅｌｌｉａ算法中最主要的部件之一，而且Ｆ变换被加、解密过程和密钥扩展过程所共用（１２８比特密钥的加、解密各用１８次，密钥扩展用４次）。Ｃａｍｅｌｌｉａ算法的Ｆ变换在设计时采用１轮的ＳＰＮ（Ｓｕｂｓｔｉｔｕｔｉｏｎ Ｐｅｒｍｕｔａｔｉｏｎ Ｎｅｔｗｏｒｋ），包括一个Ｐ变换（线性）和一个Ｓ变换（非线性）。在Ｆｅｉｓｔｅｌ型密码使用一轮ＳＰＮ作轮函数时，对更高阶的差分和线性特性概率的理论评估变得更加复杂，在相同安全水平下的运行速度有所提高。 %26;#183;Ｐ变换 Ｃａｍｅｌｌｉａ算法的Ｐ变换（见式（２））是一个线性变换。为了通信中软、硬件实现的高效性，它适合采用异或运算，并且其安全性能足以抵抗差分和线性密码分析。其在３２位处理器、高端智能卡上的应用，跟在８位处理器上一样。 %26;#183;Ｓ变换 Ｃａｍｅｌｌｉａ算法采用的Ｓ盒（见式（３））是一个ＧＦ（２８）上的可逆变换，它加强了算法的安全性并且适用于小硬件设计。众所周知，ＧＦ（２８）上函数的最大差分概率的最小值被证明为２－６，最大线性概率的最小值推测为２－６。Ｃａｍｅｌｌｉａ算法选择ＧＦ（２８）上能够获得最好的差分和线性概率的可逆函数作Ｓ盒，而且Ｓ盒每个输出比特具有高阶布尔多项式，使得对Ｃａｍｅｌｌｉａ进行高阶差分攻击是困难的。Ｓ盒在ＧＦ（２８）上输入、输出相关函数上的复杂表达式，使得插入攻击对Ｃａｍｅｌｌｉａ无效。 Ｓ：Ｌ→Ｌ (l"1(8),l"1(8),l"1(8),l"1(8),l"1(8),l"1(8),l"1(8),l"1(8)→ *s1(l"1(8)),s2(l"2(8)),s3(l"3(8)),s4("4(8)),s2(l"5(8)),s3(l"6(8)), s4(l"7(8),s1(l"8(l8(8))) 其中， ｓ２:ｙ(８)＝ｓ1(x(8))=h(g(f(0xC5+x(8))))+0x6E s２:Y(８)＝ｓ2(ｘ(８))=s1(x(8))＜＜＜１ (３) ｓ３:ｙ(８)＝ｓ３(ｘ(８))＝ｓ１(ｘ(８))＞＞＞１ ｓ４:ｙ(８)＝ｓ４(ｘ(８))＝ｓ１(ｘ(８))＜＜＜１ 算法中构造了四个不同的Ｓ盒，提高了Ｃａｍｅｌｌｉａ算法抵抗阶段差分攻击的安全性。为了在小硬件上设计实现，ＧＦ（２８）上的元素可以表示成系数为ＧＦ（２４）上的多项式。这样，在实现Ｓ盒时，只需运用子域ＧＦ（２４）上很少的操作。ｓ１变换中所采用的ｆ、ｈ、ｇ函数分别如（４）、（５）、（６）式所示。 (ｂ１,ｂ２,ｂ３,ｂ４,ｂ５,ｂ６,ｂ７,ｂ８)＝ｇ(ａ１,ａ２,ａ３,ａ４,ａ５,ａ６,ａ７,ａ８) 其中,(ｂ８＋ｂ７α＋ｂ６α２＋ｂ５α３)＋(ｂ４＋ｂ３α＋ｂ２α２＋ｂ１α３)β ＝１／（(ａ８＋ａ７α＋ａ６α２＋ａ５α３)＋(ａ４＋ａ３α＋ａ２α２＋ａ１α３)）(６) 规定（６）式中ＧＦ(２的８次方)上运算＝1/０，β是ＧＦ（２的８次方）上方程ｘ８＋ｘ６＋ｘ５＋ｘ３＋１＝０的根，ａ＝β２３８＝β６＋β５＋β３＋β２是ＧＦ（２的４次方）上方程ｘ４＋ｘ＋１＝０的根。当然根据性能要求，在具体实现加密算法时，Ｓ盒的实现电路也可以直接查表的方式进行。 %26;#183;ＦＬ／ＦＬ－１变换 Ｃａｍｅｌｌｉａ算法每六圈加入一次ＦＬ／ＦＬ－１变换，用来打乱整个算法的规律性。加入ＦＬ／ＦＬ－１变换的另一个好处是可以抵抗未知的密码攻击方法，而且加入ＦＬ／ＦＬ－１变换并不影响Ｆｅｉｓｔｅｌ结构加、解密过程相同。 ＦＬ：Ｌ%26;#215;Ｌ→Ｌ （ＸＬ（３２）｜｜ＸＲ（３２），ｋｌＬ（３２）｜｜ｋｌＲ（３２）→（７） （ＹＲ（３２）∪ｋｌＲ（３２），ＹＬ（３２）｜｜（（ＸＬ（３２）∩ｋｌＬ（３2）＜＜＜１）+ＹＲ（３２） ＦＬ－１：Ｌ%26;#215;Ｌ→Ｌ （ＹＬ（３２）｜｜ＹＲ（３２），ｋｌＬ（３２）｜｜ｋｌＲ（３２）→ （８） （ＹＲ（３２）∪ｋｌＲ（３２），ＹＬ（３２）｜｜（（ＸＬ（３２）∩ｋｌＬ（３２）＜＜＜１）+ＹＲ（３２） ２ Ｃａｍｅｌｌｉａ算法的加、解密及密钥扩展实现过程 （１）加、解密过程 Ｃａｍｅｌｌｉａ算法的整个加密过程有１８轮Ｆｅｉｓｔｅｌ结构，在第６轮和第１２轮之后加入了ＦＬ／ＦＬ－１变换层，用来打乱算法的规律性，并且在第１轮之前和最后１轮之后使用了１２８比特的异或操作。解密过程与加密过程完全相同，只是圈密钥注入顺序与加密相反。１２８比特密钥Ｃａｍｅｌｌｉａ算法的加密过程如图１所示。 （２）密钥扩展 Ｃａｍｅｌｌｉａ算法的密钥扩展遵循了严格的设计准则，如实现简单且与加、解密过程共用部件，密钥配置时间小于加密时间，支持在线密钥生成，没有等效密钥，能够抵抗相关密钥攻击和滑动攻击等。整个过程只需通过三个中间变量，ＫＬ（１２８）＝Ｋ（１２８），Ｋ（１２８）＝０ＫＡ的简单移位即可得到子密钥ｋｗｔ（６４）（ｔ＝１，…，４），ｋｕ（６４）（ｕ＝１，…，１８）和ｋｌｖ（６４）（ｖ＝１，…，４），且中间生成过程与加密过程共用了部件Ｆ（如图１、２所示）。 ３ Ｃａｍｅｌｌｉａ算法的安全性 设计者用差分扩散概率和线性相关概率的保守上界证明了任何含ＳＰＮ网络的十六圈Ｃａｍｅｌｌｉａ密码对差分密码分析和线性密码分析都是安全的；此外，通过对活动Ｓ盒的计数说明十二圈Ｃａｍｅｌｌｉａ中没有概率大于２－１２８的差分特征和线性特征；带或不带ＦＬ层的十圈Ｃａｍｅｌｌｉａ都具有伪随机置换特性，能够抵抗截断差分攻击和线性密码分析；设计者还声称Ｃａｍｅｌｌｉａ能够抵抗不可能差分攻击、Ｂｏｏｍｅｒａｎｇ攻击、高阶差分攻击、相关密钥攻击、插入攻击、Ｓｌｉｄｅ攻击、线性和攻击及Ｓｑｕａｒｅ攻击。在密钥的安全性上，一方面不存在等效密钥；另一方面，子密钥来自主密钥的加密结果ＫＡ和ＫＢ，改变主密钥并不能获得预想的ＫＡ和ＫＢ，反之亦然，因而无法控制和预测子密钥之间的关系，从而相关密钥攻击难以成功。由于密钥长度不少于１２８比特，以当前的计算能力还无法对Ｃａｍｅｌｌｉａ成功实施诸如密钥穷举搜索攻击、时间存储权衡攻击、字典攻击和密钥匹配等类型的强力攻击。 ４ Ｃａｍｅｌｌｉａ算法在各种平台上的性能比较 评测一个分组密码的好坏，除了要求其具有高的安全性外，还要求算法在应用平台上实现简单。Ｃａｍｅｌｌｉａ算法在设计时充分考虑到了这一点，下面给出其在各种平台上的性能参数。评测算法在软件平台上实现性能时，首要考虑其速度，其次还要看算法实现时所需的存储空间，表１前半部分给出了Ｃａｍｅｌｌｉａ算法在常用的３２位处理器上各种软件平台的实现性能。高的加密速度和低的存储需求，表明Ｃａｍｅｌｌｉａ算法可以有效地应用于各种软件系统中。从表１后半部分可以看出Ｃａｍｅｌｌｉａ算法在高端和低端的智能卡平台上同样有着良好的性能；由于Ｃａｍｅｌｌｉａ算法的密钥扩展与加、解密过程有共用部分，所以其硬件平台所需的芯片面积大大减少，降低了硬件成本，便于推广应用，详细参数见表２。 表1 Camellia算法在软件和智能卡平台上的性能 环 境 语 言 速度加、解密 RAM合计 ROM合计 PIII700MHz128MB256 L2-cache Assembly 241.5Mbps 64bytes 11420bytes PII300MHz160MB512 L2-cache VC++6 66.6Mbps 108bytes 9461bytes PIII 1GHz512MB256 L2-cache Java 161.4Mbps \ \ Intel 8051 12MHz Assembly 10217 10.22msec 32bytes 990bytes Z80 5MHz Assembly 35951 7.19msec 106bytes 1698bytes MC68HC705 B16 2.1MHz Assembly 9900 4.71msec 208bytes \ 表2 Camellia算法在硬件平台上的性能 环 境 设计Lab 速度 芯片面积 加、解密 单元 合计 ASIC Unrolled Mitsubishi0.18μm 2785.00Mbps Kgate 244.90 Loop Mitsubishi0.18μm 1881.25Mbps Kgate 44.30 FPGA Unrolled Xilinx VirtexE 401.89Mbps Slice 9426 Loop Xilinx VirtexE 227.42Mbps Slice 1780 从本文可以看出，分组密码加密算法发展到今天，不论是从安全性还是从实用性的角度都越来越强。ＮＥＳＳＩＥ标准中的Ｃａｍｅｌｌｉａ加密算法充分考虑到了各种因素，既保证了算法的安全性又考虑到其在各种平台上的实现效率，尤其是针对小硬件的设计思想，使其有着广泛的应用前景。