AnnouncementReviewBasic TerminologyFeistel Cipher StructureSlide 5DES (Data Encryption Standard)DES Top ViewBit Permutation (1-to-1)Per-Round Key GenerationA DES RoundMangler FunctionSlide 12S-Box (Substitute and Shrink)S-Box Example (S-Box 1)DES StandardDES Box SummaryOutlinesAvalanche EffectStrength of DES – Key SizeDES ReplacementAESSlide 22Private-Key CryptographyPublic-Key CryptographySlide 25Slide 26Public-Key CharacteristicsPublic-Key CryptosystemsSlide 29Modular ArithmeticModular AdditionModular MultiplicationSlide 33Totient FunctionModular ExponentiationSlide 36Slide 37RSA (Rivest, Shamir, Adleman)What Is RSA?RSA ExampleHow Does RSA Work?Why Does RSA Work?Is RSA Secure?Symmetric (DES) vs. Public Key (RSA)Announcement•Homework 1 out, due 1/18 11:59pm•If you purchased the textbooks, but it hasn’t arrived, please see TA for copies of the questions, •Project 1 due tomorrow midnightReview•Overview of Cryptography•Classical Symmetric Cipher–Substitution Cipher–Transposition Cipher–Product Cipher•Modern Symmetric Ciphers (DES)Basic Terminology•plaintext - the original message •ciphertext - the coded message •cipher - algorithm for transforming plaintext to ciphertext •key - info used in cipher known only to sender/receiver •encipher (encrypt) - converting plaintext to ciphertext •decipher (decrypt) - recovering ciphertext from plaintext•cryptography - study of encryption principles/methods•cryptanalysis (codebreaking) - the study of principles/ methods of deciphering ciphertext without knowing key•cryptology - the field of both cryptography and cryptanalysisFeistel Cipher Structure•Feistel cipher implements Shannon’s S-P network concept–based on invertible product cipher•Process through multiple rounds which –partitions input block into two halves–perform a substitution on left data half–based on round function of right half & subkey–then have permutation swapping halvesFeistel Cipher Structure• Feistel cipher implements Shannon’s S-P network concept• Achieve diffusion and confusionDES (Data Encryption Standard)•Published in 1977, standardized in 1979.•Key: 64 bit quantity=8-bit parity+56-bit key–Every 8th bit is a parity bit.•64 bit input, 64 bit output.DESEncryption64 bit M 64 bit C56 bitsDES Top ViewPermutationPermutationSwapRound 1Round 2Round 16Generate keysInitial Permutation48-bit K148-bit K248-bit K16Swap 32-bit halvesFinal Permutation64-bit Output48-bit K164-bit Input56-bit Key…...Bit Permutation (1-to-1)…….…….. 1 2 3 4 3222 6 13 32 3Input:Output 0 0 1 0 1 1 0 1 1 11 bitPer-Round Key Generation28 bits 28 bits48 bitsKiOneroundCircular Left Shift Circular Left Shift28 bits 28 bitsPermutationwith DiscardInitial Permutation of DES keyC i-1D i-1C iD iRound 1,2,9,16: single shiftOthers: two bitsA DES Round48 bits32 bits32 bits Ln32 bits Rn32 bits Ln+132 bits Rn+1 ES-BoxesP48 bitsKiOne RoundEncryptionManglerFunctionMangler Function4444444 46666666 6+ + +++ ++ +6666666 6S8S1 S2 S7S3 S4 S5 S64444444 4PermutationThe permutation produces “spread” among the chunks/S-boxes!Bits Expansion (1-to-m)…….…….. 1 2 3 4 5 32Input:Output 0 0 1 0 1 1 1 2 3 4 5 6 7 8 481 0 0 1 0 1 0 1 1 0S-Box (Substitute and Shrink)•48 bits ==> 32 bits. (8*6 ==> 8*4)•2 bits used to select amongst 4 substitutions for the rest of the 4-bit quantity2 bitsrowSii= 1,…8.I1I2I3I4I5I6O1O2O3O44 bitscolumnS-Box Example (S-Box 1)0 1 2 3 4 5 6 7 8 9…. 150 14 4 13 1 2 15 11 8 31 0 15 7 4 14 2 13 1 102 4 1 14 8 13 6 2 11 153 15 12 8 2 4 9 1 7 5Each row and column contain different numbers.Example: input: 100110 output: ???DES Standard•Cipher Iterative Action :–Input: 64 bits–Key: 48 bits–Output: 64 bits•Key Generation Box :–Input: 56 bits–Output: 48 bitsOne round (Total 16 rounds)DES Box Summary•Simple, easy to implement:–Hardware/gigabits/second, software/megabits/second•56-bit key DES may be acceptable for non-critical applications but triple DES (DES3) should be secure for most applications today•Supports several operation modes (ECB CBC, OFB, CFB) for different applicationsOutlines•Strength/weakness of DES, AES•Public Key Cryptography•Modular Arithmetic•RSAAvalanche Effect •Key desirable property of encryption alg•Where a change of one input or key bit results in changing more than half output bits•DES exhibits strong avalancheStrength of DES – Key Size•56-bit keys have 256 = 7.2 x 1016 values•Brute force search looks hard•Recent advances have shown is possible–in 1997 on a huge cluster of computers over the Internet in a few months –in 1998 on dedicated hardware called “DES cracker” by EFF in a few days ($220,000)–in 1999 above combined in 22hrs!•Still must be able to recognize plaintext•No big flaw for DES algorithmsDES Replacement•Triple-DES (3DES)–168-bit key, no brute force attacks–Underlying encryption algorithm the same, no effective analytic attacks–Drawbacks•Performance: no efficient software codes for DES/3DES•Efficiency/security: bigger block size desirable•Advanced Encryption Standards (AES) –US NIST issued call for ciphers in 1997–Rijndael was selected as the AES in Oct-2000AES•Private key symmetric block cipher •128-bit data, 128/192/256-bit keys •Stronger & faster than Triple-DES •Provide full specification & design details •Evaluation criteria–security – effort to practically cryptanalysis–cost – computational–algorithm & implementation characteristicsOutlines•Strength/weakness of DES, AES•Public Key Cryptography•Modular Arithmetic•RSAPrivate-Key Cryptography•Private/secret/single key cryptography uses one key •Shared by both sender and receiver •If this key is disclosed communications are compromised •Also is symmetric, parties are equal •Hence does not protect sender from receiver forging a message & claiming is sent by senderPublic-Key Cryptography•Probably most significant advance in the 3000 year history of cryptography •Uses two keys – a public & a