Camellia算法S盒的紧凑硬件实现*

2021-11-20 02:13魏子豪张英杰孙思维史丹萍罗宜元
密码学报 2021年5期
关键词:表达式元件文献

魏子豪,张英杰,胡 磊,孙思维,史丹萍,罗宜元

1.中国科学院 信息工程研究所 信息安全国家重点实验室,北京 100093

2.中国科学院大学 密码学院,北京 100049

3.密码科学技术国家重点实验室,北京 100878

4.中国科学院大学 网络空间安全学院,北京 100049

5.惠州学院 计算机科学与工程学院,惠州 516007

1 引言

Camellia分组密码算法由三菱公司和日本电信电话公司在2000年共同设计[1].由于其较高的安全性以及在软、硬件平台上高效的实现性能,该算法在2003年欧洲NESSIE项目中被评选为获胜算法,同年在日本CRYPTREC计划中被评选为推荐算法,2004年成为IETF标准算法,2005年成为ISO/IEC标准算法,2006年成为PKCS#11认证密码.

在硬件平台上实现时,存在这样一种应用场景:由于环境约束,电路芯片的面积必须比较小,因此能使用的电路资源也相对有限,除了满足正常运行功能之外,设计者还需要提供安全加解密能力,例如银行卡芯片、无线传感器节点等.在这种情况下,密码算法实现者对资源面积这一参数更敏感.在Camellia算法中,S盒作为唯一的非线性部件,需要消耗的资源最多,可以优化的空间也比线性部件大,因此通常我们会研究S盒的实现方法.

本文结构如下:第2节简单介绍塔域实现的基础知识和通用方法;第3节将塔域实现和Camellia的具体结构相结合,根据该密码算法的特点采用了针对性的优化方式;第4节汇总了实现方案的数据,并通过仿真实验将它与以前的方案对比;第5节是对全文的总结,以及对未来工作的展望.

2 预备知识

2.1 塔域表现形式

我们可以用其系数组成的向量(b7,b6,···,b0)T来表示b.

图1 两种不同的域扩张方式Figure 1 Two different ways of field extensions

b=γ1Y16+γ0Y,

γ1=Γ3Z4+Γ2Z,γ0=Γ1Z4+Γ0Z,

Γ3=g7W2+g6W,Γ2=g5W2+g4W,Γ1=g3W2+g2W,Γ0=g1W2+g0W,

其中,γ1,γ0∈F24,Γ3,Γ2,Γ1,Γ0∈F22,g i∈F2,0≤i≤7,即

b=g7W2Z4Y16+g6W Z4Y16+g5W2Z Y16+g4W Z Y16+g3W2Z4Y+g2W Z4Y+g1W2Z Y+g0W Z Y.

我们将这组由W,Z和Y组成的基叫做塔域基,记为T B,

T B=[W2Z4Y16,W Z4Y16,W2Z Y16,W Z Y16,W2Z4Y,W Z4Y,W2Z Y,W Z Y],

在T B下,b可由另一组系数向量(g7,g6,···,g0)T来表示.

由于塔域基中的每个基底分量都是F28中的元素,都可以用多项式基来表示,

T B[i]=W h Z j Y k=(X7,X6,···,X0)V i,i=7,6,···,0,

其中T B[i]表示塔域基的第i个分量,V i表示它在多项式基下的系数列向量,因此塔域基整体也可以用多项式基表示为

b的两组系数向量之间存在如下转换关系

2.2 F28逆运算的塔域实现

γλ=(Γ1Z4+Γ0Z)(Λ1Z4+Λ0Z)

=[Γ1Λ1T+(Γ1+Γ0)(Λ1+Λ0)N T2]Z4+[Γ0Λ0T+(Γ1+Γ0)(Λ1+Λ0)N T2]Z.

ΓΔ=(u1W2+u0W)(v1W2+v0W)

=[u1·v1⊕(u1⊕u0)·(v1⊕v0)]W2+[u0·v0⊕(u1⊕u0)·(v1⊕v0)]W.

2.3 常用电路元件

表1 三种工艺库下常用电路元件的面积Table 1 Area of frequently-used gates in three CMOS technology libraries

3 实现方案

Camellia算法一共使用了4个不同的S盒s1,s2,s3,s4,其中

s2(x)=s1(x)≪1,

s3(x)=s1(x)≫1,

s4(x)=s1(x≪1),

图2 直观地表示了两种基下逆运算之间的联系.

图2 多项式基下求逆和塔域基下求逆之间的关系Figure 2 Relationship between inversion under polynomial basis and inversion under tower basis

进而S(b)可表示为

第2.2节的运算表达式显示,I T B的计算过程受r(y),s(z),t(w)三个不可约多项式影响,参考文献[10]可知,三个多项式共会产生720种有效情况.我们运用文献[6-10]中的知识,对所有有效情况进行了搜索,得到了一种和文献[10]不同,并且效果更好的实现方案,其中多项式的系数和它们的根如表2所示,它们的值均是基于多项式基的表示.

表2 三个不可约多项式的系数及其根Table 2 Values of coefficients and roots of three irreducible polynomials

我们使用5个模块来完成S盒的功能,如图3所示,每个部分的实现细节见下列各小节.

图3 S盒整体结构Figure 3 S-box structure

3.1 头部模块实现方案

头部模块实现了等式(1)中的γ1γ0τ2+(γ1+γ0)2ν部分,记结果为φ.用2.1节的塔域表示符号将γ1γ0τ2和(γ1+γ0)2ν展开到比特级,可得表达式

γ1γ0τ2=(Γ3Z4+Γ2Z)(Γ1Z4+Γ0Z)·(N·Z4+N·Z)2

=g6g2⊕(g7⊕g6)(g3⊕g2)⊕(g7⊕g5)(g3⊕g1)⊕(g7⊕g6⊕g5⊕g4)(g3⊕g2⊕g1⊕g0)]W2Z4+[g7g3⊕g6g2⊕(g6⊕g4)(g2⊕g0)⊕(g7⊕g6⊕g5⊕g4)(g3⊕g2⊕g1⊕g0)]W Z4+[g4g0⊕(g5⊕g4)(g1⊕g0)⊕(g7⊕g5)(g3⊕g1)⊕(g7⊕g6⊕g5⊕g4)(g3⊕g2⊕g1⊕g0)]W2Z+[g5g1⊕g4g0⊕(g6⊕g4)(g2⊕g0)⊕(g7⊕g6⊕g5⊕g4)(g3⊕g2⊕g1⊕g0)]W Z

(γ1+γ0)2ν=[(Γ3+Γ1)Z4+(Γ2+Γ0)Z]2·(N·Z4+0·Z)

=(g7⊕g6⊕g3⊕g2)W2Z4+(g6⊕g2)W Z4+(g7⊕g5⊕g3⊕g1)W2Z+(g7⊕g6⊕g5⊕g4⊕g3⊕g2⊕g1⊕g0)W Z.

m9=g7⊕g6m8=g3⊕g2m7=g7⊕g5m6=g3⊕g1

m5=g6⊕g4m4=g2⊕g0m3=g7⊕g6⊕g5⊕g4m2=g3⊕g2⊕g1⊕g0

m1=g5⊕g4m0=g1⊕g0,

φ=(g6g2⊕m9m8⊕m7m6⊕m3m2⊕m9⊕m8)W2Z4+(g7g3⊕g6g2⊕m5m4⊕m3m2⊕g6⊕g2)W Z4+(g4g0⊕m1m0⊕m7m6⊕m3m2⊕m7⊕m6)W2Z+(g5g1⊕g4g0⊕m5m4⊕m3m2⊕m3⊕m2)W Z.

运用文献[6-10]中的优化方法,最终表达式为

在不考虑m9,m8,···,m0实现方式(即假设比特序列g和m均已知)的情况下,实现该表达式需要8个NAND门、4个NOR门和12个XOR门.

3.2 中部模块实现方案

φ=p3W2Z4+p2W Z4+p1W2Z+p0W Z

λ=(p2p1p0⊕p3p1⊕p2p1⊕p1⊕p0)W2Z4+(p3p1p0⊕p3p1⊕p2p1⊕p2p0⊕p0)W Z4+(p3p2p0⊕p3p1⊕p3p0⊕p3⊕p2)W2Z+(p3p2p1⊕p3p1⊕p3p0⊕p2p0⊕p2)W Z.

传统方法利用了逆运算在塔域上的结构特点来实现,当我们舍弃这一特征,转而应用文献[9]中的方法时,可以得到一个面积更小的实现方案:

t1=NAND(p2,p0)t2=NOR(p3,p1)t3=XNOR(t1,t2)t4=MUX(p3,p0,1)

t5=MUX(p1,p2,1)t6=MUX(p0,t3,p1)t7=MUX(t3,p1,t4)t8=MUX(p2,t3,p3)

t9=MUX(t3,p3,t5),

λ=(t7,t6,t9,t8),

共使用1个NAND门,1个NOR门,1个XNOR门和6个MUX元件.

通过观察可知,

MUX(s,a,1)=s·a⊕s⊕1=NANDN(a,s),

一般情况下,NANDN元件的面积小于MUX元件,当工艺库支持NANDN元件时,我们可以进一步优化t4和t5:

t4=NANDN(p0,p3),t5=NANDN(p2,p1).

3.3 尾部模块实现方案

尾部模块实现了等式(1)中λγ0和λγ1的部分表达式.设

λ=l3W2Z4+l2W Z4+l1W2Z+l0W Z,

k4=l3⊕l2,k3=l3⊕l1,k2=l2⊕l0,k1=l3⊕l2⊕l1⊕l0,k0=l1⊕l0,

e17=NAND(g3,l3)e16=NAND(m8,k4)e15=NAND(g2,l2)e14=NAND(m4,k2)

e13=NAND(m6,k3)e12=NAND(m2,k1)e11=NAND(g1,l1)e10=NAND(m0,k0)

e9=NAND(g0,l0)e8=NAND(g7,l3)e7=NAND(m9,k4)e6=NAND(g6,l2)

e5=NAND(m5,k2)e4=NAND(m7,k3)e3=NAND(m3,k1)e2=NAND(g5,l1)

e1=NAND(m1,k0)e0=NAND(g4,l0),

λγ0=(e17⊕e16⊕e14⊕e13)W2Z4+(e15⊕e16⊕e12⊕e13)W Z4+(e11⊕e10⊕e14⊕e13)W2Z+(e9⊕e10⊕e12⊕e13)W Z,

λγ1=(e8⊕e7⊕e5⊕e4)W2Z4+(e6⊕e7⊕e3⊕e4)W Z4+(e2⊕e1⊕e5⊕e4)W2Z+(e0⊕e1⊕e3⊕e4)W Z.

从表达式中可以看到,最后的结果是从18个NAND门的输出中分别抽取4个异或在一起,形成的8个组合.参考文献[7]中的优化方式,在尾部模块中,我们只实现比特序列k和e,将更进一步的异或操作留到之后的模块中去完成.这样尾部模块一共使用了5个XOR门和18个NAND门.

3.4 输入、输出模块实现方案

在有限域中,元素与常数的乘法运算以及元素的2β次幂运算均可转化为对该元素的线性变换,即

其中Mα,Mβ分别表示常数α和2β次幂运算对应的矩阵,因此等式(2)可以重写为

优化方法在求逆运算过程产生的额外效果可以从图4中看出来.

图4 优化方法对逆运算的影响Figure 4 Influence of optimization

进而S(b)可以对应重写为

这个优化只影响输入、输出模块,对其他部分没有影响.

实现输入、输出模块的过程本质上是求解SLP(shortest linear straight-line programs)问题,而SLP问题已经被证明是NP-hard问题[7].目前已经存在多种方法来对其优化,如文献[7-9,16-18],其中文献[17]是将SLP问题转换为SAT问题,利用SAT求解器来运算,对维数较小的矩阵能获得可证明的最优解,而其他文献则都是启发式算法,只能得到较好的结果.针对当前规模较大的输入、输出模块,我们使用了文献[7]中的算法.

α有255种取值,β有8种取值,因此(α,β)共有2040种组合情况.在尝试了所有组合对应的矩阵后,我们发现其中6种组合能使输入、输出模块的实现代价之和最小,其取值和实现代价总和的情况见表3,其中α的值是多项式基下的表达式.而其他组合则会使用更多的XOR/XNOR门电路,通常会增加1-16个.

表3 α、β的最佳取值和矩阵实现情况Table 3 Best values ofαandβ,and sum of implementations of their corresponding matrices

当我们取第一组最佳组合时,输入模块具体为:

一共使用了17个XOR/XNOR门和1个NOT门,实现方案如下:

t1=XOR(b4,b1)t2=XNOR(b4,b2)t3=XNOR(b6,b1)t4=XOR(b7,b0)

t5=XOR(b6,b3t6=XNOR(t4,t5)t7=XOR(t1,t6)t8=XNOR(b0,t7)

t9=XOR(b1,t8)t10=XNOR(t2,t5)t11=XOR(t1,t10)t12=XOR(t4,t10)

t13=XOR(t4,t7)t14=XOR(b5,t13)t15=XOR(t9,t14)t16=XNOR(b6,t15)

t17=XOR(t8,t16),

g=(t1,t6,t11,t2,t9,b1,t14,t3)

m=(t7,t8,t10,t15,t12,NOT(b6),t4,t16,t13,t17).

输出模块具体为:

一共使用了28个XOR/XNOR门,实现方案如下:

t1=XOR(e8,e5)t2=XOR(e6,e0)t3=XOR(e6,e3)t4=XNOR(t1,t3)

t5=XOR(e1,t2)t6=XNOR(e7,t5)t7=XOR(e4,t1)t8=XNOR(t5,t7)

t9=XNOR(e10,t6)t10=XNOR(e9,t4)t11=XOR(e16,t9)t12=XOR(t10,t11)

t13=XNOR(e15,t12)t14=XOR(e17,e11)t15=XOR(e13,e12)t16=XOR(t12,t15)

t17=XOR(e10,e8)t18=XOR(e2,t2)t19=XOR(t17,t18)t20=XNOR(e16,t8)

t21=XOR(t16,t20)t22=XNOR(t8,t11)t23=XNOR(t14,t22)t24=XOR(t14,t16)

t25=XOR(t19,t24)t26=XOR(e14,e13)t27=XOR(e11,t19)t28=XOR(t26,t27),

S(b)=(t28,t8,t23,t25,t6,t13,t4,t21).

4 实验结果

我们将第3节各小节描述的数据汇总到表4中.利用Synopsys Design Compiler软件,结合三种工艺库的库文件,可以对Camellia的各种实现方案做综合仿真,结果见表5.

表4 各模块所用电路元件数量Table 4 Gate number for each module

表5 不同论文下的实现方案综合结果Table 5 Synthesis results of different implementations

5 总结

通过划分AES密码算法S盒轻量化实现时的优化方法,我们成功地将这些技术运用到Camellia中,在此基础上当实际使用的工艺库允许一些复合元件时,我们可以做更进一步的优化.实验结果显示,运用了新技术的方案比现有的最佳方案减少了从4.66 GE到8.25 GE不等的面积.

下一步的研究方向是针对深度做优化实现,以及在同时考虑面积和深度两个维度的情况下,设计一种比较平衡的方案.

猜你喜欢
表达式元件文献
一种智能磁条传感器
既有建筑结构鉴定表达式各分项系数的确定分析
Hostile takeovers in China and Japan
灵活选用二次函数表达式
Cultural and Religious Context of the Two Ancient Egyptian Stelae An Opening Paragraph
直流电机电枢绕组分布排列和连接解析
浅析C语言运算符及表达式的教学误区
The Application of the Situational Teaching Method in English Classroom Teaching at Vocational Colleges
The Role and Significant of Professional Ethics in Accounting and Auditing
如何读懂色环电阻