# What is the smallest $n = pq$ for which the RSA encryption and decryption works?

The example at https://www.di-mgt.com.au/rsa_alg.html#simpleexample claims that the smallest value for the modulus $n$ for which the RSA algorithm works is $n = 11 \times 3 = 33$.

But slide number 30 (page 30) of http://haifux.org/lectures/161/RSA-lecture.pdf claims that $n = 5 \times 11 = 55$ as the minimal example of RSA key.

I would like to know why $n = 2 \times 5 = 10$ is not the minimal example. For example,

\begin{align*} p &= 2 \\ q &= 5 \\ n = pq &= 10 \\ \phi(n) = (p - 1)(q - 1) &= 4 \\ e &= 3 \\ d &= 3 \\ \end{align*}

These numbers seem valid because $e$ is coprime to $\phi(n)$ and $ed \equiv 1 \pmod{\phi(n)}$.

Both encryption and decryption seems to work fine with this. Let the message $m = 8$. Therefore the ciphertext is $m^e \text{ mod } n = 2.$ The plaintext can be retrieved again as $2^d \text{ mod } n = 8.$

Why is $n = 2 \times 5 = 10$ not the smallest $n$ for which the RSA encryption and decryption works fine?

• They may have some implicit cryptographic strength requirements, such as $e\neq d$. But formally, it seems to me like it works. – Arthur May 3 '18 at 11:56
• If $e \neq d$ is necessary, I would like to know why it is necessary. In that case, the next smallest example I can come up with is $p = 2$, $q = 11$, $n = 22$, $\phi(n) = 10$, $e = 3$, and $d = 7$ which is again inconsistent with the two articles I linked to in my question which are both inconsistent with each other. – Lone Learner May 3 '18 at 12:05
• If I actually knew how they've chosen their "smallest" examples, I would have posted an answer. And if I'm right about them having cryptographic strength requirements, then $e\neq d$ might not be the only cryptographic requirement they have. I did say "such as". – Arthur May 3 '18 at 12:07
• @Arthur I understand you. My previous question is not directed to you in particular but at anyone who could answer and clarify these things. I also wonder if it makes sense to think about cryptographic strength when the purpose is to find the smallest example for which the algorithm works because $n$ being so small and easily factorizable makes cryptographic strength irrelevant, in my opinion. – Lone Learner May 3 '18 at 12:11
• @Moo Since $n = 10$ in my scheme we can only encrypt and decrypt numbers less than 10. The claimed minimums may or may not allow decryption of the alphabet A-Z depending on how they are encoded. If we encode A=0, B=1, ..., Z=25, then the claimed minimums would allow the encryption and decryption of A-Z. What's your point? – Lone Learner May 4 '18 at 12:47

I've looked at the two papers. Clearly, strength is not the point, even $p,q$ of the order of about a hundred are open to attacks by hand/calculator.

Firstly $e\neq d$ is an absolute requirement for the definition of RSA since in practice $e$ is public and $d$ is private (needs to be kept secret) so both cannot be the same.

The other problem is that one chooses odd primes for RSA. The reason being if you choose $p=2,$ then your $\phi(n)=(p-1)(q-1)=q-1,$ directly reveals the value of $p$. The reason this is important is that the valid user in posession of the secret key $e,$ also knows $p$ and $q$ (it's been proved that knowing $(n,e)$ you can find $p,q$) and thus can break the system.

In fact the exponentiation for decryption $C^d$ are performed separately mod $p$ and $q$ by the legitimate user for efficiency, and then the Chinese Remainder Theorem is used to obtain $C^d$ modulo $n.$

What if we chose the smaller prime to be $p=3$? This presents a problem for the popular choice of exponent $e=3.$ By Fermat's little theorem, $$a^p\equiv a~(\textrm{mod}~p),$$ for all integers $a$ which means that the subgroup of multiplication modulo $p=3,$ is "inactive" in some sense in the exponentiation operation and then $q$ could be discovered by a cryptanalyst.

In summary, the smaller prime must be at least $p=5.$ Taking $p=5,$ the smallest $q$ would be 7, otherwise taking the integer square root of $n$ is equivalent to factorisation.

If $p=5,q=7$ then $\phi(n)=24,$ which violates the requirement $gcd(e,\phi(n))=1,$ for the exponent $e=5.$

So take $p=5,q=11$ to get $n=55,$ ruling out $n=33,$ as I explained above.

• So what is the smallest $n = pq$ for which the RSA encryption and decryption works? – Lone Learner May 12 '18 at 4:20
• please see my edit – kodlu May 12 '18 at 7:50
• I don't understand why $e \neq d$ is necessary. Sure, $e$ is public but the attacker may not know that the secret $d$ equals $e$. He still needs to brute force $d$ to know that it is same as $e$. The same thing holds true for $p = 2$. The attacker still needs to factor $n$ to determine $p = 2$. These are perils of small numbers not a specific choice of $p$ and $q$. But we have already established that strength is not of concern because we want to demonstrate RSA with small numbers. – Lone Learner May 13 '18 at 4:55