module TSS::Util

Common utility, math, and conversion functions.

Constants

C
EXP

The EXP table. The elements are to be read from top to bottom and left to right. For example, EXP is 0x01, EXP is 0x1a, and so on. Note that the EXP entry is present only as a placeholder, and is not actually used in any computation.

HUMAN_SHARE_RE

The regex to match against human style shares

LOG

The LOG table. The elements are to be read from top to bottom and left to right. For example, LOG is 0, LOG is 75, and so on. Note that the LOG entry is present only as a placeholder, and is not actually used in any computation.

Public Class Methods

basis_poly(i, u) click to toggle source

Secret Reconstruction Function

We define the function L_i (for i from 0 to M-1, inclusive) that takes as input an array U of M pairwise distinct octets, and is defined as

                          U[j]
L_i(U) = GF_PRODUCT   -------------
         j=0,M-1, j!=i  U[j] (+) U[i]

Here the product runs over all of the values of j from 0 to M-1, excluding the value i. (This function is equal to ith Lagrange function, evaluated at zero.) Note that the denominator in the above expression is never equal to zero because U is not equal to U whenever i is not equal to j.

@param i [Integer] a single Integer @param u [Array<Integer>] an Array of Integers @return [Integer] a single Integer

# File lib/tss/util.rb, line 185
def self.basis_poly(i, u)
  prod = 1

  (0..(u.length - 1)).each do |j|
    next if i == j
    prod = gf256_mul(prod, gf256_div(u[j], gf256_add(u[j], u[i])))
  end

  prod
end
bytes_to_hex(bytes) click to toggle source
# File lib/tss/util.rb, line 241
def self.bytes_to_hex(bytes)
  hex = ''
  bytes.each { |b| hex += sprintf('%02x', b) }
  hex.downcase
end
bytes_to_utf8(bytes) click to toggle source
# File lib/tss/util.rb, line 232
def self.bytes_to_utf8(bytes)
  bytes.pack('C*').force_encoding('utf-8')
end
calc_combinations(n, r) click to toggle source
# File lib/tss/util.rb, line 372
def self.calc_combinations(n, r)
  factorial(n) / (factorial(r) * factorial(n - r))
end
extract_share_header(share) click to toggle source
# File lib/tss/util.rb, line 343
def self.extract_share_header(share)
  h = Splitter::SHARE_HEADER_STRUCT.decode(share)
  h[:identifier] = h[:identifier].delete("\x00")
  return h
end
f(x, bytes) click to toggle source

Share generation Function

The function f takes as input a single octet X that is not equal to 0x00, and an array A of M octets, and returns a single octet. It is defined as:

f(X, A) =  GF_SUM A[i] (*) X^i
           i=0,M-1

Because the GF_SUM summation takes place over GF(256), each addition uses the exclusive-or operation, and not integer addition. Note that the successive values of X^i used in the computation of the function f can be computed by multiplying a value by X once for each term in the summation.

@param x [Integer] a single Integer @param bytes [Array<Integer>] an Array of Integers @return [Integer] a single Integer @raise [TSS::Error] if the index value for the share is zero

# File lib/tss/util.rb, line 153
def self.f(x, bytes)
  raise TSS::Error, 'invalid share index value, cannot be 0' if x == 0
  y = 0
  x_i = 1

  bytes.each do |b|
    y = gf256_add(y, gf256_mul(b, x_i))
    x_i = gf256_mul(x_i, x)
  end

  y
end
factorial(n) click to toggle source
# File lib/tss/util.rb, line 354
def self.factorial(n)
  (1..n).reduce(:*) || 1
end
gf256_add(a, b) click to toggle source

GF(256) Addition The addition operation returns the Bitwise Exclusive OR (XOR) of its operands.

@param a [Integer] a single Integer @param b [Integer] a single Integer @return [Integer] a GF(256) SUM of a and b

# File lib/tss/util.rb, line 91
def self.gf256_add(a, b)
  a ^ b
end
gf256_div(x, y) click to toggle source

The division operation takes a dividend X and a divisor Y as input and computes X divided by Y as follows. If X is equal to 0x00, then the operation returns 0x00. If Y is equal to 0x00, then the input is invalid, and an error condition occurs. Otherwise, the value EXP[(LOG - LOG) modulo 255] is returned.

@param x [Integer] a single Integer @param y [Integer] a single Integer @return [Integer] a GF(256) division of x divided by y @raise [TSS::Error] if an attempt to divide by zero is tried

# File lib/tss/util.rb, line 128
def self.gf256_div(x, y)
  return 0 if x == 0
  raise TSS::Error, 'divide by zero' if y == 0
  EXP[(LOG[x] - LOG[y]) % 255]
end
gf256_mul(x, y) click to toggle source

The multiplication operation takes two elements X and Y as input and proceeds as follows. If either X or Y is equal to 0x00, then the operation returns 0x00. Otherwise, the value EXP[ (LOG + LOG) modulo 255] is returned.

@param x [Integer] a single Integer @param y [Integer] a single Integer @return [Integer] a GF(256) multiplication of x and y

# File lib/tss/util.rb, line 113
def self.gf256_mul(x, y)
  return 0 if x == 0 || y == 0
  EXP[(LOG[x] + LOG[y]) % 255]
end
gf256_sub(a, b) click to toggle source

The subtraction operation is identical to GF(256) addition, because the field has characteristic two.

@param a [Integer] a single Integer @param b [Integer] a single Integer @return [Integer] a GF(256) subtraction of a and b

# File lib/tss/util.rb, line 101
def self.gf256_sub(a, b)
  gf256_add(a, b)
end
hex_to_bytes(str) click to toggle source
# File lib/tss/util.rb, line 252
def self.hex_to_bytes(str)
  [str].pack('H*').unpack('C*')
end
hex_to_utf8(hex) click to toggle source
# File lib/tss/util.rb, line 261
def self.hex_to_utf8(hex)
  bytes_to_utf8(hex_to_bytes(hex))
end
lagrange_interpolation(u, v) click to toggle source

Secret Reconstruction Function

We denote the interpolation function as I. This function takes as input two arrays U and V, each consisting of M octets, and returns a single octet; it is defined as:

I(U, V) =  GF_SUM  L_i(U) (*) V[i].
           i=0,M-1

@param u [Array<Integer>] an Array of Integers @param v [Array<Integer>] an Array of Integers @return [Integer] a single Integer

# File lib/tss/util.rb, line 208
def self.lagrange_interpolation(u, v)
  sum = 0

  (0..(v.length - 1)).each do |i|
    sum = gf256_add(sum, gf256_mul(basis_poly(i, u), v[i]))
  end

  sum
end
pad(str, k = TSS::PADDING_BLOCK_SIZE_BYTES) click to toggle source
# File lib/tss/util.rb, line 281
def self.pad(str, k = TSS::PADDING_BLOCK_SIZE_BYTES)
  return str if k.zero?
  str_bytes = str.is_a?(Array) ? str : TSS::Util.utf8_to_bytes(str)
  l = str_bytes.length
  val = k - (l % k)
  pad_bytes = [val] * val
  padded_str_bytes = str_bytes + pad_bytes
  str.is_a?(Array) ? padded_str_bytes : TSS::Util.bytes_to_utf8(padded_str_bytes)
end
secure_compare(a, b) click to toggle source
# File lib/tss/util.rb, line 326
def self.secure_compare(a, b)
  return false unless a.bytesize == b.bytesize
  ah = Digest::SHA256.hexdigest(a)
  bh = Digest::SHA256.hexdigest(b)

  l = ah.unpack('C*')
  r, i = 0, -1
  bh.each_byte { |v| r |= v ^ l[i+=1] }
  r == 0
end
unpad(str, k = TSS::PADDING_BLOCK_SIZE_BYTES) click to toggle source
# File lib/tss/util.rb, line 297
def self.unpad(str, k = TSS::PADDING_BLOCK_SIZE_BYTES)
  return str if k.zero?
  str_bytes = str.is_a?(Array) ? str : TSS::Util.utf8_to_bytes(str)
  val = str_bytes.last
  raise 'Input is not padded or padding is corrupt' if val > k
  # Verify that the proper number of PKCS#7 padding bytes are present
  # and match the last byte value in both value and number of bytes present.
  raise 'Padding bytes are invalid' unless str_bytes.last(val).all? {|b| b == val}
  l = str_bytes.length - val
  unpadded_str_bytes = str_bytes.take(l)
  str.is_a?(Array) ? unpadded_str_bytes : TSS::Util.bytes_to_utf8(unpadded_str_bytes)
end
utf8_to_bytes(str) click to toggle source
# File lib/tss/util.rb, line 223
def self.utf8_to_bytes(str)
  str.bytes.to_a
end
utf8_to_hex(str) click to toggle source
# File lib/tss/util.rb, line 270
def self.utf8_to_hex(str)
  bytes_to_hex(utf8_to_bytes(str))
end