1
$\begingroup$

I am somewhat familiar with the RSA algorithm, and I know that the security comes from the fact that the totient $\phi(m)$ is difficult to compute when $m$ is large and of unknown factorisation. I have more or less assumed that something like this lies at the base for most modern public-key encryption, but how widespread in the real world are public key encryption schemes (including RSA) for which "finding $\phi(m)$ from $m$" is the main bottleneck for a brute-force attack?

I'm not asking how many such schemes there are out there that people have invented (although I actually only know of RSA, so if someone were to, say, drop the names of one or three others, that would be cool), but rather, in a sense, what qualification can I use when I say "_____ of modern public key encryption hinges on the fact that $\phi(m)$ is hard to compute" to laypeople, for instance in a high school math class where we take a day off from the usual curriculum. Can I say "Almost all of modern encryption", or "Most" or do I have to moderate it to "A lot", or even just "Some"?

Improve this question
$\endgroup$
7
  • $\begingroup$ Do you really need to say this in the first place? I'm not sure it would be really useful, what matters is that such hard problems exist. $\endgroup$
    – fkraiem
    Oct 18, 2016 at 5:38
  • $\begingroup$ @fkraiem Not to people wondering "how is this relevant?" or "why are you even talking about this?" Plus, I'm personally curious. $\endgroup$
    – Arthur
    Oct 18, 2016 at 6:26
  • $\begingroup$ By algorithms do you public key encryption schemes? If you really want to know about all algorithms this becomes a very wide question. $\endgroup$
    – Guut Boy
    Oct 18, 2016 at 6:32
  • $\begingroup$ @GuutBoy Yes. I did mention public key encryption once in my question, but I could've been clearer throughout that my question is limited to that class of algorithms. $\endgroup$
    – Arthur
    Oct 18, 2016 at 6:46
  • $\begingroup$ I'm assuming the answer is none. Real-world implementations of RSA use the Carmichael function. I'm guessing anything else that could use the totient function, could also use the Carmichael function. So none, "depend" on totient function in the sense that without that function, they could not exist. $\endgroup$
    – mikeazo
    Oct 18, 2016 at 12:42

1 Answer 1

Reset to default
5
$\begingroup$

I know that the security comes from the fact that the totient $\phi(n)$ is difficult to compute

Actually, we don't know that. We know that if we can recover $\phi(n)$, we can decrypt an RSA encrypted message (given the public key), but we don't know how to go the other way; given a way to decrypt RSA encrypted message (given the ciphertext and the public key), how we might recover $\phi(n)$. Decrypting RSA messages might be easier than recovering $\phi(n)$.

However, to address your question "what public key algorithms assume that recovering $\phi(n)$ is hard", well, recovering $\phi(n)$ is equivalent to factoring $n$ (in the sense that if you can solve one of them, you can immediately solve the other". Hence, what you're looking for are public encryption methods that assume that factorization is difficult; I believe that list would be RSA, Rabin and Paillier (which is a public key encryption scheme with some additional homomorphic properties that can be useful at time).

Improve this answer
$\endgroup$
2
  • $\begingroup$ As for why anybody would use Rabin: The variant Rabin-Williams offers really fast signature verification if that matters to you. $\endgroup$
    – SEJPM
    Oct 18, 2016 at 20:34
  • $\begingroup$ It should probably also be mentioned that there are schemes with security based on other hard problems. Saying that "Almost all of modern encryption" is based on this would not be true. $\endgroup$
    – Guut Boy
    Oct 19, 2016 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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