Читать книгу Security Engineering - Ross Anderson - Страница 183

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