ones. Side-channel attacks and even physical probing of devices take a lot more work.
With signatures, things are slightly simpler. In general, it's often enough to just hash the message before applying the private key: (mod ); PKCS #7 describes simple mechanisms for signing a message digest [1010]. However, in some applications one might wish to include further data in the signature block, such as a timestamp, or some randomness to make side-channel attacks harder.
Many of the things that have gone wrong with real implementations have to do with side channels and error handling. One spectacular example was when Daniel Bleichenbacher found a way to break the RSA implementation in SSL v 3.0 by sending suitably chosen ciphertexts to the victim and observing any resulting error messages. If he could learn from the target whether a given , when decrypted as (mod ), corresponds to a PKCS #1 message, then he could use this to decrypt or sign messages [265]. There have been many more side-channel attacks on common public-key implementations, typically via measuring the precise time taken to decrypt. RSA is also mathematically fragile; you can break it using homomorphisms, or if you have the same ciphertext encrypted under too many different small keys, or if the message is too short, or if two messages are related by a known polynomial, or in several other edge cases. Errors in computation can also give a result that's correct modulo one factor of the modulus and wrong modulo the other, enabling the modulus to be factored; errors can be inserted tactically, by interfering with the crypto device, or strategically, for example by the chipmaker arranging for one particular value of a 64-bit multiply to be computed incorrectly. Yet other attacks have involved stack overflows, whether by sending the attack code in as keys, or as padding in poorly-implemented standards.
5.7.2 Cryptography based on discrete logarithms
While RSA was the first public-key encryption algorithm deployed in the SSL and SSH protocols, the most popular public-key algorithms now are based on discrete logarithms. There are a number of flavors, some using normal modular arithmetic while others use elliptic curves. I'll explain the normal case first.
A primitive root modulo is a number whose powers generate all the nonzero numbers mod ; for example, when working modulo 7 we find that = 25 which reduces to 4 (modulo 7), then we can compute as or which is 20, which reduces to 6 (modulo 7), and so on, as in Figure 5.17.
Thus 5 is a primitive root modulo 7. This means that given any , we can always solve the equation (mod 7); is then called the discrete logarithm of modulo 7. Small examples like this can be solved by inspection, but for a large random prime number , we do not know how to do this efficiently. So the mapping (mod ) is a one-way function, with the additional properties that and . In other words, it is a one-way homomorphism. As such, it can be used to construct digital signature and public key encryption algorithms.
= 5
(mod 7)
=
25
4
(mod 7)
4 x 5
6
(mod 7)
6 x 5
2
(mod 7)
2 x 5
3
(mod 7)
3 x 5
1
(mod 7)
Figure 5.17: Example of discrete logarithm calculations
ones. Side-channel attacks and even physical probing of devices take a lot more work.
