Module: Runar::ECPrimitives

Included in:
ECDSA
Defined in:
lib/runar/ec_primitives.rb

Constant Summary collapse

SECP256K1_P =

secp256k1 curve parameters.

0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
SECP256K1_N = 
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
SECP256K1_GX = 
0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
SECP256K1_GY = 
0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

Class Method Summary collapse

Class Method Details

.extended_gcd(a, b) ⇒ Array(Integer, Integer, Integer)

Extended Euclidean algorithm.

Returns [gcd, x, y] such that a*x b*y = gcd+.

Parameters:

  • a (Integer)
  • b (Integer)

Returns:

  • (Array(Integer, Integer, Integer)) 


31
32
33
34
35
36
 
# File 'lib/runar/ec_primitives.rb', line 31

def extended_gcd(a, b)
  return [b, 0, 1] if a.zero?

  g, x, y = extended_gcd(b % a, a)
  [g, y - (b / a) * x, x]
end

.mod_inv(a, m) ⇒ Integer

Modular multiplicative inverse.

Returns x such that a * x ≡ 1 (mod m). Handles negative a by reducing modulo m first.

Parameters:

  • a (Integer) —

    value to invert

  • m (Integer) —

    modulus

Returns:

  • (Integer)

Raises:

  • (ArgumentError) —

    if the inverse does not exist



47
48
49
50
51
52
53
 
# File 'lib/runar/ec_primitives.rb', line 47

def mod_inv(a, m)
  a %= m if a.negative?
  g, x, = extended_gcd(a, m)
  raise ArgumentError, 'no modular inverse' unless g == 1

  x % m
end

.point_add(p1, p2) ⇒ Array(Integer, Integer)?

secp256k1 point addition.

nil represents the point at infinity (additive identity).

rubocop:disable Metrics/AbcSize, Metrics/MethodLength, Naming/MethodParameterName

Parameters:

  • p1 (Array(Integer, Integer), nil)
  • p2 (Array(Integer, Integer), nil)

Returns:

  • (Array(Integer, Integer), nil) 


65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
 
# File 'lib/runar/ec_primitives.rb', line 65

def point_add(p1, p2)
  return p2 if p1.nil?
  return p1 if p2.nil?

  x1, y1 = p1
  x2, y2 = p2

  if x1 == x2
    return nil if y1 != y2 # p1 == -p2 → point at infinity

    lam = 3 * x1 * x1 * mod_inv(2 * y1, SECP256K1_P) % SECP256K1_P
  else
    lam = (y2 - y1) * mod_inv(x2 - x1, SECP256K1_P) % SECP256K1_P
  end

  x3 = (lam * lam - x1 - x2) % SECP256K1_P
  y3 = (lam * (x1 - x3) - y1) % SECP256K1_P
  [x3, y3]
end

.point_mul(k, point) ⇒ Array(Integer, Integer)?

secp256k1 scalar multiplication (double-and-add).

Returns k * point, or nil (point at infinity) when k is zero.

WARNING: This implementation uses a simple double-and-add algorithm that is NOT constant-time. Execution time leaks information about the scalar via branch timing on each bit. This is acceptable for test/verification use (e.g., ECDSA verify, OP_PUSH_TX with k=1) but MUST NOT be used with real private keys in a networked/production context. For production signing, use a constant-time implementation (e.g., Montgomery ladder).

rubocop:disable Naming/MethodParameterName

Parameters:

  • k (Integer) —

    scalar

  • point (Array(Integer, Integer), nil) —

    base point

Returns:

  • (Array(Integer, Integer), nil) 


101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/runar/ec_primitives.rb', line 101

def point_mul(k, point)
  result = nil
  addend = point

  while k.positive?
    result = point_add(result, addend) if k.odd?
    addend = point_add(addend, addend)
    k >>= 1
  end

  result
end