Module: BSV::Primitives::Secp256k1

Defined in:
lib/bsv/primitives/secp256k1.rb

Overview

Pure Ruby secp256k1 elliptic curve implementation.

Provides field arithmetic, point operations with Jacobian coordinates, and windowed-NAF scalar multiplication. Ported from the BSV TypeScript SDK reference implementation.

All field operations work on plain Ruby Integer values (arbitrary precision, C-backed in MRI). No external gems required.

Defined Under Namespace

Classes: Point

Constant Summary collapse

P =

The secp256k1 field prime: p = 2^256 - 2^32 - 977

0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
N =

The curve order (number of points on the curve).

0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
HALF_N =

Half the curve order, used for low-S normalisation (BIP-62).

N >> 1
GX =

Generator point x-coordinate.

0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
GY =

Generator point y-coordinate.

0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
P_PLUS1_DIV4 =

(P + 1) / 4 — used for modular square root since P ≡ 3 (mod 4).

(P + 1) >> 2
MASK_256 =

256-bit mask for fast reduction.

(1 << 256) - 1

Class Method Summary collapse

Class Method Details

.bytes_to_int(bytes) ⇒ Integer

Convert a big-endian binary string to an Integer.

Parameters:

  • bytes (String) —

    binary string (ASCII-8BIT)

Returns:

  • (Integer) 


53
54
55
 
# File 'lib/bsv/primitives/secp256k1.rb', line 53

def bytes_to_int(bytes)
  bytes.unpack1('H*').to_i(16)
end

.fadd(a, b) ⇒ Object

Modular addition in the field.



108
109
110
 
# File 'lib/bsv/primitives/secp256k1.rb', line 108

def fadd(a, b)
  fred(a + b)
end

.finv(a) ⇒ Integer

Modular multiplicative inverse in the field (Fermat’s little theorem).

Parameters:

  • a (Integer) —

    value to invert (must be non-zero mod P)

Returns:

  • (Integer) —

    a^(P-2) mod P

Raises:

  • (ArgumentError) —

    if a is zero mod P



127
128
129
130
131
 
# File 'lib/bsv/primitives/secp256k1.rb', line 127

def finv(a)
  raise ArgumentError, 'field inverse is undefined for zero' if (a % P).zero?

  a.pow(P - 2, P)
end

.fmul(a, b) ⇒ Object

Modular multiplication in the field.



98
99
100
 
# File 'lib/bsv/primitives/secp256k1.rb', line 98

def fmul(a, b)
  fred(a * b)
end

.fneg(a) ⇒ Object

Modular negation in the field.



118
119
120
 
# File 'lib/bsv/primitives/secp256k1.rb', line 118

def fneg(a)
  a.zero? ? 0 : P - a
end

.fred(x) ⇒ Integer

Fast reduction modulo the secp256k1 prime.

Exploits the structure P = 2^256 - 2^32 - 977 to avoid generic modular division. Two folding passes plus a conditional subtraction.

Parameters:

  • x (Integer) —

    non-negative integer

Returns:

  • (Integer) —

    x mod P, in range [0, P)



84
85
86
87
88
89
90
91
92
93
94
95
 
# File 'lib/bsv/primitives/secp256k1.rb', line 84

def fred(x)
  # First fold
  hi = x >> 256
  x = (x & MASK_256) + (hi << 32) + (hi * 977)

  # Second fold (hi <= 2^32 + 977, so one more pass suffices)
  hi = x >> 256
  x = (x & MASK_256) + (hi << 32) + (hi * 977)

  # Final conditional subtraction
  x >= P ? x - P : x
end

.fsqr(a) ⇒ Object

Modular squaring in the field.



103
104
105
 
# File 'lib/bsv/primitives/secp256k1.rb', line 103

def fsqr(a)
  fred(a * a)
end

.fsqrt(a) ⇒ Integer?

Modular square root in the field.

Uses the identity sqrt(a) = a^((P+1)/4) mod P, valid because P ≡ 3 (mod 4). Returns nil if a is not a quadratic residue.

Parameters:

  • a (Integer)

Returns:

  • (Integer, nil) —

    the square root, or nil if none exists



140
141
142
143
 
# File 'lib/bsv/primitives/secp256k1.rb', line 140

def fsqrt(a)
  r = a.pow(P_PLUS1_DIV4, P)
  fsqr(r) == (a % P) ? r : nil
end

.fsub(a, b) ⇒ Object

Modular subtraction in the field.



113
114
115
 
# File 'lib/bsv/primitives/secp256k1.rb', line 113

def fsub(a, b)
  a >= b ? a - b : P - (b - a)
end

.int_to_bytes(n, length = 32) ⇒ String

Convert an Integer to a fixed-length big-endian binary string.

Parameters:

  • n (Integer) —

    the integer to convert

  • length (Integer) (defaults to: 32) —

    desired byte length (default 32)

Returns:

  • (String) —

    binary string (ASCII-8BIT)

Raises:

  • (ArgumentError) 


62
63
64
65
66
67
68
69
70
71
 
# File 'lib/bsv/primitives/secp256k1.rb', line 62

def int_to_bytes(n, length = 32)
  raise ArgumentError, 'negative integer' if n.negative?

  hex = n.to_s(16)
  hex = "0#{hex}" if hex.length.odd?
  raise ArgumentError, "integer too large for #{length} bytes" if hex.length > length * 2

  hex = hex.rjust(length * 2, '0')
  [hex].pack('H*')
end

.jp_add(p, q) ⇒ Array

Add two Jacobian points.

Parameters:

  • p (Array) —

    first Jacobian point

  • q (Array) —

    second Jacobian point

Returns:

  • (Array) —

    resulting Jacobian point



210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
 
# File 'lib/bsv/primitives/secp256k1.rb', line 210

def jp_add(p, q)
  _px, _py, pz = p
  _qx, _qy, qz = q
  return q if pz.zero?
  return p if qz.zero?

  z1z1 = fsqr(pz)
  z2z2 = fsqr(qz)
  u1 = fmul(p[0], z2z2)
  u2 = fmul(q[0], z1z1)
  s1 = fmul(p[1], fmul(z2z2, qz))
  s2 = fmul(q[1], fmul(z1z1, pz))

  h = fsub(u2, u1)
  r = fsub(s2, s1)

  if h.zero?
    return r.zero? ? jp_double(p) : JP_INFINITY
  end

  hh = fsqr(h)
  hhh = fmul(h, hh)
  v = fmul(u1, hh)

  x3 = fsub(fsub(fsqr(r), hhh), fmul(2, v))
  y3 = fsub(fmul(r, fsub(v, x3)), fmul(s1, hhh))
  z3 = fmul(h, fmul(pz, qz))
  [x3, y3, z3]
end

.jp_double(p) ⇒ Array(Integer, Integer, Integer)

Double a Jacobian point.

Formula from hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html (a=0 for secp256k1).

Parameters:

  • p (Array(Integer, Integer, Integer)) —

    Jacobian point [X, Y, Z]

Returns:

  • (Array(Integer, Integer, Integer)) 


192
193
194
195
196
197
198
199
200
201
202
203
 
# File 'lib/bsv/primitives/secp256k1.rb', line 192

def jp_double(p)
  x1, y1, z1 = p
  return JP_INFINITY if y1.zero?

  y1sq = fsqr(y1)
  s = fmul(4, fmul(x1, y1sq))
  m = fmul(3, fsqr(x1)) # a=0 for secp256k1
  x3 = fsub(fsqr(m), fmul(2, s))
  y3 = fsub(fmul(m, fsub(s, x3)), fmul(8, fsqr(y1sq)))
  z3 = fmul(2, fmul(y1, z1))
  [x3, y3, z3]
end

.jp_neg(p) ⇒ Object

Negate a Jacobian point.



388
389
390
391
392
 
# File 'lib/bsv/primitives/secp256k1.rb', line 388

def jp_neg(p)
  return p if p[2].zero?

  [p[0], fneg(p[1]), p[2]]
end

.jp_to_affine(jp) ⇒ Array(Integer, Integer)

Convert a Jacobian point to affine coordinates.

Parameters:

  • jp (Array(Integer, Integer, Integer))

Returns:

  • (Array(Integer, Integer)) —

    affine [x, y], or nil for infinity



244
245
246
247
248
249
250
251
252
253
 
# File 'lib/bsv/primitives/secp256k1.rb', line 244

def jp_to_affine(jp)
  _x, _y, z = jp
  return nil if z.zero?

  zinv = finv(z)
  zinv2 = fsqr(zinv)
  x = fmul(jp[0], zinv2)
  y = fmul(jp[1], fmul(zinv2, zinv))
  [x, y]
end

.scalar_add(a, b) ⇒ Object

Scalar addition mod N.



171
172
173
 
# File 'lib/bsv/primitives/secp256k1.rb', line 171

def scalar_add(a, b)
  (a + b) % N
end

.scalar_inv(a) ⇒ Object

Scalar multiplicative inverse (Fermat).

Raises:

  • (ArgumentError) —

    if a is zero mod N



159
160
161
162
163
 
# File 'lib/bsv/primitives/secp256k1.rb', line 159

def scalar_inv(a)
  raise ArgumentError, 'scalar inverse is undefined for zero' if (a % N).zero?

  a.pow(N - 2, N)
end

.scalar_mod(a) ⇒ Object

Reduce modulo the curve order.



150
151
152
153
154
 
# File 'lib/bsv/primitives/secp256k1.rb', line 150

def scalar_mod(a)
  r = a % N
  r += N if r.negative?
  r
end

.scalar_mul(a, b) ⇒ Object

Scalar multiplication mod N.



166
167
168
 
# File 'lib/bsv/primitives/secp256k1.rb', line 166

def scalar_mul(a, b)
  (a * b) % N
end