1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ They may have some implicit cryptographic strength requirements, such as $e\neq d$. But formally, it seems to me like it works. $\endgroup$ – Arthur May 3 '18 at 11:56
  • $\begingroup$ 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. $\endgroup$ – Lone Learner May 3 '18 at 12:05
  • $\begingroup$ 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". $\endgroup$ – Arthur May 3 '18 at 12:07
  • $\begingroup$ @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. $\endgroup$ – Lone Learner May 3 '18 at 12:11
  • $\begingroup$ @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? $\endgroup$ – Lone Learner May 4 '18 at 12:47
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So what is the smallest $n = pq$ for which the RSA encryption and decryption works? $\endgroup$ – Lone Learner May 12 '18 at 4:20
  • $\begingroup$ please see my edit $\endgroup$ – kodlu May 12 '18 at 7:50
  • $\begingroup$ 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. $\endgroup$ – Lone Learner May 13 '18 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.