Class: Rb25519::FField::MontgomeryEC

Inherits:
EC
  • Object
show all
Defined in:
lib/rb-pure25519.rb,
lib/rb-pure25519.rb

Overview

Extend the Montgomery EC with projective (XZ) coordinate functions

Direct Known Subclasses

EC25519

Instance Attribute Summary collapse

Attributes inherited from EC

#field

Instance Method Summary collapse

Methods inherited from EC

#naive_points, #scale_double_add, #scale_naive

Constructor Details

#initialize(field, a: nil, b: nil) ⇒ MontgomeryEC

Returns a new instance of MontgomeryEC.



421
422
423
424
425
426
427
428
 
# 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

Instance Attribute Details

#a ⇒ Object

Returns the value of attribute a.



419
420
421
 
# File 'lib/rb-pure25519.rb', line 419

def a
  @a
end

#b ⇒ Object

Returns the value of attribute b.



419
420
421
 
# File 'lib/rb-pure25519.rb', line 419

def b
  @b
end

Instance Method Details

#double_point(point_a) ⇒ Object

Doubles a point in affine coordinates



479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
 
# 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) ⇒ Object 



431
432
433
434
435
436
 
# 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) ⇒ Object

Add points in affine coordinates



443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
 
# 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 ⇒ Object

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



684
685
686
687
688
689
690
691
692
693
694
695
696
697
 
# 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) ⇒ Object 



636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
 
# 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) ⇒ Object

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



558
559
560
561
562
563
564
565
566
567
568
 
# 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) ⇒ Object 



528
529
530
 
# 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) ⇒ Object

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))



619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
 
# 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) ⇒ Object

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



543
544
545
546
547
548
549
550
 
# 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