Cryptography筆記9 - Block Cipher: DES

DES (Data Encryption Standard)

1997年被破解(exhaustive search)，被AES取代。架構是一個Feistel network (Feistel是發明人姓名):

f1 ... fd 是d個arbitrary functions，一開始round0 n-bit R0 變成下一個round1的L1，而L0則和f1(R0) exclusive or之後變成R1，這樣是一個round，然後一直下去:

我們要證明為何Feistel network是invertible? 其實上面數學式很簡單就可以建構出inverse function:

所以decryption network就等於是encryption network的反向:

3-round Fiestel Network is a secure PRP

有個證明的理論，如果某個secure PRF f maps n bits to n bits，則用此secure f在3 rounds的Fiestel Network中當作每一個round的round function，也會形成一個secure PRP (block cipher):

注意每個round的key要independent!

DES 的Feistel Network

1. round = 16 (f1, f2, ... f16   ,  16個round functions)，每個f都來自同一個定義F(k,x)，但是16個不一樣的key k，所以形成了16個不同的f。

每個round function運作如下:

首先32-bit input x (e.g. R0)經過某個expansion function，把32 bit map成48 bit，然後跟48-bit round key XOR形成一個48-bit結果，此48bit又被分成8個6 bits input，丟入S1, .. S8 boxes中，S function maps 6 bits to 4 bits，最後此8 * 4 = 32 bits經過某種permutation function的出f function最後的結果32 bit。

s-boxes的選擇關乎DES的安全性，不能是linear function! 這部分先暫時說道這。有需要再補充。

2. DES key = 56 bits，經過key expansion變成16個48-bit round keys

兩個32 bits blocks (R0, L0) 先經過(spec明定的) iniital permutation IP，然後經過16-round Feistel newtork，最後在經過spec明定的final permutation (就是IP的inverse)，最後得出加密過個64-bit block。