Answer:
a) To set up an RSA system for Alice, we first need to calculate the values of Phi, (e,n), and (d,n).
We begin by calculating n as the product of the two given prime numbers: n = p * q = 2253637 * 885839 = 1,998,771,944,443
Next, we calculate Phi(n) using the formula: Phi(n) = (p-1)(q-1) Phi(n) = (2253637-1)(885839-1) = 1,997,860,307,256
We now need to choose a public key exponent, e. e must be a positive integer that is relatively prime to Phi(n) (i.e., they share no common factors other than 1). We can choose any value of e that satisfies this condition. A common choice is e = 65537, which is a prime number that is commonly used in practice. In this case, we can verify that e and Phi(n) are relatively prime: gcd(e, Phi(n)) = gcd(65537, 1,997,860,307,256) = 1
So we can use (e,n) = (65537, 1,998,771,944,443) as Alice's public key.
To calculate the private key exponent, d, we need to find the modular inverse of e modulo Phi(n). In other words, we need to find a value of d such that: e*d ≡ 1 (mod Phi(n))
We can use the extended Euclidean algorithm to find d. The algorithm produces a sequence of remainders and coefficients such that, at each step, the remainder is the previous remainder modulo the original number, and the coefficients are determined by the quotients in the division algorithm. When the remainder is 1, we can use the coefficients to calculate the modular inverse.
Using the extended Euclidean algorithm with e=65537 and Phi(n)=1,997,860,307,256, we get:
1,997,860,307,256 = 30,437 * 65,537 + 39,815
65,537 = 1,644 * 39,815 + 2,297
39,815 = 17 * 2,297 + 44
2,297 = 52 * 44 + 29
44 = 1 * 29 + 15
Step-by-step explanation: