1~5轮LBlock的多项式表示及完全性分析

1~5轮LBlock 的多项式多项式表示表示表示及完全性分析及完全性分析

彭昌勇1,2，祝跃飞1，顾纯祥1，米顺强3

(1. 解放军信息工程大学信息工程学院，郑州 450002；2. 解放军信息工程大学理学院，郑州 450001；

3. 解放军95833部队，北京 100092)

摘 要：用统计测试方法分析密码算法的完全性存在误差。为此，利用符号计算软件Mathematica 7.0，以明文和密钥比特为自变量，得到LBlock 分组密码第1轮~第5轮输出的多项式表达式，结果显示，LBlock 第5轮输出的任何比特至多与45个明文比特、49个密钥比特有关，说明5轮LBlock 还未达到完全性。

关键词关键词：：完全性；分组密码；LBlock 密码；多项式表示；符号计算；Mathematica 软件

Polynomial Expression and Completeness Analysis

of 1~5 Round LBlock

PENG Chang-yong 1,2, ZHU Yue-fei 1, GU Chun-xiang 1, MI Shun-qiang 3

(1. Institute of Information Engineering, PLA Information Engineering University, Zhengzhou 450002, China;

2. School of Science, PLA Information Engineering University, Zhengzhou 450001, China;

3. 95833 PLA Troops, Beijing 100092, China)

【Abstract 】There are errors in analyzing the completeness of a cryptographic algorithm by statistical testing method. By using the symbolic computation software Mathematica 7.0, the polynomial expressions(in terms of the plaintext bits and key bits) of the output of 1~5 round of the block cipher LBlock are obtained. The result shows that any bit of the output of the 5th round of LBlock depends on at most 45 plaintext bits and 49 key bits, which means that 5-round LBlock is not complete.

【Key words 】completeness; block cipher; LBlock cipher; polynomial expression; symbolic computation; Mathematica DOI: 10.3969/j.issn.1000-3428.2012.09.047

计 算 机 工 程 Computer Engineering 第38卷 第9期 V ol.38 No.9 2012年5月

May 2012

·安全技术安全技术·· 文章编号文章编号：：1000—3428(2012)09—0155—03 文献标识码文献标识码：：A

中图分类号中图分类号：：TP309.2

1 概述

轻量级分组密码由于在无线射频识别(Radio Frequency Identification, RFID)的电子标签、传感器网络等受限环境下有重要应用，因此是目前分组密码的一个热点研究领域[1-4]。轻量级分组密码从其设计上还是采用与传统分组密码类似的迭代结构，即将明文用简单的轮函数在轮密钥的作用下进行多次迭代，最终得到密文。轮密钥通过密钥调度算法由主密钥生成。分组密码根据其迭代结构的不同，主要分为Feistel 结构和SPN(Substitution Permutation Network)。前者的典型代表是美国的数据加密算法(Data Encryption Algorithm, DES)，后者的典型代表是美国的高级加密标准(Advanced Encryption Standard, AES)。LBlock 分组密码[1]是我国学者提出的一种 32轮、分组长度为64比特、主密钥为80比特的类Feistel 结构的轻量级分组密码。

完全性是密码算法一个非常重要的属性，由文献[5-6]分别给出。完全性是指加密函数输出的每一比特都与所有输入比特有关。衡量一个算法的完全性通常是用统计测试的方 法[7]，但统计测试总是有误差的。因此，本文通过用符号计算直接给出第1轮~第5轮LBlock 的数学表达式，从而更直接地分析算法完全性。

2 LBlock 算法描述

2.1 加密过程

LBlock 是分组长度为64比特、密钥长度为80比特、加密轮数为32轮的变体Feistel 结构的分组密码。设M =X 1||X 0

表示64比特明文，则加密过程如下：

(1)对于i = 2, 3,…, 33，执行： 111(,)(8)i i i i X F X K X ???=⊕<<< 其中，<<<8

表示左循环移8位。

(2)输出密文C =X 32||X 33。

[1]⊕

图1 LBlock 加密结构

基金项目基金项目：：郑州市科技创新团队基金资助项目(10CXTD150) 作者简介作者简介：：彭昌勇(1974－)，男，博士研究生，主研方向：分组密码；祝跃飞，教授、博士；顾纯祥，副教授、博士；米顺强，助理研 究员

收稿日期收稿日期：：2011-02-10 E-mail ：pengchangyong@9a372b475727a5e9856a61f6

156 计 算 机 工 程 2012年5月5日

轮函数F 定义如下：

32(,)(()){0,1}i i F X K P S X K =⊕∈

其中，32,{0,1}i X K ∈；S 和P 表示混淆和扩散函数。

混淆函数定义如下：

3232:{0,1}{0,1}S →

7654321076543210||||||||||||||||||||||||||||Y Y Y Y Y Y Y Y Y Z Z Z Z Z Z Z Z Z =→

=

777666555444333222111000()()()()()()()()

Z s Y Z s Y Z s Y Z s Y Z s Y Z s Y Z s Y Z s Y ========

混淆函数S 中的每个i s 是4比特的S 盒，如图2所示。

s 0 14, 9, 15, 0, 13, 4, 10, 11, 1, 2, 8, 3, 7, 6, 12, 5 s 1 4, 11, 14, 9, 15, 13, 0, 10, 7, 12, 5, 6, 2, 8, 1, 3 s 2 1, 14, 7, 12, 15, 13, 0, 6, 11, 5, 9, 3, 2, 4, 8, 10 s 3 7, 6, 8, 11, 0, 15, 3, 14, 9, 10, 12, 13, 5, 2, 4, 1 s 4 14, 5, 15, 0, 7, 2, 12, 13, 1, 8, 4, 9, 11, 10, 6, 3 s 5 2, 13, 11, 12, 15, 14, 0, 9, 7, 10, 6, 3, 1, 8, 4, 5 s 6 11, 9, 4, 14, 0, 15, 10, 13, 6, 12, 5, 7, 3, 8, 1, 2 s 7 13, 10, 15, 0, 14, 4, 9, 11, 2, 1, 8, 3, 7, 5, 12, 6 s 8 8, 7, 14, 5, 15, 13, 0, 6, 11, 12, 9, 10, 2, 4, 1, 3 s 9

11, 5, 15, 0, 7, 2, 9, 13, 4, 8, 1, 12, 14, 10, 3, 6

图2 LBlock 的S 盒

扩散函数定义如下：

3232:{0,1}{0,1}P →

7654321076543210||||||||||||||||||||||||||||Z Z Z Z Z Z Z Z Z U U U U U U U U U =→=

7664574532201301

U Z U Z U Z U Z U Z U Z U Z U Z ========

[1]⊕

图3 LBlock 轮函数F 的结构

2.2 密钥调度

密钥调度算法输入80比特主密钥，输出32个32比特长的轮子密钥。初始时，80比特主密钥存储于密钥寄存器K 中，

记为：

79780K k k k =?

其中，0k 表示最低位，本文统一用该约定，即一个二进制串的最右边比特表示其最低位。

算法步骤具体如下：

(1)输出K 的最左边32比特作为轮子密钥K 1。 (2)对于 i =1,2,…,31,执行： 1)K <<< 29

2)[k 79 k 78 k 77 k 76] = s 9[k 79 k 78 k 77 k 76] [k 75 k 74 k 73 k 72] = s 8[k 75 k 74 k 73 k 72] 其中，s 9是和s 8图2中的S 盒。

3)[k 50 k 49 k 48 k 47]=[ k 50 k 49 k 48 k 47]⊕[i ]2 其中，[i ]2是i 的二进制表示。

4)输出K 当前内容的最左边32比特作为轮子密钥K i +1。

3 5轮LBlock 的多项式表示

本文利用符号计算数学软件Mathematica7.0给出LBlock 第1轮~第5轮每个输出比特的多项式表达式(以明文比特和主密钥比特为自变量)。基本思路如下：首先给出LBlock 的非线性组件S 盒的代数表达式。然后给出轮子密钥的代数表达式。有了这些表达式后，可以直接用Mathematica 编出LBlock 的纯符号加密程序，其程序流程和用C 语言编写LBlock 的加密程序一样，所不同的是，可以将每个明文比特和主密钥比特都用纯符号代入，进行运算。最终得到第1轮~第5轮LBlock 的多项式表示。

(1)S 盒的代数表达式

设X =x 3x 2x 1x 0表示S 盒的输入，则由图2可以得到每个S 盒的真值表。根据真值表，利用文献[8]的算法即可求得输出。这里只给出s 0的输出03210()s X y y y y =的代数表示式，具体如下：

y 3=1+ x 0 x 1 + x 0 x 2 + x 3 + x 1 x 3 + x 0 x 2 x 3

y 2=1 + x 0 +x 0x 2 + x 1x 2 +x 3+x 0x 3+ x 2x 3 + x 0x 2x 3 + x 1x 2x 3 y 1=1 + x 0 + x 2 + x 0 x 2 + x 1 x 2 + x 3 y 0=x 0 + x 1 + x 2 + x 3 + x 2 x 3

(2)轮子密钥的代数表达式

根据S 盒的代数表达式，可以很容易地用Mathematica 编程得到轮密钥用主密钥表示的代数表达式，只要将对应的S 盒的代数表达式作为子函数即可。

得到轮密钥表达式的Mathematica 程序如下：

lBlockKeySchedule[MasterKey_,round_] := Module[

{keyRegister, SubKey, i}, SubKey = Table[0, {round}]; SubKey[[1]] = MasterKey[[1;; 32]]; keyRegister = MasterKey; For[i = 1, i < round, i++,

keyRegister = RotateLeft[keyRegister, 29]; keyRegister[[1;;4]] = s9[keyRegister[[1 ;;4]]]; keyRegister[[5 ;;8]] = s8[keyRegister[[5 ;;8]]]; keyRegister[[30;;34]]=keyRegister[[30;;34]]+ IntegerDigits[i,2,5];

keyRegister=

PolynomialMod[Expand[keyRegister], 2]; SubKey[[i + 1]] = keyRegister[[1 ;; 32]]; ];

Return[SubKey]

第38卷第9期157 彭昌勇，祝跃飞，顾纯祥，等：1~5轮LBlock的多项式表示及完全性分析

];

程序输入：

(1)MasterKey：80比特，用纯符号表示。

(2)round：轮数(由于轮数较大时，轮子密钥的表达式也比较复杂，因此设定轮数作为参数来控制只生成加密函数需要的轮子密钥。本文只能给出5轮LBlock的代数表达式，因此，轮子密钥的代数表达式也只需要生成5轮)。

程序输出：

round个轮子密钥。每个轮子密钥都是64比特。每个比特都是用主密钥表示的代数表达式。其中，s9和s8用由图2所得到的多项式表示进行定义；RotateLeft、IntegerDigits、PolynomialMod 和Expand 都是Mathematica的内置命令，其具体含义可参阅Mathematica的帮助文档。

有了S盒和轮子密钥的代数表达式，就可以像编写轮子密钥的生成程序那样编写LBlock加密函数的Mathematica代码。其过程与用任何编程语言类似。用文献[1]给出的2个测试向量代入符号加密程序，得到了完全相同的输出结果。

将加密程序用明文符号和主密钥符号代入，就可以得到LBlock第1轮~第5轮输出的代数表达式。需要说明的是，本文只是形式上用Mathematica对符号明文和符号密钥进行函数运算，并没有完全展开成多项式的代数标准型。第1轮~第3轮输出的最低比特的代数表达式如下：

第1轮：

p32

第2轮：

k52 + k54 +k55 + p24 + p36 + p38 +(k52 + p36)(k54 +p38)+ (k53 + p37)(k54 + p38) + p39

第3轮：

k23+ k25+ k26+ k60+ k61+ p28+ p30+ p31+ p44+ p45+ (k61 + p45) (k63 + p47) + (k60 + p44) (k62 + p46) (k63 + p47) + (k61 + p45) (k62 + p46)(k63 + p47) + (1+ k25 + k61 + k62 + k63 + p30+ p45 + p46 + (k60 + p44)(k62 + p46)+ (k61 + p45) (k62 + p46) + p47)(1+ k23 + k60 + k61 + k62+p28+ p44 + p45 + p46 + (k62 + p46)(k63 + p47)) + (1+ k25 + k61 + k62 + k63 + p30 + p45 + p46 + (k60 + p44) (k62 + p46) + (k61 + p45)(k62 + p46) + p47) (1 + k24 + k61 + k62 + k63 + p29 + p45 + (k60 + p44)(k61 + p45) + p46 + (k60 + p44)(k62 + p46) + p47 + (k60 + p44)(k63 + p47) + (k61 + p45)(k63 + p47) + (k62 + p46)(k63 + p47) + (k60 + p44)(k62 + p46)(k63 + p47)) + p56.

第4轮和第5轮输出的代数表达式太复杂，因此，这里不再给出。

4 基于代数表达式的1~5轮LBlock完全性分析

根据第3节给出的LBlock的输出比特的代数表达式，可以直接分析其完全性。密码算法的完全性是指每个输出比特都与所有输入比特有关[5-6]。本文利用Mathematica内置命令Variables给出第1轮~第5轮LBlock输出的每个比特所含的自变量。

这里先给出第1轮~第5轮LBlock输出的每个比特所含的主密钥变量个数。

第1轮：

{4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, 4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0} 第2轮：

{8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, 8,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4, 4,4,4,4,4,4,4,4} 第3轮：

{16,16,16,16,16,16,16,16,16,16,16,16,13,13,13,13,16,16, 16,16,16,16,16,16,16,16,16,16,16,16,16,16,8,8,8,8,8,8,8,8,8,8,8, 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8}

第4轮：

{27,27,27,27,25,25,25,25,25,25,25,25,24,24,24,24,29,29, 29,29,30,30,30,30,25,25,25,25,29,29,29,29,16,16,16,16,16,16, 16,16,16,16,16,16,13,13,13,13,16,16,16,

16,16,16,16,16,16,16,16,16,16,16,16,16}

第5轮：

{41,41,41,41,41,41,41,41,45,45,45,45,41,41,41,41,49,49, 49,49,49,49,49,49,44,44,44,44,44,44,44,44,27,27,27,27,25,25, 25,25,25,25,25,25,24,24,24,24,29,29,29,29,30,30,30,30,25,25, 25,25,29,29,29,29}

下面是第1轮~第5轮输出所含的明文变量个数：

第1轮：

{5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, 5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1} 第2轮：

{9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9, 9,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5} 第3轮：

{17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17, 17,17,17,17,17,17,17,17,17,17,17,17,17,17,9,9,9,9,9,9,9,9,9,9,9, 9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9}

第4轮：

{29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29, 29,29,29,29,29,29,29,29,29,29,29,29,29,29,17,17,17,17,17,17, 17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17, 17,17,17,17,17,17}

第5轮：

{45,45,43,45,45,45,45,43,45,45,45,45,45,45,45,45,45,45, 43,45,45,45,45,43,45,45,45,45,45,45,45,45,29,29,29,29,29,29, 29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29,29, 29,29,29,29,29,29}

由上述的变量个数可以看出，5轮LBlock的输出的任何比特都远未达到完全性，这是因为LBlock的明文和主密钥分别是64比特和80比特。第1轮~第5轮输出的任何比特都只和部分明文与部分主密钥有关。

5 结束语

本文基于符号计算软件Mathematica，给出了LBlock 第1轮~第5轮的显式代数表达式，进而根据该表达式直接给出了第1轮~第5轮LBlock的完全性分析的结果，即5轮LBlock的输出的任何比特都远未达到完全性。该方法还可以用于对其他算法的完全性分析。所得到的代数表达式也可以用于对LBlock密码算法的侧信道分析。

参考文献

[1] Wu Wenling, Zhang Lei. LBlock: A Lightweight Block Cipher[C]//

Proceedings of ACNS’11. Heidelberg, Germany: Springer, 2011: 327-344.

[2] Hong D, Sung J, Hong S, et al. HIGHT: A New Block Cipher

Suitable for Low-resource Device[C]//Proceedings of CHES’06.

Heidelberg, Germany: Springer, 2006: 46-59.

[3] de Canniere C, Dunkelman O, Knezevic M. KA TAN and

KTANTAN: A Family of Small and Efficient Hardware-oriented Block Ciphers[C]//Proceedings of CHES’09. Heidelberg, Germany: Springer, 2009.

(下转第179页)

本文来源：https://www.bwwdw.com/article/qafe.html