class Rb25519::FField::MontgomeryEC

Toy Montgomery curve to test

Montgomery curves have the form:

B * y^2 = x^3 + A * x^2 + x

Test cases:

E(@a = 3, @b = 1) over p=47

H = [5,8] on curve.

Extend the Montgomery EC with projective (XZ) coordinate functions

Attributes

a[RW]
b[RW]

Public Class Methods

new(field, a: nil, b:nil) click to toggle source
Calls superclass method Rb25519::FField::EC::new
# File lib/rb-pure25519.rb, line 421
def initialize(field, a: nil, b:nil)
  super(field)

  @a = @field[ a || 3]
  @b = @field[ b || 1]

  @a24 = (@a + 2) / @field[4]
end

Public Instance Methods

double_point(point_a) click to toggle source

Doubles a point in affine coordinates

# File lib/rb-pure25519.rb, line 479
def double_point(point_a)
  #puts "Double point: #{point_a.inspect}"

  return point_a if point_a == ECInfinity

  xa = point_a[0].kind_of?(FFieldValue) ? point_a[0] : @field[point_a[0]]
  ya = point_a[1].kind_of?(FFieldValue) ? point_a[1] : @field[point_a[1]]


  bb_inv = (@b * 2 * ya).inv

  c1 = (xa**2 * 3   +    @a * xa * 2     + 1 )

  
  xc = @b * c1**2 * bb_inv**2   - @a - xa - xa
  yc = (xa * 2 + xa + @a) * c1 / (@b * ya * 2)     -    @b * c1**3 * bb_inv**3  - ya


  #x3 = b*   (3*x12+2*a*x1+1) **2   /   (2*b*y1)**2  -a-x1-x1

  #y3 = (2*x1+x1+a)  *(3*x12+2*a*x1+1)/(2*b*y1)-b*(3*x12+2*a*x1+1)3/(2*b*y1)3-y1

  [xc, yc]
end
on_curve(x,y) click to toggle source
# File lib/rb-pure25519.rb, line 431
def on_curve(x,y)
  x = @field[x] unless x.kind_of? FFieldValue
  y = @field[y] unless y.kind_of? FFieldValue

  (@b * y**2) == (x**3) + x**2 * @a + x
end
point_add(point_a, point_b) click to toggle source

Add points in affine coordinates

# File lib/rb-pure25519.rb, line 443
def point_add(point_a, point_b)

  return point_b if point_a == ECInfinity
  return point_a if point_b == ECInfinity

  xa = point_a[0].kind_of?(FFieldValue) ? point_a[0] : @field[point_a[0]]
  xb = point_b[0].kind_of?(FFieldValue) ? point_b[0] : @field[point_b[0]]

  ya = point_a[1].kind_of?(FFieldValue) ? point_a[1] : @field[point_a[1]]
  yb = point_b[1].kind_of?(FFieldValue) ? point_b[1] : @field[point_b[1]]

  #puts "MontgomeryEC#point-add: #{[xa, ya].inspect}  + #{[xb, yb].inspect}"

  if xa == xb and ya == -yb
    return ECInfinity
  end

  if xa == xb and ya == yb
    return double_point(point_a)
  end

  # All the following operations are in F_p (eg, "mod p")

  l = ( yb - ya) / (xb - xa)
  m = ya - l * xa

  xc = @b * l**2 - @a - xa - xb
  yc = (xa * 2 + xb + @a) * (yb - ya) / (xb - xa)   -   ( @b * (yb - ya) ** 3 ) / (xb - xa)**3     - ya
  [xc, yc]
end
pts() click to toggle source

List of scaled points of [5,8] on toy curve to test laddering and other REPL-style exploration/testing to get this working right.

# File lib/rb-pure25519.rb, line 684
def pts
  [
    [ @field[ 0], @field[ 0] ],    # 0
    [ @field[ 5], @field[ 8] ],    # 1
    [ @field[14], @field[44] ],    # 2
    [ @field[41], @field[36] ],    # 3
    [ @field[34], @field[ 6] ],    # 4
    [ @field[23], @field[37] ],    # 5
    [ @field[17], @field[ 4] ],    # 6
    [ @field[43], @field[36] ],    # 7
    [ @field[ 8], @field[17] ],    # 8
    [ @field[40], @field[28] ],    # 9
  ]
end
scale_proj(k, p) click to toggle source
# File lib/rb-pure25519.rb, line 636
  def scale_proj(k, p)
#    puts "Scaling #{k} times: #{p.inspect}"

    pa = ECInfinity
    pb = p.to_xz

    x = p[0]


    bits = k.bit_length
#    puts "Bits: #{bits}"

    (1..bits).each do |j|
#      puts "Aff[a:x] = #{[pa, pa.to_xy ]}"
#      puts "Aff[b:x] = #{[pb, pb.to_xy ]}"

      if (k >> (bits - j) ) & 1 == 0

#        puts "[[ bit: 0 ]]; pb = pa + pb; pa = 2*pa"

        pb = xz_simple_add( pa, pb, x )
        pa = xz_double( pa )
      else

#        puts "[[ bit: 1 ]]; pb = 2*pb; pa = pa + pb"

        pa = xz_simple_add( pa, pb, x )
        pb = xz_double(pb)
      end

#      puts

    end

#      puts "--end--"
#      puts "Aff[a:x] = #{pa[0] / pa[1]}"
#      puts "Aff[b:x] = #{pb[0] / pb[1]}"

    return ECInfinity if pa[1] == 0
    pa
  end
xz_double(pa) click to toggle source

Implementing “mdbl-1987-m” described in DJB's EFD database: hyperelliptic.org/EFD/g1p/auto-montgom-xz.html

# File lib/rb-pure25519.rb, line 558
def xz_double(pa)
  x1 = pa[0]
  z1 = pa[1]

  c = (x1 - z1)**2
  d = (x1 * 4 * z1)

  x3 = (x1 + z1) ** 2 *  c
  z3 = d*( c + @a24 * d )
  [x3, z3]
end
xz_from_xy(point) click to toggle source
# File lib/rb-pure25519.rb, line 528
def xz_from_xy(point)
  return [ @field[point[0].to_i], @field[1] ]
end
xz_simple_add(pa, pb, x) click to toggle source
Implement the XZ coordinates from
"Speeding the Pollard and elliptic curve methods of factorization" p.261

Actually, best description is at:

Cryptographic Algorithms on Reconfigurable Hardware p.301

Actually-- I'm not sure where this one came from.  Figuring out XZ
projective point adding was a real pain in the ass!

Test points for scaling/point addition and testing the Montgomery ladder.

(5 : 8 : 1)

--
(2, (14 : 44 : 1))
(3, (41 : 36 : 1))
(4, (34 : 6 : 1))
(5, (23 : 37 : 1))
(6, (17 : 4 : 1))
(7, (43 : 36 : 1))
(8, (8 : 17 : 1))
(9, (40 : 28 : 1))
(10, (7 : 11 : 1))
(11, (46 : 1 : 1))
(12, (27 : 29 : 1))
(13, (20 : 14 : 1))
(14, (6 : 1 : 1))
(15, (35 : 14 : 1))
(16, (36 : 14 : 1))
(17, (45 : 7 : 1))
(18, (18 : 17 : 1))
(19, (39 : 1 : 1))
(20, (37 : 29 : 1))
(41, (41 : 11 : 1))
(42, (14 : 3 : 1))
(43, (5 : 39 : 1))
(44, (0 : 1 : 0))
(45, (5 : 8 : 1))
# File lib/rb-pure25519.rb, line 619
def xz_simple_add(pa, pb, x)

  return pb if (pa == ECInfinity)
  return pa if (pb == ECInfinity)
  
  x1 = pa[0]
  z1 = pa[1]
  x2 = pb[0]
  z2 = pb[1]

  x3 =       ( (x1 - z1)*(x2 + z2) + (x1 + z1)*(x2 - z2) )**2
  z3 =  x *  ( (x1 - z1)*(x2 + z2) - (x1 + z1)*(x2 - z2) )**2

  [x3, z3]
end
xz_to_xy(point) click to toggle source

Convert XZ to XY coordinates.

point must be Array<FastFrac<FFieldValue>> to work in the EC field.

Montgomery curves have the form:

B * y^2 = x^3 + A * x^2 + x

# File lib/rb-pure25519.rb, line 543
def xz_to_xy(point)

  x = point[0] / point[1]

  y_sq = (x**3 + x**2 * @a + x) / @b

  return y_sq.sqrt.map{|e| [x, e]}
end