Module: RSA::ACC::Functions

Included in:
MembershipProof, PoE, PoE, PoKE2, PoKE2, RSA::Accumulator
Defined in:
lib/rsa/acc/functions.rb

Constant Summary collapse

ELEMENT_DST =

Domain separation tags. Elements, Fiat-Shamir challenges and plain hashes are hashed with a distinct tag each, so that a caller supplied element can never be made to produce the same digest as a challenge over group elements.

'RSA-ACC/v1/element'.freeze
CHALLENGE_DST = 
'RSA-ACC/v1/challenge'.freeze
HASH_DST = 
'RSA-ACC/v1/hash'.freeze

Instance Method Summary collapse

Instance Method Details

#blake2_hash(*params) ⇒ Integer

Computes hash value from params.

Parameters:

  • params (Array[Integer])

Returns:

  • (Integer) —

    hash value.



97
98
99
100
 
# File 'lib/rsa/acc/functions.rb', line 97

def blake2_hash(*params)
  digest = RbNaCl::Hash.blake2b(encode_fields(HASH_DST, params.map { |p| even_hex(p) }))
  digest.unpack("H*").first.to_i(16)
end

#compute_challenge(*params) ⇒ Integer

Computes a challenge from params.

Parameters:

  • params (Array[Integer])

Returns:

  • (Integer) —

    prime number of challenge.



90
91
92
 
# File 'lib/rsa/acc/functions.rb', line 90

def compute_challenge(*params)
  prime_from(CHALLENGE_DST, params.map { |p| even_hex(p) })
end

#egcd(x, y) ⇒ Array[Integer, Integer]

Computes Bezout coefficients. see: https://github.com/dryruby/rsa.rb/blob/b1366970d31dba0078fd06d9f5d3ddd4952fb087/lib/rsa/math.rb#L143

Parameters:

  • x (Integer)
  • y (Integer)

Returns:

  • (Array[Integer, Integer]) —

    Bezout coefficients



81
82
83
84
85
 
# File 'lib/rsa/acc/functions.rb', line 81

def egcd(x, y)
  return [0, 1] if x.modulo(y).zero?
  a, b = egcd(y, x.modulo(y))
  [b, a - b * x.div(y)]
end

#elements_to_prime(elements) ⇒ Integer

Converts a list of elements to an product of prime numbers.

Parameters:

  • elements (Array[String]) —

    a list of element.

Returns:

  • (Integer) —

    an product of prime numbers

Raises:

  • (ArgumentError) —

    If elements is not a non-empty list of String.



44
45
46
47
 
# File 'lib/rsa/acc/functions.rb', line 44

def elements_to_prime(elements)
  raise ArgumentError, 'elements must be a non-empty Array of String.' unless valid_elements?(elements)
  elements.map{|e|hash_to_prime(e)}.inject(:*)
end

#hash_to_prime(element) ⇒ Integer

Convert element to prime number.

Parameters:

  • element (String) —

    an element to be converted.

Returns:

  • (Integer) —

    prime number.

Raises:

  • (TypeError) 


33
34
35
36
37
38
 
# File 'lib/rsa/acc/functions.rb', line 33

def hash_to_prime(element)
  # Not String#to_s: that would map nil and other objects onto the prime of their
  # string form, so nil and "" would become the same element.
  raise TypeError, "element must be a String, got #{element.class}." unless element.is_a?(String)
  prime_from(ELEMENT_DST, [element])
end

#normalize(elem, modulus) ⇒ Integer

Computes the canonical representative of elem in the quotient group Z_n^* / +-1. Z_n^* always contains the known order-2 element -1, and the Adaptive Root Assumption which NI-PoE and NI-PoKE2 rely on does not hold in a group with a known low order element. Identifying y with -y removes it, so every group element MUST be normalized before it is hashed into a challenge, compared, or published as part of a proof.

Parameters:

  • elem (Integer) —

    an element of Z_n^*.

  • modulus (Integer) —

    modulus of the group.

Returns:

  • (Integer) —

    the smaller of elem and -+elem+ modulo modulus.



24
25
26
27
28
 
# File 'lib/rsa/acc/functions.rb', line 24

def normalize(elem, modulus)
  y = elem % modulus
  neg = modulus - y
  y < neg ? y : neg
end

#shamir_trick(w1, w2, x, y, modulus) ⇒ Integer

Computes (xy) th root of g given xth and yth roots of g. x and y is co-prime. (a, b) ← Bezout(x, y)

Parameters:

  • w1 (Integer) —

    first witness.

  • w2 (Integer) —

    second witness.

  • x (Integer)
  • y (Integer)

Returns:

  • (Integer) —

    w1^b * w2^a

Raises:

  • (ArgumentError) 


65
66
67
68
69
70
71
72
73
74
 
# File 'lib/rsa/acc/functions.rb', line 65

def shamir_trick(w1, w2, x, y, modulus)
  w1 = normalize(w1, modulus)
  w2 = normalize(w2, modulus)
  unless normalize(w1.pow(x, modulus), modulus) == normalize(w2.pow(y, modulus), modulus)
    raise ArgumentError, 'w1^x != w2^y'
  end
  a, b = egcd(x, y)
  raise ArgumentError, 'Inputs does not co-prime.' unless a * x + b * y == 1
  normalize(w1.pow(b, modulus) * w2.pow(a, modulus), modulus)
end

#valid_elements?(elements) ⇒ Boolean

Check whether elements can be converted to a product of primes. Verifiers use this to turn a malformed proof into a false result instead of an exception.

Parameters:

  • elements (Object)

Returns:

  • (Boolean) 


53
54
55
 
# File 'lib/rsa/acc/functions.rb', line 53

def valid_elements?(elements)
  elements.is_a?(Array) && !elements.empty? && elements.all? { |e| e.is_a?(String) }
end