A generation ago, an ordinary person’s only brush with cryptography might be watching a spy movie. Now we all rely cryptography every day, whether we realize it or not.
Before you could read this web page, your web browser and our web server exchanged public keys, using asymmetric encryption to exchange keys for symmetric encryption. The modern web, and even the modern economy, would not be possible without encryption.
Here are some of the blog posts on this site related to cryptography.
Cryptography expert Bruce Schneier once said “Modern cryptanalysis is possible primarily because people make mistakes.” In theory, cryptographic algorithms like RSA should be secure, if implemented with sufficiently large keys. If and when large-scale quantum computing becomes practical, this would change. But the biggest threat to RSA, and other algorithms, for now at least, is poor implementation, not quantum computers. The posts below address common implementation weaknesses.
- Attack on RSA with exponent 3
- RSA with one shared prime
- RSA with pseudoprimes
- RSA exponents are mostly all the same in practice
Random Number Generation
Cryptography and random number generation are closely related. The security of many encryption algorithms depends on the quality of randomly generated keys and nonces. A small bias in a random number generator may give an attacker the starting point for an exploit. Random number generation is subtle, and a generator with excellent statistical properties may be insecure and unsuitable for cryptographic applications.
Secure hash functions
When a character in Hemingway’s The Sun Also Rises is asked how he went bankrupt, he replies “Two ways. Gradually and then suddenly.” One could say something similar for how hash functions fail. First a researcher finds a theoretical weakness of no practical importance. Then another researcher improves on the initial exploit and soon the function is practically compromised.
With a state of the art hash function, the biggest vulnerability is not the hash function itself but the way it is used. For example, a secure hash function applied to a known, moderately sized list of possible inputs is insecure.
- Microsoft replacing SHA-1
- Reversing an MD5 hash
- Hash function menagerie
- Salting and stretching a password
- Computing hash functions from the command line
Elliptic Curve Cryptography
Elliptic curve cryptography (ECC) is a practical application of some elegant abstract mathematics. The choice of curve impacts security and efficiency. There’s always suspicion that an elliptic curve may have some hidden exploitable structure that makes cryptography using this curve insecure. And because of Shor’s factoring algorithm, we know that ECC would break if quantum computing became practical.
- What is an elliptic curve?
- Naming elliptic curves
- Ed448 Goldilocks
The most widely used public key cryptographic algorithms are vulnerable to attack from quantum computers, and so the race is on to design, implement, and verify algorithms that would be resistant to attack from an adversary in possession of a quantum computer. The posts below discuss some of the approaches to developing PQC algorithms, algorithms that would remain secure in a post quantum computer world.
- From now until quantum
- Learning with errors
- Code-based encryption
- Unbalanced oil and vinegar
- Isogeny-based methods
Symmetric encryption is quite different from asymmetric (public key) encryption. Apparently methods like AES would remain secure in an era of quantum computing. The first two posts below are about symmetric encryption.
The last link in the list, homomorphic encryption, may turn out to be very important. Homomorphic encryption allows computing on encrypted data. An agent can take encrypted input and produce encrypted output, without needing to or being able to decrypt the input. Homomorphic encryption algorithms have existed for quite some time, but have been impractical. The methods have become more efficient, and are efficient enough for some applications now. It seems reasonable to expect that efficiency and adoption will increase over time.
- Feistel networks
- The AES S-box
- Secret sharing with polynomials
- Index of coincidence
- Format-preserving encryption
- Homomorphic encryption