高效Kasumi加密算法的軟件設計與實現(xiàn)

李 翔， 徐 童， 熊 焰

（中國科學技術(shù)大學 計算機科學與技術(shù)學院，安徽 合肥 230027）

0 引言

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

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

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

1 Kasumi算法

Kasumi算法是分組密碼 MISTY1[2]的一個改進版本，64 bit的輸入在128 bit密鑰的加密下產(chǎn)生64比特的輸出。該算法是一個八輪的 Feistel網(wǎng)絡[3]，包括FL，F(xiàn)O和FI 3個子函數(shù)，每個子函數(shù)使用對應的子密鑰 KL，KO和 KI，分別由 128位密鑰生成。其結(jié)構(gòu)如圖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輪的子函數(shù)FLi和FOi，RKi為該輪的子密鑰，如圖所示。最后，第 8輪的結(jié)果L8|| R8即為Kasumi算法最終的64 bit輸出。

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

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

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

2 相關工作

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

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

3 本方法的實現(xiàn)過程

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

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

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

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

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

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

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

3.3 快速密鑰生成

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

4 實驗結(jié)果

為了評估本文方法的性能，我們在Intel Nehalem 3.33GHz CPU和Intel C++ Compiler 11.1環(huán)境下進行了3組實驗，每組運行1000000次，最后取3組實驗的平均值與協(xié)議中的標準實現(xiàn)[8]進行比較。比較結(jié)果如圖3。

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

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

5 結(jié)語

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

[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].通信技術(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.