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
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
# File lib/tss/util.rb, line 241 def self.bytes_to_hex(bytes) hex = '' bytes.each { |b| hex += sprintf('%02x', b) } hex.downcase end
# File lib/tss/util.rb, line 232 def self.bytes_to_utf8(bytes) bytes.pack('C*').force_encoding('utf-8') end
# File lib/tss/util.rb, line 372 def self.calc_combinations(n, r) factorial(n) / (factorial(r) * factorial(n - r)) end
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
# File lib/tss/util.rb, line 354 def self.factorial(n) (1..n).reduce(:*) || 1 end
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
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
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
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
# File lib/tss/util.rb, line 252 def self.hex_to_bytes(str) [str].pack('H*').unpack('C*') end
# File lib/tss/util.rb, line 261 def self.hex_to_utf8(hex) bytes_to_utf8(hex_to_bytes(hex)) end
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
# 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
# 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
# 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
# File lib/tss/util.rb, line 223 def self.utf8_to_bytes(str) str.bytes.to_a end
# File lib/tss/util.rb, line 270 def self.utf8_to_hex(str) bytes_to_hex(utf8_to_bytes(str)) end