p(n) = n [p:p/n (1) where the product is over all primes that divide n, including...

Transcribed Image Text:

p(n) = n [p:p/n (1) where the product is over all primes that divide n, including n if n is prime. 3. Choose a small prime number as an encryption component g, that is relatively (n). That means, prime to gcd(g, (n)) = 1, i.e., ged(g, (p-1)(q-1)) = 1. 4. Compute the multiplicative inverse [h] (n) of [9](n). That is, [9]p(n) [h]p(n) = [1]p(n). The inverse exists and is unique. That is, the decryption component h=g¹ mod p(n). 5. Let pkey=(n, g) be the public key, and skey = (p, q, h) be the secret key. For any message M mod n, the encryption of M is C=M³ mod n. The decryption of C is M = C¹ mod n. End of the formalization of the RSA public-key cryptosystem. Use the RSA Cryptosystem formalism for solving problem I. Given g = 59, p = 991 and q = 997. I.1. [30 pts.] Show that the given values of g. p, and q are prime, I.1.a Use the Algorithm Sieve (the Sieve of Eratosthenes Method) to check whether p is a prime. I.1.b Based on Fermat's Little Theorem, the algorithm in Figure 1.8 can be used to check whether q is a prime. What is the most reasonable set {a₁1, a2, ..., ak} that is used for applying this algorithm? I.1.c. How do you check that g is a prime? Show the work of how you compute. [Hint: There is a distinct difference between Algorithm Sieve and Fermat's Little Theorem for finding the solution. The latter requires to apply "function modexp(x, y, N), Fig 1.4, Chapter 00_03" to compute modular exponentiation. For the former one, the Algorithm Sieve deletes only the numbers which are divisible by the primes. If you use this approach, use a table to show the elimination process. If you use Fermat's Little Theorem approach, show all the computations for modular exponentiation.] p(n) = n [p:p/n (1) where the product is over all primes that divide n, including n if n is prime. 3. Choose a small prime number as an encryption component g, that is relatively (n). That means, prime to gcd(g, (n)) = 1, i.e., ged(g, (p-1)(q-1)) = 1. 4. Compute the multiplicative inverse [h] (n) of [9](n). That is, [9]p(n) [h]p(n) = [1]p(n). The inverse exists and is unique. That is, the decryption component h=g¹ mod p(n). 5. Let pkey=(n, g) be the public key, and skey = (p, q, h) be the secret key. For any message M mod n, the encryption of M is C=M³ mod n. The decryption of C is M = C¹ mod n. End of the formalization of the RSA public-key cryptosystem. Use the RSA Cryptosystem formalism for solving problem I. Given g = 59, p = 991 and q = 997. I.1. [30 pts.] Show that the given values of g. p, and q are prime, I.1.a Use the Algorithm Sieve (the Sieve of Eratosthenes Method) to check whether p is a prime. I.1.b Based on Fermat's Little Theorem, the algorithm in Figure 1.8 can be used to check whether q is a prime. What is the most reasonable set {a₁1, a2, ..., ak} that is used for applying this algorithm? I.1.c. How do you check that g is a prime? Show the work of how you compute. [Hint: There is a distinct difference between Algorithm Sieve and Fermat's Little Theorem for finding the solution. The latter requires to apply "function modexp(x, y, N), Fig 1.4, Chapter 00_03" to compute modular exponentiation. For the former one, the Algorithm Sieve deletes only the numbers which are divisible by the primes. If you use this approach, use a table to show the elimination process. If you use Fermat's Little Theorem approach, show all the computations for modular exponentiation.]

Answer rating: 100% (QA)

Lets solve the problem I1 which involves confirming the primality of the given numbers g 59 p 991 and q 997 I1a To determine if a number for example p ... View the full answer