1
$\begingroup$

I'm having a hard time understanding the purpose of having two primes $p,q$ for RSA to work. To illustrate my point, imagine only one prime ($p$) is used.

Alice, the encryptor, can take the public encryption exponent $e$, which Bob, the decryptor, created (along with the private exponent $d$) to satisfy $$ed\equiv 1\pmod{p-1}$$ Alice then encrypts $M$, sending $C=M^e$ (the full value without a modulus) to Bob.

Bob receives $C$ and retrieves the message: $$C^d\pmod p$$ $$=M^{ed}\pmod p$$ $$=M^{(p-1)k+1}\pmod p$$ $$=M\pmod p$$ $$\text{(by Fermat's Little Theorem)}$$ Assuming an attacker cannot guess $p$ from $e$, this should be secure. Instead, RSA creates exponents according to $$ed\equiv 1\pmod{(p-1)(q-1)}$$ and decrypts with $$C^d\pmod p$$ $$=M^{(p-1)(q-1)k+1}\pmod p$$ $$=M\pmod p$$ $$=M\pmod q$$ $$=M\pmod {pq}$$ From this, it seems that the only benefit of using two primes is so that Alice can take a take a modulus before sending the ciphertext. If only one prime is used, Alice could send the ciphertext $\mod p$ and preserve correctness, but then she could use $p$ to derive $d$, whereas in the two prime version, she can still take a $\mod n$ without knowing $p$ or $q$. I suspect modular exponentiation is much cheaper computationally that regular exponentiation, and that perhaps that is why two primes are used in practice. Is this the only reason? And if so why is the concept of factoring a semi-prime number so central to the idea of RSA?

$\endgroup$
3
$\begingroup$

"I suspect modular exponentiation is much cheaper computationally that regular exponentiation, and that perhaps that is why two primes are used in practice."

Yes, modular exponentiation is much faster.

How much do you think a number expands if you perform non-modular exponentiation?

And what's keeping an adversary from just trying all possible inputs, and encrypt them to see which one matches?

You can of course random pad $M$ with e.g. 128 random bits, but then your input will grow even larger, the exponentiation slower and the result even larger.


But most importantly, what's hard about calculating $\sqrt[e]C=\sqrt[e]{M^e}=M$ if $e$ is known? I don't think that that's a hard problem even if $e$ is very large. For a large $e$ the calculation really becomes problematic because the result size would be humongous anyway.

Of course, your encryption function needs to be irreversible without the private key value - in this case $d$ - and it isn't.

$\endgroup$
  • $\begingroup$ Running a small algorithm in my mind, where I just guess the high order bits and see the result is larger or smaller after exponentiation makes me think that only in the order of $|M|$ exponentiations are required tops, so I guess that just cannot be secure, no matter the size of the exponent. $\endgroup$ – Maarten Bodewes Oct 13 at 0:46
  • $\begingroup$ $(e,p)$ is public and magically we know $\phi(p) = p-1$. boom. But without factoring we don't know $\phi(n)$ so we cannot find $d$ that easily. $\endgroup$ – kelalaka Oct 13 at 7:43
  • 3
    $\begingroup$ @kelalaka If I understand the question correctly, $p$ is not part of the public key. (Nor is it required for encryption in the ill-fated scheme described. So that's actually fine.) $\endgroup$ – Maeher Oct 13 at 14:07

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.