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