Cryptography

Cryptography

1. History

   • Book- David Kahn- The code breakers (1996)
   • Ciphers
     • Symmetric Ciphers
       • Because both D and E use the same secret key; K
       • E; Encryption algorithm
       • D; Dicription algorithm
     • 1. Substitution ciphers
       • substituting one letter with another
       • Solving- cipher text only attack
         • frequency of english letters
           • E: 12.7%
           • T: 9.1%
           • A: 8.1%
           • The rest appear similarly
         • frequency of pairs of letters
           • 'he', 'ar', 'in', 'th'
       • size of key space
         • 26!
     • Caesar cipher
       • Not a cipher- doesn't have a key
       • A fixed substitution
       • Easy to solve because it's not random
     • 2. Vigener cipher (16th century, Rome)
       • k= cipher text (e.g. crypto) repeated
       • m= message
       • c= k+m
       • Solving
         • length of the key, e.g. 6
         • break c into groups of 6
         • work out the most common letter in the set and substract by E
     • 3. Rotor machines (1870-1943)
       • ciphers used to decode an electric mechine
       • Disk rotates by one
       • Enigma machine
     • 4. Data encryption standards; DES (1974)
       • Federal law- a standard for encryptions DES: key = 2^56, block size = 64 bits>> currently insecure
       • Today
         • AES (2001)
         • Salsa20 (2008)

2. What is it?

   • Uses
     • Encryption of files
     • Protection
     • User authentication
     • Limitations
       • Not a solution for all security problems
       • Useless unless implemented correctly
   • 1. Secret Keys
     • Single use
       • used to encrypt one message
     • Multiple use
       • can be used to encrypt multiple messages- needs more machinery and security 
   • 2. Digital signatures- how to
     • how to create a digital signature that will be hard to forge
   • 3. Anonymous communication
     • Mix net
       • when sending messages they get encrypted in the process, so a person would only be able to tell the output and not the identity of the sender
     • bidirectional
     • anonymous digital cash
       • Need to prevent double spending-  If someone spends more than once the identity becomes revealed
     • Secure Multi-party computation
       • 'Trusted party'
         • So there is a middle party which gets all the data before revealing the output
       • No trusted party
         • There is always a way to compute the output without a middle party 
   • 4. Secure communication
   • Three steps:
     • Precisely specific threat model
       • What an attacker can do to an encryption >> make it unforgable
     • Provide a construction
     • Proving that breaking a construction under threat model will solve an underlying hard problem
       • If an attacker can break the construction they can use that to make it harder to break
   • Crypto-magic
     • Privately outsourcing computation
       • allows to compute encrypted data- e.g. running a search on google on encryption data
     • Zero knowledge
       • Proving you solved something without providing the solution >> e.g. proving that you know what the prime numbers are of a certain value N-pxq