Block ciphers Linear and Differential Cryptanalysis 曹天杰 Tianjie Cao ticao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou China 中国矿业大学计算机科学与技术学院 2003.516
1 曹天杰 Tianjie Cao tjcao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.5.16 Block ciphers Linear and Differential Cryptanalysis
Block cipher Definition An n-bit block cipher is a function E:Vn×KVn, uch that for each key K∈K E(P; K )is an invertible mapping( the encryption function for k) from vn to Vn, written Ex(P). The inverse mapping is the decryption function, denoted DK(C). p denotes that ciphertext results from encrypting plaintext P under k
2 Block cipher Definition An n-bit block cipher is a function E : VnK→Vn , such that for each key K K, E(P;K) is an invertible mapping (the encryption function for K) from Vn to Vn , written EK (P). The inverse mapping is the decryption function, denoted DK (C). P denotes that ciphertext results from encrypting plaintext P under K
Iterating Block ciphers Definition A product cipher combines two or more transformations in a manner intending that the resulting ipher is more secure than the individual components Definition An iterated block cipher is a block cipher involving the sequential repetition of an internal function called a round function. Parameters include the number of rounds nr the block bitsize n and the bitsize k of the input key K from which Nr subkeys Ki (round keys)are derived. For invertibility(allowing unique decryption), for each value Ki the round function is a bijection on the round input
3 Iterating Block ciphers Definition A product cipher combines two or more transformations in a manner intending that the resulting cipher is more secure than the individual components. Definition An iterated block cipher is a block cipher involving the sequential repetition of an internal function called a round function. Parameters include the number of rounds Nr, the block bitsize n, and the bitsize k of the input key K from which Nr subkeys Ki (round keys) are derived. For invertibility (allowing unique decryption), for each value Ki the round function is a bijection on the round input
Iterating block ciphers Iterated block cipher Random( binary)keyK→ round keys:K1…,KN 2. Round function g W=g w-1, kr), where wr-1 is the previous state
4 Iterating Block ciphers 1. Iterated block cipher Random (binary) key K ➔ round keys: K1 ,..., K Nr , 2. Round function g wr = g(wr-1 , Kr ), where wr-1 is the previous state
Iterated cipher Encryption operation W←X g w, Ki), W2=g w1, K2), WNr= g.1, KNr), y←w
5 Iterated cipher … Encryption operation: w0 x w1 = g(w0 , K1 ), w2 = g(w1 , K2 ), wNr = g(wNr-1 , KNr), y wNr
erated cipher For decryption we must have g(, K) must be invertible for all K Then decryption is the reverse of encryption bottom-up
6 Iterated cipher … For decryption we must have: g(.,K) must be invertible for all K Then decryption is the reverse of encryption (bottom-up)
Diffusion and confusion - shannon Diffusion. The relationship between the statistics of the plaintext and the ciphertext is as complex as possible: the value of each plaintext bit affects many ciphertext bits Confusion: the relationship between the statistics of the plaintext and the value of the key is as complex as possible
7 Diffusion and Confusion -- Shannon • Diffusion. The relationship between the statistics of the plaintext and the ciphertext is as complex as possible: the value of each plaintext bit affects many ciphertext bits. • Confusion: the relationship between the statistics of the plaintext and the value of the key is as complex as possible
Shannon's Principle of Confusion Substitution Cipher MESSAGE FROM MARY STUART KILL THE QUEEN Substitution Table-Caesar's Cipher ABCDEEGHIUKLMNOPORSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC key =3 Cyclic shifts PHVD JHIUR PPDUB VWDU WNLOO WKHTX HHQ General substitution table ABCDEFGHIJKLMNOPORSTUVWXYZ EYUOBMDXVTHIUPRCNAKQLSGZEW 26! possible keys JBKKE DBMAR UJEAF KOLEA QHVII OXBNL BBP 8
8 ABCDEFGHIJKLMNOPQRSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXYZABC Substitution Table - Caesar‘s Cipher Shannon‘s Principle of Confusion Substitution Cipher MESSAGE FROM MARY STUART KILL THE QUEEN PHVVD JHIUR PPDUB VWXDU WNLOO WKHTX HHQ PHVVD J PHVVD key = 3 cyclic shifts ABCDEFGHIJKLMNOPQRSTUVWXYZ EYUOBMDXVTHIJPRCNAKQLSGZFW General Substitution Table 26! possible keys JBKKE DBMAR JJEAF KQLEA QHVII QXBNL BBP
Shannon's Principle of Diffusion Transposition Cipher MESSAGE FROM MARY STUART KILL THE QUEEN 1 23456789 Key =9 columns MESSAGEFR Plaintext in OMMARYST U ART LLT H EQUEEN Extended key: 491753286+ order of columns Ciphertext out 9!=362880keys MOAEE MRQSM TUSAK EARIE GYLNE SLETT RUH SMTUE SLGYL NMOAE ARIER UHSAK EFTTE MRQ Diffusion means permutation of bit or byte positions
9 4 9 1 7 5 3 2 8 6 Extended key: order of columns 9! = 362‘880 keys Shannon‘s Principle of Diffusion Transposition Cipher MESSAGE FROM MARY STUART KILL THE QUEEN M E S S A G E F R O M M A R Y S T U A R T T H E K I L L Q U E E N Plaintext in Ciphertext out MOAEE MRQ MOAEE MRQSM TU MOAEE MRQSM TUSAK E MOAEE MRQSM TUSAK EARIE MOAEE MRQSM TUSAK EARIE GYLN MOAEE MRQSM TUSAK EARIE GYLNE SLFTT RUH Diffusion means permutation of bit or byte positions ! 1 2 3 4 5 6 7 8 9 Key = 9 columns SMTUE SLGYL NMOAE ARIER UHSAK EFTTE MRQ
Exclusive OR Fundamental operation of many ciphers yzy⊕z ● Properties 0 >yy=0 0 >y0=y >y1=y y由z⊕z=y
10 Exclusive OR Fundamental operation of many ciphers 1 0 1 1 1 0 0 1 1 0 0 0 y z y z • Properties ➢ y y = 0 ➢ y 0 = y ➢ y 1 = y ➢ y z z = y