天天看點
傳回

【密碼學】DES、AES、RC4對稱密碼

對稱密碼

  • 資料加密标準
  • 進階加密标準
  • 分組密碼的工作模式
  • 僞随機數的産生和流密碼

資料加密标準

DES

  1. 明文m(64bit)的位通過一個固定的初始置換進行置換，得到m0 = IP(m)。記做m0 = L0R0。L0為m0的前32位，R0為m0的後32位。
  2. 對1<=i<=16,執行操作：*Li=R(i-1) Ri=L(i-1)⊕f(R(i-1),Ki)*其中Ki是從K得到的48位的串，f是一個函數
  3. 左右交換，得到R16L16，用初始置換的逆作用得到密文c=IP^(-1)(R16L16)
  • 初始置換：可以描述成一個初始置換表
  • 函數f(R,Ki)
    • R通過擴充置換表擴充成E®，注意E®有48位。
    • 計算E®⊕Ki,将48位分成B1B2……B8,其中Bj有6bit。
    • 有8個S盒，Bj是Sj的輸入。記Bj=b1b2b3b4b5b6。b1b6确定S盒的行，b2b3b4b5确定S盒的列，按此方式得到八個4位的輸出C1,C2，……,C8。
    • C1,C2，……,C8根據下表做置換。
    • 得到的32位結果就是f(R，Kj）
  • 如何得到K1，K2，…，K16，我們是從64位的密鑰K開始的。
    • 丢掉校驗位，其餘位用密鑰置換表做置換，結果寫為C0D0,其中C0D0都是28bit。
    • 對1<=i<=16,令Ci=LSi(C(i-1)),Di=LSi(D(i-1))。這裡的LSi是根據下表對輸入左移1或2個位置。
    • 根據下表，從56位的串CiDi中選取48位的串，輸出是Ki

進階加密标準：Rijndael

Rijndael的結構

Rijndael的密鑰長度有128位、192位、256位3種。通用的設計準則：可逆性：所有步驟是可逆的；簡單性：避免複雜元件。Rijndael算法由十輪組成（192位12輪，256位14輪），每一輪有一個原始密鑰生成的輪密鑰，還有一個第0輪的密鑰，就是原始密鑰。每一輪輸入輸出都是128bit。每一輪都有四個基本步驟
  1. ByteSub變換（BS）：一個非線性層，目的是抵抗差分和線性攻擊。
  2. ShiftRow變換（SR）：一個線性層，目的是經過多輪的作用對位進行混淆。
  3. MixColumn變換（MC）：目的與SR相似。
  4. AddRoundKey（ARK）：這一輪的輪密鑰和上述層的結果做異或。
  • ARK，使用第0輪的輪密鑰。
  • 9輪的BS，SR，MC，ARK，使用第一輪至第九輪的輪密鑰。
  • 最後一輪：BS，SR，ARK，使用第十輪的輪密鑰（第十輪密鑰用到MC。 
Rijndael(state, CipherKey)
{//使用Rijndael進行加密的進階算法
	KeyExpansion(CipherKey,ExpandedKey);
	AddRoundKey(State,ExpandedKey[0]);//ARK為初始密鑰加法
	For(i = 1; i <= Nr; i++)
		Round(State, ExpandedKey[i]);
	FinalRound(State,ExpandedKey[Nr]);//最後使用輪變換FinalRound
	}
           
//Rijndeal的輪變換
Round(State,ExpandedKey[i])
{
	SubBytes(state);
	ShiftRow(state);
	MixColumn(state);
	AddRoundKey(State,ExpandedKey[i]);
	}
FinalRound(State,ExpandedKey[Nr])
{
	SubBytes(States);
	ShiftRows(States);
	AddRoundKey(State,ExpandedKey[Nr]);
	}

輪變換

  • 步驟SubBytes：磚匠置換，包含一個作用在狀态位元組上的S-盒，用Srd表示。
    • Srd的設計準則：
      • 非線性度
        • 相關性：輸入-輸出之間的最大相關幅度必須盡可能小
        • 差分傳播機率的最大值必須盡可能小
      • 數複雜度：在GF（2^8）中Srd應該具有複雜的代數表達式
    • Srd的選擇：構造為g和一個可逆仿射變換f的序列。
      • g ： a -> b = a^(-1)
      • 仿射變換f可描述為：先進行多項式乘法，然後再與一個常量異或。
  • 步驟ShiftRows：位元組換位
    • 設計準則：
      • 最佳擴散性：4個偏移量必須互不相同
      • 其他擴散效果：抗擊截短差分攻擊和滲透攻擊的能力必須最大
    • 偏移量的選擇：
      • 對于128bit分組，偏移量的值選0，1，2，3，各行使用其中任意一個
      • 各種偏移量的選擇并非完全等價
  • 步驟MixColumn：作用在狀态各列的磚匠置換
    • 設計準則：
      • 次元：該變換是一個作用在4位元組列上的磚匠變換。
      • 線擴性：該變換是GF（2）上的線性變換。
      • 擴散性：改變換需要有相應的擴散能力。
      • 在8位處理器上的性能
    • 選取：
      • 擴散性和性能選擇使D-盒的定義：将狀态的列看做GF(28)上的多項式，并在模x4+1下與一個給定的多項式c（x）相乘。
      • 多項式c(x)=03x3+01x2+01x+0.它與x^4+1互素，是可逆的。
      • 因為與一個固定的多項式模乘可表示為一個矩陣乘法。設b(x)=c(x)*a(x)(modx^4+1)。
  • 密鑰加法：
    • 狀态的調整通過與一個輪密鑰進行逐位異或而得到。輪密鑰記做ExpandedKey[i]。
    • 輪密鑰ExpanedKey由密碼密鑰通過密鑰編排方案導出，輪密鑰長度等于分組長度。ARK的逆仍是其自身。

輪的數目

  • 疊代型分組密碼抗擊密碼分析攻擊的能力随輪數的增加而增加。
  • 考慮抗擊捷徑攻擊來确定輪的數目，在此基礎上增加了一個适當的安全餘量。對分組長度和密鑰長度均是128bit的Rijndael，并未發現對具有六輪以上的簡化版本實施的捷徑攻擊，又增加了4輪作為安全餘量。這是一個保守的做法因為：
    • Rijndael中兩輪即可提供以下意義的“全擴散”。每個狀态比特均依賴于兩輪前的所有狀态比特，或者一個狀态比特的改變均可能對兩輪之後的半數狀态比特産生影響。再增加四輪可以看作是在密碼的開始和結束時增加了一個“全擴散步驟”。Rijndael輪變換的高擴散性歸功于它再所有狀态比特上的均勻結構。
    • 為了攻擊密碼的第n+1輪或n+2輪，線性密碼分析、差分密碼分析和截短差分攻擊通常采用一個直到n輪的傳播軌迹。滲透攻擊也是如此，它利用一個四輪的傳播結構來攻擊六輪。在這方面，增加四輪實際上使得找到一個傳播軌迹所周遊的輪數增加一倍。
  • 對于較長密鑰的Rijndael，密碼密鑰每增加32bit，輪的數目增加一輪。
    • 主要目的之一是使比窮舉密鑰搜尋攻擊更加有效的捷徑攻擊失效。
    • （部分）已知密鑰和相關密鑰攻擊利用了密碼密鑰中的比特資訊，或者具有利用不同密碼密鑰的能力。如果增加密鑰長度，密碼分析者的搜尋範圍會增加
    • 如果密碼分組長度大于128bit，就采用三輪來實作全擴散，因為輪變換的羅三能力随着分組長度的增加而變低。
    • 更大的分組長度将增加可能出現的模式的選取範圍，這些模式可用在某幾輪的輸入輸出上。這一附加的靈活性可使攻擊所必須處理的範圍擴大一輪或更多輪。

密碼編排方案

密鑰的編排方案包括兩部分，即密鑰的擴充和輪密鑰的選取。密鑰的擴充是指如何由密碼密鑰得到ExpandedKey.由于改密碼要求一個輪密鑰用于初始密鑰加法，而且每輪都需要一個輪密鑰，是以ExpandedKey中的全部比特數等于分組長度乘以輪數加一。注意ExpandedKey總是由密碼密鑰導出，從不被直接指定。
  • 設計準則
    • 效率
      • 工作記憶體：應當能用少量的工作記憶體來執行密鑰編排方案
      • 性能：多種處理器上均應具有高性能
    • 對稱消除：應使用輪常量來消除對稱性
    • 擴散：應将密碼密鑰的差分有效的擴散到擴充密鑰中
    • 非線性性：避免擴充密鑰中的差分僅由密碼密鑰的差分完全決定
  • 128位原始密鑰的擴充
    • 開始的4列為W(0),W(1),W(2),W(3),新的列遞歸生成。
      • i不是4的倍數：W(i) = W(i - 4)⊕W(i - 1)
      • i是4的倍數：W(i) = W(i - 4)⊕T(W(i - 1))（TT(W(i - 1))是對W(i-1)的變換）
        • 記列W(i-1)中的元素為a，b，c，d，循環移位得到b，c，d，a。
        • 将這些位元組用S-盒相應的元素替代，得到4個位元組e，f，g，h，
        • 計算有限域GF(2^8)中的常亮： r ( i ) = 0000001 0 ( i − 4 ) / 4 r(i) = 00000010^{(i-4)/4} r(i)=00000010(i−4)/4
        • 那麼T(W(i - 1)）是如下列向量：(e⊕r(i),f,g,h)
    • 第i輪的輪密鑰：W(4i),W(4i+1),W(4i+2),W(4i+3)

S盒的構成

S盒簡單的數學描述。輸入一個位元組x7x6x5x4x3x2x1x0,其中每一個xi都是一個二進制的位。先計算它在GF(2^8)中的逆，如果位元組是00000000，就沒有逆，用00000000來代替逆。得到的位元組y7y6y5y4y3y2y1y0可以看成一個八維的列向量，最右邊的位y0在最高的位置。将這個向量左乘一個矩陣，再加上列向量(1,1,0,0,0,1,1,0),得到（z0,z1,z2,z3,z4,z5,z6,z7)。位元組(z7,z6,z5,z4,z3,z2,z1,z0)是S盒中的一項。
S盒考慮了以下問題：映射x->x^(-1)是一個非線性的變換，但簡單的一個映射不足以抵抗某些攻擊，是以還要乘以一個矩陣加上一個列向量。選擇這樣一個矩陣因為它形式簡潔，列向量的選擇是因為防止S盒的輸入和輸出相同或互反。

解密算法

  • ByteSub、ShiftRow、MixColumn和AddRoundKey每一步都是可逆的
  • ByteSub的逆是另一個查找表，叫InvByteSub。
  • ShiftRow的逆是将行右移而不是左移，得到InvShiftRow。
  • Mixcolumn的逆存在因為MixColumn中用的矩陣是可逆的。InvMixColumn變化通過乘以一個矩陣。
  • AddRoundKey的逆是它自身
解密算法可以直接利用步驟InvByteSub、InvShiftRow、InvMixColumn和AddRoundKey的逆并倒置其次序得到，成為直接解密算法。在這個算法中，不僅步驟本身和加密不同，而且步驟出現的順序也不相同。注意到，先BS後SR和先SR後BS是一樣的，因為BS一次作用于一個位元組，而SR是對多個位元組位置的替換。同樣的，ISR和IBS的先後次序也是可以交換的。我們想同時交換ARK和IMC的次序但是行不通，經過研究我們在解密中可以用先IMC後IARK來代替先IARK後IMC。
  1. ARK，使用第十輪的輪密鑰。
  2. 九輪的IBS、ISR、IMC、IAPK，使用第九輪到第一輪的密鑰。
  3. 最後一輪：IBS、ISR、ARK、使用第0輪的密鑰。
  • 8位處理器上，解密速度不如加密速度快，因為InvMixColumn的4x4矩陣比MixColumn的4x4矩陣的項要複雜一些
  • 加密過程最後一輪省略了MixColumn：考慮到解密算法，影響算法的速度。

僞随機數的産生和流密碼

随機數産生的原則

  • 僞随機數發生器：用于生産不限長位流的算法稱為PRNG。通常應用是做對稱流密碼的輸入
  • 僞随機函數(PRF）：PRF用于産生固定長度的僞随機位串。例如對稱加密密鑰和時變值。
  • 随機性
    • 分布均勻性：0和1出現的頻率大約相等。
    • 可伸縮性：用于序列的任何測試也可以用于從序列中抽取的子序列的測試。
    • 獨立性：序列中任何子序列不能由其他子序列推導出。
    • 一緻性：對于所有初始值（種子），發生器的行為必須具有一緻性。基于單個種子産生的輸出測試PRNG是不充分的。
  • 不可預測性
    • 前向不可預測性：如果不知道種子，那麼不管序列中前面的多少位都無法預測序列中的下一位。
    • 後向不可預測性：從産生的任何值都不能推斷出種子值
  • 種子的要求種子本身必須是随機數或者僞随機數。

僞随機數發生器

  • 評價随機數發生器的三個标準
  • 生成函數應是全周期的，即函數再重複之前應該産生0至m-1之間的所有數。
  • 産生的序列應顯得很随機。
  • 生成函數可以用32位運算器友善的實作。
線性同餘發生器

四個參數：m：模；a：乘數；c：增量； X 0 X_0 X0​:初始值或稱種子

随機數序列{X_n}按疊代式： X n + 1 = ( a X n + c ) m o d m X_n+_1=(aX_n+c)mod m Xn​+1​=(aXn​+c)modm

BSS發生器
  • 首先選擇兩個大素數p和q，要求：

  • 然後BBS按下列算法産生位 B i B_i Bi​序列

    X 0 = s 2 m o d n X_0=s^2modn X0​=s2modn

    f o r i = 1 t o ∞ fori=1to \infty fori=1to∞

    X i = ( X i − 1 ) 2 m o d n Xi=(X_i-_1)^2modn Xi=(Xi​−1​)2modn

    B i = X i m o d 2 Bi=Ximod2 Bi=Ximod2

RC4算法

初始化S

開始時，S的元素的值按升序被置為0~255。同時建立一個臨時向量T.如果密鑰K的長度為256位元組，則将K附給T。否則若秘鑰長度為keylen個位元組(keylen < 256),則将K的值賦給T的前keylen個元素，并循環重複用K的值賦給T剩下的元素，直到T的所有元素都被指派。

/*初始化*/
for i=0 to 255 do
S[i] = i;
T[i] = K[i mod keylen];

然後用T産生S的初始置換，從S[0]到S[255],對每個S[i]，根據由T[i]确定的方案，将S[i]置換為S中的另一位元組：

/* S的初始置換 */
j = 0;
for i=0 to 255 do
	j = (j + S[i] + T[i]) mod 256;
Swap(S[i],S[j]);

因為對S的操作僅僅是交換，是以唯一的改變就是置換，S仍然包含所有值為0~255的元素。

密鑰流的産生

向量S一旦完成初始化，輸入密鑰就不再被使用。密鑰流的生成過程是，從S[0]到S[255],對每個S[i]，根據S的目前配置，将S[i]與S中的另一位元組置換。當S[255]置換完成後，操作繼續重複從S[0]開始：

/* 密鑰流的生成 */	
i,j = 0;
while (true)
	i = (i + 1) mod 256;
	j = (j + S[i]) mod 256;
Swap(S[i],S[j]);
t = (S[i] + S[j]) mod 256;
k = S[t];

加密中，将k的值與明文的下一位元組進行異或；解密中，将k的值與密文的下一位元組異或。

A5算法

A5流加密法是一種無規律的多LFSR系統。它由三個不同大小的LFSR組成，分别為A、B和C。A有19位，B有22位，C有23位。流輸出是這些寄存器的XOR邏輯運算結果。寄存器是無規則排程的，意味着每個寄存器在不同排程規劃所移的位不同。每個寄存器的時鐘信号由x，y，z的值決定，x是第一個寄存器的第9位，y是第二個寄存器的第11位，z是第三個寄存器的第11位。移位函數實作了三個輸入x、y和z的多數功能。當且僅當兩個或多個輸出為1時，多數函數(maj(x,y,z))為1。是以，隻有x XOR maj(x,y,z) = 0時A才移位。隻有y XOR maj(x,y,z) = 0時B才移位。隻有z XOR maj(x,y,z) = 0時C才移位。

密鑰是這三個寄存器的初始值，意味着A5有一個64位的密鑰。

真随機數發生器

真随機數發生器(TRNG)使用不可預測源來産生随機數。

  • 熵源
  • 聲音/圖像輸入
  • 磁盤驅動
  • PRNG和TRNG的比較
    • PRNG的效率較高，是确定性的，周期性的
    • TRNG的效率較低，是非确定性的，非周期性的
  • Intel數字随機數發生器(DRNG)
    • 完全由硬體實作
    • 整個DRNG和處理器在同一個多核晶片上，減少了硬體随機數發生器之間的I/O時延。
密碼學 DES AES RC4 随機數生成
上一篇: 随機信号分析基礎——例題篇（例題3.4）
下一篇: Linux 記憶體管理：DAX（Direct Access）機制的作用及實作原理Linux Memory Management：The Function and the Implementation of DAX（Direct Access）Mechanism

繼續閱讀