[curves] Introduction to ECC

Tue Mar 13 14:34:21 PDT 2018

Hi Brad,

I will try to keep this short.

On 03/13/2018 09:07 PM, Brad Klee wrote:
> After: https://moderncrypto.org/mail-archive/curves/2018/000982.html
> And: https://moderncrypto.org/mail-archive/curves/2018/000981.html
>
> Hi Dominik,
>
> I am not wrong. In this disagreement, you seem confused about
> solutions of diophantine equations. You suggest that a curve will have
> as many distinct solutions over Z^2 as over (Z/pZ)^2 with prime p.
> This counters common sense, which states that there are not
> arbitrarily many solutions to any particular diophantine equation,
> i.e. over Z^2.
No, I am stating that all solutions over R^2 mapped as repetitions with
coordinate translation x'=x+mp, y=y+np for all m,n\in Z contain all
curve solutions over (Z/pZ)^2. That means, that "infinitely wrapping a
smooth curve over a torus" is the right projection if we want to depict
the repetitive nature of GF(p) in two dimensions (circle would work in
one dimension) for any given curve f(x,y)=0.
>
> So what is actually happening?
>
> Take the example curve: 0 = -36 + 400*x^2 - 2000*x^2 y + 400*y^2
> depicted over a finite field in the left panel of [1]. This is another
> form of the Jacobi quartic, but we might consider it  a "new curve"
> because the addition rule on the cubic involves a linear intersection
> geometry, different from the quartic. More heresy, the x=0 solution
> occurs at y=2. Starting with P =[2/5,7/10], we calculate sequences
> over Q and GF[23],
Assuming f(x,y)= -36 + 400*x^2 - 2000*x^2 y + 400*y^2 we see that there
are smooth curves drawn in the form of f(x+mp,y+np)=0 for some chosen
values of m and n. And of course, the values are chosen in a way that
shows only parts of infinitely-wrapped smooth curve (or a distinct
number of "new curves" with aforementioned coordinate translation) that
actually hit some interesting points in the (Z/pZ)^2 domain. That is
fine - of course you cannot work with the rest of the points I always
draw and I am talking about. They are there just to help the reader
think about the very nature of the underlying field.
>
> nP        : [2/5, 7/10], [-(7/60), -(11/45)], [-(110/527), 3367/9610],
> [184223/336840, 125521/804005], [172557142/149756395,
> 546265447/84739210] . . .
> nP%23 : [5, 3], [11, 11], [9, 15], [17, 6], [4, 18], [20, 10], [21,
> 20], [0,2], [2, 20], [3, 10], [19, 18], [6, 6], [14, 15], [12, 11],
> [18,3], [ infty,0 ] . . . Repeats . . .
>
> This example shows what actually happens. The Q-sequence visits
> infinitely many //fractions// of increasing complexity. Introducing a
> finite field such as GF[23], we find the subgroup structure used in
> ECC. Please realize that the map from Q^2 ---> (Z/pZ)^2 //is not// a
> modulus-type map!  
Ok, I am not going into big detail here, but let me show you, that it
may be a modulus-type map after all.

\frac{2}{5}\equiv 2\frac{1}{5}\mod 23

So we find a multiplicative inverse of 5 over GF(23), which is 14 as
14\cdot 5\equiv 1\mod 23

Therefore \frac{2}{5}\equiv 2\cdot 14\mod 23, which gives us
\frac{2}{5}\equiv 28\mod 23 which yields (unsurprisingly) 5.

The same applies for 7/10 which translates to 3 using the same modular
arithmetic.

We surely confirm that both f(5,3)\equiv 0\mod 23 as it is -136436\mod
23=0, what about the rational notation then? It actually is the case
that f(2/5,7/10)=0 so both solutions are apparently valid over GF(23).

Now let's find f(5+23m,3+23n) to prove that my hypothesis might be
right. If we are unable to find m,n\in Z, I am wrong, if we can find it,
I might be right after all.

And for example f(5+23,3)\equiv 0\mod 23 (looks like infinitely many
repetitions hit this point actually).

I think I understand your point, but that does not invalidate my
hypothesis (which I think can be really easily proven, because if there
exist particular solutions in m and n, those solutions are present in
the set of all m,n\in Z). So again, the curve depicted in the left panel
of [1] can be drawn over a area of R^2 which covers the (Z/pZ)^2 domain
and if we select only those points that fall into (Z/pZ)^2 from the
infinite wrapping around this part of R^2, they do indeed contain all
solutions of such curve over given (Z/pZ)^2 - that is GF(23) in our case.

Please mind that I am primarily talking about finding rational points
over GF(p) now. You are slightly mixing it with the group addition law
used with given curve. Those are not the same things, although you may
typically use the group addition law to generate the rational points
over GF(p) - but sometimes not all. Take Ed25519 for example. You have
to chose generators from all subgroups in order to generate all points
of Ed25519 this way. This is why you need to zero out specified bits
when you are using Ed25519 as a building block of some cryptosystem
(typically for signatures here). If you fall into a small subgroup, you
are screwed in case of signatures. In case of finding all rational
points, you just do not find them all.

I didn't study the addition law used with the curve you posted (but I
have put it on my TODO list) - but if you are saying that it involves
linear intersections, I can also state that such linear intersection
rule would also work by wrapping the line infinitely around the torus
and it would eventually hit the given rational point which maps to the
same rational point over Q you mention above. This is no coincidence,
but again it is a feature of the underlying field. I hope I can show
this in the next video (it is getting tricky). And to add more
confusion, for every line over R^2 (or Q^2 thereof) you can draw two
different lines on the torus having the same properties when it comes to
explaining the group law. It is not in my writing plan (yet), but it can
be really easily shown in Weierstrass simple form (and that is another
reason I started with creating visualizations using the Weierstrass
simple form - it really helps you develop the necessary tools).
>
> The other issue is evaluation of nP using the quartic rule. Apply
> shear transform P=[2/5,7/10] ---> P' = [2/5, 3/10]. Then calculate via
> EFD formulas:
>
> nP'          : [2/5, 3/10], [-(36/35), 1203/490], [-(110/527),
> 670563/2777290], [202104/921115, 80558112963/339381137290] . . .
> nP' % 23 : [5, 21], [20, 1], [9, 8], [17, 15], [4, 1], [11, 4],
> [21,10], [ infty,0], [2, 10], [12, 4], [19, 1], [6, 15], [14, 8], [3,
> 1], [18, 21], [0, 21] . . . Repeats . . .
> nP % 23  : [5, 3], [20, 12], [9, 15], [17, 13], [4, 18], [11, 19],
> [21, 20], [infty, 0], [2, 20], [12, 19], [19, 18], [6, 13], [14, 15],
> [3,12], [18, 3], [0, 21] . . . Repeats . . .
>
> Now compare cosets C_16/C_2. They are the same between iterations. The
> two C_8 subgroups are different:
>
> G1: [11, 11], [17, 6], [20, 10], [0, 2], [3, 10], [6, 6], [12, 11],
> [Infty, 0]
> G2: [20, 12], [17, 13], [11, 19], [infty, 0], [12, 19], [6, 13], [3,
> 12], [0, 21]
>
> Maybe G1 and G2 such as these could lead to an interesting pairing
> scheme [2] ? More on this question and evaluation over C & C^2 soon.
Now we are talking about something completely different. The generated
subgroups are an interesting feature of given curve and it is nice that
it can be shown on GF(p) with reasonably small p. About the pairing -
well ... I would love to read about that if you find anything
interesting there. Right now I am knee-deep in Ed25519 and Curve25519
embedded implementations and making nice pictures and videos makes me
breath easier :)

And I am really curious about your work over C^2 here. Just writing
about that makes me want to get back to academia :)

Cheers and keep up the good work!
Dominik

P.S.: It wasn't short after all ... my apologies for that.
>  
> Cheers,
>
> Brad
>
>
> [1] https://ptpb.pw/AfTT.png
> [2] http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf
>
>