Whilst many developers have to incorporate a degree of "security" or "crypto" elements into products they build, it recently came to my attention that many developers have a thin grasp of the mathematical concepts that underpin the foundations of cryptography. I guess it shouldn't have surprised me, but none-the-less it did.
For example, many developers will tell you that passwords should not be stored in clear-text in the database, but rather the hash of the password should be stored. That is excellent advice, but when probed on hash functions - what exactly are they, how do they work, what assumptions do they make, etc - you'll quickly find that it is an area that isn't well understood by many developers.
Under the covers hash functions are specialized one way functions. One way functions are a cryptographic primitive that, by definition, are "easy" to compute in one direction but "hard" to calculate in the other direction, that is, finding the inverse. In this context, "easy" means solvable in polynomial time, and "hard" means, on average, the inverse for some randomly given value is not solvable in polynomial time. That is, easy means ∈ P, and hard means ∈ NP.
Let me give an example to demonstrate the easy/hard asymmetry that gives the one way function it's power. Consider the following equation:
c ≡ be mod m (1) [ here b is the "base", e is the "exponent", and m is the "modulus" ]
This is called modular or discrete exponentiation and it is a carefully constructed equation to exhibit qualities that make it a suitable one way function. Essentially, (1) consists of 2 components: an exponentiation operation, be, and a modulus operation. It's clear that evaluating be requires e-1 multiplication operations. This can also be seen by considering the recurrence relationship :
be = b. b(e-1) (2)
= b. b. b(e-2)
= b. b. b. b. ... .b
The astute reader will note that we can perform this more efficiently by computing b2, and then multiplying that by itself to get b4 and so on to get b8, b16, b32 and so on. We can see that this approach requires approximately log2(e) operations. This is called exponentiation by squaring. It should be noted that there is considerable efficiency to be gained in using an Θ(log2e) algorithm over a Θ(e) algorithm when e is large.
The second component needing evaluation in (1) is the modulus operation. This involves dividing be by m and finding the remainder. So overall we can be certain that we have an expression that can be solved in polynomial time. Let's now consider the inverse function. That is, calculating e for given values of c, b and m. The equation is:
e = loge (b) -> Zn (3)
This is a discrete logarithm to base e in Zn and the tractability of such a problem is known to be hard and have no efficient solutions (unless of course, you have a quantum computer). Ergo, modular exponentiation is an elegant construction that can be used as a cryptographic one way function. Indeed, this particular function is the basis of the ElGamal encryption scheme.
The strength of one-way functions is in the difficulty in calculating the inverse. In the forward direction we have a problem ∈ P, and in the the reverse direction we have a problem ∈ NP. Clearly, we are assuming that:
P ≠ NP (4)
(4) is considered to be one of the most fundamental, yet difficult, open unresolved mathematical equations. Presently this assumption stated in (4) is a safe, albeit unproven, assumption as the majority of mathematicians believe (4) to be true as it has been scrutinized over many years without being disproved. The importance of this assumption is exemplified by the lucrative financial rewards (1 million USD) on offer from the Clay Institute for a formal proof or disproof. To date, however, no one has been able to offer such a proof. Until that happens cryptographers will continue to assume this is the case.