Asymmetric Cryptography

Message authentication using HMACs works just fine, but how do we distribute symmetric cipher keys among the users? We can pass them around on floppies or fancy USB pen-drives with encrypted partitions on them, but what if many users live all over the world? What if the physical key distribution method takes time and the keys must be frequently changed? This is the case with the traditional WEP, which should be rotated every few minutes.

Key-encrypting keys (KEKs) were offered as symmetric cipher keys used only to encrypt other symmetric cipher keys before they are distributed. Therefore, only the distribution of KEK is required. Still, how do we distribute the KEK in a secure manner? Won't it become a single point of failure for the whole organization? A model of physical KEK distribution would become very vulnerable to social engineering attacks and we know that social engineering tends to wreak more havoc than all known cracking tools combined (see Mitnick's The Art of Deception (John Wiley & Sons, 2002, ISBN: 0471237124) as a reference). Besides, from a management viewpoint, won't such a system give too much power and responsibility to a small group of people, perhaps even a single person on a technical team?

The answer lies in using asymmetric ciphers. One-way hashes are nothing more than fancy symmetric ciphers that take a constant of necessary length as plaintext, enciphered data as a large "key," and run a huge amount of complex rounds to make the decryption unfeasible. Symmetric ciphers are nothing more than sophisticated, modern-day, digital Enigma-style rotor machines. Replace the rotors and cogwheels with CPU registers and available instructions, make them operate in accordance with well-established laws and principles (Shannon, Feistel, etc.), and you will get the idea.

Asymmetric ciphers, on the contrary, are based on solving specific mathematical tasks in the world of large numbers. In layman's terms, imagine an equation impossible to solve without a certain variable. That variable is kept secret and is called a private key. The rest of the variables can be given to anyone else to initiate the task; this is called a public key. The algorithm of the equation itself does not have to be secret, and encrypting or decrypting data depends on the success of solving the equation. To get closer to the heart of the problem, imagine a cryptographic hash function that is relatively easy to compute but practically impossible to invert, unless a certain value is known. That value (or, more likely, values) is called a trapdoor. The mathematical relationship between the trapdoor (the basis for the private key) and variables given to the public (the basis for the public key) is very costly to solve, making the deduction of private key from the public one close to impossible if you take into account the computational power of today's machines. This is referred to as a hard problem.

As far as the practical implementation of such a mathematical concept goes, mankind came up with three secure hard problems to use: factoring large numbers into prime factors, calculating discrete logarithms in a finite field, and, as a variation of this, calculating elliptic curve discrete logarithms. All these problems have one thing in common: Although conceptually they might not be too difficult to solve, in practice and with current computing power, solving one of these problems might take more time than it takes our universe to expand to the point of collapse and the next Big Bang.

Whitfield Diffie and Martin Hellman proposed the idea of asymmetric cryptography in 1976. Their method was based on calculating discrete logarithms in a finite field. Although it might sound sophisticated to a non-mathematician, in reality the Diffie–Hellman (DH) system is very simple and elegant.