ECDSA Ruby

ellipse.rb

require 'prime'

class Point
  attr_accessor :x, :y

  def initialize(ix, iy)
    @x = ix
    @y = iy
  end

  def infinity?
    @x == 0 and @y == 0
  end

  def clone
    Point.new(@x, @y)
  end
end

module FiniteMath
  def self.factor(num, pow, mod)
    return 1 if pow == 0
    if pow % 2 == 1
      return (num * factor(num, pow-1, mod)) % mod
    else
      return factor((num ** 2) % mod, pow/2, mod)
    end
  end

  def self.divide(num, num2, mod)
    return nil if (num2 % mod) == 0
    (num * inverse(num2, mod)) % mod
  end

  def self.inverse(num, mod)
    return nil if (num % mod) == 0
    (num ** (mod-2)) % mod
  end
end

# y^2 = x^3 + ax + b
class EllipticCurve
  # prime -> a prime number that defines the finite field (or modular arithmetic)
  # a -> a in above equation
  # b -> b in above equation
  # base -> base point for curve
  # n -> order of the curve. valid private keys: 1 <= key < n
  attr_accessor :prime, :a, :b, :base, :n

  def initialize(p, ia, ib, bp)
    @prime = p
    @a = ia
    @b = ib
    @base = bp
    @n = order(bp)
  end

  def is_on_curve?(point)
    lside = (point.y ** 2) % @prime
    rside = (point.x ** 3 + @a * point.x + @b) % @prime

    lside == rside
  end

  def points
    return [] if @prime % 4 != 3
    factor = (@prime + 1) / 4
    points = []
    (0...@prime).each do |x|
      ysq = (x**3 + @a*x + @b) % @prime
      y = FiniteMath.factor(ysq, factor, @prime)
      points << Point.new(x, y) if ysq == FiniteMath.factor(y, 2, @prime)
      ny = @prime - y
      points << Point.new(x, ny) if ysq == FiniteMath.factor(ny, 2, @prime)
    end
    points
  end

  def order(point)
    i = 1
    until scalar_mult(i, point).infinity?
      i += 1
      return nil if i > 10000
    end
    return i
  end

  def max_order_point
    max = 0
    maxpoint = nil
    points.each do |pt|
      ord = order(pt)
      if ord > max and Prime.prime?(ord)
        max = ord
        maxpoint = pt
      end
    end
    return {max: max, point: maxpoint}
  end

  def add(p, q)
    return q.clone if p.infinity?
    return p.clone if q.infinity?

    r = Point.new(0, 0)

    lam = FiniteMath.divide(q.y - p.y, q.x - p.x, @prime)
    return r if lam.nil?
    r.x = (lam ** 2 - p.x - q.x) % @prime
    r.y = (lam * (p.x - r.x) - p.y) % @prime

    r
  end

  def double(point)
    r = Point.new(0, 0)

    lam = FiniteMath.divide(3 * point.x ** 2 + @a, 2 * point.y, @prime)
    return r if lam.nil?
    r.x = (lam ** 2 - 2 * point.x) % @prime
    r.y = (lam * (point.x - r.x) - point.y) % @prime

    r
  end

  def scalar_mult(num, point)
    return Point.new(0, 0) if num == 0
    if num % 2 == 1
      return add(point, scalar_mult(num - 1, point))
    else
      return scalar_mult(num / 2, double(point))
    end
  end

  def pub_for_priv(priv)
    scalar_mult(priv, @base)
  end

  def sign(z, priv)
    r, s = 0, 0
    while r == 0 or s == 0
      k = rand(1...@n)
      kpt = scalar_mult(k, @base)
      r = kpt.x % @n
      continue if r == 0
      s = FiniteMath.divide(z + r * priv, k, @n)
    end
    {r: r, s: s}
  end

  def verify(z, sig, pub)
    return false if pub.infinity?
    return false unless is_on_curve?(pub)
    return false unless scalar_mult(@n, pub).infinity?

    return false unless (1...@n).cover?(sig[:r])
    return false unless (1...@n).cover?(sig[:s])

    w = FiniteMath.inverse(sig[:s], @n)
    u1 = (z * w) % @n
    u2 = (sig[:r] * w) % @n
    c = add(scalar_mult(u1, @base), scalar_mult(u2, pub))
    sig[:r] == c.x
  end
end

# curve equation: y^2 = x^3 + ax + b

# We get some easy calculation benefits for finding points/order
# fits prime % 4 = 3, e.g. 19 not 17. If you know the base point/order, this is unnecessary

# ec = ElliptalCurve.new(prime number, a, base point)
# private_key = rand(1...ec.n)
# public_key = ec.pub_for_priv(private_key)

# To find a good base point, you can initially supply a point at (0, 0)
# Then call ec.max_order_point, which will return the highest prime order and associated point
# You can then instantiate a new curve with that base point and use it for calculations