高級加密標準的數(shù)學基礎

1、高級加密標準的數(shù)學基礎第1頁，共24頁，2022年，5月20日，21點45分，星期四字節(jié)運算：有限域GF(28)上的運算1.有限域GF(23)2.有限域GF(28)3.有限域GF(28)的加法運算4.有限域GF(28)的乘法運算第2頁，共24頁，2022年，5月20日，21點45分，星期四有限域GF(23) GF(23)表示域中有23個元素，除0之外的7個元素由本原多項式構(gòu)造。 假定其本原多項式為： m(x)=x3+x+1第3頁，共24頁，2022年，5月20日，21點45分，星期四有限域GF(23)的多項式表示GF(23):000,001,010,011,100,101,110,111 第4

2、頁，共24頁，2022年，5月20日，21點45分，星期四有限域GF(23)的本原多項式的根表示定義為本原多項式 m(x)=x3+x+1的根，即 3+ +1=0 和3 = +1GF(23): 0, 0, 1, 2, 3, 4, 5, 6 第5頁，共24頁，2022年，5月20日，21點45分，星期四有限域GF(28)有限域GF(28)表示特征為2的具有28元素的有限域。這里表示成系數(shù)在0,1中的多項式的集合： b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0這樣任意的8位二進制數(shù)就和有限域中的一個多項式建立了一一對應的關系。第6頁，共24頁，2022年，5月20日，21

3、點45分，星期四加法運算 在多項式表示中，GF(28)上兩個元素的和仍然是一個次數(shù)不超過7的多項式，其系數(shù)等于兩個元素對應系數(shù)的模2加（比特異或）。 由于每個元素的加法逆元等于自己，所以減法和加法相同。第7頁，共24頁，2022年，5月20日，21點45分，星期四乘法運算 要計算GF(28)上的乘法，必須先確定一個GF(2)上的8次不可約多項式； GF(28)上兩個元素的乘積就是這兩個多項式的模乘（以這個8次不可約多項式為模）。 在Rijndael密碼中，這個8次不可約多項式確定為m(x)= x8+x4+x3+x+1 它的十六進制表示為11B。第8頁，共24頁，2022年，5月20日，21點4

4、5分，星期四例題 例題. 計算GF(28)上的兩個元素10010001和00100010的乘積。 答案：10000100第9頁，共24頁，2022年，5月20日，21點45分，星期四x乘法 GF(28)上還定義了一個運算，稱之為x乘法， 其定義為xb(x)= b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0 x(mod m(x) 如果b7=0，求模結(jié)果不變， 否則為乘積結(jié)果減去m(x)，即求乘積結(jié)果與m(x)的異或。 由此得出x（十六進制數(shù)02）乘b(x)可以 先對b(x)在字節(jié)內(nèi)左移一位（最后一位補0）， 若b7=1，則再與1B（其二進制為00011011）做逐比特

5、異或來實現(xiàn)， 該運算記為b=xtime(a)。第10頁，共24頁，2022年，5月20日，21點45分，星期四 AES Logtable 第11頁，共24頁，2022年，5月20日，21點45分，星期四AES alogtable第12頁，共24頁，2022年，5月20日，21點45分，星期四字運算：系數(shù)在GF(28)上的多項式運算 字：4個字節(jié)構(gòu)成的向量 。 4個字節(jié)構(gòu)成的向量可以表示為系數(shù)在GF(28)上的次數(shù)小于4的多項式。第13頁，共24頁，2022年，5月20日，21點45分，星期四字（多項式）的加法 對應的多項式的系數(shù)相加 第14頁，共24頁，2022年，5月20日，21點45分，星

6、期四字（多項式）的乘法 規(guī)定多項式的乘法運算必須要取模M(x)=x4+1，這樣使得次數(shù)小于4的多項式的乘積仍然是一個次數(shù)小于4的多項式. 將多項式的模乘運算記為 ，設a(x)= a3x3+a2x2+a1x+a0，b(x)= b3x3+b2x2+b1x+b0， c(x)= a(x) b(x)=c3x3+c2x2+c1x+c0。由于xj mod (x4+1)= x j mod 4，所以c0=a0b0 a3b1 a2b2 a1b3；c1= a1b0 a0b1 a3b2 a2b3；c2= a2b0 a1b1 a0b2 a3b3；c3= a3b0 a2b1 a1b2 a0b3。 第15頁，共24頁，20

7、22年，5月20日，21點45分，星期四字（多項式）的乘法可將上述計算表示為第16頁，共24頁，2022年，5月20日，21點45分，星期四例題例題. 計算0 xB7A5662F 0 x03010102 mod M(x)=X4+1得到0 xC7？A0？，請將?？處填滿。例題. 計算0 xC7DAA0E6 0 x0B0D090E mod M(x)=X4+1得到0 x？A5？2F ，請將?？處填滿。例題. 計算0 x03010102 0 x0B0D090E mod M(x)=X4+1第17頁，共24頁，2022年，5月20日，21點45分，星期四產(chǎn)生過程1997年4月15日，美國ANSI發(fā)起征集A

8、ES（advanced encryption standard）的活動，并為此成立了AES工作小組。此次活動的目的是確定一個非保密的、可以公開技術細節(jié)的、全球免費使用的分組密碼算法，以作為新的數(shù)據(jù)加密標準。1997年9月12日，美國聯(lián)邦登記處公布了正式征集AES候選算法的通告。對AES的基本要求是： 比三重DES快、 至少與三重DES一樣安全、 數(shù)據(jù)分組長度為128比特、密鑰長度為128/192/256比特。第18頁，共24頁，2022年，5月20日，21點45分，星期四產(chǎn)生過程1998年8月12日，在首屆AES候選會議（first AES candidate conference）上公布了A

9、ES的15個候選算法，任由全世界各機構(gòu)和個人攻擊和評論。1999年3月，在第2屆AES候選會議（second AES candidate conference）上經(jīng)過對全球各密碼機構(gòu)和個人對候選算法分析結(jié)果的討論，從15個候選算法中選出了5個。 這5個是RC6、Rijndael、SERPENT、Twofish和MARS2000年10月2日，NIST宣布Rijndael作為新的AES。至此，經(jīng)過3年多的討論，Rijndael終于脫穎而出。第19頁，共24頁，2022年，5月20日，21點45分，星期四設計思想Rijndael密碼的設計力求滿足以下3條標準： 抵抗所有已知的攻擊。 在多個平臺上速度快，編碼緊湊。 設計簡單。第20頁，共24頁，2022年，5月20日，21點45分，星期四設計思想其輪函數(shù)是由3個不同的可逆均勻變換組成的，稱它們?yōu)?個“層”。 所謂“均勻變換”是指狀態(tài)的每個比特都是用類似的方法進行處理的。不同層的特定選擇大部分是建立在“寬軌跡策略”的應用基礎上的。 簡單地說，“寬軌跡策略”就是提供抗線性密碼分析和差分密碼分析能力的一種設計。第21頁，共24頁，2022年，5月20日，21點45分，星期四設計思想為實現(xiàn)寬軌跡策略，輪函數(shù)3個層中的每一層都有它自己的功能： 線性混合層確保多輪之上的高度擴散； 非線性層 將具有最優(yōu)的“最壞情