[Cryptography] Why is ECC secure?

Bill Cox waywardgeek at gmail.com
Tue Aug 18 11:36:58 EDT 2015


I think I'm finally getting the basics of why we like elliptic curve
crypto.  Here's my attempt to explain it in regular English.

These are curves such that they fit into this form:

    a @ b = Finv(F(a) + F(b))

The @ is the group "addition" operator and the + is some group operation,
likely addition or multiplication.  In the case of Edwards elliptic curves,
F(a) is a line integral along a path on the unit sphere.

These would all be trivially broken except:

1) F(a) is a transcendental function, with no modular arithmetic equivalent
2) Finv(F(a) + F(b)) is algebraic

This means we can easily compute the result, but not the magic in the
middle, where we're doing addition or multiplication on the transcendental
functions.

In elliptic curve crypto, during DH key agreement, Alice publishes
Finv(am*F(g)) mod p, where am is Alice's secret and g is the group
generator.  If we could compute Finv(x) mod p, Alice's secret would be
revealed.

It's a rare function that fits in this form and is algebraic when built
with a transcendental function F.  The circle group is in this form, when F
= arcsin(x).  It turns out that:

    sin(arcsin(x1) + arcsin(x2)) = x1x2 - y1y2
    where y1 = sqrt(1 - x1^2), and y2 = sqrt(1 - x2*2)

If this weren't the same as simple matrix multiplication, we might have
trouble analyzing it, but it is, and we can convert this easily to regular
DLP.  So, naturally, we want to know what functions are in this form but
are not equivalent to some well understood linear system.  Elliptic curves
seem to fit the bill.

In unrelated noodling...

I was trying to figure out what the NSA could possibly hide in a random
looking group seed.  It might be the case that they know the original
arithmetic representation of the group seed on the curve, and no one else
does.

If I were attacking either the circle group or any Edwards curve, and I
knew the generator's original arithmetic (x, y) position on the curve, and
if I could find an arithmetic point on the curve which is in the group and
maps to Alice's public key point, then it becomes trivial to reveal Alice's
secret.  Could it be helful to know the arithmetic representation of g on
the curve to map Alice's pubic key to such a point?

I think we've shown that finding such a point in the circle group is
equivalent to DLP, since I can convert the circle group problem into
regular DLP, and find the multiple of g that generates Alice's pubic key
point.  So, using DLP, I can find the arithmetic point on the curve.  If
instead, I were given an arithmetic representation (it would be a big
operator tree corresponding to the multiplication of g by am), I can easily
find am just by doing line integrals to am and dividing by the line
integral to g.

Therefore, on the circle group mapping a public key point to an arithmetic
point in the group on the circle is equivalent to DLP.  We can pose the
same problem for Edwards curves.  If we can map Alice's public key point to
an arithmetic representation of the point on the curve that is in the
group, then we can trivially reveal Alice's secret.  This problem is
equivalent to finding Alice's secret on Edwards curves.

Would knowing the arithmetic representation for g help?  I it might...

That's the only potential use for obscuring the original point that I can
think of...

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150818/533a4c36/attachment.html>


More information about the cryptography mailing list