基于k-分割Feistel網(wǎng)絡(luò)的FPE方案

李經(jīng)緯，賈春福，劉哲理，李敏

（1. 南開(kāi)大學(xué) 信息技術(shù)科學(xué)學(xué)院，天津 300071；2. 福建師范大學(xué) 網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室, 福建 福州350007）

1 引言

保留格式加密(FPE, format-preserving encryption)[1]是一種新型加密技術(shù)，通過(guò)將某種特定格式的明文加密為與其具有相同格式的密文，使現(xiàn)有數(shù)據(jù)庫(kù)中數(shù)據(jù)的加解密，既不需要改動(dòng)應(yīng)用系統(tǒng)，也不需要改動(dòng)數(shù)據(jù)庫(kù)結(jié)構(gòu)。此外，F(xiàn)PE還可應(yīng)用于數(shù)據(jù)遮蔽[2]、網(wǎng)絡(luò)數(shù)據(jù)安全[3]和格式依賴加密[4]等領(lǐng)域。

國(guó)外已取得一些FPE相關(guān)理論研究成果[5～9]。其中，文獻(xiàn)[5]關(guān)注整數(shù)集上的 FPE問(wèn)題，提出generalized-Feistel方法，該方法首次將Feistel網(wǎng)絡(luò)引入到FPE方案構(gòu)建。其后FPE方案FFSEM[6]、FFX[7,8]、BPS[9]等都延續(xù)這一思想，采用各種類型2-分割Feistel網(wǎng)絡(luò)。

表1 Feistel網(wǎng)絡(luò)在典型FPE方案中的應(yīng)用情況

目前，處理charsn上的FPE問(wèn)題即意味著構(gòu)造分組長(zhǎng)度為n的FPE密碼(盡管文獻(xiàn)[9]提出BPS方案的CBC模式，但未給出相關(guān)安全性分析)。然而當(dāng)前2-分割Feistel網(wǎng)絡(luò)，在n相當(dāng)大時(shí)，使用的偽隨機(jī)函數(shù)輸入和輸出寬度也相當(dāng)大，設(shè)計(jì)和實(shí)現(xiàn)一個(gè)大規(guī)模偽隨機(jī)函數(shù)通常是困難的[10]。

作者已在文獻(xiàn)[11]中對(duì)已有 FPE模型進(jìn)行了分析，提出 FPE方案設(shè)計(jì)框架，將任意問(wèn)題域的 FPE方案構(gòu)造轉(zhuǎn)移為編碼方案設(shè)計(jì)和整數(shù)FPE算法設(shè)計(jì)。本文在此基礎(chǔ)上，關(guān)注當(dāng)前 FPE方案中各種類型Feistel網(wǎng)絡(luò)的適用性，針對(duì)使用2-分割Feistel網(wǎng)絡(luò)構(gòu)造的FPE密碼分組長(zhǎng)度適應(yīng)范圍較小的問(wèn)題，提出基于k-分割type-2 Feistel網(wǎng)絡(luò)的FPE方案，以滿足各種長(zhǎng)度數(shù)據(jù)的加密需求。該方案結(jié)合 cycle-walking[5]可以解決任意整數(shù)集上的FPE問(wèn)題。最后通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)和分析各種 Feistel網(wǎng)絡(luò)達(dá)到雪崩準(zhǔn)則所需輪次數(shù)和時(shí)間開(kāi)銷(xiāo)，以驗(yàn)證type-2 Feistel網(wǎng)絡(luò)可以使用較小規(guī)模偽隨機(jī)函數(shù)構(gòu)造各種分組長(zhǎng)度密碼。

2 Feistel網(wǎng)絡(luò)在FPE中的應(yīng)用分析

目前已提出的FPE方案多數(shù)使用Feistel網(wǎng)絡(luò)，表1總結(jié)了Feistel網(wǎng)絡(luò)在典型FPE方案中應(yīng)用情況，考慮的主要要素包括：Feistel網(wǎng)絡(luò)類型、偽隨機(jī)函數(shù)構(gòu)造方法和輪次數(shù)等。

由表1可知如下內(nèi)容。

1) 當(dāng)前FPE方案均采用2-分割Feistel網(wǎng)絡(luò)，包括平衡Feistel網(wǎng)絡(luò)、非平衡Feistel網(wǎng)絡(luò)、交互式Feistel網(wǎng)絡(luò)以及它們的數(shù)值形式。2-分割Feistel網(wǎng)絡(luò)都將輸入等長(zhǎng)或不等長(zhǎng)地劃分為L(zhǎng)和R這2部分，然后使用偽隨機(jī)函數(shù)分別執(zhí)行如圖 1所示的輪運(yùn)算，以形成下一輪輸入。

圖1 2-分割Feistel網(wǎng)絡(luò)

2) Feistel網(wǎng)絡(luò)的效率主要取決于偽隨機(jī)函數(shù)。當(dāng)前使用Feistel網(wǎng)絡(luò)的FPE方案中，偽隨機(jī)函數(shù)構(gòu)造方法包括基于偽隨機(jī)置換的構(gòu)造方案[6]和基于消息認(rèn)證碼的構(gòu)造方案[3,7,9]，其本質(zhì)都是填充原輸入，通過(guò)偽隨機(jī)置換或消息認(rèn)證碼作用，形成函數(shù)輸出[12]。

3) 在采用安全偽隨機(jī)函數(shù)的情況下，F(xiàn)eistel網(wǎng)絡(luò)安全性與輪次數(shù)相關(guān)。文獻(xiàn)[13～15]證明至少6輪運(yùn)算才能保證Feistel網(wǎng)絡(luò)在各種攻擊模型(已知明文攻擊、自適應(yīng)選擇明文攻擊和自適應(yīng)選擇明文密文攻擊)下的安全性。文獻(xiàn)[16]進(jìn)一步分析一般 Feistel網(wǎng)絡(luò)(包括平衡、非平衡、交互式和type-1, 2, 3 Feistel網(wǎng)絡(luò))超越生日邊界的安全性，證明執(zhí)行足夠多輪運(yùn)算后，一般Feistel網(wǎng)絡(luò)在選擇密文攻擊下，能夠抵抗 2m(1-ε)次惡意查詢(這里m為一般Feistel網(wǎng)絡(luò)使用的偽隨機(jī)函數(shù)輸入寬度，ε為大于0的極小數(shù))。

3 基于k-分割Feistel網(wǎng)絡(luò)的FPE方案

針對(duì)2-分割Feistel網(wǎng)絡(luò)構(gòu)造的FPE密碼分組長(zhǎng)度適應(yīng)范圍較小的問(wèn)題，構(gòu)造基于k-分割Feistel網(wǎng)絡(luò)的整數(shù)FPE方案(這里以4-分割為例，如果輸入寬度很大，可考慮增加子分組數(shù)目)。該方案還可進(jìn)一步擴(kuò)展，結(jié)合文獻(xiàn)[11]或 rank-then-encipher方法[3]解決復(fù)雜問(wèn)題域(如正則語(yǔ)言等)中的FPE問(wèn)題。

3.1k-分割Feistel網(wǎng)絡(luò)

k-分割Feistel網(wǎng)絡(luò)包括type-1、type-2和type-3，通過(guò)將輸入比特串等分為k個(gè)子分組，能夠有效避免大寬度偽隨機(jī)函數(shù)設(shè)計(jì)和實(shí)現(xiàn)的困難，已被廣泛應(yīng)用于各種分組密碼的構(gòu)造，例如CAST-256(type-1)、RC6(type-2)和 MARS(type-3)等。其每一輪工作原理如圖2所示。

圖2k-分割Feistel網(wǎng)絡(luò)(k= 4的情況)

1) Type-1 Feistel網(wǎng)絡(luò)執(zhí)行X2'=FK(X1)⊕X2，連接X(jué)2'||X3||X4||X1作為下一輪迭代輸入。

2) Type-2 Feistel網(wǎng)絡(luò)執(zhí)行X2'=FK1(X1)⊕X2和X4'=FK2(X3) ⊕X4，連接X(jué)2'||X3||X4'||X1作為下一輪迭代輸入。

3) Type-3 Feistel網(wǎng)絡(luò)執(zhí)行X2'=FK1(X1)⊕X2，X3'=FK2(X2) ⊕X3和X4'=FK3(X3) ⊕X4，連接X(jué)2'||X3'||X4'||X1作為下一輪迭代輸入。

3.2 基于type-2 Feistel網(wǎng)絡(luò)的整數(shù)FPE方案

在k-分割Feistel網(wǎng)絡(luò)中，type-2具有安全和效率的最佳平衡：①擴(kuò)散性方面，type-2只需較少輪次即可達(dá)到與type-1相當(dāng)?shù)陌踩?，而type-3每一輪運(yùn)算需調(diào)用更多次偽隨機(jī)函數(shù)，計(jì)算復(fù)雜性較高[17]；②雪崩效應(yīng)方面，雖然 type-2滿足雪崩準(zhǔn)則所需 Feistel輪次數(shù)略大于type-3，但在調(diào)用偽隨機(jī)函數(shù)次數(shù)上，type-2大約只是type-3的一半[18]。

因此，試圖設(shè)計(jì)基于type-2 Feistel網(wǎng)絡(luò)的整數(shù)FPE方案，描述如下。

系統(tǒng)初始化 setup：初始化系統(tǒng)參數(shù)，包括：①基于type-2 Feistel網(wǎng)絡(luò)的加密算法所需參數(shù)，如輪次數(shù)r、偽隨機(jī)函數(shù)F和子分組數(shù)目k等；②待解決問(wèn)題域?n= { 0,1,… ,n-1}；③密鑰K= (K1,K2)。

加密過(guò)程encrypt：輸入明文整數(shù)M，執(zhí)行type-2 Feistel網(wǎng)絡(luò)加密過(guò)程。圖 3描述了k= 4時(shí)使用type-2 Feistel網(wǎng)絡(luò)加密的Enc_Feistel算法。

圖3 Enc_Feistel算法

Enc_Feistel算法將輸入整數(shù)X表示為二進(jìn)制形式Xbin，并均勻分割為，如果|Xbin|位數(shù)不足，則以0填充，然后執(zhí)行r輪運(yùn)算，以加密二進(jìn)制串最后返回的十進(jìn)制形式作為算法輸出。

單純Feistel網(wǎng)絡(luò)只適用于加密二進(jìn)制符號(hào)串，可通過(guò)結(jié)合cycle-walking方法確保二進(jìn)制輸出最終落在指定整數(shù)集內(nèi)，以解決任意整數(shù)集上的FPE問(wèn)題。結(jié)合cycle-walking的整個(gè)加密過(guò)程如圖4所示。

圖4 基于type-2 Feistel網(wǎng)絡(luò)的整數(shù)FPE方案

解密過(guò)程 decrypt：類似于 encrypt，將整數(shù)密文Y編碼為二進(jìn)制數(shù)后，進(jìn)行基于type-2 Feistel網(wǎng)絡(luò)的解密，并結(jié)合cycle-walking，直到有合法明文輸出為止。

3.3 偽隨機(jī)函數(shù)構(gòu)造

Type-2 Feistel網(wǎng)絡(luò)的效率主要取決于采用的偽隨機(jī)函數(shù)，設(shè)計(jì)安全高效的偽隨機(jī)函數(shù)是構(gòu)造基于type-2 Feistel網(wǎng)絡(luò)FPE密碼的關(guān)鍵。上節(jié)提出的FPE方案將采用截?cái)鄠坞S機(jī)置換輸出的方式構(gòu)造偽隨機(jī)函數(shù)。

如圖5所示，在采用截?cái)鄠坞S機(jī)置換的構(gòu)造方式中，首先將輸入串X和調(diào)整因子t填充為適應(yīng)偽隨機(jī)置換分組長(zhǎng)度的二進(jìn)制向量Vector，不足分組長(zhǎng)度時(shí)以0填充，然后基于密鑰K使用偽隨機(jī)置換加密Vector（這里i=1或2），最后根據(jù)所需位數(shù)截?cái)嗉用芙Y(jié)果。

圖5 偽隨機(jī)函數(shù)構(gòu)造算法

需要指出的是：①在偽隨機(jī)函數(shù)構(gòu)造中引入調(diào)整因子，以保證每一輪使用的偽隨機(jī)函數(shù)不同(如圖5所示，可將當(dāng)前輪次數(shù)作為偽隨機(jī)函數(shù)調(diào)整因子輸入)；②采用的偽隨機(jī)置換 PRP可以是任意安全的對(duì)稱分組密碼(例如DES、AES等)，但PRP分組長(zhǎng)度必須不小于偽隨機(jī)函數(shù)輸入輸出規(guī)模，如果待構(gòu)造的偽隨機(jī)函數(shù)輸入輸出規(guī)模超過(guò)一個(gè) PRP分組長(zhǎng)度，只能通過(guò)增加type-2 Feistel網(wǎng)絡(luò)子分組個(gè)數(shù)，將大規(guī)模偽隨機(jī)函數(shù)的構(gòu)造分散為構(gòu)造多個(gè)小規(guī)模偽隨機(jī)函數(shù)。

3.4 安全性分析

2002年，Black和Rogaway[5]首次提出保留格式加密標(biāo)準(zhǔn)安全目標(biāo)，即偽隨機(jī)置換安全。FPE本質(zhì)是特定消息空間內(nèi)的偽隨機(jī)置換。

2011年，文獻(xiàn)[19]總結(jié)保留格式加密的相關(guān)攻擊模型和安全目標(biāo)，指出FPE是一種特殊的對(duì)稱密碼，其安全性歸約為采用基礎(chǔ)模塊的安全性。

本文提出的 FPE方案基礎(chǔ)模塊包括：①type-2 Feistel網(wǎng)絡(luò)，用于構(gòu)造分組長(zhǎng)度略大于logn的分組密碼(這里n為待加密消息空間大小)；②cycle-walking，用于保證分組密碼最終輸出在可接受范圍內(nèi)。鑒于文獻(xiàn)[16]對(duì)type-2 Feistel網(wǎng)絡(luò)超越生日邊界安全性的結(jié)論以及文獻(xiàn)[5]和文獻(xiàn)[3]關(guān)于 cycle-walking不會(huì)降低密碼安全性的分析，因此，基于type-2 Feistel網(wǎng)絡(luò)構(gòu)建的整數(shù)FPE方案是安全的。

3.5 效率分析

Type-2 Feistel網(wǎng)絡(luò)每一輪加密的時(shí)間消耗包括：①將輸入劃分成k個(gè)長(zhǎng)度為m位子分組的時(shí)間tsplit(不失一般性，這里始終假設(shè)k= 4)；②偽隨機(jī)函數(shù)作用子分組的時(shí)間tcompute；③連接各子分組形成下一輪輸入或最終密文的時(shí)間tjoint。如果采用的輪次數(shù)為r，則type-2 Feistel網(wǎng)絡(luò)加密總耗時(shí)TFeistel=tsplit+ 2rtcompute+tjoint。

為確保type-2 Feistel網(wǎng)絡(luò)加密結(jié)果最終輸出在可接受范圍內(nèi)，需結(jié)合cycle-walking方法。其中，每次迭代結(jié)果屬于指定整數(shù)集的概率與該整數(shù)集大小和基于type-2 Feistel網(wǎng)絡(luò)的密碼分組長(zhǎng)度相關(guān)。

如果待加密消息空間為n?，所采用密碼分組長(zhǎng)度為N。假設(shè)type-2 Feistel網(wǎng)絡(luò)構(gòu)造的密碼為理想分組密碼(即對(duì)任意明文加密，其密文為消息空間任意點(diǎn)的概率都相同)，那么每一次迭代輸出結(jié)果落入n?的概率約為

通常情況下，為使概率值p盡可能大，可根據(jù)待加密消息空間大小構(gòu)造合適寬度的Feistel網(wǎng)絡(luò)。此時(shí) type-2 Feistel網(wǎng)絡(luò)的寬度應(yīng)為不小于且能被k整除的整數(shù)，因此各子分組寬度為整個(gè)type-2 Feistel網(wǎng)絡(luò)寬度(這里表示不小于x的最小整數(shù))。

需要指出的是，雖然能夠通過(guò)構(gòu)造合適寬度的Feistel網(wǎng)絡(luò)，在一定程度上降低迭代次數(shù)，但是，由于每一次迭代輸出結(jié)果落入n?的概率為，因此，應(yīng)在偽隨機(jī)函數(shù)構(gòu)造許可的情況下，盡可能使用較少子分組數(shù)目；是方案最壞情況，此時(shí)每次迭代輸出屬于n?的近似概率為

根據(jù)以上分析，應(yīng)用所提方案處理n?上的FPE問(wèn)題，在n略大于 2sk時(shí)，效率較低。事實(shí)上，目前基于Feistel網(wǎng)絡(luò)的整數(shù)FPE方案均存在上述缺陷，在任意整數(shù)集上探索無(wú)需結(jié)合cycle-walking的高效FPE方案仍為開(kāi)放性問(wèn)題。

4 實(shí)驗(yàn)

以雪崩準(zhǔn)則作為加密算法實(shí)際安全性指標(biāo)，對(duì)比分析各種分組長(zhǎng)度下，type-2 Feistel網(wǎng)絡(luò)與當(dāng)前FPE方案中其他 Feistel網(wǎng)絡(luò)達(dá)到雪崩準(zhǔn)則所需Feistel輪次數(shù)和時(shí)間開(kāi)銷(xiāo)。

4.1 雪崩準(zhǔn)則

分組密碼設(shè)計(jì)目的在于通過(guò)提供足夠混淆和擴(kuò)散特性，以抵抗對(duì)手針對(duì)密碼體制的統(tǒng)計(jì)分析。混淆和擴(kuò)散對(duì)密文的影響可用雪崩準(zhǔn)則衡量：如果一種密碼滿足雪崩準(zhǔn)則，那么在任何時(shí)候，改變其輸入比特串中某一位，將會(huì)致使至少一半輸出比特發(fā)生改變[20]，其數(shù)學(xué)定義如下。

定義1E為分組長(zhǎng)度為N的分組密碼，如果對(duì)于任意密鑰K和明文X1≠X2但|X1|=|X2|，都有

成立，那么E滿足雪崩準(zhǔn)則。這里，dist(·,·)為漢明距離，Exp(·)為期望。

4.2 達(dá)到雪崩準(zhǔn)則的Feistel網(wǎng)絡(luò)輪次數(shù)分析

實(shí)驗(yàn)環(huán)境為：CPU為Intel(R) Core 2 Quad，主頻 2.66GHz，內(nèi)存 3GB。測(cè)試的分組長(zhǎng)度為128～512bit，并規(guī)定：①對(duì)于每種分組長(zhǎng)度，隨機(jī)產(chǎn)生密鑰及該分組長(zhǎng)度下的明文A、B，這里A、B僅有一個(gè)比特不同；②采用AES作為基礎(chǔ)分組密碼構(gòu)造偽隨機(jī)函數(shù)。當(dāng)偽隨機(jī)函數(shù)規(guī)模要求小于128bit時(shí)，直接截?cái)嗝芪淖鳛楹瘮?shù)輸出；當(dāng)偽隨機(jī)函數(shù)規(guī)模要求大于128bit時(shí)，這種構(gòu)造是困難的，這里通過(guò)截?cái)?AES-CBC的密文來(lái)近似偽隨機(jī)函數(shù)；③分別使用 FFSEM(對(duì)應(yīng)平衡 Feistel網(wǎng)絡(luò))、FFX-1(對(duì)應(yīng)非平衡 Feistel網(wǎng)絡(luò))、FFX-2(對(duì)應(yīng)交互式Feistel網(wǎng)絡(luò))和type-2 Feistel網(wǎng)絡(luò)對(duì)A和B進(jìn)行加密，若存在100輪以內(nèi)運(yùn)算使該類型Feistel網(wǎng)絡(luò)達(dá)到雪崩準(zhǔn)則，表明成功，否則認(rèn)為失敗。

針對(duì)每種分組長(zhǎng)度和Feistel網(wǎng)絡(luò)類型，進(jìn)行了100次測(cè)試，并對(duì)成功達(dá)到雪崩準(zhǔn)則所需的平均輪次數(shù)以及成功次數(shù)進(jìn)行統(tǒng)計(jì)，實(shí)驗(yàn)數(shù)據(jù)如表2所示。

表2 Feistel網(wǎng)絡(luò)成功達(dá)到雪崩準(zhǔn)則時(shí)平均輪次數(shù)

由表2可知如下內(nèi)容。

1) FFSEM的平衡Feistel網(wǎng)絡(luò)在128～256bit分組長(zhǎng)度范圍內(nèi)，只需較少輪次數(shù)，然而分組長(zhǎng)度超過(guò)256bit時(shí)，需構(gòu)造128bit以上的偽隨機(jī)函數(shù)，此時(shí)采用的截?cái)郃ES-CBC密文方式，達(dá)成的效果明顯不如基于AES的截?cái)喾椒?，因此造成失敗次?shù)增加。但隨分組長(zhǎng)度繼續(xù)增加，成功次數(shù)略有回升，說(shuō)明采用AES-CBC密文截?cái)喾绞綐?gòu)造的近似偽隨機(jī)函數(shù)，隨著單個(gè)分組長(zhǎng)度范圍內(nèi)構(gòu)造的函數(shù)規(guī)模的增加，隨機(jī)性也會(huì)緩慢提升，但仍達(dá)不到要求。

2) FFX-1的非平衡Feistel網(wǎng)絡(luò)(這里采用3:2非平衡劃分)在128～192bit分組長(zhǎng)度范圍內(nèi)，采用直接截?cái)郃ES的方式構(gòu)造偽隨機(jī)函數(shù)，較少輪次即可達(dá)到雪崩準(zhǔn)則。然而，當(dāng)分組長(zhǎng)度為224bit時(shí)，需通過(guò)AES-CBC密文截?cái)鄻?gòu)造具有90bit輸入和134bit輸出的偽隨機(jī)函數(shù)，近似構(gòu)造方式導(dǎo)致的較低隨機(jī)性嚴(yán)重影響Feistel網(wǎng)絡(luò)效率。其后，F(xiàn)eistel網(wǎng)絡(luò)成功率和輪次效率逐漸提升是因?yàn)镕FX-1采用擴(kuò)張的偽隨機(jī)函數(shù)(輸入寬度小于輸出寬度)，隨分組長(zhǎng)度增加，擴(kuò)張效果愈發(fā)明顯，一定程度降低了不良偽隨機(jī)函數(shù)的影響。

3) FFX-2的交互式Feistel網(wǎng)絡(luò)(這里采用3:2非平衡劃分)在128～192bit范圍內(nèi)具有較高輪次效率。由于與FFX-1相同的原因，并且FFX-2在偶數(shù)輪次采用壓縮的偽隨機(jī)函數(shù)(輸入寬度大于輸出寬度)，在224～320bit范圍內(nèi)，輪次效率降至最低。其后，隨偽隨機(jī)函數(shù)規(guī)模的增加，效率和成功率緩慢提升。但分組長(zhǎng)度為448bit時(shí)，偶數(shù)輪次需構(gòu)造具有268bit輸入和 180bit輸出的偽隨機(jī)函數(shù)，采用AES-CBC密文截?cái)喾绞?，可能造成碰?不同輸入被映射為相同輸出)，效率極低。

4) Type-2 Feistel網(wǎng)絡(luò)在整個(gè)分組長(zhǎng)度范圍內(nèi)，均可采用AES直接截?cái)嗟姆绞綐?gòu)造偽隨機(jī)函數(shù)，所需輪次數(shù)和成功率都具有穩(wěn)定性。

由以上分析可知，目前較大規(guī)模偽隨機(jī)函數(shù)很難構(gòu)造，AES-CBC無(wú)法達(dá)到真正偽隨機(jī)性，導(dǎo)致FFSEM和FFX-2效果不佳；FFX-1采用擴(kuò)張的偽隨機(jī)函數(shù)，一定程度上降低了不良偽隨機(jī)函數(shù)的影響，但在224～288bit范圍內(nèi)，所需偽隨機(jī)函數(shù)規(guī)模剛好超過(guò)一個(gè)AES分組長(zhǎng)度，輪次效率和成功率仍然較低；type-2能夠使用較小規(guī)模偽隨機(jī)函數(shù)應(yīng)對(duì)較大分組長(zhǎng)度范圍內(nèi)數(shù)據(jù)加密的情況，具有廣泛實(shí)用性。

4.3 達(dá)到雪崩準(zhǔn)則的Feistel網(wǎng)絡(luò)效率分析

由于FFSEM和FFX-2在分組長(zhǎng)度較大時(shí)失敗幾率較高，其輪次數(shù)無(wú)法真正說(shuō)明問(wèn)題，因此這里將僅對(duì)FFX-1和type-2完成不同分組長(zhǎng)度下數(shù)據(jù)加密的時(shí)間開(kāi)銷(xiāo)進(jìn)行對(duì)比分析。

實(shí)驗(yàn)規(guī)定如4.2節(jié)，這里只測(cè)試FFX-1和type-2成功達(dá)到雪崩準(zhǔn)則時(shí)，消耗的平均時(shí)間。需要指出的是，這里的時(shí)間消耗包括2部分：①對(duì)隨機(jī)產(chǎn)生的樣例A和B進(jìn)行Feistel輪運(yùn)算加密消耗的時(shí)間；②每一輪加密結(jié)束后，比較輸出結(jié)果與原始明文間比特位差異消耗的時(shí)間。

圖6對(duì)比了FFX-1和type-2成功達(dá)到雪崩準(zhǔn)則的時(shí)間效率（當(dāng)分組長(zhǎng)度為224bit時(shí)，使用FFX-1的100組樣例，在100輪運(yùn)算內(nèi)均不能滿足雪崩準(zhǔn)則），其變化趨勢(shì)由4.2節(jié)討論的輪次數(shù)決定，這里不再詳述。需要指出的是，分組長(zhǎng)度在128～208bit范圍內(nèi)，F(xiàn)FX-1和type-2都采用直接AES截?cái)喾绞綐?gòu)造，但FFX-1每一輪只需調(diào)用一次偽隨機(jī)函數(shù)，而type-2需調(diào)用2次，因此，F(xiàn)FX-1在較短分組長(zhǎng)度情況下，效率優(yōu)于type-2。

圖6 Feistel網(wǎng)絡(luò)成功達(dá)到雪崩準(zhǔn)則時(shí)的時(shí)間消耗

由以上分析可知，F(xiàn)FX-1存在224～304bit的低效范圍，而且效率具有嚴(yán)重的不穩(wěn)定性。type-2 Feistel網(wǎng)絡(luò)在整個(gè)分組長(zhǎng)度范圍內(nèi)都能穩(wěn)定地在2ms內(nèi)達(dá)到雪崩準(zhǔn)則，具有較高效率。

5 結(jié)束語(yǔ)

本文關(guān)注當(dāng)前FPE方案中Feistel網(wǎng)絡(luò)的適用性，從Feistel網(wǎng)絡(luò)類型、偽隨機(jī)函數(shù)構(gòu)造方式以及輪次數(shù)與安全性的關(guān)系，分析了Feistel網(wǎng)絡(luò)在FPE中應(yīng)用現(xiàn)狀。

目前FPE中Feistel網(wǎng)絡(luò)都為2-分割，對(duì)偽隨機(jī)函數(shù)要求較高，不能適應(yīng)于構(gòu)造靈活分組長(zhǎng)度的FPE密碼。針對(duì)此問(wèn)題，提出基于k-分割的type-2 Feistel網(wǎng)絡(luò)的FPE方案，該方案結(jié)合cycle-walking能夠解決任意整數(shù)集上的FPE問(wèn)題。但是，也指出在結(jié)合cycle-walking時(shí)，最壞情況下每一次迭代輸出落入n?的概率大約只有(這里k為 type-2 Feistel網(wǎng)絡(luò)劃分的子分組個(gè)數(shù))，效率較低。

基于Feistel網(wǎng)絡(luò)的FPE方案，核心在于Feistel網(wǎng)絡(luò)，由于Feistel網(wǎng)絡(luò)的不同，使其具有不同適用性。通過(guò)實(shí)驗(yàn)對(duì)比各種Feistel網(wǎng)絡(luò)達(dá)到雪崩準(zhǔn)則所需輪次數(shù)和時(shí)間開(kāi)銷(xiāo)，發(fā)現(xiàn) type-2 Feistel網(wǎng)絡(luò)在128～512bit分組長(zhǎng)度范圍內(nèi)均可采用AES直接截?cái)嗟姆绞綐?gòu)造偽隨機(jī)函數(shù)，具有較高成功率和穩(wěn)定的效率，從而驗(yàn)證了基于 type-2 Feistel網(wǎng)絡(luò)構(gòu)造的FPE方案具有廣泛的實(shí)用性。

[1] SPIES T. Format preserving encryption. unpublished white paper[EB/OL]. http://www.voltage.com, 2008.

[2] RADHAKRISHNAN R, KHARRAZI M, MEMON N. Data masking:a new approach for steganography[J]. Journal of VLSI Signal Processing, 2005, 41(3):293-303.

[3] BELLARE M, RISTENPART T, ROGAWAY P,et al. Format- preserving encryption[A]. Selected Areas in Cryptography 16th Annual International Workshop, SAC 2009[C]. Springer, Lecture Notes in Computer Science, 2009. 295-312.

[4] STUTZ T, UHL A. Efficient format-compliant encryption of regular languages: block-based cycle-walking[A]. 11th IFIP TC 6/TC 11 International Conference[C]. Springer, Lecture Notes in Computer Science, 2010. 81-92.

[5] BLACK P, ROGAWAY P. Ciphers with arbitrary finite domains[A].Topics in Cryptology-CT-RSA’02[C]. 2002. 114-130.

[6] SPIES T. Feistel finite set encryption mode[EB/OL]. http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-s pec.pdf.

[7] BELLARE M, ROGAWAY P, SPIES T. The FFX mode of operation for format-preserving encryption[EB/OL]. http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffx/ffx-spec.pdf.

[8] BELLARE M, ROGAWAY P, SPIES T. Addendum to the FFX mode of operation for format-preserving encryption[EB/OL]. http://csrc.ncsl.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffx/ ffx-spec2.pdf.

[9] BRIER E, PEYRIN T, STERN J. BPS: a format-preserving encryption proposal[EB/OL]. http://brutus.ncsl.nist.gov/groups/ST/ tookit/BCM/documents/proposedmodes/bps/bps-spec.pdf.

[10] CANDA V, TRUNG T. Scalable block ciphers based on Feistel-like structure[J]. Tara Mt Math Publ, 2002, 25: 39-66.

[11] 劉哲理, 賈春福, 李經(jīng)緯. 保留格式加密模型研究[J]. 通信學(xué)報(bào),2011, 32(6): 184-190.LIU Z L, JIA C F, LI J W. Research on format-preserving encryption modes[J]. Journal on Communications, 2011, 32(6): 184-190.

[12] HALL C, WAGNER D, KELSEY J,et al. Building PRFs from PRPs[A]. LNCS 1462: Fast Software Encryption[C]. Berlin: Springer,1998. 370-389.

[13] LUBY M, RACKOFF C. How to construct pseudorandom permutations from pseudorandom functions[J]. SIAM Journal on Computing,1988, 17(2): 373-386.

[14] PATARIN J. Pseudorandom permutations based on the DES scheme[A].LNCS 514: Eurocode’90[C]. Berlin: Springer, 1990. 193- 204.

[15] PATARIN J. Security of random Feistel schemes with 5 or more rounds[A]. LNCS 3152: 24th Annual International Cryptology Conference[C]. Berlin: Springer, 2004. 135-158.

[16] HOANG T, ROGAWAY P. On generalized Feistel networks[A].LNCS 6223: 30th Annual International Cryptology Conference[C].Berlin: Springer, 2010. 613-630.

[17] IBRAHIM S, MAAROF M, IDRIS N. Avalanche analysis of extended Feistel network[EB/OL]. http://eprints.utm.my/3258/1/Subariah_PARS05.pdf.

[18] IBRAHIM S, MAAROF M. Diffusion analysis of a scalable Feistel network[A]. Proceeding of 3rd World Enformatika Conference, Istanbul[C]. 2005.98-101.

[19] 劉哲理, 賈春福, 李經(jīng)緯. 保留格式加密技術(shù)研究[J]. 軟件學(xué)報(bào).2012,23(1):152-170.LIU Z L, JIA C F, LI J W. Research on format-preserving encryption techniques[J]. Journal of Software, 2012,23(1):152-170.

[20] HEYS H, TAVARES S. Avalanche characteristics of substitution permutation encryption networks[J]. IEEE Transactions on Computer,44(9): 1131-1139.