Crypto U3, Theoretical vs. Practical Security

Crypto U3, Theoretical vs. Practical Security

1. perfect secrecy

   • Attacker gets no info about the plaintext by observing the ciphertext, other than what was was known before the ciphertext was cobserved.
   • Gordon's "flash math" version of perfect secrecy
     • [Image: https://lh5.googleusercontent.com/-bm3mNTn_vpY/UVf2zUjHt8I/AAAAAAAAAbM/2PH9xvxP4QQ/s582/flashymathdefinitionofperfectsecrecy.png]

2. in theory, there exists unbreakable cryptosystems

   • perfectly secret
   • one time pad
     • each letter of a plaintext is transformed with a randomly generated key that is the same length as the plaintext
     • practical problems
       • key establishment expensive (creating random sequences)
       • key distribution a challenge (key changes each time)
       • key length potentially very large
     • OTP

3. practical security

   • COVERAGE what is the covertimeneeded for the plaintext?
     • design system to protect against known attacks that would result in plaintext compromise in shorter than covertime
   • computational complexity
     • algorithm complexity
       • for each possible input to the algorithm, the amount of time it takes to run
         • length of input measured in bits
     • mathematical complexity - algorithms can be run in
       • polynomial time
         • a algorithm that can usually be run in real time with any sized input
         • "time taken to execute process for an input of size n is not greater than n^r for some number r"
         • example: multiplication, addition
       • expontential time
         • an algorithm that cannot be run in "real" time with most inputs
         • "if the time taken to execute the process for an input of size n is approximately a^n for some number a"
         • example: factorization
         • Just because an algorithm is exponentially hard, it does not mean that it is impossible to solve for all values.
   • computing exhaustive key search time
     • need
       • algorithm complexity
       • computer speed
     • example
       • general algorithm complexity forkey search is 2^n
         • our example key length is 30, so the complexity for this example is n^30
           • our example computer does 1,000,000 operations per second
             • So, 2^30 / 10^6 = roughly 1000 seconds
   • EVOLUTION when designing algorithms, take into consideration current and emerging state of processing power in computers
   • when designing cryptosystems, make sure that the implementation does not undermine the power of the algorithms used
   • practice good key management