1Page 1Page 1Introduction to Cryptography Paul [email protected] SystemsExcept as otherwise noted, the content of this presentation is licensed under the Creative Commons Attribution 2.5 License.Page 2Page 2Ngywioggazhon PystempAuesfnsicutiwf & MoiiunocaiwnPiqtoaoypPage 3Page 3Cryptographic SystemsAuthentication & CommunicationProtocolsPage 4cryptographyκρυπόςhiddenγραφίαwritingA secret manner of writing, … Generally, the art of writing or solving ciphers. — Oxford English DictionaryPage 5cryptologyκρυπόςhiddenλογιαspeaking1967 D. Kahn, Codebreakers p. xvi, Cryptology is the science that embraces cryptography and cryptanalysis, but the term ‘cryptology’ sometimes loosely designates the entire dual field of both rendering signals secure and extracting information from them. — Oxford English DictionaryPage 6Cryptography  SecurityCryptography may be a component of a secure systemAdding cryptography may not make a system secure2Page 7TermsPlaintext (cleartext), message Mencryption, E(M)produces ciphertext, C=E(M)decryption: M=D(C)Cryptographic algorithm, cipherPage 8Terms: types of ciphers• restricted cipher• symmetric algorithm• public key algorithmPage 9Restricted cipherSecret algorithm• Leaking• Reverse engineering– HD DVD (Dec 2006) and Blu-Ray (Jan 2007)– RC4– All digital cellular encryption algorithms– DVD and DIVX video compression– Firewire– Enigma cipher machine– Every NATO and Warsaw Pact algorithm during Cold WarPage 10The keyBTW, the above is a bump key. See http://en.wikipedia.org/wiki/Lock_bumping.Page 11The keySource: en.wikipedia.org/wiki/Pin_tumbler_lockPage 12The keySource: en.wikipedia.org/wiki/Pin_tumbler_lock3Page 13The key• We understand how it works:– Strengths– Weaknesses• Based on this understanding, we can assess how much to trust the key & lock.Source: en.wikipedia.org/wiki/Pin_tumbler_lockPage 14Symmetric algorithmSecret keyC= EK(M )M= DK(C )Page 15Public key algorithmPublic and private keysC1= Epublic(M)M= Dprivate(C1 )also:C2= Eprivate(M)M= Dpublic(C2 )Page 16McCarthy’s puzzle (1958)The setting:• Two countries are at war• One country sends spies to the other country• To return safely, spies must give the border guards a password• Spies can be trusted• Guards chat – information given to them may leakPage 17McCarthy’s puzzleChallengeHow can a guard authenticate a person without knowing the password?Enemies cannot use the guard’s knowledge to introduce their own spiesPage 18Solution to McCarthy’s puzzleMichael Rabin, 1958Use one-way function, B = f(A)– Guards get B…• Enemy cannot compute A– Spies give A, guards compute f(A)• If the result is B, the password is correct.Example function:Middle squares• Take a 100-digit number (A), and square it• Let B = middle 100 digits of 200-digit result4Page 19One-way functions• Easy to compute in one direction• Difficult to compute in the otherExamples:Factoring:pq = NEASYfind p,qgiven NDIFFICULTDiscrete Log:abmod c= NEASYfind bgiven a, c, NDIFFICULTPage 20McCarthy’s puzzle exampleExample with an 18 digit numberA = 289407349786637777A2= 83756614110525308948445338203501729Middle square, B = 110525308948445338Given A, it is easy to compute BGiven B, it is extremely hard to compute A110525308948445338Page 21More terms• one-way function– Rabin, 1958: McCarthy’s problem– middle squares, exponentiation, …• [one-way] hash function– message digest, fingerprint, cryptographic checksum, integrity check• encrypted hash– message authentication code– only possessor of key can validate messagePage 22More terms• Stream cipher– Encrypt a message a character at a time• Block cipher– Encrypt a message a chunk at a timePage 23Yet another term• Digital Signature– Authenticate, not encrypt message– Use pair of keys (private, public)– Owner encrypts message with private key– Sender validates by decrypting with public key– Generally use hash(message).Page 24Cryptography: what is it good for?• Authentication– determine origin of message• Integrity– verify that message has not been modified• Nonrepudiation– sender should not be able to falsely deny that a message was sent• Confidentiality– others cannot read contents of the message5Page 25Cryptographic toolbox• Symmetric encryption• Public key encryption• One-way hash functions• Random number generatorsPage 26Page 26Classic CryptosystemsPage 27Page 27Substitution CiphersPage 28Cæsar cipherEarliest documented military use of cryptography– Julius Caesar c. 60 BC– shift cipher: simple variant of a substitution cipher– each letter replaced by one npositions awaymodulo alphabet sizen= shift value = keySimilar scheme used in India– early Indians also used substitutions based on phoneticssimilar to pig latinLast seen as ROT13 on Usenet to keep the reader from seeing offensive messages unwillinglyPage 29Cæsar cipherA B C D E F G H I J K L MN O P Q R S T U V WX Y ZA B C D E F G H I J K L M N O P Q R S T U VWX Y ZPage 30Cæsar cipherA B C D E F G H I J K L M N O P Q R S T U V WX Y ZU V WX Y Z A B C D E F G H I J K L M N O P Q R S Tshift alphabet by n (6)6Page 31Cæsar cipherA B C D E F G H I J K L M N O P Q R S T U VWX Y ZA B C D E F G H I J K L M N O P Q R S TU V WX Y ZMY CAT HAS FLEASPage 32Cæsar cipherA B C D E F G H I J K L M N O P Q R S T U V WX Y ZA B C D E F G H I J K L M N O P Q R S TU V W X Y ZMY CAT HAS FLEASGPage 33Cæsar cipherA B C D E F G H I J K L M N O P Q R S T U VWX Y ZA B C D E F G H I J K L M N O P Q R S TU V WX Y ZMY CAT HAS FLEASGSPage 34Cæsar cipherA B C D E F G H I J K L M N O P Q R S T U V WX Y ZA B C D E F G H I J K L M N O P Q R S TU V W X Y ZMY CAT HAS FLEASGSWPage 35Cæsar cipherA B C D E F G H I J K L M N O P Q R S T U VWX Y ZA B C D E F G H I J K L M N O P Q R S TU V WX Y ZMY CAT HAS FLEASGSWUPage 36Cæsar cipherA B C D E F G H I J K L M N O P Q R S T U V WX Y ZA B C D E F G H I J K L M N O P Q R S TU V W X Y ZMY CAT HAS FLEASGSWUN7Page 37Cæsar cipherA B C D E F G H I J K L M N O P Q R S T U VWX Y ZA B C D E F G H I J K L M N O P Q R S TU V WX Y ZMY CAT HAS FLEASGSWUNBPage 38Cæsar cipherA B C D E F G H I J K L M N O P Q R S T U V WX Y ZA B C D E F G H I J K L M N O P Q R S TU V W X Y ZMY CAT HAS FLEASGSWUNBUPage 39Cæsar cipherA B C D E F G H I J K L M N O P Q R S T U VWX Y ZA B C D E F G H I J K L M N O P Q R S TU V WX Y ZMY CAT HAS FLEASGSWUNBUMPage 40Cæsar