![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
4.2.3 Other Useful FactsWe next mention another result from elementary group theory, called Lagranges Theorem, that will be relevant in our treatment of the RSA Cryptosystem. For a (finite) multiplicative group G, define the order of an element g ∈ G to be the smallest positive integer m such that gm = 1. The following result is fairly simple, but we will not prove it here. THEOREM 4.4 (Lagrange) Suppose G is a multiplicative group of order n, and g∈ G. Then the order of g divides n. For our purposes, the following corollaries are essential. COROLLARY 4.5 If PROOF COROLLARY 4.6 (Fermat) Suppose p is prime and PROOF If p is prime, then φ(p) = p - 1. So, for At this point, we know that if p is prime, then THEOREM 4.7 If p is prime, then An element α having order p - 1 is called a primitive element modulo p. Observe that α is a primitive element if and only if Now, suppose p is prime and α is a primitive element modulo p. Any element Thus β is itself a primitive element if and only if gcd(p - 1, i) = 1. It follows that the number of primitive elements modulo p is φ(p - 1). Example 4.4 Suppose p = 13. By computing successive powers of 2, we can verify that 2 is a primitive element modulo 13: The element 2i is primitive if and only if gcd(i, 12) = 1; i.e., if and only if i = 1, 5, 7 or 11. Hence, the primitive elements modulo 13 are 2, 6, 7 and 11.
4.3 The RSA CryptosystemWe can now describe the RSA Cryptosystem. This cryptosystem uses computations in The formal description of the cryptosystem is given in Figure 4.2. Lets verify that encryption and decryption are inverse operations. Since we have that for some integer t ≥ 1. Suppose that as desired. We leave it as an exercise for the reader to show that (xb)a ≡ x (mod n) if Here is a small (insecure) example of the RSA Cryptosystem. Example 4.5 Suppose Bob chooses p = 101 and q = 113. Then n = 11413 and φ(n) = 100 × 112 = 11200. Since 11200 = 26527, an integer b can be used as an encryption exponent if and only if b is not divisible by 2, 5 or 7. (In practice, however, Bob will not factor φ(n). He will verify that gcd(φ(n), b) = 1 using the Euclidean algorithm.) Suppose Bob chooses b = 3533. Then the Extended Euclidean algorithm will yield Hence, Bobs secret decryption exponent is a = 6597. Bob publishes n = 11413 and b = 3533 in a directory. Now, suppose Alice wants to send the plaintext 9726 to Bob. She will compute and send the ciphertext 5761 over the channel. When Bob receives the ciphertext 5761, he uses his secret decryption exponent to compute (At this point, the encryption and decryption operations might appear to be very complicated, but we will discuss efficient algorithms for these operations in the next section.) The security of RSA is based on the hope that the encryption function eK (x) = xb mod n is one-way, so it will be computationally infeasible for an opponent to decrypt a ciphertext. The trapdoor that allows Bob to decrypt is the knowledge of the factorization n = pq. Since Bob knows this factorization, he can compute φ(n) = (p - 1)(q - 1) and then compute the decryption exponent a using the Extended Euclidean algorithm. We will say more about the security of RSA later on.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |