面向數字型的輕量級保形加密算法研究

劉波濤 彭長根 吳睿雪 丁紅發 謝明明

1(貴州大學計算機科學與技術學院 貴陽 550025)2(中國電子科技集團大數據研究院有限公司 貴陽 550081)3(公共大數據國家重點實驗室(貴州大學) 貴陽 550025)4(貴州財經大學信息學院 貴陽 550025)

信息化時代，數字數據在生活當中是無處不在，例如身份證號、手機號、信用卡號及客戶號等都是數字重要的應用，而這些數據是包含了個人身份識別信息以及商業財產機密等，為了防止存儲在物聯網終端設備中這些有價值的數字數據被惡意攻擊者竊取利用，是需要對其進行加密處理來實現防護.

由于物聯網終端設備自身存在計算能力弱及存儲空間非常有限的特點[1]，而終端設備的數字型數據利用輕量級分組密碼(例如PRESENT[2]密碼、SKINNY[3]密碼、SFN[4]密碼等)直接加密保護，得到加密后的密文數據類型與長度發生變化，這些數據的結構改變導致數據無法存回終端設備，從而造成額外的成本開銷與損失.為了解決該問題，采用保形加密(format-preserving encryption, FPE)進行對數據加密保護，加密后的密文與明文具有相同的數據格式，從而不需要破壞終端設備數據存儲結構[5].

保形加密是一類新型、特殊的加密技術，廣泛應用于數據遮蔽領域，其相關的研究一直備受密碼學者的關注.從1981年就開始進行探索研究[6]，到2002年，由Black和Rogaway[7]提出FPE的基本模型與方法，并且也是首次給出了其安全性，所提出其中包括3種傳統型的算法：Prefix型算法，Cycle-Walking型算法和Generalized-Feistel型算法，其在一定程度上解決了整數上的FPE問題.隨后，Bellare等人[8]基于Cycle-Walking型算法進行了拓展，提出了一種基于非平衡Feistel網絡的整數FPE算法；Jia等人[9]基于Generalized-Feistel型算法，提出了一種基于Type-2 Feistel網絡的整數FPE算法；Bellare等人[10]在CCS 2017上提出了基于身份的保型加密算法.對于保形加密算法安全性分析而言，Bellare等人[11]在CCS 2016上提出基于Feistel網絡的保形加密算法的消息恢復攻擊，Durak等人[12]在CRYPTO 2017上針對FF3保形加密算法進行攻擊;Hoang等人[13]在CRYPTO 2018上提出基于Feistel網絡的保形加密算法的已知明文消息恢復攻擊;在實際應用中，Zou等人[14]實現將Prefix型保形加密算法進行加密保護中文名字等.

現有的保形加密算法中存在實現效率不高、資源較大的問題，而傳統的Prefix型保形加密算法相比其他傳統的Cycle-Walking型和Generalized-Feistel型保形加密算法操作過程簡單，對數據加解密操作速度較快，是一個良好的保形加密算法.但是傳統的Prefix型保形算法也有2方面的不足：1)利用傳統的高級加密標準(advanced encryption standard, AES)[15]分組密碼算法作為置換表的構建算法，從而造成置換表的建立會耗費大量時間與軟硬件資源，無法適用于物聯網終端設備.2)主要是進行實現整型字段的加密處理，從而無法很好地實現數字類型數據的加密；且在實現整型字段數據時，該方法也只能處理消息空間整數集小的數據，對常用的信用卡號、電話號碼、身份證號及各種驗證碼等較長的數字型數據不能夠很好保形加密處理.并且國內外尚未發現公開發表有關物聯網設備終端數據保形加密算法研究成果.

本文提出一種面向數字型的輕量級保形加密算法，先通過輕量級分組密碼算法構造數字型置換表，要加密數字型明文與輕量級分組密碼的加密密鑰進行一一對應相加、取模10操作，再進行數字型置換表置換加密操作，得到數字型密文數據.該算法做到了保持加密前后的數據格式不改變，實現了數據遮蔽，并且對任何長度的數字型數據，進行高效、安全的加密保護，節省了軟件實現的開銷與硬件實現的成本，對于保護物聯網終端設備數據存儲的安全，無疑具有重要意義.

1 PRESENT密碼

在2007年PRESENT輕量級分組密碼是由國際加密硬件與嵌入式系統國際會議上被提出的，成為了IOS-29192標準.在輕量級分組密碼中，PRESENT密碼的提出是一個里程碑性研究，該密碼高效的、低資源設計優點已被其后很多輕量級分組密碼所模仿與采用，例如GIFT密碼[16]與RECTANGLE密碼[17]，其S盒有良好的密碼特性，LED[18]與QTL[19]等多個密碼采用該S盒.

PRESENT密碼的分組長度是64 b，密鑰長度有80 b和128 b兩種，加密變換需要31輪迭代運算，采用SP(substitution-permutation)網絡結構，包含密鑰擴展函數(keySchedule)與加密輪函數，輪函數是輪密鑰加變換(addRoundKey)、S盒變換(sBoxLayer)及P置換(pLayer) 3個模塊構成，如圖1所示(⊕為異或符).

Fig. 1 The encryption process of PRESENT圖1 PRESENT加密流程圖

輕量級PRESENT密碼描述為：設64 b中間變量為state，80 b和128 b初始密鑰為k，64 b輪密鑰為rk.加密輪函數的3個模塊具體描述：

1) 輪密鑰加變換

輪密鑰加變換是state與rk一一異或運算操作：

(1)

2) S盒變換

S盒變換是將state劃分為16個4 b數據，每4 b數據經過一個4×4的S盒替換運算.

(2)

3) P置換

P置換變換是state進行每1 b移位運算操作，置換層的各比特通過公式置換(b代表每1 b)，該操作在硬件實現過程不需要消耗資源：

(3)

輪函數結構如圖2所示.

Fig. 2 The round function structure of PRESENT圖2 PRESENT密碼的輪函數結構

密鑰擴展函數具體描述為(以80 b密鑰為例)：

1) 循環移位變換

循環移位變換是k進行向左循環移61 b：

k←k<<<61.

(4)

2) 常數加變換

常數加變換是k進行異或一個5 b輪常數(round_count)：

k←k⊕round_count.

(5)

密鑰擴展函數中的S盒與加密輪函數共用一個S盒，而S盒替換只對80 b密鑰中4 b進行一次替換.

輕量級PRESENT密碼自被提出來，密碼學者一直對其進行一系列的安全分析，最新的PRESENT密碼分析結果如表1所示，經過10年的不斷的考驗，PRESENT密碼是滿足當前安全應用的需求.

Table 1 Results of Cryptanalysis of PRESENT表1 PRESENT密碼的攻擊分析

表1中攻擊類型：多維線性攻擊(multidimen-sional linear cryptanalysis, MLC)、截斷差分攻擊(truncated differential cryptanalysis, TDC)、FFT-多維線性攻擊(fast Fourier transform multidimen-sional linear cryptanalysis, FFT-MLC)、Biclique攻擊(Biclique cryptanalysis, BC).

2 構造面向數字型的輕量級保形加密算法

在構造新的保形加密算法中，效率和安全性永遠是值得探討和研究的，其保證算法的安全性條件下做到構建一個高效、低資源的保形加密算法.由于傳統的Prefix型保形加密算法相比其他Cycle-Walking型和Generalized-Feistel型保形加密算法更具有簡潔、高效的特點，本文將改進于傳統的保形Prefix型算法來實現一種高效、低資源的面向數字型保形加密算法.

對于數字型的數據，明文消息空間數據集為X=0,1,…,9，為了保持密文消息數據集與明文消息數據集相同，算法中構建的置換表的數據集也為X=0,1,…,9.一種高效、低資源的面向數字型保形加密算法的構造分為6個步驟進行實現：

1) 利用輕量級分組密碼加密

將0～9這10個數字加載至寄存器，利用輕量級分組密碼對這10個數字進行加密EP操作，輕量級分組密碼密鑰為k，得到元組I：

I=(EP(0,k),EP(1,k),…,EP(9,k)).

(6)

其中，每一個分量元組Ij=(EP(j,k))(0≤j≤9)，這些分量元組長度與輕量級分組密碼算法的分組長度相同，一般為64 b.

2) 元組數據排序

將步驟1中每一個分量元組Ij=(EP(j,k))進行二進制數從高位到低位大小判斷排序，得到一個數字型置換表序列T.

3) 明文相加、取模10

將明文M加載至寄存器中，M與輕量級分組密碼的加密密鑰進行一一對應相加、取模10操作：

(M+k) mod 10.

(7)

4) 明文加密置換

將步驟3運算的結果數據，進行步驟2得到的置換表置換操作，得到密文C，這個置換加密為ET，保形加密具體流程如圖3所示.

C=ET((M+k) mod 10).

(8)

5) 構造逆置換表

在正置換表的基礎上，構造一個逆的置換表用于解密密文，該逆置換表也是一個數字型置換表序列T-1.

6) 密文解密置換

將C先進行逆置換表置換操作，然后與輕量級分組密碼密鑰進行一一對應相減取模10運算，得到M，具體流程如圖4所示.

(9)

Fig. 3 The encryption process of lightweight format-preserving algorithm圖3 輕量級保形算法加密流程

Fig. 4 The decryption process of lightweight format-preserving algorithm圖4 輕量級保形算法解密流程

3 面向數字型的輕量級保形加密算法實現

一種高效、低資源的面向數字型保形加密算法的具體實現，構造置換表的輕量級分組密碼是采用第1節描述的PRESENT密碼.

首先將十進制(decimal, DEC)的0～9這10個整數用二進制4 b數據表示，并加載至寄存器，在寄存器中分別進行高位填補60個二進制數0，從而得到10個64 b數據，作為構造數字型置換表的待加密數據，如表2所示.

將填補后這10個64 b二進制數作為PRESENT密碼算法的10個待加密數據，選取PRESENT密碼的加密密鑰，選擇為PRESENT密碼的80 b密鑰長度，此次加密密鑰任選為十六進制(hexadecimal, HEX)的642A032F5010040760CB.將這10個待加密數據用這個加密密鑰分別進行PRESENT密碼加密操作，得到10個密文數據，將密文數據進行對應0～9數字大小的分布標記，這個分布序號標記列表作為一個數字型正置換表，如表3數據變換過程所示.

Table 2 The Supplement of Integer表2 整數填補數據表

Table 3 The Construction of Numeric Typed Permutation Table表3 數字型正置換表構造

從表3得到分布標記“1876249035”10個數字的序列，作為數字型正置換表T，如表4所示:

Table 4 The Numeric Typed Permutation Table表4 數字型正置換表

將要加密數字型明文數據加載至寄存器，在這里選取銀行卡號作為要加密數字型明文數據，銀行卡號為6212262402033357571.在應用設備當中，將要加密的真實銀行卡號數字數據與PRESENT輕量級分組密碼的加密密鑰(642A032F5010040760CB)進行一一對應相加、取模10運算操作，具體為

(6+6)%10=2，(2+4)%10=6，(1+2)%10=3，

(2+10)%10=2，(2+0)%10=2，(6+3)%10=9，

(2+2)%10=4，(4+15)%10=9，(0+5)%10=5，

(2+0)%10=2，(0+1)%10=1，(3+0)%10=3，

(3+0)%10=3，(3+4)%10=7，(5+0)%10=5，

(7+7)%10=4，(5+6)%10=1，(7+0)%10=7，

(1+12)%10=3.

當加密密鑰比要加密的真實數字型明文數據長，將取加密密鑰的對應前面部分數據；當加密密鑰比要加密的真實數字型明文數據短，首先選擇密碼算法那種較長的密鑰，如果那種較長的密鑰還是比加密的真實數字型明文數據短，則選擇較長的密鑰前后部分異或操作進行擴充數據，從而擴充到相加一一對應的密鑰長度，在實例當中，80 b加密密鑰比要加密的真實銀行卡數字數據長，進行舍棄最后一個為“11”數.

將一一對應相加、取模運算得到數字型數據為2632294952133754173，再一一進行數字型正置換表置換加密操作，例如數字“2”通過數字型正置換表置換為數字“7”，數字“6”通過數字型正置換表置換為數字“9”，依次進行全部置換操作，置換后，為了保證算法的安全，將數字型正置換表進行刪除操作，置換加密后得到，數字型密文數據為7967752547866 042806，該密文數據與真實的銀行卡號具有相同的數據類型，這樣完成了銀行卡號數據的加密保護.

進行加密后的數字型密文數據解密恢復操作，在構造數字型正置換表序列的基礎上來構造逆置換表序列，將數字型正置換表序號進行取反、重排操作，得到數字型逆置換表序列T-1，如表5所示：

Table 5 The Inverse Numeric Typed Permutation Table表5 數字型逆置換表

將加密后的數字型密文數據(79677525478 66042806)一一進行逆置換表置換恢復操作，例如，數字“7”通過數字型逆置換表置換為數字“2”，數字“9”通過數字型逆置換表置換為數字“6”，依次進行全部置換操作，置換后，為了保證算法的安全，將數字型逆置換表進行刪除操作，置換恢復得到數據為2632294952133754173.然后在應用設備當中，將置換恢復得到數據與PRESENT輕量級分組密碼的加密密鑰(642A032F5010040760CB)進行一一對應相減、取模10運算操作，具體為

(2-6)%10=6，(6-4)%10=2，(3-2)%10=1，

(2-10)%10=2，(2-0)%10=2，(9-3)%10=6，

(4-2)%10=2，(9-15)%10=4，(5-5)%10=0，

(2-0)%10=2，(1-1)%10=0，(3-0)%10=3，

(3-0)%10=3，(7-4)%10=3，(5-0)%10=5，

(4-7)%10=7，(1-6)%10=5，(7-0)%10=7，

(3-12)%10=1.

將一一對應相減、取模10運算得到數字型數據為6212262402033357571，加密后數字型密文數據得到恢復，恢復為真實數字型明文銀行卡號.

4 算法的安全性

設計新的加密算法時，算法安全性是首要進行考慮的.面向數字型的輕量級保形加密算法，其置換表的構造取決于輕量級分組密碼，而本保形加密算法的安全性是基于輕量級分組密碼本身的安全性，且構造過程中是不會降低輕量級分組密碼本身的安全性的，因此輕量級保形加密算法有著輕量級分組密碼的安全性，另外與密鑰相加、取模操作進一步提升了算法的安全.

本保形算法中采用輕量級PRESENT密碼進行構造置換表，輕量級PRESENT密碼自被提出來，密碼學者一直對其進行一系列的安全性分析，在文中第1節，已經給出了最新的輕量級PRESENT密碼相關安全性分析結果，也表明目前輕量級PRESENT密碼是足夠安全.對于保形Prefix型加密算法而言，構造的不同加解密置換表之間具有隨機性是確保保形加密算法本身的安全性.本保形加密算法的置換表構造過程中，將進行不同的置換表之間隨機性測試，在測試實驗中，輕量級PRESENT分組密碼進行加密及密文排序處理分析，只需改變1 b的加密密鑰，這1 b數據不同的加密密鑰對應得到的置換表之間元素差別是非常大，測試結果如表6所示，通過表6給出的數據可以證明了利用輕量級PRESENT密碼構造的置換表具有隨機性，表明PRESENT密碼構造置換表是安全的.

Table 6 The Randomness of Permutation Table表6 置換表的隨機性

對于傳統的保形Prefix型加密算法而言，其置換表中的元素是0～9這10個不同的數字時，從而這數字型置換表的空間是為10！=3628800，由于這個置換表的空間不是足夠大，從而明文容易被暴力攻擊成功.為了解決傳統的保形Prefix型算法存在的這個不足，本保形算法是對傳統的保形Prefix型算法進行了改進，該改進方法是保證保形加密算法高效性的前提下使得改進后的算法具有高安全性，具體改進為：在算法中添加了將保形加密的明文與輕量級PRESENT密碼的加密密鑰進行一一對應相加、取模10運算操作，利用輕量級PRESENT密碼的加密密鑰進行保形加密算法的2次控制作用，真正實現了在保形Prefix型加密算法中加密密鑰與保形加密明文的結合，從而進一步實現對保形加密的明文進行安全性保護.這種改進方法，在當密鑰不知道的情況下是可以保護保形加密的明文數據，在置換加密操作前進行了提前變換保護，以抵抗暴力攻擊明文.

定理1.當明文與密鑰對應相加、取模10操作，再經過置換表置換加密，保形Prefix型算法可以抵抗暴力攻擊.

證明. 設一個保形加密的明文為A，一個加密密鑰為B，一個運算后結果為C，則：

C=(A+B) mod 10，

(10)

其中，C是未知的(由于C的下一步操作是進行置換表加密操作，從而C數據是不進行公開)，加密密鑰B是進行嚴格保密，也是未知的，另外取模方程運算是包含多個解，因此暴力攻擊破解的計算復雜度到達103628800，暴力破解明文A變為一個求解困難性問題，保形Prefix型算法可以有效地抵抗暴力攻擊.

證畢.

另一方面，在保形Prefix型算法中，當輸入一串連續性的數字明文，通過置換表加密之后，加密后的結果也是會出現一串連續性的數字密文.例如設輸入一串連續的數字明文為0000000000，當置換表為“1876249035”進行加密情況下，則加密輸出的密文結果為1111111111，從而出現明顯的明文與密文之間關聯關系特征暴露給攻擊者，導致了保形加密算法安全性漏洞等問題.而這種保形加密的明文與輕量級PRESENT密碼的加密密鑰進行一一對應相加、取模10運算的方法，能夠有效防止保形Prefix型加密算法出現這個漏洞性的問題.因為保形加密的明文與輕量級的加密密鑰進行相加、取模10運算操作，是利用了加密密鑰與保形加密明文的結合，進行了加密密鑰的控制(實際應用設備要求用戶設置口令密碼不能簡單為一串連續性數字)，從而不會出現保形Prefix型算法的安全漏洞性問題.本保形加密算法的改進從這2個重要的方面保證算法的安全性，使設計的新保形加密算法具有很高的安全性能.

5 算法實現性能

面向數字型的輕量級保形加密算法，對于其軟硬實現性能，關鍵在于創建置換表的分組密碼選取，當置換表創建完成之后，接下來就是簡單地相加、取模10及置換表置換操作，這些簡單的運算操作對于整個保形加密算法實現性能影響是非常小的.本實驗的運行環境是處理器為Intel Core i3-3220 CPU @3.30 GHz，內存為8 GB，固態硬盤為500 GB，操作系統為Windows 7.

將算法進行C語言實現，在Microsoft Visual C++ 6.0軟件上進行運行、編譯.選擇一個整型數字0擴充為64 b構造數字型置換表的待加密數據“0000000000000000(HEX)”，通過PRESENT輕量級分組密碼進行加密，加密花費時間為0.001 s.將對應數字0～9這10個數字擴充為10個64 b構造數字型置換表的加密數據，通過PRESENT輕量級分組密碼進行加密，加密總需花費時間為0.01 s，由于對這10條密文進行大小分布標記不需要記錄花費時間，構造置換表所需的時間就為0.01 s.置換表構建創建之后，保形加密的明文數據進行與加密密鑰進行相加、取模10及進行置換表置換操作，這些操作花費時間是微不足道的，我們在實驗中對500條19位銀行卡數字與加密密鑰相加、取模10之后，再進行置換表(1876249035)置換運算，得到保形加密后的密文數據，花費的時間為0.001 s.通過軟件實驗測試，整個輕量級保形加密算法加密500條19位銀行卡數字需要花費時間為0.011 s，得出面向數字型的輕量級保形加密算法具有實現速度快的特點.

面向數字型的輕量級保形加密算法是采用PRESENT輕量級分組密碼構造置換表，而傳統的保形Prefix型算法是采用AES密碼構造置換表，分組密碼構造置換表是保形加密算法實現性能的關鍵之處.

軟件資源消耗方面，以下給出了PRESENT-80密碼與AES -128密碼在8 b處理器與32 b處理器軟件實現資源的比較結果，如表7所示.通過AES -128密碼與PRESENT-80密碼占用的ROM與RAM數據結果對比，從而使用PRESENT密碼構造置換表來實現保形加密，做到了保形加密軟件實現輕量化.

Table 7 Comparison of PRESENT-80 and AES -128 in Software Implementation表7 PRESENT-80密碼與AES -128密碼軟件資源對比

硬件資源消耗方面，在Xilinx ISE Design Suite 13.2平臺實現算法的FPGA測試，在Synopsys Design Compiler version B-2016.06平臺實現算法的ASIC測試.在進行FPGA測試實驗中，PRESENT-80密碼占用資源面積為10 265個Slices，而AES -128密碼占用資源面積為20 173個Slices，在進行ASIC測試實驗中，PRESENT-80密碼占用的面積資源為1 570個等效門(gate equivalents, GEs)及吞吐率為200 Kbps，而AES -128密碼占用面積資源為3 400個GEs及吞吐率為12.4 Kbps.在硬件測試中，PRESENT輕量級分組密碼相比AES密碼是具有低資源、高吞吐率的優點.輕量級保型加密算法在測試中，分別占用面積為12 101個Slices與1 912個GEs(小于RFID實現安全組件2 000個GEs)，而傳統的保形Prefix型加密算法占用資源分別為21 440個 Slices與3 628個GEs.輕量級保形加密算法相比傳統的保形Prefix型加密算法，在占用面積資源上縮減了一半左右.通過這些數據分析，使用PRESENT密碼構造置換表來實現保形加密，大大減少了加密硬件資源消耗.

在軟硬件實現過程中，相比基于AES密碼的傳統保形Prefix型加密算法，本算法基于PRESENT密碼實現了保形加密的輕量化，從而節省了軟件實現的開銷與硬件實現的成本，是能夠適用于物聯網終端設備數字型數據保形加密.

6 總 結

本文提出了一種面向數字型的輕量級保形加密算法，該算法是基于輕量級PRESENT分組密碼來進行構造置換表，相比傳統的保形Prefix型算法基于AES密碼構造置換表，在軟件平臺實現中節省了ROM與RAM軟件消耗的資源，在硬件平臺實現中降低了實現成本，同時提高了吞吐率.另外，在保證算法具有高效的前提下，本算法相比傳統的保形Prefix型算法，增加了與輕量級密碼加密密鑰一一對應相加、取模10運算，大大提高了算法的安全性，并且解決了傳統的保形Prefix型算法存在安全不足性的問題以及不能加密處理較長的數字型數據.在算法中，將輕量級PRESENT密碼換為其他輕量級分組密碼來構造置換表，也是可以達到較好的效果，所以本算法是具有通用價值.

未來進行探究保形加密算法中有關密鑰管理的問題以及如何設計更高效、低資源的輕量級保形加密算法在資源受限的物聯網設備終端進行運用.