2.1 算法描述

ZUC算法是一個面向32比特字設(shè)計的序列密碼算法。其需要一個128比特的初始密鑰和一個128比特的初始變量作為輸入，輸出一串32比特字的密鑰流。生成的密鑰流可以用來進(jìn)行加密/解密和完整性認(rèn)證。

ZUC算法整體邏輯結(jié)構(gòu)如圖2-1所示，可分為上、中、下三層，上層是16級的線性反饋移位寄存器（LFSR），中間層是比特重組（BR），下層是非線性函數(shù)F。

2.1.1 參數(shù)描述

ZUC算法中的慣例如下所示。

比特：二進(jìn)制字符0和1稱為比特。

字節(jié)：由8比特組成的比特串稱為字節(jié)。

字：由2字節(jié)以上（包含2字節(jié)）組成的比特串稱為字。

整數(shù)表示：本章整數(shù)默認(rèn)采用十進(jìn)制數(shù)表示。當(dāng)采用其他進(jìn)制數(shù)表示時，將在表示之前或之后添加指示符。

例如，使用前綴“0x”表示十六進(jìn)制數(shù)，下標(biāo)“2”表示二進(jìn)制數(shù)。整數(shù)a 可以寫成不同的表示方式：

高、低位順序：字的最高位總是位于字表示中的最左邊，最低位總是位于字表示中的最右邊。

例如，假設(shè)a=1001001100101100000001011010010₂ ，那么它的最高位是1，最低位是0。

ZUC算法中常用符號及解釋如表2-1所示。

下面對一些符號進(jìn)行詳細(xì)解釋。

1）字符串連接符

對于任意兩個字符串a和b連接后生成的字符串c的描述同樣遵循相關(guān)規(guī)則。也就是說，最高位在左邊，最低位在右邊。例如：

a=0x1234

b=0x5678

于是有

c=a||b=0x12345678

2）取字的最高16比特和最低16比特的劃分

假設(shè)

a=1001001100101100000001011010010₂

于是有

a _H =1001001100101100₂

a _L =0000001011010010₂

這里值得注意的是，a_H和a_L都為16比特。

3）比特字移位

假設(shè)

a=11001001100101100000001011010010₂

于是有

a>>1=1100100110010110000000101101001₂

4）映射關(guān)系對應(yīng)賦值

假設(shè)a₀，a₁，…，a₁₅和b₀，b₁，…，b₁₅都是整型變量，那么（a₀，a₁，…，a₁₅） （b₀，b₁，…，b₁₅）的結(jié)果是b_i=a_i，0≤i≤15。

2.1.2 參數(shù)產(chǎn)生

ZUC算法在初始執(zhí)行過程中，需用到的參數(shù)為一個128比特的初始密鑰k和一個128比特的初始變量iv。

1）密鑰裝入

初始密鑰和初始變量按照如下方法加載到LFSR的寄存器單元變量s₀ ，s₁ ，…，s₁₅中，每個單元變量s_i（0≤i≤15）僅在有限域GF（2³²-1）中取值。密鑰裝入過程將128比特的初始密鑰k和128比特的初始變量iv擴(kuò)展為16個31比特，并加載到每個單元變量s_i中。

將k和iv表示成16字節(jié)串級聯(lián)的形式，即k=k₀||k₁||…||k₁₅ ，iv=iv₀||iv₁||…||iv₁₅。在LFSR中，s_i=k_i||d_i||iv_i（0≤i≤15），其中k_i和iv_i的長度均為8比特，d_i的長度為15比特。

16個已知字符串d_i級聯(lián)成一個240比特的長字符串D，D=d₀||d₁||…||d₁₅。每個d_i均具有固定參數(shù)，具體如下：

d ₀ =100010011010111₂

d ₁=010011010111100₂

d ₂ =110001001101011₂

d ₃=001001101011110₂

d ₄ =101011110001001₂

d ₅=011010111100010₂

d ₆ =111000100110101₂

d ₇ =000100110101111₂

d ₈=100110101111000₂

d ₉ =010111100010011₂

d ₁₀ =110101111000100₂

d ₁₁=001101011110001₂

d ₁₂ =101111000100110₂

d ₁₃=011110001001101₂

d ₁₄ =111100010011010₂

d ₁₅=100011110101100₂

在ZUC算法中還需用到S盒和線性變換L這兩種運(yùn)算工具。

2）S盒

32比特S盒的S由4個小的8×8的S盒并置而成，即S=（S₀，S₁，S₂，S₃），其中S₀ =S₂ ，S₁=S₃。S₀和S₁的定義分別見表2-2和表2-3。設(shè)S₀（或S₁）的8比特輸入為x，將x視為兩個十六進(jìn)制數(shù)的連接，即x=h||l，則表2-2（或表2-3）中第h行l列交叉的元素即為S₀（或S₁）的輸出S₀（x）（或S₁（x））。

設(shè)S的32比特輸入X和32比特輸出Y分別為：

X=x₀||x₁||x₂||x₃

Y=y₀||y₁||y₂||y₃

其中，x_i和y_i的長度均為8比特，則y_i=S（x_i），i=0，1，2，3。

3）線性變換L₁和L₂

L ₁和L₂都是由32比特到32比特的線性變換，其定義如下：

L ₁ (X)=X ⊕(X<<<₃₂ 2)⊕(X<<<₃₂ 10)⊕(X<<<₃₂ 18)⊕(X<<<₃₂ 24)

L ₂ (X)=X ⊕(X<<<₃₂ 8)⊕(X<<<₃₂ 14)⊕(X<<<₃₂ 22)⊕(X<<<₃₂ 30)

2.1.3 算法運(yùn)行

算法運(yùn)行分為兩個階段：初始化階段和工作階段。在初始化階段，將初始密鑰和初始變量進(jìn)行初始化，密碼算法運(yùn)行，但不產(chǎn)生輸出；在工作階段，每個時鐘脈沖均會產(chǎn)生32比特字的輸出。

1.初始化階段

按照密鑰裝入方法將128比特密鑰k和初始變量iv加載到LFSR的寄存器單元變量s₀ ，s₁ ，…s₁₅中，作為LFSR的初始狀態(tài)，并置32比特記憶單元變量R₁和R₂為全0，然后執(zhí)行下述操作。

重復(fù)執(zhí)行下述過程32次：

① Bitreorganization()

② W=F(X₀, X₁, X₂)

③ LFSRWithInitialisationMode(W>>1)

算法中各模塊解釋如下。

1）Bitreorganization比特重組模塊

Bitreorganization在圖2-1中表示為BR層，該層從LFSR的寄存器單元中抽取128比特組成4個32比特字X₀，X₁，X₂，X₃。這里的前3個字會在底層的非線性函數(shù)F中使用。最后一個字將產(chǎn)生密鑰流，以供非線性函數(shù)F 和密鑰輸出使用。假設(shè)s₀ ，s₂ ，s₅ ，s₇ ，s₉ ，s₁₁ ，s₁₄ ，s₁₅是LFSR中特定的8個單元，比特重組模塊按照如下方式形成4個32比特字X₀，X₁，X₂，X₃：

2）非線性函數(shù)F

F包括2個32比特的記憶單元R₁和R₂。F的輸入為3個32比特字X₀，X₁，X₂，F輸出為一個32比特字W。F的具體過程如下：

其中，是模2³²加法運(yùn)算，S是一個32×32比特的S盒，L₁和L₂是定義的線性變換。S盒和線性變換的具體結(jié)構(gòu)見2.1.1節(jié)。

3）LFSRWithInitialisationMode初始化

在初始化階段，LFSR接收一個31比特字u，u是通過去掉非線性函數(shù)F輸出的32比特字W的最右邊的位獲得的，即u=W >>1。在初始化階段，LFSR計算過程如下：

2.工作階段

在初始化階段后，算法進(jìn)入工作階段。在工作階段，算法執(zhí)行一次下面的操作，并丟棄函數(shù)F的輸出W。

① Bitreorganization()

② F(X₀, X₁, X₂)

③ LFSRWithWorkMode()

然后進(jìn)入密鑰輸出階段。在密鑰輸出階段，每運(yùn)行一拍，執(zhí)行下面過程一次，并輸出一個32比特字的密鑰Z。

① Bitreorganization()

② Z=F(X₀, X₁, X₂)⊕X₃

③ LFSRWithWorkMode()

其中，LFSRWithWorkMode（）不再接收任何輸入，其計算過程如下：

2.1.4 安全性分析

針對ZUC算法，這里采用猜測確定攻擊（Guess and Determine）的密碼分析方法對其安全性進(jìn)行簡要分析。

安全性分析主要分為兩個階段：第1個階段推導(dǎo)和，這是因?yàn)槿糁苯硬聹y和，則需要猜測64比特，而和為已知的全0初值，若用其推導(dǎo)和，則只需猜測16比特；第2個階段從t=2時刻（密鑰流的輸出時刻）利用已推導(dǎo)的和開始分析，并找到t=5時刻的全部內(nèi)部單元。

在推導(dǎo)的過程中，由于和為已知的全0初值，因此可以首先通過猜和的高8位推導(dǎo)出和，然后通過猜t=1時刻和的高8位推導(dǎo)出和。

t=2時刻的已知變量為和。在此時刻我們預(yù)猜測一部分內(nèi)部單元，然后由此推導(dǎo)出一部分結(jié)果。在此需要注意的是，和已不是移位得到的，因此其31位均為未知。

以此類推，在t=3、t=4、t=5時刻時均用此分析方法。在t=5時刻，由可知該時刻的已知量為，此外還有和。因此，t=5時刻的全部內(nèi)部單元均已找到。之后即可用所求內(nèi)部單元生成密鑰來檢測與原密鑰是否相同。

在猜測過程中，猜測的位置是t=0時刻的的高8位，共16比特；t=1時刻的的高8位，共16比特；t=2時刻的的高8位和的低15位，共55比特；t=3時刻共31比特；t=4時刻共8比特。因此，總共猜測16+16+55+31+8=126比特。此時搜索復(fù)雜度為O（2¹²⁶ ），而其窮盡搜索復(fù)雜度為O（2¹²⁸ ），提高了效率。

顯然，猜測確定攻擊對ZUC算法的安全性影響不大。