Feistel Networks f,…k:{0,1→0.1} Arbitrary functions ° Not necessarily invertible ④← R=L1f(R:1) 卫s8αx卫
6 Feistel Networks f1 , …, fk : {0,1}n → {0,1}n • Arbitrary functions • Not necessarily invertible f1 f2 fk-1 fk L0 : R0 : L1 : R1 : Lk-2 : Rk-2 : Lk-1 : Rk-1 : Lk : Rk : n bits n bits Round 1 Round 2 Round k-1 Round k … Li = Ri-1 Ri = Li-1 fi (Ri-1 )
Inverting a Feistel Network Theorem For any f1,…fk:{0,1}n→{0,1yn, a feistel network computes a permutationπ:{0,1}→{0,1}n L1=R1⊕f(L1 Inverse:
7 Inverting a Feistel Network f1 f2 fk-1 fk L0 : R0 : L1 : R1 : Lk-2 : Rk-2 : Lk-1 : Rk-1 : Lk : Rk : … Li-1 = Ri fi (Li ) Ri-1 = Li Theorem For any f1 , …, fk : {0,1}n → {0,1}n , a Feistel network computes a permutation p : {0,1}n → {0,1}n Inverse:
Feistel Cipher Design Principles ·b| ock size increasing size improves security, but slows cipher key size increasing size improves security, makes exhaustive key searching harder, but may slow cipher number of rounds increasing number improves security, but slows cipher subkey generation greater complexity can make analysis harder, but slows cipher · round function greater complexity can make analysis harder, but slows cipher fast software en/decryption ease of analysis are more recent concerns for practical use and testing 8
8 Feistel Cipher Design Principles • block size – increasing size improves security, but slows cipher • key size – increasing size improves security, makes exhaustive key searching harder, but may slow cipher • number of rounds – increasing number improves security, but slows cipher • subkey generation – greater complexity can make analysis harder, but slows cipher • round function – greater complexity can make analysis harder, but slows cipher • fast software en/decryption & ease of analysis – are more recent concerns for practical use and testing
Inside des cleartext DES is a feistel network with 16 rounds 64 bit cleartext blocks 56 bits key 16-round f,, 16 derived from key Feistel Network Initial permutation T (public) Decryption Apply f16, ,f,(in reverse order) Same chip ciphertext
9 Inside DES DES is a Feistel network with – 16 rounds – 64 bit cleartext blocks – 56 bits key – f1 , …, f16 derived from key – Initial permutation p (public) – Decryption • Apply f16, …, f1 (in reverse order) • Same chip cleartext ciphertext 16-round Feistel Network p p -1 key 64 64 64 64 56
Inside des Xo=P(m)= 07v0 16 Rounds,=1,2,,16: =L40f -1 Where f(Ri, Ki=p(s(e(rio ki), with operations E(expansion S(S-box lookup), and P some (permutation) c=|P1(L16R16) 10
10 Inside DES • x0 = IP(m) = L0R0 . • 16 Rounds, i = 1, 2, …, 16: Li := Ri-1 , Ri := Li-1 f (Ri-1 , Ki ), where f (Ri-1 , Ki ) = P(S(E(Ri-1 ) Ki )), with operations E (expansion), S (S-box lookup), and P some (permutation). • c = IP-1 (L16R16)