Crypto U3, Theoretical vs. Practical Security

Annotations:

• [Image: https://lh5.googleusercontent.com/-bm3mNTn_vpY/UVf2zUjHt8I/AAAAAAAAAbM/2PH9xvxP4QQ/s582/flashymathdefinitionofperfectsecrecy.png]

1. each letter of a plaintext is transformed with a randomly generated key that is the same length as the plaintext
2. practical problems
   1. key establishment expensive (creating random sequences)
   2. key distribution a challenge (key changes each time)
   3. key length potentially very large
3. OTP

1. design system to protect against known attacks that would result in plaintext compromise in shorter than covertime

1. algorithm complexity
   1. for each possible input to the algorithm, the amount of time it takes to run
      1. length of input measured in bits
2. mathematical complexity - algorithms can be run in
   1. polynomial time
      1. a algorithm that can usually be run in real time with any sized input
      2. "time taken to execute process for an input of size n is not greater than n^r for some number r"
      3. example: multiplication, addition
   2. expontential time
      1. an algorithm that cannot be run in "real" time with most inputs
      2. "if the time taken to execute the process for an input of size n is approximately a^n for some number a"
      3. example: factorization
      4. Just because an algorithm is exponentially hard, it does not mean that it is impossible to solve for all values.

1. need
   1. algorithm complexity
   2. computer speed
2. example
   1. general algorithm complexity forkey search is 2^n
      1. our example key length is 30, so the complexity for this example is n^30
         1. our example computer does 1,000,000 operations per second
            1. So, 2^30 / 10^6 = roughly 1000 seconds