RSA Encryption

The RSA encryption is based on the following procedure:
Generate two distinct primes $p$ and $q$.Compute $n = pq$ and $\phi = (p – 1)(q – 1)$.
Find an integer $e$, $1 \lt e \lt \phi$, such that $\gcd(e, \phi) = 1$.
A message in this system is a number in the interval $[0, n – 1]$.
A text to be encrypted is then somehow converted to messages (numbers in the interval $[0, n – 1]$).
To encrypt the text, for each message, $m$, $c = m^e \bmod n$ is calculated.
To decrypt the text, the following procedure is needed: calculate $d$ such that $ed = 1 \bmod \phi$, then for each encrypted message, $c$, calculate $m = c^d \bmod n$.
There exist values of $e$ and $m$ such that $m^e \bmod n = m$.We call messages $m$ for which $m^e \bmod n = m$ unconcealed messages.
An issue when choosing $e$ is that there should not be too many unconcealed messages.For instance, let $p = 19$ and $q = 37$.
Then $n = 19 \cdot 37 = 703$ and $\phi = 18 \cdot 36 = 648$.
If we choose $e = 181$, then, although $\gcd(181,648) = 1$ it turns out that all possible messages $m$ ($0 \le m \le n – 1$) are unconcealed when calculating $m^e \bmod n$.
For any valid choice of $e$ there exist some unconcealed messages.
It’s important that the number of unconcealed messages is at a minimum.
Choose $p = 1009$ and $q = 3643$.
Find the sum of all values of $e$, $1 \lt e \lt \phi(1009,3643)$ and $\gcd(e, \phi) = 1$, so that the number of unconcealed messages for this value of $e$ is at a minimum.

Firstly, compute $n$ and $\phi$ for two prime numbers $p = 1009$ and $q = 3643$.

We have $n = pq = 1009 \cdot 3643 = 3674867$ and $\phi = (p – 1)(q – 1) = 1008 \cdot 3642 = 3672576$.

The goal here is to minimize the number of unconcealed messages. A message $m$ is unconcealed if $m^e \bmod n = m$.

That happens only if $m$ divides $n$. For the given $p$ and $q$, the divisors of $n$ are $1$, $n$, $p$ and $q$.

So, the number of unconcealed messages must be 4, i.e., minimum. A parameter of interest is $e$, and we know, $1 < e < \phi$ and $\gcd(e, \phi) = 1$. It can be observed that for $e$ being any of the divisors of $\phi$ other than $1$ and $\phi$, the number of unconcealed messages is more than $4$. Therefore, the only possible values of $e$ are the numbers less than $\phi$ and relatively prime with $\phi$. This can be achieved using a method called totient function, $\phi(e)$, which gives the number of integers less than $e$ which are relatively prime to $e$. For each $e$, check if the number of unconcealed messages is $4$. Sum up all such values of $e$ that satisfy the conditions. This might be computationally intensive to calculate manually but is feasible using a program with the algorithm mentioned. Note: The computation required for this problem is quite high for manual calculations so it's practically solved using a programming language like Python employing the principles just discussed, i.e., the RSA encryption and Euler's totient function. This problem essentially becomes a combination of number theory and programming problem.

More Answers: