Upgrade to Pro — share decks privately, control downloads, hide ads and more …

CSCD27 Classical Cryptography

ThierrySans
September 15, 2016
650

CSCD27 Classical Cryptography

ThierrySans

September 15, 2016
Tweet

Transcript

  1. Caesar Cipher - the oldest cryptosystem A shift cipher –

    attributed to Julius Caesar (100-44 BC) MEET ME AFTER THE TOGA PARTY PHHW PH DIWHU WKH WRJD SDUWB Shift the alphabet 3 places further down and substitute letters a b c d e f g h i j k l m n o p q r s t u v w x y z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
  2. Definitions Plaintext
 The message in its clear form (the original

    message) Ciphertext
 The message in its ciphered form (the encrypted message) Encryption
 Transform a plaintext into ciphertext Decryption
 Transform a ciphertext into a plaintext
  3. Definitions Cryptographic algorithm
 The method to do encryption and decryption

    Cryptographic key
 An input variable used by the algorithm for the transformation N-bit security (a.k.a. the key space)
 The number of bits necessary to encode the number of possible keys
  4. Representing data as numbers Cryptographic algorithms are mathematical operations ➡

    messages and keys must be represented with numbers
 for instance : ASCII encoding
  5. Back to Caesar Cipher Algorithm : shift the alphabet of

    a certain number of positions Key : the number of positions to shift Key space : 25 possible rotations ( ~ 5 bits security ) Encoding : a b c d e f g h i j k l m n o p q r s t u v w x y z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 Encrypting and decrypting one character is obtained as follows: c = E(k,p) = (p + k) mod 26 p = D(k,c) = (c – k) mod 26
  6. The Kerckhoffs' principle (1883) “The enemy knows the system” -

    the security of a communication should not rely on the fact that the algorithms are secrets ➡ A cryptosystem should be secure even if everything about the system, except the key, is public knowledge
  7. Breaking the cipher - the attacker models • Brute force


    Try all possible keys • Ciphertext only
 You know one or several random ciphertexts • Known plaintext
 You know one or several pairs of random plaintext and their corresponding ciphertexts • Chosen plaintext
 You know one or several pairs of chosen plaintext and their corresponding ciphertexts • Chosen ciphertext
 You know one or several pairs of plaintext and their corresponding chosen ciphertexts ➡ Good crypto systems resist all attack models
  8. Breaking Caesar cipher brute force Yes ciphertext only Statistical Analysis

    known plaintext Look at the first letter and get the shift chosen plaintext Choose “A” and get the shift chosen ciphertext Choose “A” and get the shift
  9. A brief history of cryptography ~ 2000 years ago Substitution

    ciphers 
 (a.k.a mono alphabetic ciphers) few centuries later Transposition ciphers Renaissance Polyalphabetic ciphers 1844 Mechanization 1976 Public key cryptography
  10. Substitution ciphers 
 (a.k.a mono alphabetic ciphers) ➡ Improvement over

    Caesar cipher Algorithm : allow an arbitrary permutation of the alphabet Key : set of substitutions Key space : 26! possible substitutions ( 4x1026 ~ 89 bits) a b c d e f g h i j k l m n o p q r s t u v w x y z D K V Q F I B J W P E S C X H T M Y A U O L R G Z N if we wish to replace letters WI RF RWAJ UH YFTSDVF SFUUFYA
  11. Breaking substitution ciphers brute force Small key length only ciphertext

    only Statistical analysis known plaintext Match letters together chosen plaintext Choose ABCDE … and match letters chosen ciphertext Choose ABCDE … and match letters
  12. Polyalphabetic ciphers (a.k.a Renaissance Cipher) The seed of modern cryptography

    ➡ Vigenere cipher Algorithm : combine the message and the key Key : a word Key space : the length of the word wearediscoveredsaveyourself deceptivedeceptivedeceptive ZICVTWQNGRZGVTWAVZHCQYGLMGJ Advantage : Encryption of a letter is context dependent (mod 26) +
  13. Breaking Polyalphabetic Ciphers brute force Small key length only ciphertext

    only Statistical analysis for small key length and significant amount of ciphertext known plaintext Subtract plaintext from ciphertext chosen plaintext Choose AAAAA … and match letters chosen ciphertext Choose AAAAA … and match letters
  14. OTP - One Time Pad ➡ Improvement over Vigenere cipher

    Algorithm : combine the message and the key Key : an infinite random string Key space : infinite whatanicedaytoday yksuftgoarfwpfwel ZZZJUCLUDTUNNWGQS Advantage : this is the perfect cipher ! Disadvantage : hard to use in practice, how to transmit the key ? ⊕
  15. The impossibility of breaking OTP The ciphertext bears no statistical

    relationship to the plaintext ➡ No statistical analysis For any plaintext and ciphertext, there exists a key mapping one to the other, and all keys are equally probable ➡ A ciphertext can be decrypted to any plaintext of the same length
  16. Transposition Cipher Algorithm : switch letters around a permutation Key

    : a set of permutation Key space : the set of permutations helloworld LOLHERDLWO
  17. Breaking Transposition ciphers brute force Small key length only ciphertext

    only Hard known plaintext Match letters together chosen plaintext Choose ABCDE … and match letters chosen ciphertext Choose ABCDE … and match letters
  18. The seeds of modern cryptography 1. Diffusion
 Mix-up symbols
 Transposition

    Cipher 2. Confusion
 Replace a symbol with another
 Polyaphabetic Cipher, OTP 3. Pseudo-random number generation
 Use an infinite random string as key
 OTP
  19. Cryptography is not just a about confidentiality Integrity
 digital signatures,

    hash functions Non-repudiation
 contract-signing Anonymity
 electronic cash, electronic voting … Availability
  20. The crypto toolbox • Symmetric cryptography schemes • Asymmetric cryptography

    schemes • Message digests • Digital signatures • Certificates
  21. Symmetric encryption E D symmetric key symmetric key ➡ The

    same key is used for encryption and decryption
  22. Asymmetric encryption
 a.k.a Public Key Cryptography E D private key

    public key ➡ The public key for encryption ➡ The private key for decryption
  23. Message digests Message digests are meant for creating fingerprints of

    messages • Un-keyed message digest : hashes, checksum • Keyed message digests : MACs
  24. Digital Signature E D public key private key ➡ The

    private key for encryption ➡ The public key for decryption
  25. Certificates - Public Key Infrastructure Certificates are meant for verifying

    someone’s identity • Binding between a public key and an owner • Certified by a certification authority