中国矿业大学：密码学_Block ciphers-L&D（Linear and Differential Cryptanalysis）

Block ciphers Linear and Differential Cryptanalysis 曹天杰 Tianjie Cao ticao(cumt. edu. cn College of Computer science and echnology, China University of Mining and Technology Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.5.16

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:V×Kn, 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

2 Block cipher Definition An n-bit block cipher is a function E : VnK→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 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 finction. Parameters include the number of rounds nr the block bitsize n and the bitsize k of the input key k from which Nr subkeys k;(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 1. terated block cipher Random( binary)keyK→ round keys:K1…,KN, 2. Round function g W=g(wr-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

erated cipher Encryption operation Woe w1=g(wo, Ki), g w1, K2), WNr g(wNr-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

Iterated 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

Shannons Principle of Confusion Substitution Cipher MESSAGE FROM MARY STUART KILL THE QUEEN Substitution Table -Caesar's Cipher ABCDEFGHTUKLMNOPORSTUVWXYZ DEFGHIJKLMNOPQRSTUVWXY ZABC key=3 cyclic shifts PEVD UHTUR PPDUB VWADU WNLOO WKHTX HHQ General substitution table ABCDEEGHTUKLMNOPORSTUVWXYZ EYUOBMDXVTHIUPRCNAKOLSGZEW 26! possible keys UBKKE DBMAR JUEAF KOLEA QHVII QXBNL BBP

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 STUAR致立 THE QUEEN 1 234+ Key =9 columns MESSAG回ER Plaintext in oMM互 R YTT ART K I王 EQUE EN ↓↓↓↓↓↓↓ Extended key: 491753286+order of columns Ciphertext out 9!=362880keys IOAEE MROSM _USAK EARIE GYLNE SLFTT RUH SMTUE SLGY工 NMOAE AR工 ER UHSAK EFTTE MRO 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 Properties 0 0 0 y⊕y=0 y⊕0=y 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