SM4-FPE:基于SM4的數(shù)字型數(shù)據(jù)保留格式加密算法

陳 佳,彭長根,樊玫玫,丁紅發(fā) ,趙園園

1(貴州大學 數(shù)學與統(tǒng)計學院, 貴陽 550025)2(貴州大學 公共大數(shù)據(jù)國家重點實驗室, 貴陽 550025)3(貴州大學 計算機科學與技術學院, 貴陽 550025)4(貴州財經(jīng)大學 信息學院, 貴陽 550025)

1 前 言

互聯(lián)網(wǎng)時代,海量化和多樣化等特點的數(shù)值型敏感數(shù)據(jù)應用極為廣泛,例如身份證號、社保號等.傳統(tǒng)的加密方法對數(shù)值型敏感數(shù)據(jù)進行加密,通常會改變數(shù)據(jù)長度和數(shù)據(jù)類型等,使原數(shù)據(jù)庫存儲單元無法直接存儲密文結果,應用程序無法正確讀取和顯示,降低了加密結果的利用率,且易引發(fā)隱私泄露.

保留格式加密(Format-Preserving Encryption, FPE)因其可在加密明文的同時保證密文與明文格式一致,已成為密碼學和隱私保護領域的一個新興分支.2002年,Black和Rogawa[1]最早以分組加密算法分組長度為基礎,提出了基于整數(shù)域上的保留格式加密算法,其加密結果依賴明文長度和填充長度,實用性和效率不佳.以此算法的Cycle-Walking和Generalized-Feistel思想為基礎,Spies等1提出基于平衡Feistel構建的FFSEM模型;Bellare等提出了通用模型RtE[2],即排序后加密的方法,并改進提出了基于非平衡Feistel的FFX模型2;劉哲理等人[3]基于RtE模型提出對日期的保留格式加密算法;之后Brier等3對FFX進行了改進,提出BPS模型;FF3算法[4]在FFX模型的基礎上,基于Feistel結構,引入調整因子,使加密變得更加靈活;Bellare等[5]在CCS2017上提出了基于身份的保形加密算法;Durak等[6]在CRYOTO 2017上針對FF3提出保形加密算法進行攻擊;Hoang等人[7]在CRYOTO 2018上提出基于Feistel網(wǎng)絡的保形加密算法的已知明文消息恢復攻擊;在實際應用中,Zou等人[8]基于Prefix算法實現(xiàn)對中文名字進行保形加密等.現(xiàn)有保留格式加密方案大多基于Feistel結構設計,這些算法主要在基礎分組密碼算法上利用Feistel結構的輪運算(如圖1和圖2所示[2]),并改造F函數(shù),達到保留格式的加密目的.FFSEM模型在使用Cycle-Walking中需多次調用基礎分組密碼,降低加密效率;RtE模型中的效率主要取決于消息空間的排序算法的效率,存在不確定的性能問題等.可見,現(xiàn)有保留格式加密算法多以國際分組密碼算法標準為基礎設計,且對Cycle-Walking方法具有過高依賴性,對效率和安全性都造成了影響.

2Bellare M,Rogaway P,Spies T,The FFX mode of operation for format-preserving encryption.2010.http://www.csrc.nist..gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffx/ffx/-spec.pdf.

3Brier E,Peyrin T,Stern J.BPS:a Format-Preserving Encryption Proposal.2010.http://csrc.nist.gov/groups/ST/toolkit/BCM/docume-nts/proposedmodes/bps/bps-spec.pdf.

圖1 平衡Feistel結構圖Fig.1 Structure of balanced Feistel

圖2 非平衡Feistel結構圖Fig.2 Structure of unbalanced Feistel

SM4算法[9]是國家分組密碼算法標準GB/T 32907- 2016[10],在密碼技術應用推廣中正逐步取代DES、AES[11]等算法.SM4算法設計簡潔,安全高效,可以抵抗目前已知的攻擊,擁有足夠的安全冗余度[12].本文針對保留格式加密算法的上述問題,以國家分組密碼標準算法SM4為基礎,提出一種面向數(shù)字型敏感數(shù)據(jù)的保留格式加密算法,實現(xiàn)數(shù)據(jù)的機密性和隱私性.首先對數(shù)字型特征數(shù)據(jù)進行分段處理,根據(jù)分段長度的奇偶性,基于SM4加密和截取構造F函數(shù),對分段后的明文進行平衡/非平衡Feistel結構進行輪運算和取模運算,最后對Feistel結構運算加密結果進行校驗,得到數(shù)字型特征數(shù)據(jù)的密文.該算法有效地實現(xiàn)了對數(shù)字型特征數(shù)據(jù)加密前后格式的一致性,實現(xiàn)了SM4算法向保留格式加密算法的擴展,增強了SM4的應用性;相較于現(xiàn)有保留格式加密算法,該算法降低了Cycle-Walking的使用,提高了加密效率和性能;安全性證明也表明,該算法安全性與SM4算法安全性相當,具有較好的安全性.

2 基于SM4的保留格式加密算法

數(shù)字特征數(shù)據(jù)[13]除了具有基本數(shù)據(jù)類型的性質,還具有特定的自定義數(shù)據(jù)的完整性和約束性,例如身份證號碼、社保號碼及電話號碼等.一般,這類數(shù)據(jù)可以分成若干的子集,每個子集都具有某些特定的構造規(guī)則.S為特征數(shù)據(jù),S可以分成n個數(shù)據(jù)段,Si為子集,則有:

(1)

所以無法有效地直接使用基本數(shù)據(jù)類型保留格式加密算法對其加密.本文利用分段加密的思想,根據(jù)分段數(shù)的奇偶性,結合平衡Feistel和非平衡Feistel結構,實現(xiàn)對特征數(shù)據(jù)進行安全防護的保留格式加密算法.該算法的工作流程如下.

2.1 明文加密

Step1.將特征數(shù)據(jù)P劃分成m個數(shù)據(jù)段，即P=P1‖P2‖…‖Pm，|Pj|表示Pj的長度m，Yj為此時的Pj所對應的值域，Yj={yj1,yj2,…,yjSj}，Sj為Yj所含元素的個數(shù)(j=1,…,m).

Step2.判斷m奇數(shù)或偶數(shù).若m為偶數(shù)，進行Step 3；若m為奇數(shù)，則進行Step 4.其中，構造F函數(shù)PRF=trunc(SM4K(T)，r)，表示為：輸入數(shù)字連接形成的字符串T，用密鑰K和國密SM4算法進行加密，得到的結果轉化為十六進制，然后最高位截取前r位.

Step3.當m為偶數(shù)時，輸入平衡Feistel結構：L0=P1‖…‖Pm/2，R0=Pm/2+1‖…‖Pm，進行r(r為偶數(shù))輪輪運算.第i(i=1,…,r)輪的運算過程：

1)當i為奇數(shù)時

Li=Ri-1

Ri=Li-1⊕F(Ri-1,Ki)

=Li-1⊕trunc(SM4Ki(Ri-1),|Li-1|)

=P1‖…‖Pm/2⊕(Z1‖…‖Zm/2)

=y1，1+(P1-y1，1+Z1)modS1‖…

…‖ym/2,1+(Pm/2-ym/2，1+Zm/2)modSm/2

(2)

得出奇數(shù)輪的輸出結果為Li=P1‖…‖Pm/2，Ri=Pm/2+1‖…‖Pm，其中P1∈Ym/2+1,…,Pm/2∈Ym，Pm/2+1∈Y1，…,Pm∈Ym/2，|Zj|=|Pj|.

2)當i為偶數(shù)且i≠r時，同理運用公式(2)；當i=r時，Li=Ri-1，Ri=Li-1即偶數(shù)輪的輸出結果為，Li=P1‖…‖Pm/2，Ri=Pm/2+1‖…‖Pm,其中P1∈Y1,P2∈Y2,…,Pm∈Ym.

Step4.當m為奇數(shù)時，輸入非平衡Feistel結構：L0=P1‖…‖P(m-1)/2，R0=P(m+1)/2‖…‖Pm(P1∈Y1,…,Pm∈Ym)，進行r(r為偶數(shù))輪輪運算.第i(i=1,…,r)輪的運算過程：

1)當i為奇數(shù)時

Li=Ri-1

Ri=Li-1⊕F(Ri-1,Ki)

=Li-1⊕trunc(SM4Ki,|Li-1|)

=P1‖…‖P(m-1)/2⊕(Z1‖…‖Z(m-1)/2)

=y1，1+(P1-y1，1+Z1)modS1‖…‖y(m-1)/2,1

+(P(m-1)/2-y(m-1)/2，1+Z(m-1)/2)modS(m-1)/2

(3)

得出奇數(shù)輪的輸出結果Li=P1‖…‖P(m+1)/2，Ri=P(m+1)/2+1‖…‖Pm，其中P1∈Y(m+1)/2,…,P(m+1)/2∈Ym，P(m+1)/2+1∈Y1,…,Pm∈Y(m-1)/2.

2)當i為偶數(shù)且i≠r時

Li=Ri-1

Ri=Li-1⊕F(Ri-1,Ki)

=Li-1⊕trunc(SM4Ki(Ri-1),|Li-1|)

=P1‖…‖P(m+1)/2⊕(Z1‖…‖Z(m+1)/2)

=y1，1+(P1-y1，1+Z1)modS1‖…‖y(m+1)/2,1

+(P(m+1)/2-y(m+1)/2，1+Z(m+1)/2)modS(m+1)/2

(4)

當i=r時，Li=Ri-1,Ri=Li-1.

得到偶數(shù)輪的輸出結果Li=P1‖…‖P(m-1)/2,Ri=P(m+1)/2+1‖…‖Pm,其中P1∈Y1,P2∈Y2,…,Pm∈Ym.

Step5.輸出結果及校驗.得到輸出結果C=Lr‖Rr，并檢驗其是否符合其特征數(shù)據(jù)的構造規(guī)則，若不符合，則重復Step 1-Step 4，直至符合，輸出密文.

2.2 密文解密

得到密文C=Lr‖Rr,Yj為此時的Pj所對應的值域,將其劃分成m個數(shù)據(jù)段,P1∈Y1,P2∈Y2,…,Pm∈Ym,解密流程如圖3所示,具體步驟如下：

Step1.判斷m奇數(shù)或偶數(shù).若m為偶數(shù),進行Step 2；若m為奇數(shù),進行Step 3.

Step2.當m為偶數(shù)時,輸入平衡Feistel結構：Lr=P1‖…‖Pm/2,Rr=Pm/2+1‖…‖Pm,進行r(r為偶數(shù))輪輪運算.第i(i=1,…,r)輪的運算過程：

1)當i為奇數(shù)時

Lr-i=Rr-i+1

Rr-i=Lr-i+1?F(Rr-i+1,Kr-i+1)

=Lr-i+1?trunc(SM4Kr-i+1(Rr-i+1),|Lr-i+1|)

=P1‖…‖Pm/2?(Z1‖…‖Zm/2)

=y1,1+(P1-y1,1-Z1)modS1‖…‖

ym/2,1+(Pm/2-ym/2,1-Zm/2)modSm/2

(5)

得出奇數(shù)輪的輸出結果為：Lr-i=P1‖…‖Pm/2,Rr-i=Pm/2+1‖…‖Pm,其中P1∈Ym/2+1,…,Pm/2∈Ym,Pm/2+1∈Y1,…,Pm∈Ym/2.

2)當i為偶數(shù)且i≠r時,同理運用公式(5)；當i=r時,Lr-i=Rr-i+1,Rr-i=Lr-i+1即偶數(shù)輪的輸出結果為：Lr-i=P1‖…‖Pm/2,Rr-i=Pm/2+1‖…‖Pm,其中P1∈Y1,P2∈Y2, …,Pm∈Ym.

圖3 算法解密流程Fig.3 Decryption process of algorithm

Step3.當m為奇數(shù)時,輸入非平衡Feistel結構：Lr=P1‖…‖P(m-1)/2,Rr=P(m+1)/2‖…‖Pm(P1∈Y1,…,Pm∈Ym),進行r(r為偶數(shù))輪輪運算.第i(i=1,…,r)輪的運算過程：

1)當i為奇數(shù)時

Lr-i=Rr-i+1

Rr-i=Lr-i+1?F(Rr-i+1,Kr-i+1)

=Lr-i+1?trunc(SM4Kr-i+1,|Lr-i+1|)

=P1‖…‖P(m-1)/2?(Z1‖…‖Z(m-1)/2)

=y1,1+(P1-y1,1-Z1)modS1‖…‖y(m-1)/2,1

+(P(m-1)/2-y(m-1)/2,1-Z(m-1)/2)modS(m-1)/2

(6)

得出奇數(shù)輪的輸出結果Lr-i=P1‖…‖P(m+1)/2,Rr-i=P(m+1)/2+1‖…‖Pm,Rr-i=P(m+1)/2+1‖…‖Pm,其中P1∈Y(m+1)/2,…,P(m+1)/2∈Ym,P(m+1)/2+1∈Y1…,Pm∈Y(m-1)/2.

2)當i為偶數(shù)且i≠r時

Lr-i=Rr-i+1

Rr-i+1=Lr-i+1?F(Rr-i+1,Kr-i+1)

=Lr-i+1?trunc(SM4Kr-i+1(Rr-i+1),|Lr-i+1|)

=P1‖…‖P(m+1)/2?(Z1‖…‖Z(m+1)/2)

=y1,1+(P1-y1,1-Z1)modS1‖…‖y(m+1)/2,1

+(P(m+1)/2-y(m+1)/2,1-Z(m+1)/2)modS(m+1)/2

(7)

當i=r時,Li=Ri-1,Ri=Li-1.

得到偶數(shù)輪的輸出結果Li=P1‖…‖P(m-1)/2,Ri=P(m+1)/2+1‖…‖Pm,Ri=P(m+1)/2+1‖…‖Pm,其中,P1∈Y1,P2∈Y2,…,Pm∈Ym.

Step4.輸出結果及校驗.

得到輸出結果C=L0‖R0,并檢驗其是否符合其特征數(shù)據(jù)的構造規(guī)則,若不符合,則重復Step 1-Step 3,直至符合,輸出明文.

3 算法正確性驗證及效率分析

3.1 算法正確性驗證

對數(shù)據(jù)型特征數(shù)據(jù)的保留格式加密算法的具體實驗,以電話號碼和身份證號為例進行加密.為說明加密過程,設定密鑰K=1593654782163214,Feistel結構的輪次數(shù)r=4(實際應用中需要大于此值)

3.1.1 實例1：電話號碼保留格式加密

1)對合法電話號碼的具體加密過程如下：

將P=18722793543劃分成三個部分：P1=187,P2=2279,P3=3543,P1,P2,P3所對應的值域分別為Y1={180,…,189},Y2={1000,…,9999},Y3={1000,…,9999},|P1|=3,|P2|=|P3|=4,|Y1|=10,|Y2|=|Y3|=9000將L0=187,R0=2279‖3543輸入非平衡Feistel結構進行輪運算

當r=1時,第一輪運算：

L1=R0=2279‖3543

R1=L0⊕F(R0,K)

=187⊕trunc(SM4K(R0),3)

=180+(187-180+0x774)mod10

=185

(8)

當r=2,第二輪運算

L2=R1=185

R2=L1⊕F(R1,K)

=2279‖3543⊕trunc(SM4K(R1),8)

=1000+(2279-1000+0x6649)mod9000

‖1000+(3543-1000+0x78CB)mod9000

=1464‖7466

(9)

當r=3,第三輪運算

L3=R2=1464‖7466

R3=L2⊕F(R2,K)

=185⊕trunc(SM4K(R2),3)

=180+(185-180+0xF8F)mod10

=188

(10)

當r=4,第四輪運算

L4=R3=188

R4=L3=1464‖7466

(11)

最終得到密文C=18814647466.

2)對所得密文C的解密具體過程如下：

將C劃分成三個部分P1=188,P2=1464,P3=7466,P1,P2,P3Y1,Y2,Y3,|P1|,|P2|,|P3|與加密時的數(shù)值一樣將L4=188,R4=1464‖7466輸入非平衡Feistel結構進行輪運算.

當r=1時,第一輪運算：

L3=R4=1464‖7466

R3=L4?F(R4,K)

=188?trunc(SM4K(R4),3)

=180+(188-180-0xF8F)mod10

=185

(12)

當r=2,第二輪運算

L2=R3=185

R2=L3?F(R3,K)

=1464‖7466?trunc(SM4K(R3),8)

=1000+(1464-1000-0x6649)mod9000

‖1000+(3543-1000-0x78CB)mod9000

=2279‖3543

(13)

當r=3,第三輪運算

L1=R2=2279‖3543

R1=L2?F(R2,K)

=185?trunc(SM4K(R2),3)

=180+(185-180-0x774)mod10

=187

(14)

當r=4,第四輪運算

L0=R1=187

R0=L1=2279‖3543

(15)

最終得到明文P=L0‖R0=18722793543

3.1.2 實例2:身份證號保留格式加密

1)對合法身份證號加密具體過程如下：

身份證P=370722198303091503劃分成六個部分：P1=370722,P2=1983,P3=03,P4=09,P5=150,P6=3,P1,P2,P3,P4,P5,P6所對應的值域分別為Y1={100000,…,999999},Y2={1900,…,2050},Y3={1,…,12},Y4={1,…,31},Y5={100,…,999},Y6={1,…,9,X}(X表示10),|P1|=6,|P2|=4,|P3|=|P4|=2,|P5|=3,|P6|=1,|Y1|=900000,|Y2|=151,|Y3|=12,|Y4|=31,|Y5|=900,|Y6|=10.將L0=370722‖1983‖03,R0=09‖150‖3,輸入平衡Feistel結構進行輪運算

當r=1時,第1輪運算：

L1=R0=09‖150‖3

R1=L0⊕F(R0,K)

=370722‖1983‖03⊕trunc(SM4K(R0),12)

=100000+(370722-100000+0x478F97)mod900000

‖1900+(1983-1900+0xB338)mod151

‖1+(03-1+0x35)mod12

=560537‖1959‖08

(16)

當r=2時,第2輪運算：

L2=R1=560537‖1959‖08

R2=L1⊕F(R1,K)

=09‖150‖3⊕trunc(SM4K(R1),6)

=1+(09-1+0x1C)mod31‖100+(150-100

+0x508)mod900‖1+(3-1+0xB)mod10

=06‖538|4

(17)

當r=3時,第3輪運算：

L3=R2=06‖538‖4

R3=L2⊕F(R2,K)

=560537‖1959‖08⊕trunc(SM4K(R2),12)

=100000+(560537-100000+0x5820D6)mod900000

‖1900+(1959-1900+0xBE2F)mod151‖1

+(08-1+0xB4)mod12

=936111‖2024‖08

(18)

當r=4,第4輪運算

L4=R3=936111‖2024‖08

R4=L3=06‖538‖4

(19)

最終得到密文C=936111202408065384

2)對所得密文C的解密具體過程與1)解密思想相同.

算法的驗證結果表明,基于SM4的數(shù)字型數(shù)據(jù)保留格式加密算法有效地實現(xiàn)了對數(shù)字型特征數(shù)據(jù)加密前后格式的一致性.

3.2 效率分析及特征對比

基于SM4的數(shù)字型數(shù)據(jù)保留格式加密算法將明文P分成m個數(shù)據(jù)段,輸入Feistel結構,保證每個數(shù)據(jù)段的加密結果仍然屬于原來所對應的值域,降低最后數(shù)據(jù)段連接形成的密文落入錯誤域的概率.保留格式加密的主要目的是加密敏感的數(shù)字或字符,一般長度較短,雖然本算法在每一輪運算過程都使用了SM4,加解密速率會有所降低,但是對于一般的數(shù)據(jù)并不會產生影響.

設數(shù)據(jù)加密一次落入正確域的概率為,最終得到合法的密文C的期望為E,其中所需要結合Cycle-Walking的次數(shù)為n.所以有：

當n=1時,密文C落入正確域的概率為1·P1；當n=2時,密文C落入正確域的概率為P1·(1-P1)；以此類推,第n次密文C落入正確域的概率為P1·(1-P1)n-1.也即有：

(20)

所以當密文落入正確域的概率較大時,期望值越小,也即加密效率越高.

本文提出的SM4-FPE算法與FFSEM算法1及FF3[4]算法都是基于Feistel結構的認證加密算法,三個算法從算法特征的基礎分組密碼算法、適用數(shù)據(jù)類型、密鑰長度、關鍵步驟、對Cycle-walking過程的依賴、效率幾方面對比,見表1,可見SM4-FPE具有優(yōu)勢.

表1 保留格式加密算法特征對比表
Table 1 Comparison of features for different format-
preserving encryption algorithms

FFSEM[2]FF3[7]SM4-FPE基礎分組密碼AESAES、DESSM4數(shù)據(jù)類型數(shù)字字母數(shù)字密鑰長度128bit128bit/64bit128bit關鍵步驟輪操作明文映射,調整因子,輪運算輪操作Cycle-Walking 依賴高一般依賴低效率低一般高

4 算法安全性證明

保留格式加密是一種特殊的對稱密碼,是在基礎模塊上建立起來的,對密碼的基礎模塊是偽隨機置換和偽隨機函數(shù),其安全性可以規(guī)約到基礎模塊的安全性上[14].2002年,Black和Rogaway[1]首次描述了保留格式加密的安全性,提出標準的安全目標就是PRP(Pseudorandom Permutation)安全.基于SM4的保留格式加密算法,其中偽隨機函數(shù)由SM4構造,輸入數(shù)字連接形成的字符串T,用密鑰k和國密SM4算法進行加密,得到的結果轉化為十六進制,然后最高位截取前r位.因為SM4的輪函數(shù)是一次一迭代運算,主要包括參數(shù)輸入、分組變換、非線性變換等操作,可以抵抗目前已知的所有攻擊,如差分密碼攻擊、線性密碼分析以及不可能差分分析等等,擁有足夠的安全冗余度.

定理1.基于SM4的保留格式加密算法(SM4-FPE)的安全性規(guī)約為SM4的安全性,即有:

(21)

所以該算法達到了PRP安全.

定理1表明所提出的保留格式加密算法安全性與SM4相當.

5 總 結

本文針對SM4分組密碼算法,提出了一種對數(shù)字型特征數(shù)據(jù)保留格式加密的算法,該算法利用分段思想,對明文進行Feistel結構輪運算和取模運算,在每輪輪運算中用SM4加密截斷實現(xiàn)F函數(shù)功能.該算法能夠對數(shù)值型明文進行保留格式加密,且安全性與SM4相當.比起傳統(tǒng)的基本類型數(shù)據(jù)保留格式加密算法,該算法不僅保留了數(shù)據(jù)的長度和基本特征,降低了中間過程密文落入錯誤域的概率,提高了算法效率.本算法對數(shù)字型特征數(shù)據(jù)的保留格式加密是具有意義的.

下一步繼續(xù)優(yōu)化該算法Feistel結構,并且探究如何對其它特征數(shù)據(jù)設計更高效和安全的保留格式加密算法.