高效Kasumi加密算法的软件设计与实现

李 翔， 徐 童， 熊 焰

（中国科学技术大学 计算机科学与技术学院，安徽 合肥 230027）

0 引言

为了保证移动通信的安全性并满足实时性的要求，加密算法往往采用硬件实现而非软件实现。但近年来，随着通用处理器工艺的提高，其性能也越来越接近移动通信芯片的要求。使用通用处理器，同时具有开发周期短、开发模式灵活等优点，这使得对通信算法软件实现的研究越发重要，并使软件无线电（SDR）的实际部署成为可能。

Kasumi算法作为第三代移动通信系统（3G）的核心加密算法，以 f 8和 f 92种模式使用[1]，其中 f 8是加密算法，f 9是完整性算法，二者都是基于 Kasumi算法的输出反馈模式（OFB）形成的流密码。由于 Kasumi算法是基于 Feistel网络结构的分组密码，其 OFB模式无法并行实现，而且在移动通信中同时通信的不同用户需要使用不同的密钥，密钥分配也是十分耗时的计算模块，因此少有高效的软件实现方法提出。

在本文中，提出一种基于包并行的高效软件实现方法，并且对 FI子函数以查表的方式进行优化，同时引入新的SSE转置指令用于快速生成不同用户的密钥。实验表明我们的方法比协议中的实现快四倍，达到3GPP规定的实际部署的要求。

1 Kasumi算法

Kasumi算法是分组密码 MISTY1[2]的一个改进版本，64 bit的输入在128 bit密钥的加密下产生64比特的输出。该算法是一个八轮的 Feistel网络[3]，包括FL，FO和FI 3个子函数，每个子函数使用对应的子密钥 KL，KO和 KI，分别由 128位密钥生成。其结构如图1所示。

具体加密过程如下：将 64 bit的输入 I分成32 bit的2部分，分别为L0和R0，即I = L0|| R0。对于第 i轮迭代（1 ≤ i ≤ 8），Ri= Li-1，Li= Ri-1⊕fi(Li-1, RKi)。其中fi指代第i轮的子函数FLi和FOi，RKi为该轮的子密钥，如图所示。最后，第 8轮的结果L8|| R8即为Kasumi算法最终的64 bit输出。

Kasumi算法中的替换操作（Substitution）由FI子函数实现，如图 1所示，16 bit的输入被分成9 bit和7 bit2部分，分别经过S9和S72个S盒进行替换操作后，再与该轮的子密钥做异或运算，然后再做一次 S盒替换操作。所得结果连接在一起作为FI子函数的输出。

图1 Kasumi算法结构

在f 8和f 9算法中，每个用户的数据包，由基站分配初始向量和加密密钥。其中初始向量作为第一次 Kasumi算法的输入，经密钥加密后其输出作为流密码对原文进行加密，并作为下一次 Kasumi算法的输入，以此类推。由于 Kasumi算法基于Feistel网络，且每个用户的数据包的初始向量和加密密钥均不相同，因此每一次 Kasumi的加密过程依赖于前一次 Kasumi的完全结束，从而使得包内的并行不可能实现。另外，S盒的替换操作可转化为一组逻辑运算，较容易用硬件高效实现，而对软件实现来说计算复杂度较高，因此少有高效的软件实现方法提出。在软件无线电大力发展的今天，Kasumi算法的高效的软件实现亟待解决。

2 相关工作

目前有很多 Kasumi算法高效实现的方法，但大部分是通过硬件设计来实现，例如文献[4-5]提出的以简单模块重用和双通道同步内存等方式为特点的FPGA高效实现等，都是对硬件设计进行优化。

但也有基于软件的高效实现方法，如文献[6-7]提出的基于“比特切割”（bit-sliced）的快速算法。该方法同时处理 128个数据包，每次提取每个数据包中的 1 bit组成一个 128位的向量存入一个XMM寄存器中，然后对其做逻辑运算来实现 S盒的替换操作。该方法效率很高，但是其假设存在一个硬件接口用于做比特转置，这在软件中实现的效率是很低的，因此该方法在实际使用中还是不可行。

3 本方法的实现过程

在这一部分详细介绍了本文提出的基于包并行的高效 Kasumi算法的软件实现，主要包括：①利用Intel SSE指令并行处理8个数据包；②利用查找表的算法优化子函数FI；③引入新的转置指令用于快速生成密钥。

3.1 利用Intel SSE指令并行处理8个数据包

Intel在x86架构上继MMX之后引入的新单指令流多数据流指令集（SSE，Streaming SIMD Extension）。该指令集既支持定点运算，又支持浮点运算，且作用在128位的XMM寄存器上，可以分别对 8位、16位、32位、64位和 128位的数进行并行运算，因而十分高效。目前Intel的Nehalem微架构中含有16个XMM寄存器。

在f 8和f 9算法的加密过程中，320 bit的数据包需要同等长度的流密钥，因此需要进行 5次Kasumi计算。Kasumi算法过程中最耗时的模块是FI子函数，为了提高 CPU缓存的命中率，我们以FI的吞吐率来决定数据包并行的粒度。由于 FI的输入输出均为16 bit，而Intel XMM寄存器的大小为128 bit，因此我们选择以8个数据包为单位进行并行处理。对于每个数据包，我们将 64 bit的密钥初始向量分为 Ll、Lr、Rl和 Rr 4部分，然后把 8个数据包的初始向量的对应部分分别放入一个XMM寄存器中进行并行处理。

3.2 以查找表方式优化FI

FI子函数中的 S盒替换操作是整个 Kasumi算法中最耗时的模块，因此我们用查找表的方式对其进行了优化。我们将S9和S72个S盒合并为一个大小为 216的表，每次替换操作只需以 16 bit的输入为索引直接查表即可，而 FI子函数则简化为在两次查表操作之间进行一次异或运算。由于表所占空间不大，而且在设计包并行处理时将 FI模块的处理集中在一起，因此该表基本可以装入 CPU缓存中且命中率较高，从而极大地提高了加密速度。同时，还省去了对 16 bit数据进行拆分与合并的过程，并简化了密钥的生成。与协议原方法的比较见图2。

图2 FI子函数结构比较

3.3 快速密钥生成

无论是在根据 3G基站分配的参数生成初始向量，还是在由密钥生成子密钥时，都需要用到对四个128位的XMM寄存器以32 bit为单位进行转置运算。Intel SSE提供了这样一条复合指令_MM_TRANSPOSE4_PS，但是该指令是浮点数运算，由于 Kasumi加密过程中不存在浮点数运算，因此在执行该指令时需要先将变量转为浮点型，待指令执行完成后再转为整形。经 VTune工具分析后，定位到该指令为程序执行瓶颈，效率十分低下。因此，我们引入了一条新的复合指令_MM_TRANSPOSE4_EPI32，直接在整形数据上进行转置操作，从而省去了类型转换的时间。该指令具体定义如下：

4 实验结果

为了评估本文方法的性能，我们在Intel Nehalem 3.33GHz CPU和Intel C++ Compiler 11.1环境下进行了3组实验，每组运行1000000次，最后取3组实验的平均值与协议中的标准实现[8]进行比较。比较结果如图3。

图3 实验结果数据比较

以上实验结果表明，本文的方法在加密过程中可以达到每个字节消耗19.2个CPU周期，比协议的标准实现快 415%，因此本文提出的 8个数据包并行处理的实现方法已经达到了实际部署的要求。

5 结语

在本文中，提出了一个Kasumi加密算法的高效软件实现方法，采用了包并行、查找表等方式对加密过程进行了优化。实验结果表明对协议的标准实现有明显的提高，并达到了移动通信实际部署的要求。目前，下一代Intel CPU Sandy Bridge已经发布，在新的AVX指令集完整推出后，寄存器大小会升级为256 bit，届时，本文方法的实现性能应该会提高数倍。另外，在保持当前包并行粒度的前提下，可以增加包并行的数量，经大量测试来寻找性能最优的并行数。这些都是我们将来研究的方向。

[1]马炯.分组密码算法KASUMI及其在 WCDMA中的应用[J].信息安全与通信保密, 2005(02):123-126.

[2]MATSUI M, BIHAM I E.New Block Encryption Algorithm MISTY[M].UK: Springer-verlag, 1997:54-68.

[3]毛光灿, 何大可.3G核心加密算法 KASUMI算法[J].通信技术, 2002(11):92-94,97.

[4]BALDERAS T, CUMPLIDO R.An Efficient Hardware Implementation of the KASUMI Block Cipher for Third Generation Cellular Networks[EB/OL].(2004-07-22)[2011-10-29].http://Technical Conference of the International Embedded Solutions Event,2004.ccc.inaoep.mx/～rcumplido/.../GSPx04%20-%20 KASUMI.p...

[5]REN Fang, YAN Yingjian, FU Xiaobing.A Small and Efficienct Hardware Implementation of the KASUMI[C].USA:IEEE, 2009:377-380.

[6]SUNAR G G.Leveraging the Multiprocessing Capabilities of Modern Network Processors for Cryptographic Acceleration[C].USA:IEEE, 2005:235-238.

[7]Mitsuru Matsui, Junko Nakajima.On the Power of Bitslice Implementation on Intel Core2 Processor[EB/OL].(2007-04-27)[2011-10-29].http://www.iacr.org/archive/ches2007/47270121/47270121.

[8]3GPP TS 35.201.Specification of the 3GPP confidentiality and integrity algorithms;Document 1: f8 and t9 Specifications[S].USA:3GPP, 2009.