module EllipticCurve

Public Class Methods

add(point1, point2) click to toggle source

Add - Add two points together.

# 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) click to toggle source

Double - Add a point on the curve to itself.

# 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) click to toggle source

Modular Inverse.

# 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) click to toggle source

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

# 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