[Cryptography] Why is ECC secure?

Watson Ladd watsonbladd at gmail.com
Fri Aug 14 10:07:18 EDT 2015


On Thu, Aug 13, 2015 at 7:57 PM, Ray Dillinger <bear at sonic.net> wrote:
>
>
> On 08/13/2015 01:46 PM, Tony Arcieri wrote:
>
>> When it comes to cryptanalysis, the real question is the amount of work
>> that has gone into breaking things like the RSA trapdoor function as
>> opposed to just "prime numbers" or factoring. Both ECC and RSA use prime
>> numbers, and the discrete logarithm problem has probably received a similar
>> amount of study to factoring (and indeed there are spooky similarities
>> between these problems too).
>
> One thing to point out is that RSA is at least as hard as factoring
> because if you can solve RSA, you can use the solution to factor its
> modulus.  IOW, there can be no shortcut that makes it easier than
> factoring.

It's true that given phi I can factor the modulus. But it's not known
that being able to decrypt an RSA ciphertext that I can factor the
modulus. Some schemes like Rabin-Williams are provably equivalent to
factoring, but as far as I know a similar result hasn't been shown:
the best results in this direction involve unrealistic models of
algorithms, and there are proofs that certain classes of reduction
would make factoring easy.

>
> But that doesn't rule out the possibility that factoring may still be
> easier than the best way we know how to do it now.
>
>                                         Bear
>
>
>
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography



-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.


More information about the cryptography mailing list