[Cryptography] Why is ECC secure?

[Bill Cox]

Just for completeness, here's my notes on the math:

x^2 + y^2 = 1 + dx^2y^2

Define a curve C as follows:

let z' = -sqrt(d)xy

x^2 + y^2 + z^2 = 1

So, it is the unit sphere.

Let (0, 1, 0) be the origin point on the curve

C is a path inscribed on a unit sphere with a cool property.  Any point on
the Edwards curve corresponds to a point on C and can be trivially computed
using modular arithmetic.  Edwards curve addition is equivalent adding the
lengths from the origin to the two points on the sphere, weighted by a
simple weighting factor.  The weight is 1/|(x, y)|.  If the length,
computed in modular arithmetic, of both the generator and public key point
are known, then computing the discrete log can be done using regular
techniques such as index calculus.

If this where to happen, the strength of Edwards curve compatible EC crypto
would plummet, as we typically only use 256 bits in EC, while we need more
like 2048 bit to defend against index calculus.

So, can we find the line integral from the origin to (x, y, z) given x and
y using modular arithmetic?

y = sqrt((1 - x^2)/(1 + x^2))
|(x, y)| = sqrt(x^2 + (1-x^2)/(1+x^2)) = sqrt((x^2 + x^4 + 1 - x^2)/(1+x^2))
         = sqrt((x^4 + 1)/(x^2 + 1))
z = xy = x*sqrt((1 - x^2)/(1 + x^2))

x' = 1
y' = -(2 x)/(Sqrt[(1 - x^2)/(1 + x^2)] (1 + x^2)^2)
z' = (-x^4-2 x^2+1)/(sqrt((1-x^2)/(x^2+1)) (x^2+1)^2)

integrate sqrt(x'^2 + y'^2 + z'^2)/sqrt(x^2 + y^2)
 = sqrt(1 + ((2 x)/(Sqrt[(1 - x^2)/(1 + x^2)] (1 + x^2)^2))^2 + ((-x^4-2
x^2+1)/(sqrt((1-x^2)/(x^2+1)) (x^2+1)^2))^2)/sqrt((x^4 + 1)/(x^2 + 1))

Plugging the above into Wolfram's integral calculator results in:

= (Sqrt[2 - 2 x^4] Sqrt[-((1 + x^4)/((-1 + x^2) (1 + x^2)^2))]
EllipticF[ArcSin[x], -1])/Sqrt[(1 + x^4)/(1 + x^2)]

The ArcSin and especially the EllipticF are functions that I don't know how
to compute using modular arithmetic.  There are various modular-arithmetic
friendly infinite series expansions.  Are there any where we can reduce to
a reasonable finite equation using modular arithmetic?

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