Amount of possible public keys in RSA Cryptosystems

[Marceline]

Good day to everyone. I need a little help by the following task please:

Task

p und q are two different primes

a) How many possible public keys exists for the RSA-Cryptosystems with modul N = p * q?

b) Show additionally to a), that the amount of possible public keys is an even numberc) Is it possible to chose p and q that way, that there is an even public key?

Justify your answers. Without any justification, you will receive 0.00 points on the task.


My personal approach:

A public key is simply an e ∈ℤφ(N), which is relatively prime to φ(N), for example:

p = 7 and q = 13, then N is = 7*13 = 91

and φ(N) = (7-1) * (13 - 1) 72

Then, e.g. e = 5 is a public key, because 5 ∈ ℤφ(72) because 5 is relatively prime to φ(91), so it is relatively prime to 72.

So the answer would be "all possible public keys, which are releatively prime to φ(N)". But the task, ask "how many" public keys, and the task No b) gives us the hint, that the number of possible keys is an even number (which I have to show seperately). So they ask for a concrete number. How can I do this, when p and q any variables.

 

[jvicens]

Thank you for your post. I am happy to assist you with your task.

a) To answer your first question, we need to understand the concept of the RSA-Cryptosystem. In this system, the public key (e) is a number that is relatively prime to the totient (φ) of the modulus (N). The modulus (N) is the product of two distinct prime numbers (p and q). Therefore, the number of possible public keys is equal to the number of positive integers that are relatively prime to φ(N).

To calculate the totient (φ) of N, we use the formula φ(N) = (p-1)(q-1). So for example, if p = 7 and q = 13, then N = 91 and φ(N) = 72. The number of positive integers that are relatively prime to 72 is equal to the number of positive integers that are not divisible by 2, 3, or 9 (since these are the prime factors of 72).

To find the number of positive integers that are not divisible by 2, 3, or 9, we can use the principle of inclusion and exclusion. This states that the number of positive integers that are not divisible by any of these numbers is equal to the sum of the number of positive integers that are not divisible by 2, the number of positive integers that are not divisible by 3, the number of positive integers that are not divisible by 9, minus the number of positive integers that are not divisible by both 2 and 3 (since we would have counted them twice).

Using this principle, we can calculate that there are 24 positive integers that are not divisible by 2, 18 positive integers that are not divisible by 3, and 8 positive integers that are not divisible by 9. However, we need to subtract the number of positive integers that are not divisible by both 2 and 3, which is 12. Therefore, the total number of positive integers that are relatively prime to 72 is 24 + 18 + 8 - 12 = 38.

So for the given example, there are 38 possible public keys for the RSA-Cryptosystem with modulus N = 91.

b) To show that the number of possible public keys is an even number, we need to consider the fact that if p and q are two distinct primes