保留格式加密的雙擾工作模式

張玉安，王 野，漆駿鋒，胡伯良

(1.北京海泰方圓科技股份有限公司，北京100094；2.電子科技大學，四川 成都611731)

0 引言

為防止一些敏感信息被偷窺，信息加密是一種較好的應對措施。但有些情形并不需要對大量明文進行加密，比如，有一些表格，每張表格上只有手機號、身份證號和電子郵箱地址等較為敏感，其他內容無需加密。如果將這些數字串或字符串用AES或者SM4 等分組密碼算法加密，需要按128 bit(16 B)數據組作分組處理，產生的密文是16 B，有些字節是不方便打印的。如果將16 B 密文轉換成十進制數字，一般會變為一個39 位數，不僅表格內寫不下，操作起來也不方便。為解決這類問題，一些保留格式加密(Format Preserving Encryption，FPE)[1]算法方案被提出并開始走向應用。2011 年美國NIST 曾經推薦將源自FFX 方案[2]的保留格式加密算法FF1和FF3 確立為AES 標準工作模式[3-4]。

保留格式加密算法能夠將N 個數字加密成N個數字，將一串字母加密成同樣長度的一串字母，即加密后能使密文保持明文的長度和數據類型。近年來出現了很多種保留格式算法方案，但是多數方案都難以被推廣應用。困擾這些方案的核心問題是實用性和安全性。如果不允許明文組(和密文組)空間較小則不實用；如果允許明文組(和密文組)空間很小，則可能會有安全隱患[5-7]。為此，本文提出一種專門的保留格式算法工作模式，可較好地規避因明密文空間較小可能引發的安全問題。

另外，近幾年出現了一些以功率消耗少、內存占用少為特點的輕量級分組密碼算法。有些輕量級分組密碼算法的分組長度只有32 bit[8-9]，在較長的密文數據段中容易存在密文組重復。如果是ECB(電子密本)模式加密，密文組重復意味著出現了明文組重復。這意味著分組較小時報文明文格式特征易于外露。本文給出的雙擾工作模式能夠彌補分組密碼算法因明文組 (密文組) 空間較小引發的某些安全缺陷。

1 保留格式算法的一種雙擾工作模式

絕大多數保留格式加密算法都屬于分組密碼算法。分組密碼的默認工作模式是ECB[10]。但是，如DES、AES 等密碼算法還可以有OFB (輸出反饋)、CFB(密文反饋)、CTR(計數器)等工作模式。當AES(或DES)算法以OFB、CFB 或CTR 模式[11]工作時，通常被稱為分組密碼算法以序列方式工作，本質上這已經是序列密碼，不再擁有分組密碼的代替作業特征。對于一般的保留格式加密算法，默認的工作模式也是ECB，即一組碼符被替換成另一組碼符，解密時把它替換回來。如果要對長段碼符的多個分組進行保留格式加密，除了ECB 模式，能否采用類似OFB、CFB 或CTR 等序列模式呢？ 因為保留格式加密很可能要面對明密文空間較小的情形，以序列密碼方式工作時會因為亂數序列周期較小而被破譯。

正是由于保留格式加密方案允許明密文空間較小，當攻擊者獲得了很多個明密對以后，就有可能因為密文組碰撞導致更多報文的明文泄露，甚至成就攻擊者有條件嘗試一些針對密鑰的已知明文攻擊。為此，本文提出一種“雙擾工作模式”。其基本思想是對明文組和密文組加擾。明文組(密文組)由若干個碼構成，每個碼可看作是一個m 進制數，加擾是碼與碼對應相加，約定其為按位模m 加（碼間沒有進位），用符號“◎”表示。其逆變換為按位模m 減,用符號“Θ”表示。例如，字符集大小m=10，每組碼數N=4，分組碼0567 與7538 的模10 加為0567◎7578=7035，0567 與7538 的 模10 減 為0567Θ 7578=3099。

設明文字符集大小為m，分組長度為N 個碼符。用FPEnc(P，K)表示用密鑰K 對明文組P 作ECB 模式保留格式加密。如果使用IV(初始向量)且IV 與明文組類型不同，則需要按某規則將IV 轉化為N 位m 進制數，使IV 與明文組同類型。若不使用IV，則默認IV=0。雙擾工作模式的加密方法如下：

(1)以N 個碼為一組，將明文段分為t 個組P1，P2，P3，…，Pt。

(2)用密鑰K 將IV 加密(如果不使用IV 則將“0”加密)，得S0=FPEnc(IV，K)，稱S0為秘密IV。計算S1=FPEnc(0◎S0，K)=FPEnc(S0，K)。對i=2，3，…，t，計算Si=FPEnc((Si-1◎Si-2)，K)。得到擾序列S0，S1，S2，…，St。

(3)加密各個明文組。對i=1，2，3，…，t，作如下操作：

①將明文組Pi與擾碼Si-1按位模m 加(明文加擾)，得P=Pi◎Si-1。

②將P 加密，即得到C=FPEnc(P，K)。

③將C 與Si按位模m 加(密文加擾)，即得Ci=C◎Si。Ci為 第i 個 密 文 組。

雙擾工作模式分組加密流程如圖1 所示。

雙擾工作模式的解密方法與加密方法相似，需要加解密雙方約定是否使用IV。解密時步驟(3)中的加密運算相應地變為解密運算，按位模m 加相應地變為按位模m 減,參見圖2。即步驟(3)相應地變為對i=1，2，3，…，t，作如下操作：

①將密文組Ci與擾碼Si按位模m 減(密文解擾)，得C=CiΘSi。

②將C 解密，即計算P=FPDec(C，K)。

③將P 與Si-1按位模m 減(明文解擾)，即解得明文組Pi=PΘSi-1。

上述三小步可用式子描述為：

Pi=FPDec((CiΘSi)，K)ΘSi-1。

IV 的作用在于產生擾碼序列初值S0。對攻擊者來說，IV 是可見的，但S0是不可預測的。不同的IV產生不同的S0，導致產生不同的擾碼序列。

圖1 雙擾工作模式分組加密流程示意圖

2 對雙擾工作模式的性能分析

保留格式加密算法的雙擾工作模式實際是將ECB 模式與序列加密模式相互混合，可以直觀地理解為每個數據組的加密過程分為三步：(1)用一組擾碼對輸入的明文組實施加擾；(2)對加了擾的明文組作多輪迭代式分組加密；(3)用另一組擾碼對分組加密后的輸出密文進行加擾。對于實用的現代分組密碼算法，唯密文攻擊[12]幾乎沒有成功希望，所以，較為現實的攻擊方向當屬已知明文攻擊[13-14]和選擇明文(密文)攻擊[15]。為了能夠形成攻擊所需要的數據條件，攻擊者必須設法搜索和猜設一定數量的明密對。

在通常的ECB 或CBC(密文分組鏈接)工作模式下，當攻擊者截獲了某用戶的長段密文后，通過研究密文產生場景、收集與該用戶相關的相近長度明文數據、關注密文解譯方公開流露出的等長明文段落等，將某些明文段與密文段形成明密對應，進而猜設到一些明密對。甚至有可能找到密文組重復，暴露明文結構特征，為猜設明文提供重要佐證。之后，可以開展一些已知明文攻擊或選擇明文攻擊類研究課題。當明文組空間較小時，如果密文數據量較大，這類攻擊有可能產生實質效果。

圖2 雙擾工作模式解密流程示意圖

在CBC 工作模式下，假設用戶加密明文段P=(p0，p1，p2，…，pn)產 生 了 密 文C=(c0，c1，c2，… ，cn)，而且用戶在不變更密鑰情況下又加密明文段Q=(q0，q1，q2，…，qm)產生了密文D=(d0，d1，d2，…，dm)。如果攻擊者在C 和D 這兩份密文之間找到了相同的 密 文 組，比 如 有ci=dk，1 ≤i ≤n，1 ≤k ≤m，那 么，依據分組迭代時相同的密文輸出必定有相同的明文輸入，攻擊者可以推出ci-1⊕pi=dk-1⊕qk，得到ci-1⊙dk-1=pi⊙qk，這里“⊕”表示數據組異或，“⊙”表示邏 輯 同。進 而 有pi⊕qk=ci-1⊕dk-1。由 于ci-1和dk-1在密文中可見，ci-1⊕dk-1是已知的，因此，通過找到并研究相同密文組，攻擊者可以發現兩明文組間的差值，這將有助于猜設明文。同理，若在一份較長密文內找到了相同密文組，比如有ci=ck，可以獲知明文組pi與pk間的差值。所以，若能在密文數據中找到相同的密文組，則CBC 模式是有安全缺陷的，而雙擾工作模式不存在此類安全隱患。

在CTR 或OFB 模式下，如果用戶不慎重復使用了IV，會導致信息泄露。而在雙擾工作模式情形，重用IV 意味著分組序號相同的兩個數據組，加在明文上的擾碼相同、 加在密文上的擾碼也相同，具體擾碼是什么不可預測。其攻擊難度大于ECB 模式只有兩個明密對時，求取密鑰或者預測其他明密對。即使同一個IV 重復使用 n 次，雙擾工作模式的安全強度也會優于已知n 個明密對情形的已知明文攻擊。

雙擾工作模式的中心思想是通過多次加密IV產生秘密擾碼序列，擾亂分組迭代的輸入和輸出。采用本文給出的雙擾工作模式，即使攻擊者獲得了某密文段落的明文，仍然得不到明密對，因為攻擊者不能準確地猜設用于明文組和密文組的擾碼。當明文組序號不相同時，即使出現相同的密文組也無助于猜設明文信息。

擁有若干明密對構成的適度數據條件，是密碼分析和破譯的基本素材，也是破譯成功的必備基礎。雙擾工作模式遏制了攻擊者獲取有效數據的能力，使攻擊者不能具備開展密碼分析研究的數據條件。破壞了攻擊者的攻擊能力，某個層面上等同于該工作模式增強了算法的安全強度。

由于雙擾工作模式每加密一個明文組近似等于做兩次ECB 加密和兩次按位模m 加，在效率方面它只相當于通常CBC 或CTR 模式的近二分之一。大多數情形下，這不會影響實際應用。另外，由于擾碼的產生與明密文無關，致使擾碼序列可以預計算或并行計算，從而可以使雙擾工作模式的運算時間在可并行環境下逼近CBC 模式。

3 結論

算法的工作模式也是算法安全性的一個組成部分。好的工作模式可以彌補算法設計上的某些不足，為算法安全性加分，但也可能為算法工作效率減分。安全與效率通常是相互制約的兩個方面。對于保留格式加密算法，面對的場景可能是明文組空間較小，需要加密的數據量不大。所以，實際應用中用戶對效率的要求不高，安全性更為重要，這將使得雙擾工作模式擁有較好的應用前景。本文給出的雙擾工作模式實質上是分組密碼算法的一種通用工作模式，它并不局限于保留格式加密中的應用，僅僅是用于保留格式加密算法時，因為數據分組可能較小，安全性方面的優點較為突出。