Class: BLS::ProjectivePoint

Inherits:
Object
  • Object
show all
Defined in:
lib/bls/point.rb

Overview

Abstract Point class that consist of projective coordinates.

Direct Known Subclasses

PointG1, PointG2

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(x, y, z) ⇒ ProjectivePoint

Returns a new instance of ProjectivePoint.



22
23
24
25
26
27
 
# File 'lib/bls/point.rb', line 22

def initialize(x, y, z)
  @x = x
  @y = y
  @z = z
  @m_precomputes = nil
end

Instance Attribute Details

#m_precomputes ⇒ Object

Returns the value of attribute m_precomputes.



20
21
22
 
# File 'lib/bls/point.rb', line 20

def m_precomputes
  @m_precomputes
end

#x ⇒ Object (readonly)

Returns the value of attribute x.



19
20
21
 
# File 'lib/bls/point.rb', line 19

def x
  @x
end

#y ⇒ Object (readonly)

Returns the value of attribute y.



19
20
21
 
# File 'lib/bls/point.rb', line 19

def y
  @y
end

#z ⇒ Object (readonly)

Returns the value of attribute z.



19
20
21
 
# File 'lib/bls/point.rb', line 19

def z
  @z
end

Class Method Details

.dst(scheme) ⇒ String

Domain separation tag this point class uses for scheme. are signed under, kept separate from :pop so a proof cannot pass as a signature).

Parameters:

  • scheme (Symbol) —

    :basic, :pop, or :pop_proof(the tag proofs of possession

Returns:

  • (String) —

    domain separation tag.

Raises:

  • (BLS::Error) —

    Occur when the scheme is unknown.



34
35
36
37
38
39
40
41
 
# File 'lib/bls/point.rb', line 34

def self.dst(scheme)
  case scheme
  when :basic then const_get(:DST_BASIC)
  when :pop then const_get(:DST_POP)
  when :pop_proof then const_get(:DST_POP_PROOF)
  else raise BLS::Error, "Unknown scheme: #{scheme.inspect}. Must be :basic or :pop."
  end
end

.validate_hex!(hex) ⇒ Object

Check that hex is a whole number of bytes written in hex, for from_hex and hash_to_curve, which both unpack their argument with pack('H*').

pack maps a character to a nibble by its low bits, so it reads '3', '#', 'J', 'Z', 'j' and 'z' all as 3 and never complains, and it pads an odd number of digits out to a whole byte. Left alone, that gives every point and every message a large family of spellings that all arrive at the same bytes. Applications tend to carry keys around as hex and compare, deduplicate and index them that way, so the aliases matter as much here as the non-canonical encodings do a layer down.

\A..\z rather than ^..$ because those match at line boundaries in Ruby, which would let a newline carry a non-hex tail past the check.

Parameters:

  • hex (String) —

    a byte string in hex format.

Raises:

  • (PointError) —

    Occur when it is not an even length string of hex digits.



57
58
59
60
61
 
# File 'lib/bls/point.rb', line 57

def self.validate_hex!(hex)
  return if hex.is_a?(String) && hex.match?(/\A(?:[0-9a-fA-F]{2})*\z/)

  raise PointError, 'expected hex string'
end

Instance Method Details

#==(other) ⇒ Boolean

Compare one point to another.

Parameters:

Returns:

  • (Boolean) —

    whether same point or not.

Raises:



79
80
81
82
83
 
# File 'lib/bls/point.rb', line 79

def ==(other)
  raise PointError, "ProjectivePoint#==: this is #{self.class}, but other is #{other.class}" unless self.class == other.class

  (x * other.z) == (other.x * z) && (y * other.z) == (other.y * z)
end

#add(other) ⇒ Object Also known as: +

http://hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#addition-add-1998-cmo-2

Raises:



104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 
# File 'lib/bls/point.rb', line 104

def add(other)
  raise PointError, "ProjectivePoint#add: this is #{self.class}, but other is #{other.class}" unless self.class == other.class

  return other if zero?
  return self if other.zero?

  x1 = self.x
  y1 = self.y
  z1 = self.z
  x2 = other.x
  y2 = other.y
  z2 = other.z
  u1 = y2 * z1
  u2 = y1 * z2
  v1 = x2 * z1
  v2 = x1 * z2
  return double if v1 == v2 && u1 == u2
  return zero if v1 == v2

  u = u1 - u2
  v = v1 - v2
  vv = v * v
  vvv = vv * v
  v2vv = v2 * vv
  w = z1 * z2
  a = u * u * w - vvv - v2vv * 2
  x3 = v * a
  y3 = u * (v2vv - a) - vvv * u2
  z3 = vvv * w
  new_point(x3, y3, z3)
end

#calc_multiply_precomputes(w) ⇒ Object

Build the window table that #multiply then uses, trading memory for speed on a point that will be multiplied repeatedly, such as a generator.

Call this once, before the point is shared between threads. The check below is not a lock: the table takes long enough to build that MRI will switch threads part way through, so several callers can pass the check together and each build their own, each paying the time and the memory. What they build is identical, so whichever assignment lands last is still correct and no half-built table is ever visible; the cost is the duplicated work, and a guard that reads as protection while providing none.

Parameters:

  • w (Integer) —

    window width.

Raises:

  • (PointError) —

    Occur when this point already has precomputes.



273
274
275
276
277
 
# File 'lib/bls/point.rb', line 273

def calc_multiply_precomputes(w)
  raise PointError, 'This point already has precomputes.' if m_precomputes

  self.m_precomputes = [w, normalize_z(precomputes_window(w))]
end

#clear_multiply_precomputes ⇒ Object 



279
280
281
 
# File 'lib/bls/point.rb', line 279

def clear_multiply_precomputes
  self.m_precomputes = nil
end

#double ⇒ Object

http://hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#doubling-dbl-1998-cmo-2



90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/bls/point.rb', line 90

def double
  w = x * x * 3
  s = y * z
  ss = s * s
  sss = ss * s
  b = x * y * s
  h = w * w - ( b * 8)
  x3 = h * s * 2
  y3 = w * (b * 4 - h) - (y * y * 8 * ss) # W * (4 * B - H) - 8 * y * y * S_squared
  z3 = sss * 8
  new_point(x3, y3, z3)
end

#from_affine_tuple(xy) ⇒ Object 



190
191
192
 
# File 'lib/bls/point.rb', line 190

def from_affine_tuple(xy)
  new_point(xy[0], xy[1], x.class.const_get(:ONE))
end

#gen_invert_batch(nums) ⇒ Object

Inverts a whole array for the price of one inversion plus a few multiplications each. Zero is refused rather than skipped: leaving it in place would hand the caller a zero where it asked for an inverse, and Field#invert refuses it for the same reason.

Raises:

  • (BLS::Error) —

    Occur when any element is zero.



198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
 
# File 'lib/bls/point.rb', line 198

def gen_invert_batch(nums)
  raise BLS::Error, 'Zero has no multiplicative inverse.' if nums.any?(&:zero?)

  len = nums.length
  scratch = Array.new(len)
  acc = x.class::ONE
  len.times do |i|
    scratch[i] = acc
    acc *= nums[i]
  end
  acc = acc.invert
  len.times do |t|
    i = len - t - 1
    tmp = acc * nums[i]
    nums[i] = acc * scratch[i]
    acc = tmp
  end
  nums
end

#in_group? ⇒ Boolean

Check whether this point belongs to the prime-order subgroup (G1 or G2). Being on the curve is not sufficient: E(Fp) and E'(Fp2) both contain points outside the order-r subgroup, and accepting them makes keys and signatures malleable. Since r**2 does not divide the group order, [r]P == O holds only for P in the subgroup.

Returns:

  • (Boolean) —

    true if this point is in the prime-order subgroup.



167
168
169
 
# File 'lib/bls/point.rb', line 167

def in_group?
  zero? || multiply_unsafe(Curve::R).zero?
end

#max_bits ⇒ Object 



253
254
255
 
# File 'lib/bls/point.rb', line 253

def max_bits
  self.class.const_get(:MAX_BITS)
end

#multiply(scalar) ⇒ Object Also known as: *

Scalar multiplication using wNAF.

This is NOT constant time, despite what #multiply_unsafe implies by contrast. wNAF gives every window an addition, but the point it adds is read at an index derived from the scalar, and the additions themselves branch on whether an operand is the identity or the two are equal. Underneath, Ruby's bignum arithmetic and the modulo in Fp both run in time that depends on their operands. Anything the scalar decides is therefore visible to something watching timing or cache behaviour, which matters here because #sign and .from_private_key reach this with the private key. See the README.

Raises:



227
228
229
230
231
232
233
 
# File 'lib/bls/point.rb', line 227

def multiply(scalar)
  n = scalar.is_a?(Field) ? scalar.value : scalar
  raise PointError, 'Invalid scalar, expected positive integer' if n <= 0
  raise PointError, "Scalar has more bits than maxBits, shouldn't happen" if n.bit_length > max_bits

  wNAF(n).first
end

#multiply_unsafe(scalar) ⇒ Object

Scalar multiplication by plain double-and-add, which skips the addition entirely on a zero bit and so takes a number of operations that tracks the scalar's Hamming weight. Only for scalars an observer already knows, such as the curve parameters. #multiply hides that particular pattern, but is not constant time either.

Raises:



148
149
150
151
152
153
154
155
156
157
158
159
160
 
# File 'lib/bls/point.rb', line 148

def multiply_unsafe(scalar)
  n = scalar.is_a?(Field) ? scalar.value : scalar
  raise PointError, 'Point#multiply: invalid scalar, expected positive integer' if n <= 0

  p = zero
  d = self
  while n.positive?
    p += d unless (n & 1).zero?
    d = d.double
    n >>= 1
  end
  p
end

#negate ⇒ Object 



85
86
87
 
# File 'lib/bls/point.rb', line 85

def negate
  new_point(x, y.negate, z)
end

#new_point(x, y, z) ⇒ Object 



72
73
74
 
# File 'lib/bls/point.rb', line 72

def new_point(x, y, z)
  self.class.new(x, y, z)
end

#normalize_z(points) ⇒ Object 



257
258
259
 
# File 'lib/bls/point.rb', line 257

def normalize_z(points)
  to_affine_batch(points).map{ |p| from_affine_tuple(p) }
end

#precomputes_window(w) ⇒ Object 



236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
 
# File 'lib/bls/point.rb', line 236

def precomputes_window(w)
  windows = (BigDecimal(max_bits) / w).ceil
  window_size = 2**(w - 1)
  points = []
  p = self
  windows.times do
    base = p
    points << base
    (1...window_size).each do
      base += p
      points << base
    end
    p = base.double
  end
  points
end

#subtract(other) ⇒ Object Also known as: -

Raises:



137
138
139
140
141
 
# File 'lib/bls/point.rb', line 137

def subtract(other)
  raise PointError, "ProjectivePoint#subtract: this is #{self.class}, but other is #{other.class}" unless self.class == other.class

  add(other.negate)
end

#to_affine(inv_z = z.invert) ⇒ Object 



177
178
179
 
# File 'lib/bls/point.rb', line 177

def to_affine(inv_z = z.invert)
  [x * inv_z, y * inv_z]
end

#to_affine_batch(points) ⇒ Object

affine representation.

Raises:

  • (PointError) —

    Occur when any of points is the point at infinity, which has no



183
184
185
186
187
188
 
# File 'lib/bls/point.rb', line 183

def to_affine_batch(points)
  raise PointError, 'The point at infinity has no affine representation.' if points.any?(&:zero?)

  to_inv = gen_invert_batch(points.map(&:z))
  points.map.with_index { |p, i| p.to_affine(to_inv[i]) }
end

#validate_group! ⇒ Object

Validate that this point belongs to the prime-order subgroup.

Raises:

  • (PointError) —

    Occur when this point is not in the prime-order subgroup.



173
174
175
 
# File 'lib/bls/point.rb', line 173

def validate_group!
  raise PointError, 'Invalid point: not in prime-order subgroup' unless in_group?
end

#zero ⇒ Object 



67
68
69
70
 
# File 'lib/bls/point.rb', line 67

def zero
  one = x.class.const_get(:ONE)
  new_point(one, one, x.class.const_get(:ZERO))
end

#zero? ⇒ Boolean

Returns:

  • (Boolean) 


63
64
65
 
# File 'lib/bls/point.rb', line 63

def zero?
  z.zero?
end