李 翔， 徐 童， 熊 焰

（中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 合肥 230027）

0 引言

為了保證移動(dòng)通信的安全性并滿(mǎn)足實(shí)時(shí)性的要求，加密算法往往采用硬件實(shí)現(xiàn)而非軟件實(shí)現(xiàn)。但近年來(lái)，隨著通用處理器工藝的提高，其性能也越來(lái)越接近移動(dòng)通信芯片的要求。使用通用處理器，同時(shí)具有開(kāi)發(fā)周期短、開(kāi)發(fā)模式靈活等優(yōu)點(diǎn)，這使得對(duì)通信算法軟件實(shí)現(xiàn)的研究越發(fā)重要，并使軟件無(wú)線電（SDR）的實(shí)際部署成為可能。

Kasumi算法作為第三代移動(dòng)通信系統(tǒng)（3G）的核心加密算法，以 f 8和 f 92種模式使用[1]，其中 f 8是加密算法，f 9是完整性算法，二者都是基于 Kasumi算法的輸出反饋模式（OFB）形成的流密碼。由于 Kasumi算法是基于 Feistel網(wǎng)絡(luò)結(jié)構(gòu)的分組密碼，其 OFB模式無(wú)法并行實(shí)現(xiàn)，而且在移動(dòng)通信中同時(shí)通信的不同用戶(hù)需要使用不同的密鑰，密鑰分配也是十分耗時(shí)的計(jì)算模塊，因此少有高效的軟件實(shí)現(xiàn)方法提出。

在本文中，提出一種基于包并行的高效軟件實(shí)現(xiàn)方法，并且對(duì) FI子函數(shù)以查表的方式進(jìn)行優(yōu)化，同時(shí)引入新的SSE轉(zhuǎn)置指令用于快速生成不同用戶(hù)的密鑰。實(shí)驗(yàn)表明我們的方法比協(xié)議中的實(shí)現(xiàn)快四倍，達(dá)到3GPP規(guī)定的實(shí)際部署的要求。

1 Kasumi算法

Kasumi算法是分組密碼 MISTY1[2]的一個(gè)改進(jìn)版本，64 bit的輸入在128 bit密鑰的加密下產(chǎn)生64比特的輸出。該算法是一個(gè)八輪的 Feistel網(wǎng)絡(luò)[3]，包括FL，F(xiàn)O和FI 3個(gè)子函數(shù)，每個(gè)子函數(shù)使用對(duì)應(yīng)的子密鑰 KL，KO和 KI，分別由 128位密鑰生成。其結(jié)構(gòu)如圖1所示。

具體加密過(guò)程如下：將 64 bit的輸入 I分成32 bit的2部分，分別為L(zhǎng)0和R0，即I = L0|| R0。對(duì)于第 i輪迭代（1 ≤ i ≤ 8），Ri= Li-1，Li= Ri-1⊕fi(Li-1, RKi)。其中fi指代第i輪的子函數(shù)FLi和FOi，RKi為該輪的子密鑰，如圖所示。最后，第 8輪的結(jié)果L8|| R8即為Kasumi算法最終的64 bit輸出。

Kasumi算法中的替換操作（Substitution）由FI子函數(shù)實(shí)現(xiàn)，如圖 1所示，16 bit的輸入被分成9 bit和7 bit2部分，分別經(jīng)過(guò)S9和S72個(gè)S盒進(jìn)行替換操作后，再與該輪的子密鑰做異或運(yùn)算，然后再做一次 S盒替換操作。所得結(jié)果連接在一起作為FI子函數(shù)的輸出。

圖1 Kasumi算法結(jié)構(gòu)

在f 8和f 9算法中，每個(gè)用戶(hù)的數(shù)據(jù)包，由基站分配初始向量和加密密鑰。其中初始向量作為第一次 Kasumi算法的輸入，經(jīng)密鑰加密后其輸出作為流密碼對(duì)原文進(jìn)行加密，并作為下一次 Kasumi算法的輸入，以此類(lèi)推。由于 Kasumi算法基于Feistel網(wǎng)絡(luò)，且每個(gè)用戶(hù)的數(shù)據(jù)包的初始向量和加密密鑰均不相同，因此每一次 Kasumi的加密過(guò)程依賴(lài)于前一次 Kasumi的完全結(jié)束，從而使得包內(nèi)的并行不可能實(shí)現(xiàn)。另外，S盒的替換操作可轉(zhuǎn)化為一組邏輯運(yùn)算，較容易用硬件高效實(shí)現(xiàn)，而對(duì)軟件實(shí)現(xiàn)來(lái)說(shuō)計(jì)算復(fù)雜度較高，因此少有高效的軟件實(shí)現(xiàn)方法提出。在軟件無(wú)線電大力發(fā)展的今天，Kasumi算法的高效的軟件實(shí)現(xiàn)亟待解決。

2 相關(guān)工作

目前有很多 Kasumi算法高效實(shí)現(xiàn)的方法，但大部分是通過(guò)硬件設(shè)計(jì)來(lái)實(shí)現(xiàn)，例如文獻(xiàn)[4-5]提出的以簡(jiǎn)單模塊重用和雙通道同步內(nèi)存等方式為特點(diǎn)的FPGA高效實(shí)現(xiàn)等，都是對(duì)硬件設(shè)計(jì)進(jìn)行優(yōu)化。

但也有基于軟件的高效實(shí)現(xiàn)方法，如文獻(xiàn)[6-7]提出的基于“比特切割”（bit-sliced）的快速算法。該方法同時(shí)處理 128個(gè)數(shù)據(jù)包，每次提取每個(gè)數(shù)據(jù)包中的 1 bit組成一個(gè) 128位的向量存入一個(gè)XMM寄存器中，然后對(duì)其做邏輯運(yùn)算來(lái)實(shí)現(xiàn) S盒的替換操作。該方法效率很高，但是其假設(shè)存在一個(gè)硬件接口用于做比特轉(zhuǎn)置，這在軟件中實(shí)現(xiàn)的效率是很低的，因此該方法在實(shí)際使用中還是不可行。

3 本方法的實(shí)現(xiàn)過(guò)程

在這一部分詳細(xì)介紹了本文提出的基于包并行的高效 Kasumi算法的軟件實(shí)現(xiàn)，主要包括：①利用Intel SSE指令并行處理8個(gè)數(shù)據(jù)包；②利用查找表的算法優(yōu)化子函數(shù)FI；③引入新的轉(zhuǎn)置指令用于快速生成密鑰。

3.1 利用Intel SSE指令并行處理8個(gè)數(shù)據(jù)包

Intel在x86架構(gòu)上繼MMX之后引入的新單指令流多數(shù)據(jù)流指令集（SSE，Streaming SIMD Extension）。該指令集既支持定點(diǎn)運(yùn)算，又支持浮點(diǎn)運(yùn)算，且作用在128位的XMM寄存器上，可以分別對(duì) 8位、16位、32位、64位和 128位的數(shù)進(jìn)行并行運(yùn)算，因而十分高效。目前Intel的Nehalem微架構(gòu)中含有16個(gè)XMM寄存器。

在f 8和f 9算法的加密過(guò)程中，320 bit的數(shù)據(jù)包需要同等長(zhǎng)度的流密鑰，因此需要進(jìn)行 5次Kasumi計(jì)算。Kasumi算法過(guò)程中最耗時(shí)的模塊是FI子函數(shù)，為了提高 CPU緩存的命中率，我們以FI的吞吐率來(lái)決定數(shù)據(jù)包并行的粒度。由于 FI的輸入輸出均為16 bit，而Intel XMM寄存器的大小為128 bit，因此我們選擇以8個(gè)數(shù)據(jù)包為單位進(jìn)行并行處理。對(duì)于每個(gè)數(shù)據(jù)包，我們將 64 bit的密鑰初始向量分為 Ll、Lr、Rl和 Rr 4部分，然后把 8個(gè)數(shù)據(jù)包的初始向量的對(duì)應(yīng)部分分別放入一個(gè)XMM寄存器中進(jìn)行并行處理。

3.2 以查找表方式優(yōu)化FI

FI子函數(shù)中的 S盒替換操作是整個(gè) Kasumi算法中最耗時(shí)的模塊，因此我們用查找表的方式對(duì)其進(jìn)行了優(yōu)化。我們將S9和S72個(gè)S盒合并為一個(gè)大小為 216的表，每次替換操作只需以 16 bit的輸入為索引直接查表即可，而 FI子函數(shù)則簡(jiǎn)化為在兩次查表操作之間進(jìn)行一次異或運(yùn)算。由于表所占空間不大，而且在設(shè)計(jì)包并行處理時(shí)將 FI模塊的處理集中在一起，因此該表基本可以裝入 CPU緩存中且命中率較高，從而極大地提高了加密速度。同時(shí)，還省去了對(duì) 16 bit數(shù)據(jù)進(jìn)行拆分與合并的過(guò)程，并簡(jiǎn)化了密鑰的生成。與協(xié)議原方法的比較見(jiàn)圖2。

圖2 FI子函數(shù)結(jié)構(gòu)比較

3.3 快速密鑰生成

無(wú)論是在根據(jù) 3G基站分配的參數(shù)生成初始向量，還是在由密鑰生成子密鑰時(shí)，都需要用到對(duì)四個(gè)128位的XMM寄存器以32 bit為單位進(jìn)行轉(zhuǎn)置運(yùn)算。Intel SSE提供了這樣一條復(fù)合指令_MM_TRANSPOSE4_PS，但是該指令是浮點(diǎn)數(shù)運(yùn)算，由于 Kasumi加密過(guò)程中不存在浮點(diǎn)數(shù)運(yùn)算，因此在執(zhí)行該指令時(shí)需要先將變量轉(zhuǎn)為浮點(diǎn)型，待指令執(zhí)行完成后再轉(zhuǎn)為整形。經(jīng) VTune工具分析后，定位到該指令為程序執(zhí)行瓶頸，效率十分低下。因此，我們引入了一條新的復(fù)合指令_MM_TRANSPOSE4_EPI32，直接在整形數(shù)據(jù)上進(jìn)行轉(zhuǎn)置操作，從而省去了類(lèi)型轉(zhuǎn)換的時(shí)間。該指令具體定義如下：

4 實(shí)驗(yàn)結(jié)果

為了評(píng)估本文方法的性能，我們?cè)贗ntel Nehalem 3.33GHz CPU和Intel C++ Compiler 11.1環(huán)境下進(jìn)行了3組實(shí)驗(yàn)，每組運(yùn)行1000000次，最后取3組實(shí)驗(yàn)的平均值與協(xié)議中的標(biāo)準(zhǔn)實(shí)現(xiàn)[8]進(jìn)行比較。比較結(jié)果如圖3。

圖3 實(shí)驗(yàn)結(jié)果數(shù)據(jù)比較

以上實(shí)驗(yàn)結(jié)果表明，本文的方法在加密過(guò)程中可以達(dá)到每個(gè)字節(jié)消耗19.2個(gè)CPU周期，比協(xié)議的標(biāo)準(zhǔn)實(shí)現(xiàn)快 415%，因此本文提出的 8個(gè)數(shù)據(jù)包并行處理的實(shí)現(xiàn)方法已經(jīng)達(dá)到了實(shí)際部署的要求。

5 結(jié)語(yǔ)

在本文中，提出了一個(gè)Kasumi加密算法的高效軟件實(shí)現(xiàn)方法，采用了包并行、查找表等方式對(duì)加密過(guò)程進(jìn)行了優(yōu)化。實(shí)驗(yàn)結(jié)果表明對(duì)協(xié)議的標(biāo)準(zhǔn)實(shí)現(xiàn)有明顯的提高，并達(dá)到了移動(dòng)通信實(shí)際部署的要求。目前，下一代Intel CPU Sandy Bridge已經(jīng)發(fā)布，在新的AVX指令集完整推出后，寄存器大小會(huì)升級(jí)為256 bit，屆時(shí)，本文方法的實(shí)現(xiàn)性能應(yīng)該會(huì)提高數(shù)倍。另外，在保持當(dāng)前包并行粒度的前提下，可以增加包并行的數(shù)量，經(jīng)大量測(cè)試來(lái)尋找性能最優(yōu)的并行數(shù)。這些都是我們將來(lái)研究的方向。

[1]馬炯.分組密碼算法KASUMI及其在 WCDMA中的應(yīng)用[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].通信技術(shù), 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.