elliptic_curve.rb

elliptic_curve.rb

class Point
	def initialize(x, y)
		@x = x
		@y = y
	end
	
	def to_s
		"(#{@x}, #{@y})"
	end
	
	def x
		@x
	end
	
	def x=(x)
		@x = x
	end
	
	def y
		@y
	end
	
	def y=(y)
		@y = y
	end
	
	def==(point)
		@x == point.x && @y == point.y
	end
end

class EllipticGroup
	def initialize(prime, origin)
		@prime = prime
		@origin = origin
	end
	
	def add(point1, point2 = nil)
		print "#{point1} + #{point2}\n"
		if point2.nil? || point1 == point2
			add_same_point(point1)
		else
			add_different_points(point1, point2)
		end
	end
	
	def multiply(scalar, point)
		print "#{scalar} * #{point}\n"
		raise StandardError if scalar < 1
		if scalar % 2 == 0
			value = multiply(scalar / 2, point)
			add(value, value)
		elsif scalar == 1
			point
		else
			add(point, multiply(scalar - 1, point))
		end
	end
	
private
	def add_different_points(point1, point2)
		gradient = modulo_divide(point2.y - point1.y, point2.x - point1.x)
		print "Gradient = #{gradient}\n"
		x = (gradient * gradient - point1.x - point2.x) % @prime
		print "X = #{x}\n"
		y = (gradient * (point1.x - x) - point1.y) % @prime
		print "Y = #{y}\n"
		
		Point.new(x, y)
	end
	
	def add_same_point(point)
		if point.y == 0 then
			@origin
		else
			gradient = modulo_divide(3 * point.x * point.x + @origin.x, 2 * point.y)
			#print "Gradient = #{gradient}\n"
			x = (gradient * gradient - 2 * point.x) % @prime
			#print "X = #{x}\n"
			y = (gradient * (point.x - x) - point.y) % @prime
			#print "Y = #{y}\n"
		
			Point.new(x, y)
		end
	end
	
	def modulo_divide(a, b)
		if a < 0 && b < 0
			a = -a
			b = -b
		end
		
		print "#{a} <=> #{b}\n"
		print "#{(a * modulo_rational(1, b))}\n"
		delta = (a * modulo_rational(1, b)) % @prime
		#print "Divide #{a} over #{b} mod #{@prime} = #{delta}\n"
		delta
	end
	
	def modulo_rational(num, denom)
		raise StandardError if num != 1
		# x * prime + y * denom = num
		prime, result = extended_gcd(@prime, denom)
		
		residue = (result * denom + prime * @prime) % @prime
		if residue == @prime - 1
			print "#{prime} <=> #{result}\n"
			result = -result
			residue = (result * denom + prime * @prime) % @prime
		end
		raise StandardError if residue != 1
		
		#print "Rational of #{Rational(num, denom)} = #{result} mod #{@prime}\n"
		result
	end

	# From https://gist.github.com/gpfeiffer/4013925
	def extended_gcd(a, b)
		# trivial case first: gcd(a, 0) == 1*a + 0*0
		return 1, 0 if b == 0

		# recurse: a = q*b + r
		q, r = a.divmod b
		s, t = extended_gcd(b, r)

		# compute and return coefficients:
		# gcd(a, b) == gcd(b, r) == s*b + t*r == s*b + t*(a - q*b)
		return t, s - q * t
	end
end

class EllipticCurve
	def initialize(group, point, order)
		@group = group
		@point = point
		@order = order
	end
end

test_group = EllipticGroup.new(23, Point.new(1, 1))
print test_group.add(Point.new(4, 0), Point.new(7, 11))
print "\n"
print test_group.add(Point.new(3, 10), Point.new(9, 7))
print "\n"
print test_group.add(Point.new(7, 11))
print "\n"
print test_group.add(Point.new(9, 7))
print "\n"


test_group2 = EllipticGroup.new(31, Point.new(1, 1))
print test_group2.add(Point.new(4, 10), Point.new(7, 17))
print "\n"
print test_group2.multiply(3, Point.new(28, 8))
print "\n"
print test_group2.add(Point.new(28, 8), Point.new(28, 8))
print "\n"
print test_group2.add(Point.new(28, 8), Point.new(11, 14))
print "\n"

print test_group2.multiply(6, Point.new(0, 1))