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