[Cryptography] Why is ECC secure?

[Bill Cox]

On Fri, Aug 14, 2015 at 11:11 AM, Richard Outerbridge <outer at sympatico.ca>
wrote:

>
> > On 2015-08-14 (226), at 12:35:09, Bill Cox <waywardgeek at gmail.com>
> wrote:
> >
> > Duh... any operator of the form Finv(F(a) + F(b)) forms a group.  It is
> associative and commutative.  The identity element is Finv(0).  The inverse
> of x is Finv(-F(x)).  I really would have enjoyed the class where they
> teach this :)
>
> Somewhat sarcastic are we feeling this morning, Sir?  Usual shave?
> __outer
>
>
Actually, there's a sad story here.  I love group theory.  However, in the
class I took at Berkeley on intro group theory, they allowed a prof who had
recently had a stroke teach it, but the guy had lost all of his
mathematical ability.  So... we all failed the final, and the math
department gave us all A's anyway.  I was unable to continue with the
second course since I had learned nothing from the first.  So, all I have
now is a Wikipedia level of knowledge of group theory.

Anyway, I had fun this morning coming up with all sorts of group addition
laws of the form Finv(F(a) + F(b)).  Here's one of the simplest:

  let F(x) = 1/x for x != 0, and 0 for x = 0
  Finv(x)  = 1/x for x != 0, and 0 for x = 0
  Addition rule: 1/(1/a + 1/b), or 0 if a == 0, b == 0, or 1/a + 1/b == 0

We need a "0" element, which is why we need F(0) = 0.  Now check for
inverse:

  inv(a) = Finv(-F(a)) = 1/(-1/a) = -a

We can define this on the open interval (-1, 1), which excludes 1, and -1,
which map to themselves, which would cause problems.  This seems to satisfy
the definition of a group.

To make it faster for modular arithmetic, we only have to do the modular
inverse at end of computation if we track numerator/denominator separately:

an/ad @ bn/bd = 1/(ad/an + bd/bn) = 1/((ad*bn + an*bd)/(an*bn) =
an*bn/(ad*bn + an*bd)

This is only 3 multiplications and one addition per group operation, which
I think is quite a bit faster than Edwards curve performance with
protective coords.  Have simpler groups like this one been broken?  I'm
trying to get my head around why we need the full complexity of elliptic
curve crypto to get the security we need, and understanding weaknesses in
this system and why such weaknesses are not in regular elliptic crypto
would give me some more confidence in elliptic crypto.

I wrote some simple Python code to implement it, which is attached.  An
interesting property in this group is that anything multiplied (not added)
by itself is 1.  One way to think of it is that the group operation is
putting n resistors in parallel, and the result is the resistance of the
parallel structure.  Are there standard attacks I can try against it?

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150814/8bf8148e/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: simple.py
Type: text/x-python
Size: 2929 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150814/8bf8148e/attachment.py>