Module: EllipticCurve

Defined in:
lib/elliptic_curve.rb

Class Method Summary collapse

Class Method Details

.add(point1, point2) ⇒ Object

Add - Add two points together.



45
46
47
48
49
50
51
52
53
54
55
56
57
 
# File 'lib/elliptic_curve.rb', line 45

def self.add(point1, point2)
  #double if both points are the same
  return double(point1) if point1 == point2

  #slope = (y1 - y2) / (x1 - x2)
  slope = ((point1[:y] - point2[:y]) * modinv(point1[:x] - point2[:x])) % $p
  #new x = slope^2 - x1 - x2
  x = (slope ** 2 - point1[:x] - point2[:x]) % $p
  #new y = slope * (x1 - new x) - y1
  y = ((slope * (point1[:x] - x)) - point1[:y]) % $p

  return { x: x, y: y }
end

.double(point) ⇒ Object

Double - Add a point on the curve to itself.



32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/elliptic_curve.rb', line 32

def self.double(point)
  #slope = (3x^2 + a) / 2y
  slope = ((3 * point[:x] ** 2) * modinv((2 * point[:y]))) % $p # using modular inverse to perform "division"

  #new x = slope^2 - 2x
  x = (slope ** 2 - (2 * point[:x])) % $p
  #new y = slope * (x - new x) * y
  y = (slope * (point[:x] - x) - point[:y]) % $p

  return { x: x, y: y }
end

.modinv(a, m = $p) ⇒ Object

Modular Inverse.



20
21
22
23
24
25
26
27
28
29
 
# File 'lib/elliptic_curve.rb', line 20

def self.modinv(a, m = $p)
  a = a % m if a < 0
  prevy, y = 0, 1
  while a > 1
    q = m / a
    y, prevy = prevy - q * y, y
    a, m = m % a, a
  end
  return y
end

.multiply(k, point = $g) ⇒ Object

Multiply - Use the double and add operations to multiply a point by an integer.



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/elliptic_curve.rb', line 60

def self.multiply(k, point = $g)
  # create a copy the initial starting point (for use in addition later on)
  current = point

  # convert integer to binary representation (for use in the double and add algorithm)
  binary = k.to_s(2)

  # double and add algorithm for fast multiplication
  binary.split("").drop(1).each do |char| # ignore first binary character
    # 0 = double
    current = double(current)

    # 1 = double and add
    if char == "1"
      current = add(current, point)
    end
  end

  return current
end