An interesting J alternative to OOP that works quite well for ec and ecdsa code
is promoting monads to dyads, and dyads to adverbs in order to pass relatively
constant control information around.
An example of other languages overuse of classes is something like Points.
Which are obvious mere data.
In the case of EC curves in a field and the relationship to points, a curve is
a constant parameter to functions.
For ECDSA purposes, the curve constants are: (for curve y2=x3+ax+b mod p)
Prime(field p) , a , b, Gx, Gy where (Gx,Gy) can be thought of as the first
point in the group mod p.
Cliff's code for generating a random EC curve slightly modified to return these
parameters in order:
ranEC=:3 : 0
whilst. g=y do.
'x1 y1 a'=.x:?3#y NB.<.<:2^31
b=.y|(*:y1)-x1*(a+*:x1)
g=.y +. +/ 4 27* (a,b) ^ 3 2
end.
y,a,b,g,x1,y1
)
g is 1 if the field is prime, and may be higher if p (y) is composite.
] c =. ranEC 2333
2333 1625 1701 881 1087 1
many EC operations need access to curve parameters : add, mult, double, sign,
verify, generate keys...
Its pretty easy to pick out just the parameters than any 1 function needs out
of the curve variable, and putting p and a at the head is useful because almost
all of the functions need p, and double needs p and a, and a function that just
needs those 2, can call 2 {.x (or m), and so can be called without passing the
full curve. While g is not needed for ECDSA over a prime field, putting it in
the middle is an alternative to excluding it altogether. Putting Gx, and Gy at
the end has a similar flexible purpose to 'p a' at the head. Accessing them
with _2 {. x will allow a function to be called with the curve or just the 2
points as paramaeters.
I just thought I'd share this neat feature of J organization, that can save a
lot of lines of code over classes.
----- Original Message -----
From: Raul Miller <[email protected]>
To: Programming forum <[email protected]>
Cc:
Sent: Friday, January 31, 2014 3:58:48 PM
Subject: Re: [Jprogramming] math requests
point add was not commutative in the python implementation either.
Consider:
y3 = ( l * ( self.__x - x3 ) - self.__y ) % p
Thanks,
--
Raul
On Thu, Jan 30, 2014 at 10:41 PM, Pascal Jasmin <[email protected]> wrote:
> Hi Cliff,
> I don't understand how to go from xyz back to xy coordinates.
>
>
> At any rate, here is the affine (python) implementation. (I posted invmod
> earlier):
>
>
> Pointadd =: 1 : 0 NB. n is curve p a b
> :
> p =. {. m NB.'p a b' =. n
> if. y -: p,0 do. x return. end.
> if. x -: p,0 do. y return. end.
> if. x -: y do. m Pointdouble y return. end.
> 'xx xy' =. x
> 'yx yy' =. y
> if. (xx = yy) *. 0=p|xy+yy do. p,0 return. end.
> l =. p | (p invmod yx - xx ) * yy - xy
> (p| (l*xx -x3 ) - xy ) ,~ x3=. p | yx -~ xx -~ l * l
> )
> Pointdouble =: 4 : 0
> 'p a'=. 2{. x
> if. y -: p,0 do. y return. end.
> 'xx xy' =. y
> l =. p | (p invmod xy * 2 ) * a + 3 * *: xx
> (p| (l*xx -x3 ) - xy ) ,~ x3=. p | (+: xx) -~ l * l
> )
> Pointmul =: 1 : 0 NB. sum of binary mask of repeated squares
> :
> m Pointadd/^:(1<#) |. bin # |. m Pointdouble^:(i. # bin =. 2 #. inv x) y
> )
>
> It passes the python tests, but it worries me that addition is not
> commutative. I also don't know how to code the point at infinity (I put 0,p
> but that is never reached).
>
> 3 10 (23 Pointadd) 9 7
> 17 20
>
> (23 1 Pointadd) each /\ 18 # <3 10
> ┌────┬────┬────┬────┬────┬────┬────┬─────┬───┬─────┬───┬─────┬────┬─────┬────┬─────┬────┬────┐
> │3 10│7 12│19 5│17 3│9 16│12 4│11 3│13 16│0 1│20 13│6 3│22 19│16 2│12 15│12
> 8│16 21│22 4│6 20│
> └────┴────┴────┴────┴────┴────┴────┴─────┴───┴─────┴───┴─────┴────┴─────┴────┴─────┴────┴────┘
>
> ,. (2+ i.16) (23 1 Pointmul)"0 1 ] 3 10
> 7 12
> 19 5
> 17 3
> 9 16
> 12 4
> 11 3
> 13 16
> 0 1
> 6 4
> 18 20
> 16 20
> 5 15
> 13 21
> 2 21
> 5 19
> 18 3
>
> These lists diverge after the item 0 1 is reached, which is the origin and a
> good candidate for infinity? I don't seem to understand what order is.
>
>
>
>
>
> ----- Original Message -----
> From: Cliff Reiter <[email protected]>
> To: [email protected]
> Cc:
> Sent: Wednesday, January 29, 2014 3:32:21 PM
> Subject: Re: [Jprogramming] math requests
>
> Some elliptic curve stuff; I think there is a +1 error that Roger Hui
> noticed in the factorization method.
>
> http://archive.vector.org.uk/art10007270
> http://archive.vector.org.uk/art10007280
>
> Best, Cliff
>
>
> On 1/29/2014 11:35 AM, Pascal Jasmin wrote:
>>
>> With all of the mathematicians on this list, these functions have likely
>> been implemented before in J.
>>
>> elyptic curve point add, multiplication and double
>> a python reference implementation:
>> https://github.com/warner/python-ecdsa/blob/master/ecdsa/ellipticcurve.py
>>
>> the functions are: __add__ __mul__ and double
>>
>> if I may suggest J explicit signatures for the first 2 functions as:
>>
>> F =: 4 : 0
>> 'yx yy yo' =. y
>> 'xx xy xo' =. x
>> )
>>
>> Some other methods than the python reference could be considered here:
>>
>> http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
>>
>>
>> also appreciated if you have in implementation of inverse_mod
>> for reference function of same nate at:
>> https://github.com/warner/python-ecdsa/blob/master/ecdsa/numbertheory.py
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>>
>
> --
> Clifford A. Reiter
> Lafayette College, Easton, PA 18042
> http://webbox.lafayette.edu/~reiterc/
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
