Elliptic Curve Cryptography: a gentle introduction

Re:Elliptic Curve Cryptography: a gentle introduction by ColinWright on Sunday May 17, 2015 @05:54PM (#9561858)

It's more complicated than that. Consider RSA.

    Choose p, q, and let n=pq

        Note: phi(n) = (p-1)(q-1)

    Choose e

    Compute d such that de = 1 (mod phi(n))

        The number d is your private key.

    Given a message M, E(M) = M^e (mod n)

    Given an encrypted message E, D = E^d (mod n).

    Magically, D=M.

Now multiplying the numbers p and q is a one-way function, because there is no effective way to factor n (if p and q are chosen suitably.) The exponentiation M^e is a trap-door function because normally you can't undo it, but with any of the extra knowledge p, q, or d, then you can undo it.

There are nuances, and time and time again I meet people who think lots of things are the same when in fact they are different, and the differences matter.

A one-way function is not necessarily a trap-door function.

In this case many things are equivalent in the sense that one can easily be computed given another, but the details actually matter.

The point, though, is that there are on-way functions that do not have trap-doors and hence are not trap-door functions. The definition as given in the blog post seems to conflate the two, when in fact the difference is important. PKCs are often made by starting with a provably one-way function and trying to find a way of inserting a trap-door without weakening it.

(Sorry if this is a little incoherent, it's late here, and I need to do some stuff before going to bed, and I have an early start tomorrow.)

[ Parent | on HN ]

Re:Elliptic Curve Cryptography: a gentle introduction by nightcracker on Monday May 18, 2015 @03:13AM (#9563143)

Perhaps a better example of a one-way function vs. a trap door is with symmetric cryptography? Let's look at two examples of a 2^128 -> 2^128 function f(n):

- The first 128 bits of SHA2(n). It should be computationally infeasible to find n from the output.

- AES128(n, k). It should be computationally infeasible to find n from the output, unless you know k.

[ Parent | on HN ]