Cryptography (Classic & Modern) Course - King Khalid University PDF

Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Course Cryptography (Classic & Modern) College of Computer Science,...

Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Course Cryptography (Classic & Modern) College of Computer Science, King Khaled University 'KKU', KSA okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA No List of Topics Contact Hours 1. Review of number theory, Probability and Statistics Ch01 Maths 4 2. Security functions of cryptography Ch1 8 Intro & Ch2 Classical 3. Symmetric cryptography Ch3- 8 1 & Ch3-2 4. Public key cryptography Ch4-1 8 & Ch4-2 5. Key generation, Management, Exchange and distribution 8 Ch5 6. Digital certificate Ch6 2 7. Hash functions Ch6 4 8. Digital signature Ch7 4 9. Collision resistance Ch7 2 10.HMIDA, okhtar BEN Common Cryptographic Dr. & Protocols Full Professor, Head andExpert of ATMS Lab, standards Processing , in SignalCh8 CS4College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 3-2 : Symmetric Cryptography, Block Cipher, DES  Block Ciper Principle in Symmetric Cryptography  DES Principle vs History  DES Operation ; Phase1: Initia Permutation ‘IP(x)’  DES Operation ; Phase2: Keys’ Generation  DES Operation ; Phase3: Iterations and Rounds  DES Operation ; Phase4: Inverse Permutation ‘IP-1’ okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Modern Block Ciphers One of the most widely used types of Cryptographic Algorithms Provide secrecy and/or authentication services In particular will introduce DES (Data Encryption okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Block Ciphers vs Stream Ciphers Block ciphers process messages into blocks, each of which is then en/decrypted Like a substitution on very big characters 64-bits or more Stream ciphers process messages a bit or byte at a time when encrypting/decrypting Many current ciphers are block ciphers Hence are focus of course okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Symmetric encryption - Block Cipher Principle - Principle: The text is divided into different blocks of fixed size. One block is processed at a time, producing one block of encrypted data. - The block must be fully available before processing - The same function and the same key are used to encrypt successive blocks. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Block Ciphers - Operation Operates on a single chunk (“block”) of Plaintext For example, 64 bits for DES Algorithm… Same key is reused for each block (can use short keys) Result should look like a random permutation As if Plaintext bits were randomly shuffled ! Only computational guarantee of secrecy Not impossible to break, just very expensive… If there is no efficient algorithm (unproven assumption!), then can only break by brute-force, try-every-possible-key search. Time/cost of breaking the cipher exceeds the value and/or useful lifetime of protected information okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Block Ciphers : Example the Permutations 1 1 1 2 3 4 2 2 3 3 4 4 2 4 1 3 CODE becomes DCEO For N-bits input, N! possible permutations Idea: split plaintext into blocks, for each block use secret key to pick a permutation, rinse and repeat Without the key, permutation should “look random” okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Block Cipher Operation (Simplified) Block of plaintext Key Add some secret key bits to provide confusion S S S S S S S S Each S-box permutes its input bits in a repeat for several rounds “random-looking” way to provide diffusion (spread plaintext bits S S S S throughout ciphertext) Procedure must be reversible Block of ciphertext (for decryption) okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Claude Shannon : Substitution-Permutation Ciphers in 1949 Claude Shannon introduced idea of Substitution- Permutation (S-P) networks… modern substitution-transposition product cipher These form the basis of modern block ciphers… S-P networks are based on the two primitive cryptographic operations we have seen before: Substitution (S-box) Permutation (P-box) provide confusion and diffusion of message okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 3-2 : Symmetric Cryptography, Block Cipher, DES  Block Ciper Principle in Symmetric Cryptography  DES Principle vs History  DES Operation ; Phase1: Initia Permutation ‘IP(x)’  DES Operation ; Phase2: Keys’ Generation  DES Operation ; Phase3: Iterations and Rounds  DES Operation ; Phase4: Inverse Permutation ‘IP-1’ okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Data Encryption Standard (DES) Most widely used block cipher in world Adopted in 1977 by NBS (now NIST http://www.itl.nist.gov/fipspubs/fip46-2.htm ) Encrypts 64-bit data ; using (16 keys) : 64 to 56 to 48- bits keys Has widespread use ; Has been considerable controversy over its security. (DES Key Creation) (DES Message Encryption) https://youtu.be/8TWdL1C7DGY https://youtu.be/fdJokZ_gkl4 okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES History IBM developed Lucifer cipher : by team led by Feistel used 64-bit data blocks with 128-bit key then redeveloped as a commercial cipher with input from NSA and others ; in 1973 NBS issued request for proposals for a national cipher standard ; IBM submitted their revised Lucifer which was eventually accepted as the DES… okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA  Message is split into blocks of 64 Bits ;  Secret chosen Key of 64 Bits ; then generation of 16 (48 Bits) Keys, for 16 rounds…  Initialization: Permutation of all 64 Bits DES History forming the message block.  64 Bits Block is cut into two parts: L0 (32) and R0 (32) S-Boxes are tables that define permutations.  Stages of this development have remained The DES (Data Encryption Standard) algorithm (the secret, is the most widelySused design encryption algorithm in the world. Boxes). For many years, and among many people, "secret code making" and DES have been synonymous. And despite the recent coup by the Electronic Frontier Foundation in creating a $220,000 machine to crack DES-encrypted messages, DES will live on in government and banking for years to come through a life- extending version called "triple-DES." okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Data Encryption Standard (DES) Data Encryption Standard (DES) is an example of symmetric encryption (same key to Encryt et Decryt) based on the CBC technique (encrypted blocks are linked); it is widely employed by the US Federal Government. Divide into blocks with 64-bits: Blocks using relatively short keys of 64-bits real size and 56-bits effective size and (16 generated Keys) 48-bits execution size. Algorithm : Product of Substitutions & Transpositions. Easy implementation in hardware. Transposition boxes P-Box Substitution boxes S-Box okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Chapter 2: Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Cryptography Data Encryption Standard (DES)  The symmetric block cipher scheme  Developed in the 70s by IBM, ANSI standard in 1981 (ANSI X3.92)  Widely used in banking transactions  No longer considered robust enough  Principle: (16 generated Keys) Since the creation of DES, many other algorithms 48-bits execution size (recipes for changing data) have emerged which are based on design principles similar to DES. (1) 023 Understanding DES Block Cipher – YouTube (2) (1) Data Encryption Standard (DES) - Explained with an Exampl e - Cryptography - CyberSecurity - CSE4003 - YouTube okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , 16 CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Message of Plaintext DES Ph a se We Have Encryption 1 16 rounds 48 bit Algorithm Ph a se 2 Ph Then a se Generate 3 Key for each round Decryption Ph Similar a se Message Algorythm 4 CipherText okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA 04 Phases of DES Algorithm Phase 1: Initial Permutation ‘IP’ For each block of 64 bits ‘x’ of the text, we calculate an initial permutation y=IP(x). ‘y’ is represented as y=L0R 0 , where L0 is the Left 32 bits of y, R0 is the Right 32 bits. Phase 2: Diversification of the key into 16 sub-Keys : 64 – 56 – 48 Bits each Key… ‘K’ is a fixed secret 64 Bits Key. From ‘K’, we genrate16 sub-keys (K1,...,K16) at 48 Bits each. Phase 3: Iteration : We apply 16 iterations (for each K1,...,K16) of the same function. From LiRi (for i from 1 to 16), Li+1Ri+1 is hence calculated by setting: Li+1 = Ri and Ri+1 = Li XOR f(Ri,Ki ). Phase 4: Final permutation : The inverse of the Initial Permutation ‘IP ’ is applied to okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing ,-1 CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Encryption ‘m’ or Decryption ‘m’ 64-Bits input block 16 sub-keys ‘C’ 64-Bits input block K1,...,K16 ‘x’ 48 Bits each DES 32 Bits Li 32 Bits Ri Subkey 48 Bits Subkey 48 Bits 32 Bits Li+1 32 Bits Ri+1 16 Rounds Ki Ki Encryption function Decryption function Here, One Round ‘i‘ + + 32 Bits Li+1 32 Bits Ri+1 32 Bits Li 32 Bits Ri O ne ‘i‘ Ro un ‘C’ 64-Bits block output ‘m’ 64-Bits block output d okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 3-2 : Symmetric Cryptography, Block Cipher, DES  Block Ciper Principle in Symmetric Cryptography  DES Principle vs History  DES Operation ; Phase1: Initia Permutation ‘IP(x)’  DES Operation ; Phase2: Keys’ Generation  DES Operation ; Phase3: Iterations and Rounds  DES Operation ; Phase4: Inverse Permutation ‘IP-1’ okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES – Phase 1 - Initial IP Initial Permutation Permutatio n Then, at the end, IP-1 IP According to this Table y = IP(x) x : 64 Bits 0011 … 10 1 2 3 4 5 6 7 8 9 … ,, ,,, ,,, 5 5 5 6 6 6 6 6 7 8 9 0 1 2 3 4 Bit at position 58 5 5 4 3 2 1 1 2 6 … ,, ,,, ,,, 6 5 4 3 3 2 1 7 become the 8 0 2 4 6 8 0 0 3 5 7 9 1 3 5 bit at position okhtar 1 BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES – Phase 1 - 1 2 3 4 5 6 7 8 IP 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 IP - Initial Permutation 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 Plaintext ( 64- bit block ‘x’) 59 51 43 35 27 19 11 3 IP 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 xample: Permuted block ( 64 bits) 2 58 1 0 0 ‘x’ 64Bits 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0001010 101 1 8 ‘y’=IP(x 1………………..0 …… ) okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES – Phase 1 - IP 58 50 42 34 26 18 10 2 Phase 1: 60 52 44 36 28 20 12 4 Encode each 64-Bits block 62 54 46 38 30 22 14 6 of data : 64 56 48 40 32 24 16 8 A- Do an Initial 57 49 41 33 25 17 9 1 Permutation 59 51 43 35 27 19 11 3 based on 61 53 45 37 29 21 13 5 permutation table (IP). 63 55 47 39 31 23 15 7 Example: Applying the initial permutation to the block of text x, we get x = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 okhtar 1111 BEN HMIDA, 0000 1010 1010 Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES – Phase 1 - IP B- Divide Permuted block IP : Left half L1 (32 bits), and Right half R1 (32 bits). Example: From IP, we get L1 and R1 x = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 L0 R0 IP = 1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010 L = 1100 1100 0000 0000 1100 1100 1111 1111 okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES – Phase 1 - IP C- From Permuted block IP ; we get the initial Bolck L0R0 L0 (32 bits) and R0 (32 bits). L0 = 1100 1100 0000 0000 1100 1100 1111 1111 R0 = 1111 0000 1010 1010 1111 0000 1010 1010 We can go henceforth for the Rounds’ iterations According to the generated Keys (K1,...,K16 ) In order to get the relative Blocks L R L R until L16Rat16 1 Processing okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal CS College King Kh 1 ; 2 ,2  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 3-2 : Symmetric Cryptography, Block Cipher, DES  Block Ciper Principle in Symmetric Cryptography  DES Principle vs History  DES Operation ; Phase1: Initia Permutation ‘IP(x)’  DES Operation ; Phase2: Keys’ K1,...,K16 Generation  DES Operation ; Phase3: Iterations and Rounds  DES Operation ; Phase4: Inverse Permutation ‘IP-1’ okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES Phase 2: Keys’ Generation 64 Bits Comp1 56 bits = 28+28 + Rot° then Comp2 24+24=48 Sub-keys (Round keys: K1,...,K16) are generated from the main 64-Bits secret key ‘K’ A 1st Compression of the key ‘K’ 64 bits  56 bits : 8 bits will be ignored !!! Split the 56-bit key into two segments : 28 Bits + 28 iBts Rotation of each segment by 1 or 2 bits to the left : Rot° 28 bits + Rot° 28 bits. 2nd Compression  Selection of 24 bits of each segment : 24 bits + 24 bits okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES Phase 2: Keys’ Generation 64 Bits Comp1 56 bits = 28+28 + Rot° then Comp2 24+24=48 The sub-keys (Round keys) are generated from the main 64-bit key: A 1st compression of the key (64 bits  56 bits) : 8 bits will be ignored !!! Split the 56-bit key into two segments : 28 bits + 28 bits Rotation of each segment by 1 or 2 bits to the leftt : Rot 28 bits + Rot 28 bits. 2nd compression  Selection of 24 okhtar BEN HMIDA, bits of each segment Dr. & Full : 24ofbits Professor, Head ATMS+ 24Expert in Signal Processing, Lab, CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES Phase 2: Keys’ Generation 64 Bits Comp1 56 bits = 28+28 + Rot° then Comp2 24+24=48 Step 1: Reduce the number of bits from 64 bits to 48 bits. A. 64 Bits to 56 Bits : Do an initial permutation based on permutation table. PC-1 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 PC-1 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 Example: From the original 64-Bits key ‘K’ ; we get ‘K+’ 56-Bits K = 0001 0011 0011 0100 0101 0111 0111 1001 1001 1011 1011 1100 1101 1111 1111 0001 K+BEN okhtar = 1111 0000 HMIDA, 1100 1100 1010 1010 1111 0101 0101 0110 0110 CS Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , 0111 1000 College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES Phase 2: Keys’ Generation 64 Bits Comp1 56 bits = 28+28 + Rot° then Comp2 24+24=48 B. Split this key into left and right halves, C0 and D0, where each half has 28 bits. Example: From the permuted key K+, we get C0 = 1111000 0110011 0010101 0101111 D0 = 0101010 1011001 1001111 0001111 C. Create 16 subkeys to be used in the 16 rounds from ; beginning from C0 and D0 : With C0 and D0 , we now want to create sixteen blocks Cn and Dn, n = 1, 2,..., 16 Each block ’Cn and Dn’ is formed from the previous pair Cn-1 and Dn-1, respectively, For n = 1, 2,..., 16, we use the following schedule of "left shifts" of the previous block. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES Phase 2: Keys’ Generation 64 Bits Comp1 56 bits = 28+28 + Rot° then Comp2 24+24=48 Ki 64-Bits Symmetric Key We ignore 1 bit out of 8 for a possible control of 56-Bits key parity 28 bit 28 bit 10001011101000101110111101 0101000000100000010101011 0101 111 C0 Shift by 1 or 2 D0 Shift by 1 or 2 Round 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ‘I’ Decal 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 Shift This means, C3 and D3 are obtained from C2 and D2, respectively, by two (02) left shifts, and C16 and D16 are obtained from C15 and D15, respectively, by one left shift. (DES Key Creation) https://youtu.be/8TWdL1C7DGY okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES Phase 2: Keys’ Generation 64 Bits Comp1 56 bits = 28+28 + Rot° then Comp2 Ki 24+24=48 28 bits + 28 bits shifted = 56 bits shifted 000101110100010111011 101000000100000010101 110101011 0111110 18 ignored 28 Compressed Skipped bits Permutation 48 Bits 1 2 3 4 5 6 7 8 9 10 11 12 14 17 11 24 1 5 3 28 15 6 21 10 23 19 12 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA C0 = 1111000011001100101010101111 C9 = 0101010101111111100001100110 D0 = 0101010101100110011110001111 D9 = 0011110001111010101010110011 C1 = 1110000110011001010101011111 C10 = 0101010111111110000110011001 DES Phase 2: D1 = 1010101011001100111100011110 D10 = 1111000111101010101011001100 C2 = 1100001100110010101010111111 Keys’ GenerationD = 0101010110011001111000111101 2 C11 = 0101011111111000011001100101 D11 = 1100011110101010101100110011 C3 = 0000110011001010101011111111 64 Bits Comp1 56 bits C12 = 0101111111100001100110010101 D3 = 0101011001100111100011110101 = D12 = 0001111010101010110011001111 28+28 + Rot° C4 = 0011001100101010101111111100 D4 = 0101100110011110001111010101 C13 = 0111111110000110011001010101 then Comp2 24+24=48 D13 = 0111101010101011001100111100 C5 = 1100110010101010111111110000 D5 = 0110011001111000111101010101 C14 = 1111111000011001100101010101 C6 = 0011001010101011111111000011 D14 = 1110101010101100110011110001 D6 = 1001100111100011110101010101 C15 = 1111100001100110010101010111 C7 = 1100101010101111111100001100 D15 = 1010101010110011001111000111 D7 = 0110011110001111010101010110 C16 = 1111000011001100101010101111 C8 = 0010101010111111110000110011 D16 = 0101010101100110011110001111 okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA D. Applying the following Permutation Table to each of the concatenated pairs CnDn. DES Phase 2: 14 3 17 28 11 24 15 1 5 6 21 10 Keys’ Generation 23 19 12 4 26 8 PC-2 16 7 27 20 13 2 64 Bits Comp1 56 bits 41 52 31 37 47 55 = 30 40 51 45 33 Each 48 pair has 56 bits, 28+28 + Rot° 44 49 39 56 34 but 53PC-2 only uses 48 then 46 42 50 36 29 of32 these. Comp2 24+24=48 Example: For the first key we have C1D1 = 1110000 1100110 0101010 1011111 1010101 0110011 0011110 0011110 which, after we apply the permutation PC-2, becomes K1 = 000110 110000 001011 101111 111111 000111 000001 110010 okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA For the other keys we have : K2 = 011110 011010 111011 011001 110110 111100 100111 100101 K3 = 010101 011111 110010 001010 010000 101100 111110 011001 DES Phase 2: K4 = 011100 101010 110111 010110 110110 110011 010100 011101 K5 = 011111 001110 110000 000111 111010 110101 001110 101000 Keys’ Generation K6 = 011000 111010 010100 111110 010100 000111 101100 101111 64 Bits Comp1 56 bits K7 = 111011 001000 010010 110111 111101 100001 100010 111100 = K8 = 111101 111000 101000 111010 110000 010011 101111 111011 28+28 + Rot° K9 = 111000 001101 101111 101011 111011 011110 011110 000001 then Comp2 24+24 K10 = 101100 011111 001101 000111 101110 100100 011001 001111 = K11 = 001000 010101 111111 010011 110111 101101 001110 000110 48 Bits Keys K12 = 011101 010111 000111 110101 100101 000110 011111 101001 K13 = 100101 111100 010111 010001 111110 101011 101001 000001 K14 = 010111 110100 001110 110111 111100 101110 011100 111010 K15 = 101111 111001 000110 001101 001111 010011 111100 001010 K16 = 110010 110011 110110 001011 000011 100001 011111 110101 okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 3-2 : Symmetric Cryptography, Block Cipher, DES  Block Ciper Principle in Symmetric Cryptography  DES Principle vs History  DES Operation ; Phase1: Initia Permutation ‘IP(x)’  DES Operation ; Phase2: Keys’ Generation  DES Operation ; Phase3: Iterations and Rounds  DES Operation ; Phase4: Inverse Permutation ‘IP-1’ okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA 04 Phases of DES Algorithm Phase 1: Initial Permutation ‘IP’ For each block of 64 Bits ‘x’ of the text, we calculate a finite permutation y=IP(x). ‘y’ is represented as y=L0R 0 , where L0 is the Left 32 bits of y, R0 is the Right 32 bits. Phase 2: Diversification of the key into 16 sub-Keys : 64 – 56 – 48 Bits each Key… ‘K’ is a fixed secret 64 Bits Key. From ‘K’, we genrate16 sub-keys (K1,...,K16) at 48 Bits each. Phase 3: Iteration : We apply 16 iterations (for each K1,...,K16) of the same function. From LiRi (for i from 1 to 16), Li+1Ri+1 is hence calculated by setting: Li+1 = Ri and Ri+1 = Li XOR f(Ri,Ki ). Phase 4: Final permutation : The inverse of the Initial Permutation ‘IP ’ is applied to okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing ,-1 CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA General Depiction DES Encryption Algorithm okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Encryption ‘m’ or Decryption ‘m’ 64-Bits input block 16 sub-keys ‘C’ 64-Bits input block K1,...,K16 ‘x’ 48 Bits each DES 32 Bits Li 32 Bits Ri Subkey 48 Bits Subkey 48 Bits 32 Bits Li+1 32 Bits Ri+1 16 Rounds Ki Ki Encryption function Decryption function Here, One Round ‘i‘ + + 32 Bits Li+1 32 Bits Ri+1 32 Bits Li 32 Bits Ri O ne ‘i‘ Ro un ‘C’ 64-Bits block output ‘m’ 64-Bits block output d okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Recap DES Algorithm okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Recap DES Algorithm okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES (Phase 3 : Rounds & Iterations) The secret key is transformed into 16 Ki parts of 48 Bits : K1 ; K2 ; K3 ;…; K16 Then, we swap the two parts by introducing a function of the key. L1 = R 0. R1 = L0 + f (K1, R0). This operation is repeated 16 times. At each step i, we have: okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES (Phase 3 : Rounds & Iterations) Ki represents the subkey number ‘i ‘ obtained from the secret key. The calculation of ‘f’ is done as follows: The 32 Bits of the R part are extended to 48 Bits using a Table called E (Expansion). This new R, E(R) to be more precise, is added XOR to Ki. The result is divided into eight (08) sequences Bi of six (06) Bits: By HMIDA, okhtar BEN Using the Dr. S-Box Table, the & Full Professor, Headdata of these of ATMS eight Lab, Expert sequences in Signal gives Processing , a result of at CS College 32King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Data Encryption HAS Standard A (DES) B B Encryption function ‘f’ VS C okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Data Encryption Standard (DES) Ri Ki Expansion: 32 - 48 Bits A 48 48 Bits Bits 6 Bits 6 Bits B Sj: Reduction by blocks 6 Bits towards 4Bits 4 Bits 4 Bits 32 Bits Permutation the 32 Bits by P C 32 Bits okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Data Encryption Standard (DES) Sample okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA A- Expansion function : 32 Bits to 48 Bits A 32-bits input blocks Ri to a 48-bits block Ri'. Split of 32-Bits into 4-Bits segments Expand each 4-Bits segment with the bits of its neighbors to expect 6-Bits. XOR the 48-Bits output with the key. 32-Bits 1 2 3 4 5 6 7 8 9 … 3 2 32 1 2 3 4 5 4 5 6 7 8 9 ,,, 2 2 3 3 3 1 48- 1 2 3 8 9 0 1 2 47 48 4 Bits okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA B- Substitute function There are 8 S-Boxes, one for each Bi. BSj : R 6B ed Each S-Box has 16 columns and 4 rows. its uc to tion wa rd by b s4 Bi = b1b2b3b4b5b6. We calculate Bi lock ts s r = b1b6 c = b2b3b4b5. Look at the number in row r and column c. It was coded on 4 bits ; corresponds to the output Si(Bi). Then we perform a permutation represented by a table called P and the result of this permutation is returned by the function f. For Decryption, do the reverse operation. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  S ; KKU - KSA Cryptography (Classic) College of Computer Science ; King Khalid University j: Red 6B its uction B tow ard by blo s4 Bits cks 6 Bits  input 0 0 1 0 0 1 B- 11104 Bits  output Substitution 010 14 0 Function According to 00 this Table 01 14 10 11 A 6-Bits sub-block is transformed into a 4-Bits sub-block. okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA C – Permutation function According to this Table Pe C rmut at ion th e 32 Bi ts by P The Bit at position 1 was sent to position 16 okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Data Encryption Standard (DES) Ri Ki Expansion: 32 - 48 Bits A 48 48 Bits Bits 6 Bits 6 Bits B Sj: Reduction by blocks 6 Bits towards 4Bits 4 Bits 4 Bits 32 Bits Permutation the 32 Bits by P C 32 Bits okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Encryption Decryption ‘m’ 64-Bits input block 16 sub-keys ‘C’ 64-Bits input block K1,...,K16 48 Bits each DES 32 Bits Li 32 Bits Ri Subkey 48 Bits Subkey 48 Bits 32 Bits Li+1 32 Bits Ri+1 16 Rounds Ki Ki Encryption function Decryption function Here, One Round ‘i‘ + + 32 Bits Li+1 32 Bits Ri+1 32 Bits Li 32 Bits Ri O ne ‘i‘ Ro un ‘C’ 64-Bits block output ‘m’ 64-Bits block output d okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 3-2 : Symmetric Cryptography, Block Cipher, DES  Block Ciper Principle in Symmetric Cryptography  DES Principle vs History  DES Operation ; Phase1: Initia Permutation ‘IP(x)’  DES Operation ; Phase2: Keys’ Generation  DES Operation ; Phase3: Iterations and Rounds  DES Operation ; Phase4: Inverse Permutation ‘IP-1’ okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Final Permutation IP-1 The output result is a 64-Bits Ciphertext ‘C’ In the end, IP-1 According to this Table Link : DES (DES Message Encryption) https://youtu.be/fdJokZ_gkl4 https://youtu.be/cVhlCzmb-v0 okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA DES – Phase 4 – IP - Inverse 1 and Final Inversse and Final Permutatio At the end, IP-1 n Permutation IP-1 According to this Table x = IP-1(c) c : 64 Bits 0011 … 10 1 2 3 4 5 6 7 8 9 … ,, ,,, 5 5 5 5 6 6 6 6 6 6 7 8 9 0 1 2 3 4 Bit at position 64 4 8 4 1 5 2 6 3 3 … ,, ,,, ,,, 3 1 4 9 4 1 5 2 become the 0 8 6 6 4 4 2 9 3 1 9 7 7 5 bit at position okhtar 7 BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Recap DES Algorithm Final Permutation okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA General Depiction DES Encryption Algorithm Final Permutation okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh  Cryptography (Classic) College of Computer Science ; King Khalid University ; KKU - KSA Example: M Plain text message M = 0123456789ABCDEF, in hexadecimal (base 16) M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 L = 0000 0001 0010 0011 0100 0101 0110 0111 R = 1000 1001 1010 1011 1100 1101 1110 1111 The first bit of M is "0". The last bit is "1". We read from left to right. DES operates on the 64-bit blocks using key sizes of 56- bits. The keys are actually stored as being 64 bits long, but every 8th bit in the key is not used (i.e. bits numbered 8, 16, 24, 32, 40, 48, 56, and 64). However, we will nevertheless number the bits from 1 to 64, going left to right, in the following calculations. But, as you will see, the eight bits just mentioned get eliminated when we create subkeys. Let K be the hexadecimal key K = 133457799BBCDFF1. K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001 okhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Kh