7.7 The RSA algorithm
The RSA algorithm is named after its inventors, Ron Rivest, Adi Shamir, and Len Adleman (see Chapter 1, The Role of Cryptography in a Connected World, for a photo). Its trapdoor mechanism is based on the assumption that factoring, that is, finding the prime factors of a large integer n, is hard, while the inverse problem, namely multiplying prime factors to get n, is easy. While this trapdoor is certainly much easier to understand than the discrete-logarithm problem, understanding how exactly it can be used to realize a public-key cryptosystem requires a bit of math (again). We start by defining an odd-looking function.
7.7.1 Euler’s totient function
No doubt you are familiar with prime numbers. To recap, p is a prime number if it has no divisors other than 1 and p. For two integer numbers a and b, we can always find a greatest common divisor c, or c = gcd(a,b) for short. c is the greatest integer that divides both a and b. For example, 3 is the greatest...
