1.6 LOKI加密算法

LOKI是由澳大利亞的L.Brown和J.Seberry等人提出的一種16層DES型迭代分組加密算法，該加密算法于1989年提出，又于1991年做了修改，原方案稱(chēng)為L(zhǎng)OKI89，修改后的方案稱(chēng)為L(zhǎng)OKI91。LOKI加密算法和DES加密算法非常相似，也是由E擴(kuò)展、S盒代替、P置換，以及與層密鑰進(jìn)行模2加來(lái)構(gòu)建層函數(shù)的。LOKI加密算法的分組長(zhǎng)度為64比特，密鑰長(zhǎng)度也為64比特，迭代層數(shù)為16。LOKI91加密算法是AES的候選算法之一，采用16層的平衡Feistel結(jié)構(gòu)，其分組長(zhǎng)度為128比特，密鑰可以為128、192、256比特。

1.6.1 LOKI89加密算法

明文P首先與密鑰進(jìn)行模2加，再被分成32比特的左右兩部分，然后經(jīng)過(guò)如下所示的16層迭代變換。

Li=Ri-1

Ri=Li-1⊕F(Ri-1⊕Ki-1), i=1,2, …,16

最后一層不變換，第16層輸出與層密鑰K16進(jìn)行模2加后即可得到密文。

LOKI91加密算法去掉了LOKI89加密算法中的輸入、輸出與密鑰的結(jié)合過(guò)程。

F函數(shù)由E擴(kuò)展、S盒代替和P置換三部分組成。

E擴(kuò)展按表1.6.1所示的E擴(kuò)展表將32比特?cái)U(kuò)展成48比特。

表1.6.1 E擴(kuò)展表

LOKI加密算法使用了4個(gè)相同的S盒。S盒的輸入為12比特，輸出為8比特。LOKI加密算法首次使用了有限域上的多項(xiàng)式來(lái)構(gòu)建S盒，它使用了16個(gè)F2上的8次不可約多項(xiàng)式，通過(guò)有限域GF(28)中的模冪運(yùn)算來(lái)實(shí)現(xiàn)S盒代替。我們把F2上的多項(xiàng)式簡(jiǎn)記為由它們系數(shù)組成的二元數(shù)組，例如，將多項(xiàng)式x8+x6+x5+x4+x2+x+1簡(jiǎn)記為（101110111）, S盒的計(jì)算使用下列16個(gè)F2上的8次不可約多項(xiàng)式，即

二元數(shù)組與F2上的多項(xiàng)式相對(duì)應(yīng)，在S盒的計(jì)算中需要相互轉(zhuǎn)換。

將輸入的48比特從左到右每12比特輸入一個(gè) S 盒，將12比特記為 b0…b11，令 r 為（b2b3b4b5b6b7b8b9）的二進(jìn)制值，c為（b0b1b10b11）的二進(jìn)制值，則S盒的輸出值為

o=(c+r)31 mod gr

在LOKI91加密算法中，S盒的輸出值為

f=c+[(r×17)⊕0xff]mod 256

將f看成F2上的多項(xiàng)式，計(jì)算

o=f 31 mod gr

式中，o可看成二元數(shù)組，即S盒的8比特輸出。

4個(gè)S盒的32比特輸出經(jīng)過(guò)P置換后可變成層函數(shù)F的輸出，如表1.6.2所示。

表1.6.2 層函數(shù)F的輸出

LOKI89加密算法的層密鑰是通過(guò)將密鑰分成左右兩半，并且經(jīng)過(guò)變換和循環(huán)移位生成的，記K=KL| KR, ROL(·, n)表示循環(huán)左移n位，相關(guān)偽代碼如下：

for(i=0; i＜16; i+=2)
{
    Ki=KL
    KL=ROL(KL,12)
    Ki+1=KR
    KR=ROL(KR,12)
}
    KL=ROL(K14,12)
    KR=ROL(K15,12)
    K16=KL|KR

LOKI89加密算法和LOKI91加密算法的層密鑰生成規(guī)律如圖1.6.1所示。

圖1.6.1 LOKI89加密算法和LOKI91加密算法的層密鑰生成規(guī)律

1.6.2 LOKI91加密算法

LOKI91加密算法的層密鑰生成的相關(guān)偽代碼如下：

for(i=0; i＜16; i+=4)
{
    Ki=KL
    KL=ROL(KL,12)
    Ki+1=KL
    KL=ROL(KL,13)
    Ki+2=KR
    KR=ROL(KR,12)
    Ki+3=KR
    KR=ROL(KR,13)
}

LOKI91加密算法的結(jié)構(gòu)框圖和層密鑰生成過(guò)程如圖1.6.2所示。

圖1.6.2 LOKI91加密算法的結(jié)構(gòu)框圖和層密鑰生成過(guò)程

將128比特的明文分組分成64比特的左右兩部分，即L0和R0，然后進(jìn)行如下偽代碼所示的16層變換。

for(i=1; i＜=12; i++)
{
    Ri=Li-1⊕F(Ri-1+K3i-2, K3i-1);
    Li=Ri-1+K3i-2+K3i;
}

最后一層左右兩部分不變換。

K3i-2、K3i-1、K3i（i=1,2, …,16）為48個(gè)64比特的層密鑰，層密鑰生成規(guī)律如下：

（1）由輸入密鑰生成4個(gè)64比特的字K40‖K30‖K20‖K10。如果輸入密鑰長(zhǎng)度為256比特，則記為4個(gè)64比特的字Ka‖Kb‖Kc‖Kd，則

K40‖K30‖K20‖K10=Ka‖Kb‖Kc‖Kd

如果輸入密鑰長(zhǎng)度為192比特，則記為3個(gè)64比特的字Ka‖Kb‖Kc，即

K40‖K30‖K20‖K10=Ka‖Kb‖Kc‖F(Ka, Kb)

如果輸入密鑰長(zhǎng)度為128比特，則記為2個(gè)64比特的字Ka‖Kb，即

K40‖K30‖K20‖K10=Ka‖Kb‖F(Kb, Ka)‖F(Ka, Kb)

（2）進(jìn)行如下偽代碼所示的48層變換。

for(i=1; i≤48; i++)
{
    Ki=K1, i=K4, i-1⊕gi(K1, i-1, K3, i-1, K2, i-1);
    K4, i=K3, i-1;
    K3, i=K2, i-1;
    K2, i=K1, i-1;
}

其中

gi(K1, K3, K2)=F[K1+K3+(δ×i), K2]

δ=[sqrt(5)-1]×263=0x9E3779B97F4A7C15

函數(shù)F(A, B)由五部分組成，如圖1.6.3所示。

圖1.6.3 F(A, B)函數(shù)的組成示意圖

第一部分是一個(gè)由參數(shù)B（即部分密鑰）控制的比特置換，記為KP(A, B)。如果將A分成32比特的左右兩部分，即AL和AR，記B的低位32比特為BR，則KP(A, B)就是下面的置換：當(dāng)B的第i（i=1,2, …,32）比特為1時(shí)，AL和AR的對(duì)應(yīng)比特互換，用式子表示KP(A, B)：

KP(A, B)=KP(AL‖AR, BR)={[(AL&～BR)|(AR·BR)]‖[(AR&～BR)|(AL·BR)]}

式中，&～表示逐位進(jìn)行與非運(yùn)算，||表示連接，|表示逐位進(jìn)行或運(yùn)算，· 表示逐位進(jìn)行與運(yùn)算。

第二部分是一個(gè)E擴(kuò)展，它將64比特?cái)U(kuò)展成96比特后作為S盒的輸入。E擴(kuò)展規(guī)律如表1.6.3所示。

表1.6.3 E擴(kuò)展規(guī)律

第三部分是8個(gè)S盒，由S1和S2按S1S2S1S2S2S1S2S1的順序組成，S1和S2的輸入分別為13比特和11比特，輸出都為8比特，由下列兩個(gè)式子生成。

S1(x)=[(x⊕0x1fff)3 mod 0x2911]&0xff

S2(x)=[(x⊕0x7ff)3 mod 0xAA7]&0xff

上面兩個(gè)式子分別是在有限域GF(213)和GF(211)中進(jìn)行運(yùn)算的。E擴(kuò)展后的96比特從左到右依次作為8個(gè)S盒的輸入。

第四部分是一個(gè)固定的P置換，如表1.6.4所示。

表1.6.4 P置換

第五部分又是8個(gè)S盒，由S1和S2按S2S2S1S1S2S2S1S1的順序組成。P置換的64比特輸出從左到右依次作為8個(gè)S盒的低8位輸入，每個(gè)S盒的高輸入比特則由B的高32比特（63～32比特）從左到右按順序組成。