Eroding Intractability

Page #4355 of Chapter: Crypto-for-the-rest-of-us

level indicator


The setting: Your adversary knows what cipher you use, he knows what are all the possible keys that you have to choose from (the key space), and, of course, he reads your ciphertext.

Your intended reader will have a secret piece of data, called 'the key' with which he can decipher the contents of your message, while any adversary, without that key -- finds it too hard to do (intractable) within any reasonable time.

The intractability defense suffers from constant erosion. The difficulty for the adversary to spot the right key is chipping away. Two reasons:

  • Faster computers go faster through all possible keys
  • Deeper mathematical insight reveals mathematical shortcuts to crack the system

    Adversaries can always try all possible keys until they find the right key and read the contents of the message -- that is called "brute force cryptanalysis".

    To prevent "brute force cryptanalysis" it is necessary to have a large enough number of possible keys (called "key space"), so that "brute force cryptanalysis" will take too long to be effective

    So to summarize: The original message (called "the plaintext") will have to be mathematically manipulated by "The Encryption Algorithm" to create an obscure form (called "the ciphertext"), which the intended reader will be able to reverse to the plaintext, but adversaries will be unable to.

    The mathematical manipulation also called "The Method" -- it is assumed known. The secrecy is limited to the key (The Kerchoff Principle).

    The question of how to communicate a secret is reduced to how to find a mathematical formula (a method) that would insure that given the ciphertext (but lacking the key) it would be infeasible to extract the plaintext.

    While eroding intractability seems quite unappetizing because the inherent uncertainty regarding the actual residual intractability, it does have a singular attribute missing elsewhere --it's the only setting that allows for communication of secrets between strangers.
    In fact, we divide eroding intractability cryptography to:

  • Communicating a secret among acquaintances
  • Communicating a secret between strangers
    The latter is the foundation of e-commerce.
  • * Version CE-H6703 (SERVER) Crypto Academy