摘要：介紹了ＮＥＳＳＩＥ標(biāo)準(zhǔn)中的分組密碼算法——Ｃａｍｅｌｌｉａ算法的加、解密過程，并對其在各種軟、硬件平臺上的性能進(jìn)行了比較，結(jié)果表明Ｃａｍｅｌｌｉａ算法在各種平臺上均有著較高的效率。Ｃａｍｅｌｌｉａ算法與其它技術(shù)相結(jié)合將在信息安全領(lǐng)域產(chǎn)生更廣泛的應(yīng)用。

關(guān)鍵詞：ＮＥＳＳＩＥ 分組密碼 Camellia 算法 加密

繼２０００年１０月美國推出二十一世紀(jì)數(shù)據(jù)加密標(biāo)準(zhǔn)ＡＥＳ后，２００３年２月歐洲一代的安全標(biāo)準(zhǔn)ＮＥＳＳＩＥ（Ｎｅｗ Ｅｕｒｏｐｅａｎ Ｓｃｈｅｍｅｓ ｆｏｒ Ｓｉｇｎａｔｕｒｅｓ、Ｉｎｔｅｇｒｉｔｙ ａｎｄ Ｅｎｃｒｙｐｔｉｏｎ）出臺。ＮＥＳＳＩＥ是歐洲ＩＳＴ（Ｉｎｆｏｒｍａｔｉｏｎ Ｓｏｃｉｅｔｙ Ｔｅｃｈｎｏｌｏｇｉｅｓ）委員會計劃的一個項目。Ｃａｍｅｌｌｉａ算法以其在各種軟件和硬件平臺上的高效率這一顯著特點成為ＮＥＳＳＩＥ標(biāo)準(zhǔn)中兩個１２８比特分組密碼算法之一（另一個為美國的ＡＥＳ算法）。

Ｃａｍｅｌｌｉａ算法由ＮＴＴ和Ｍｉｔｓｕｂｉｓｈｉ Ｅｌｅｃｔｒｉｃ Ｃｏｒｐｏｒａｔｉｏｎ聯(lián)合開發(fā)。作為歐洲新一代的加密標(biāo)準(zhǔn)，它具有較強(qiáng)的安全性，能夠抵抗差分和線性密碼分析等已知的攻擊。與ＡＥＳ算法相比，Ｃａｍｅｌｌｉａ算法在各種軟硬件平臺上表現(xiàn)出與之相當(dāng)?shù)募用芩俣?。除了在各種軟件和硬件平臺上的高效性這一顯著特點，它的另外一個特點是針對小規(guī)模硬件平臺的設(shè)計。整個算法的硬件執(zhí)行過程包括加密、解密和密鑰擴(kuò)展三部分，只需占用８．１２Ｋ ０．１８μｍ ＣＯＭＳ工藝ＡＳＩＣ的庫門邏輯。這在現(xiàn)有１２８比特分組密碼中是的。

１ Ｃａｍｅｌｌｉａ算法的組成

Ｃａｍｅｌｌｉａ算法支持１２８比特的分組長度，１２８、１９２和２５６比特的密鑰與ＡＥＳ的接口相同。本文以１２８比特密鑰為例對Ｃａｍｅｌｌｉａ算法進(jìn)行詳細(xì)介紹。

Ｃａｍｅｌｌｉａ算法１２８比特密鑰的加、解密過程共有１８輪，采用Ｆｅｉｓｔｅｌ結(jié)構(gòu)，加、解密過程完全相同，只是子密鑰注入順序相反。而且密鑰擴(kuò)展過程和加、解密過程使用相同的部件。這使得Ｃａｍｅｌｌｉａ算法不論是在軟件平臺還是硬件平臺只需更小的規(guī)模和更小的存儲即可。

（１）Ｃａｍｅｌｌｉａ算法所采用的符號列表及其含義

Ｂ ８比特向量 Ｗ ３２比特向量

Ｌ ６４比特向量 Ｑ １２８比特向量

ｘｎ 比特向量

ｘＬ 向量ｘ的左半部分 ｘＲ 向量ｘ的右半部分

＜＜＜ 比特循環(huán)左移 ｜｜ 兩個操作數(shù)的連接

 比特的異或操作 ｘ 比特位取補(bǔ)操作

∪ 比特位的或操作 ∩ 比特位的與操作

（２）Ｃａｍｅｌｌｉａ算法所采用的變量列表及其含義

Ｍ１２８ １２８比特明文組 Ｃ１２８ １２８比特密文組

Ｋ 主密鑰 ｋｗｔ６４ ｋｕ６４ ｋｌｖ６４

（３）Ｃａｍｅｌｌｉａ算法所采用的變換函數(shù)

·Ｆ變換

Ｆ變換（見式（１））是Ｃａｍｅｌｌｉａ算法中主要的部件之一，而且Ｆ變換被加、解密過程和密鑰擴(kuò)展過程所共用（１２８比特密鑰的加、解密各用１８次，密鑰擴(kuò)展用４次）。Ｃａｍｅｌｌｉａ算法的Ｆ變換在設(shè)計時采用１輪的ＳＰＮ（Ｓｕｂｓｔｉｔｕｔｉｏｎ Ｐｅｒｍｕｔａｔｉｏｎ Ｎｅｔｗｏｒｋ），包括一個Ｐ變換（線性）和一個Ｓ變換（非線性）。在Ｆｅｉｓｔｅｌ型密碼使用一輪ＳＰＮ作輪函數(shù)時，對更高階的差分和線性特性概率的理論評估變得更加復(fù)雜，在相同安全水平下的運(yùn)行速度有所提高。

·Ｐ變換

Ｃａｍｅｌｌｉａ算法的Ｐ變換（見式（２））是一個線性變換。為了通信中軟、硬件實現(xiàn)的高效性，它適合采用異或運(yùn)算，并且其安全性能足以抵抗差分和線性密碼分析。其在３２位處理器、高端智能卡上的應(yīng)用，跟在８位處理器上一樣。

·Ｓ變換

Ｃａｍｅｌｌｉａ算法采用的Ｓ盒（見式（３））是一個ＧＦ（２８）上的可逆變換，它加強(qiáng)了算法的安全性并且適用于小硬件設(shè)計。眾所周知，ＧＦ（２８）上函數(shù)的差分概率的值被證明為２－６，線性概率的值推測為２－６。Ｃａｍｅｌｌｉａ算法選擇ＧＦ（２８）上能夠獲得的差分和線性概率的可逆函數(shù)作Ｓ盒，而且Ｓ盒每個輸出比特具有高階布爾多項式，使得對Ｃａｍｅｌｌｉａ進(jìn)行高階差分攻擊是困難的。Ｓ盒在ＧＦ（２８）上輸入、輸出相關(guān)函數(shù)上的復(fù)雜表達(dá)式，使得插入攻擊對Ｃａｍｅｌｌｉａ無效。

Ｓ：Ｌ→Ｌ

(l'1(8),l'1(8),l'1(8),l'1(8),l'1(8),l'1(8),l'1(8),l'1(8)→

*s1(l'1(8)),s2(l'2(8)),s3(l'3(8)),s4('4(8)),s2(l'5(8)),s3(l'6(8)),

s4(l'7(8),s1(l'8(l8(8)))

其中， ｓ２:ｙ(８)＝ｓ1(x(8))=h(g(f(0xC5+x(8))))+0x6E

s２:Y(８)＝ｓ2(ｘ(８))=s1(x(8))＜＜＜１ (３)

ｓ３:ｙ(８)＝ｓ３(ｘ(８))＝ｓ１(ｘ(８))＞＞＞１

ｓ４:ｙ(８)＝ｓ４(ｘ(８))＝ｓ１(ｘ(８))＜＜＜１

算法中構(gòu)造了四個不同的Ｓ盒，提高了Ｃａｍｅｌｌｉａ算法抵抗階段差分攻擊的安全性。為了在小硬件上設(shè)計實現(xiàn)，ＧＦ（２８）上的元素可以表示成系數(shù)為ＧＦ（２４）上的多項式。這樣，在實現(xiàn)Ｓ盒時，只需運(yùn)用子域ＧＦ（２４）上很少的操作。ｓ１變換中所采用的ｆ、ｈ、ｇ函數(shù)分別如（４）、（５）、（６）式所示。

(ｂ１,ｂ２,ｂ３,ｂ４,ｂ５,ｂ６,ｂ７,ｂ８)＝ｇ(ａ１,ａ２,ａ３,ａ４,ａ５,ａ６,ａ７,ａ８)

其中,(ｂ８＋ｂ７α＋ｂ６α２＋ｂ５α３)＋(ｂ４＋ｂ３α＋ｂ２α２＋ｂ１α３)β

＝１／（(ａ８＋ａ７α＋ａ６α２＋ａ５α３)＋(ａ４＋ａ３α＋ａ２α２＋ａ１α３)）(６)

規(guī)定（６）式中ＧＦ(２的８次方)上運(yùn)算＝1/０，β是ＧＦ（２的８次方）上方程ｘ８＋ｘ６＋ｘ５＋ｘ３＋１＝０的根，ａ＝β２３８＝β６＋β５＋β３＋β２是ＧＦ（２的４次方）上方程ｘ４＋ｘ＋１＝０的根。當(dāng)然根據(jù)性能要求，在具體實現(xiàn)加密算法時，Ｓ盒的實現(xiàn)電路也可以直接查表的方式進(jìn)行。

·ＦＬ／ＦＬ－１變換

Ｃａｍｅｌｌｉａ算法每六圈加入ＦＬ／ＦＬ－１變換，用來打亂整個算法的規(guī)律性。加入ＦＬ／ＦＬ－１變換的另一個好處是可以抵抗未知的密碼攻擊方法，而且加入ＦＬ／ＦＬ－１變換并不影響Ｆｅｉｓｔｅｌ結(jié)構(gòu)加、解密過程相同。
ＦＬ：Ｌ×Ｌ→Ｌ

（ＸＬ（３２）｜｜ＸＲ（３２），ｋｌＬ（３２）｜｜ｋｌＲ（３２）→（７）

（ＹＲ（３２）∪ｋｌＲ（３２），ＹＬ（３２）｜｜（（ＸＬ（３２）∩ｋｌＬ（３2）＜＜＜１）+ＹＲ（３２）

ＦＬ－１：Ｌ×Ｌ→Ｌ

（ＹＬ（３２）｜｜ＹＲ（３２），ｋｌＬ（３２）｜｜ｋｌＲ（３２）→ （８）

（ＹＲ（３２）∪ｋｌＲ（３２），ＹＬ（３２）｜｜（（ＸＬ（３２）∩ｋｌＬ（３２）＜＜＜１）+ＹＲ（３２）

２ Ｃａｍｅｌｌｉａ算法的加、解密及密鑰擴(kuò)展實現(xiàn)過程

（１）加、解密過程

Ｃａｍｅｌｌｉａ算法的整個加密過程有１８輪Ｆｅｉｓｔｅｌ結(jié)構(gòu)，在第６輪和第１２輪之后加入了ＦＬ／ＦＬ－１變換層，用來打亂算法的規(guī)律性，并且在第１輪之前和１輪之后使用了１２８比特的異或操作。解密過程與加密過程完全相同，只是圈密鑰注入順序與加密相反。１２８比特密鑰Ｃａｍｅｌｌｉａ算法的加密過程如所示。

（２）密鑰擴(kuò)展

Ｃａｍｅｌｌｉａ算法的密鑰擴(kuò)展遵循了嚴(yán)格的設(shè)計準(zhǔn)則，如實現(xiàn)簡單且與加、解密過程共用部件，密鑰配置時間小于加密時間，支持在線密鑰生成，沒有等效密鑰，能夠抵抗相關(guān)密鑰攻擊和滑動攻擊等。整個過程只需通過三個中間變量，ＫＬ（１２８）＝Ｋ（１２８），Ｋ（１２８）＝０ＫＡ的簡單移位即可得到子密鑰ｋｗｔ（６４）（ｔ＝１，…，４），ｋｕ（６４）（ｕ＝１，…，１８）和ｋｌｖ（６４）（ｖ＝１，…，４），且中間生成過程與加密過程共用了部件Ｆ（如、２所示）。

３ Ｃａｍｅｌｌｉａ算法的安全性

設(shè)計者用差分?jǐn)U散概率和線性相關(guān)概率的保守上界證明了任何含ＳＰＮ網(wǎng)絡(luò)的十六圈Ｃａｍｅｌｌｉａ密碼對差分密碼分析和線性密碼分析都是安全的；此外，通過對活動Ｓ盒的計數(shù)說明十二圈Ｃａｍｅｌｌｉａ中沒有概率大于２－１２８的差分特征和線性特征；帶或不帶ＦＬ層的十圈Ｃａｍｅｌｌｉａ都具有偽隨機(jī)置換特性，能夠抵抗截斷差分攻擊和線性密碼分析；設(shè)計者還聲稱Ｃａｍｅｌｌｉａ能夠抵抗不可能差分攻擊、Ｂｏｏｍｅｒａｎｇ攻擊、高階差分攻擊、相關(guān)密鑰攻擊、插入攻擊、Ｓｌｉｄｅ攻擊、線性和攻擊及Ｓｑｕａｒｅ攻擊。在密鑰的安全性上，一方面不存在等效密鑰；另一方面，子密鑰來自主密鑰的加密結(jié)果ＫＡ和ＫＢ，改變主密鑰并不能獲得預(yù)想的ＫＡ和ＫＢ，反之亦然，因而無法控制和預(yù)測子密鑰之間的關(guān)系，從而相關(guān)密鑰攻擊難以成功。由于密鑰長度不少于１２８比特，以當(dāng)前的計算能力還無法對Ｃａｍｅｌｌｉａ成功實施諸如密鑰窮舉搜索攻擊、時間存儲權(quán)衡攻擊、字典攻擊和密鑰匹配等類型的強(qiáng)力攻擊。

４ Ｃａｍｅｌｌｉａ算法在各種平臺上的性能比較

評測一個分組密碼的好壞，除了要求其具有高的安全性外，還要求算法在應(yīng)用平臺上實現(xiàn)簡單。Ｃａｍｅｌｌｉａ算法在設(shè)計時充分考慮到了這一點，下面給出其在各種平臺上的性能參數(shù)。評測算法在軟件平臺上實現(xiàn)性能時，首要考慮其速度，其次還要看算法實現(xiàn)時所需的存儲空間，表１前半部分給出了Ｃａｍｅｌｌｉａ算法在常用的３２位處理器上各種軟件平臺的實現(xiàn)性能。高的加密速度和低的存儲需求，表明Ｃａｍｅｌｌｉａ算法可以有效地應(yīng)用于各種軟件系統(tǒng)中。從表１后半部分可以看出Ｃａｍｅｌｌｉａ算法在高端和低端的智能卡平臺上同樣有著良好的性能；由于Ｃａｍｅｌｌｉａ算法的密鑰擴(kuò)展與加、解密過程有共用部分，所以其硬件平臺所需的芯片面積大大減少，降低了硬件成本，便于推廣應(yīng)用，詳細(xì)參數(shù)見表２。
表1 Camellia算法在軟件和智能卡平臺上的性能

表2 Camellia算法在硬件平臺上的性能

從本文可以看出，分組密碼加密算法發(fā)展到今天，不論是從安全性還是從實用性的角度都越來越強(qiáng)。ＮＥＳＳＩＥ標(biāo)準(zhǔn)中的Ｃａｍｅｌｌｉａ加密算法充分考慮到了各種因素，既保證了算法的安全性又考慮到其在各種平臺上的實現(xiàn)效率，尤其是針對小硬件的設(shè)計思想，使其有著廣泛的應(yīng)用前景。