CSC 474/574 By Dr. Peng Ning 1Computer ScienceCSC 474/574Information Systems SecurityTopic 2.1 Introduction to CryptographyCSC 474/574 By Dr. Peng Ning 2Computer ScienceCryptography• Cryptography– Original meaning: The art of secret writing– Becoming a science that relies on mathematics(number theory, algebra)– Process data into intelligible form, reversible,without data loss– Usually one-to-one (not compression)CSC 474/574 By Dr. Peng Ning 3Computer ScienceplaintextencryptionciphertextdecryptionplaintextkeykeyEncryption/Decryption• Plaintext: a message in its original form• Ciphertext: a message in the transformed, unrecognized form• Encryption: the process that transforms a plaintext into aciphertext• Decryption: the process that transforms a ciphertext to thecorresponding plaintext• Key: the value used to control encryption/decryption.CSC 474/574 By Dr. Peng Ning 4Computer ScienceCryptanalysis• Ciphertext only:– Analyze only with the ciphertext– Example: Exhaustive search until “recognizableplaintext”– Smarter ways available• Known plaintext:– Secret may be revealed (by spy, time), thus<ciphertext, plaintext> pair is obtained– Great for mono-alphabetic ciphersCSC 474/574 By Dr. Peng Ning 5Computer ScienceCryptanalysis (Cont’d)• Chosen plaintext:– Choose text, get encrypted– Useful if limited set of messages• Chosen ciphertext:– Choose ciphertext– Get feedback from decryption, etc.CSC 474/574 By Dr. Peng Ning 6Computer ScienceSecurity of An Encryption Algorithm• Unconditionally secure– It is impossible to decrypt the ciphertext– One-time pad (the key is as long as the plaintext)• Computationally secure– The cost of breaking the cipher exceeds the value of theencrypted information– The time required to break the cipher exceeds the usefullifetime of the informationiiikPC ⊕=CSC 474/574 By Dr. Peng Ning 7Computer ScienceExhaustive Key Search (Brute ForceAttack)6.4X106 years2X226µs=6.4X1012years26!=4X102626 characters(permutation)5.4X1018years2127µs=5.4X1024years2128=3.4X103812810.01 hours255µs=1142 years256=7.2X1026562.15 milliseconds232µs=35.8 minutes232=4.3X10932Time required at 106encryptions/µsTime required at 1encryption/µsNumber ofAlternative KeysKey Size(bits)CSC 474/574 By Dr. Peng Ning 8Computer ScienceSecret Keys v.s. Secret Algorithms• Security by obscurity– We can achieve better security if we keep thealgorithms secret– Hard to keep secret if used widely– Reverse engineering, social engineering• Publish the algorithms– Security of the algorithms depends on the secrecyof the keys– Less unknown vulnerability if all the smart (good)people in the world are examine the algorithmsCSC 474/574 By Dr. Peng Ning 9Computer ScienceSecret Keys v.s. Secret Algorithms (cont’d)• Commercial world– Published– Wide review, trust• Military– Keep algorithms secret– Avoid giving enemy good ideas– Military has access to the public domainknowledge anyway.CSC 474/574 By Dr. Peng Ning 10Computer ScienceSome Trivial Codes• Caesar cipher: substitution cipher:– Replace each letter with the one 3 letters later– A Æ D, B Æ E• Captain Midnight Secret Decoder rings:– shift variable by n: IBM Æ HAL– only 26 possibilitiesCSC 474/574 By Dr. Peng Ning 11Computer ScienceSome Trivial Codes (Cont’d)• Mono-alphabetic cipher:– generalization, arbitrary mapping of one letter toanother– 26!, approximately 4 ¥ 1026– statistical analysis of letter frequenciesCSC 474/574 By Dr. Peng Ning 12Computer ScienceSome Trivial Codes (Cont’d)• Hill Cipher– Encryption: C = KP or– Decryption: P = K-1C– Problem:• Known plaintext attackCSC 474/574 By Dr. Peng Ning 13Computer ScienceSome Trivial Codes (cont’d)• Poly-alphabetic Ciphers– A set of related mono-alphabetic substitution rulesis used– A key determines which particular rule is chosenfor a given transformationCSC 474/574 By Dr. Peng Ning 14Computer ScienceSome Trivial Codes (Cont’d)• All the previous codes are based on substitution• Transposition (permutation)ZTEP7YXMAOWLITNUDNOPTSOKCATTAPlaintext:652134Key:• Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZCSC 474/574 By Dr. Peng Ning 15Computer ScienceTypes of Cryptography• Number of keys– Hash functions: no key– Secret key cryptography: one key– Public key cryptography: two keys - public, private• The way in which the plaintext is processed– Block cipher: divides input elements into blocks– Stream cipher: process one element (e.g., bit) atimeCSC 474/574 By Dr. Peng Ning 16Computer ScienceplaintextencryptionciphertextdecryptionplaintextkeykeySame keySecret Key Cryptography• Same key is used for encryption and decryption• Also known as– Symmetric cryptography– Conventional cryptographyCSC 474/574 By Dr. Peng Ning 17Computer ScienceSecret Key Cryptography (cont’d)• Basic technique– Product cipher:– Multiple applications of interleaved substitutionsand permutationsplaintext S P S P S ciphertext…keyCSC 474/574 By Dr. Peng Ning 18Computer ScienceSecret Key Cryptography (cont’d)• Ciphertext approximately the same length asplaintext• Examples– Stream Cipher: RC4– Block Cipher: DES, IDEA, AESCSC 474/574 By Dr. Peng Ning 19Computer ScienceApplications of Secret Key Cryptography• Transmitting over an insecure channel– Challenge: How to share the key?• Secure Storage on insecure media• Authentication– Challenge-response– To prove the other party knows the secret key– Must be secure against chosen plaintext attack• Integrity check– Message integrity code (MIC)CSC 474/574 By Dr. Peng Ning 20Computer ScienceplaintextencryptionciphertextdecryptionplaintextPublic key Private keyPublic Key Cryptography• Invented/published in 1975• A public/private key pair is used– Public key can be publicly known– Private key is kept secret by the owner of the key• Much slower than secret key cryptography• Also known as– Asymmetric cryptographyCSC 474/574 By Dr. Peng Ning 21Computer SciencemessageSignDigital signatureVerifyYes/NoPrivate key Public keyPublic Key Cryptography (Cont’d)• Another mode: digital signature– Only the party with the private key can create a digitalsignature.– The digital signature is verifiable by anyone who knows thepublic key.– The signer cannot deny that he/she has done so.CSC 474/574 By Dr. Peng Ning 22Computer ScienceApplications of Public Key Cryptography• Data transmission:– Alice