Cryptography Exercise 9.2 answers key Q: 9.2 Perform encryption and decryption using the RSA algorithm, as in Figure 9.6, for the following: 1. p = 3; q = 11, e = 7; M = 5 2. p = 5; q = 11, e = 3; M = 9 3. p = 7; q = 11, e = 17; M = 8 4. p = 11; q = 13, e = 11; M = 7 5. p = 17; q = 31, e = 7; M = 2 Hint: Decryption is not as hard as you think; use some finesse. A: 1. n = p x q = 3 x 11 = 33 j(n) = (p-1) x (q-1) = 2 x 10 = 20 gcd(j(n), e) = gcd(20, 7) = 1 ∵ d ≡ e-1(mod j(n)) d x e mod j(n) = 1 7d mod 20 = 1 ∴ d = 3 So: Public Key pu = {e, n} = {7, 33} Private Key pr = {d, n} = {3, 33} Encryption: C = Me mod n = 57 mod 33 = 14 Decription: M = Cd mod n = 143 mod 33 = 5 2. n = p x q = 5 x 11 = 55 j(n) = (p-1) x (q-1) = 4 x 10 = 40 gcd(j(n), e) = gcd(40, 3) = 1 ∵ d ≡ e-1(mod j(n)) d x e mod j(n) = 1 3d mod 40 = 1 ∴ d = 27 So: Public Key pu = {e, n} = {3, 55} Private Key pr = {d, n} = {27, 55} Encryption: C = Me mod n = 93 mod 55 = 14 Decription: M = Cd mod n = 1427 mod 55 = 9 3. n = p x q = 7 x 11 = 77 j(n) = (p-1) x (q-1) = 6 x 10 = 60 gcd(j(n), e) = gcd(60, 17) = 1 ∵ d ≡ e-1(mod j(n)) d x e mod j(n) = 1 17d mod 60 = 1 ∴ d = 53 So: Public Key pu = {e, n} = {17, 77} Private Key pr = {d, n} = {53, 77} Encryption: C = Me mod n = 817 mod 77 = 57 Decription: M = Cd mod n = 5753 mod 77 = 8 4. n = p x q = 11 x 13 = 143 j(n) = (p-1) x (q-1) = 10 x 12 = 120 gcd(j(n), e) = gcd(120, 11) = 1 ∵ d ≡ e-1(mod j(n)) d x e mod j(n) = 1 11d mod 120 = 1 ∴ d = 11 So: Public Key pu = {e, n} = {11, 143} Private Key pr = {d, n} = {11, 143} Encryption: C = Me mod n = 711 mod 143 = 106 Decription: M = Cd mod n = 10611 mod 143 = 7 5. n = p x q = 17 x 31 = 527 j(n) = (p-1) x (q-1) = 16 x 30 = 480 gcd(j(n), e) = gcd(480, 7) = 1 ∵ d ≡ e-1(mod j(n)) d x e mod j(n) = 1 7d mod 480 = 1 ∴ d = 343 So: Public Key pu = {e, n} = {7, 527} Private Key pr = {d, n} = {343, 527} Encryption: C = Me mod n = 27 mod 527 = 128 Decription: M = Cd mod n = 128343 mod 527 = 2