Class: RSA::Accumulator

Inherits:
Object
  • Object
show all
Includes:
RSA::ACC::Functions, RSA::ACC::PoE
Defined in:
lib/rsa/accumulator.rb

Constant Summary collapse

RSA2048_MODULUS =

RSA-2048 modulus(en.wikipedia.org/wiki/RSA_numbers#RSA-2048).

25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357
RSA2048_UNKNOWN_ELEM = 
2

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from RSA::ACC::PoE

prove, verify

Methods included from RSA::ACC::Functions

#blake2_hash, #compute_challenge, #egcd, #elements_to_prime, #hash_to_prime, #shamir_trick

Constructor Details

#initialize(n, value, initial_acc, hold_elements, products = 1) ⇒ RSA::Accumulator

Initialize accumulator

Parameters:

  • n (Integer) —

    modulus

  • value (Integer) —

    a value of acc.

  • initial_acc (Integer) —

    a value of initial acc.

  • hold_elements (Boolean)
  • products (Integer) (defaults to: 1) —

    product of all elements in acc, this param is enable only hold_elements set true.



45
46
47
48
49
50
51
52
 
# File 'lib/rsa/accumulator.rb', line 45

def initialize(n, value, initial_acc, hold_elements, products = 1)
  @n = n
  @value = value
  @g = initial_acc
  @hold_elements = hold_elements
  @products = products if hold_elements
  puts "The feature which hold product of all elements is practical feature." if hold_elements
end

Instance Attribute Details

#g ⇒ Object (readonly)

Initial value



19
20
21
 
# File 'lib/rsa/accumulator.rb', line 19

def g
  @g
end

#hold_elements ⇒ Object (readonly)

tha flag which indicate hold product of all elements.



20
21
22
 
# File 'lib/rsa/accumulator.rb', line 20

def hold_elements
  @hold_elements
end

#n ⇒ Object (readonly)

Returns the value of attribute n.



17
18
19
 
# File 'lib/rsa/accumulator.rb', line 17

def n
  @n
end

#products ⇒ Object

(Optional) product of all elements in Accumulator



21
22
23
 
# File 'lib/rsa/accumulator.rb', line 21

def products
  @products
end

#value ⇒ Object

Returns the value of attribute value.



18
19
20
 
# File 'lib/rsa/accumulator.rb', line 18

def value
  @value
end

Class Method Details

.generate_random(bit_length = 3072, hold_elements: false) ⇒ RSA::Accumulator

Generate accumulator with random modulus.

Parameters:

  • bit_length (Integer) (defaults to: 3072) —

    bit length of accumulator. Default: 3072 bits.

Returns:



32
33
34
35
36
 
# File 'lib/rsa/accumulator.rb', line 32

def self.generate_random(bit_length = 3072, hold_elements: false)
  n = OpenSSL::PKey::RSA.generate(bit_length).n.to_i
  initial_value = SecureRandom.random_number(n)
  new(n, initial_value, initial_value, hold_elements)
end

.generate_rsa2048(hold_elements: false) ⇒ RSA::Accumulator

Generate accumulator using RSA2048 modulus.

Returns:



25
26
27
 
# File 'lib/rsa/accumulator.rb', line 25

def self.generate_rsa2048(hold_elements: false)
  new(RSA2048_MODULUS, RSA2048_UNKNOWN_ELEM, RSA2048_UNKNOWN_ELEM, hold_elements)
end

Instance Method Details

#==(other) ⇒ Boolean

Check whether other is same accumulator.

Parameters:

  • other (RSA::ACC:Accumulator) —

    other accumulator.

Returns:

  • (Boolean) —

    if same acc return true, otherwise return false.



73
74
75
76
 
# File 'lib/rsa/accumulator.rb', line 73

def ==(other)
  return false unless other.is_a?(Accumulator)
  self.n == other.n && self.value == other.value
end

#add(*elements) ⇒ RSA::ACC::MembershipProof

Add element to accumulator and get inclusion proof.

Parameters:

  • elements (Array[String]) —

    a list of elements to be added.

Returns:



57
58
59
60
61
62
63
64
65
66
67
68
 
# File 'lib/rsa/accumulator.rb', line 57

def add(*elements)
  current_acc = value
  p = elements_to_prime(elements)
  self.value = value.pow(p, n)
  if hold_elements
    elements.each do |e|
      p = hash_to_prime(e)
      self.products *= p unless products.modulo(p) == 0
    end
  end
  RSA::ACC::MembershipProof.new(elements, current_acc, value, RSA::ACC::PoE.prove(current_acc, p, value, n))
end

#delete(*proofs) ⇒ RSA::ACC::MembershipProof

Remove the elements in proofs from the accumulator.

Parameters:

Returns:



132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
# File 'lib/rsa/accumulator.rb', line 132

def delete(*proofs)
  return RSA::ACC::MembershipProof.new(proofs.map(&:element).flatten, value, value, RSA::ACC::PoE.prove(value, 1, value, n)) if proofs.empty?

  witnesses = proofs.map do |proof|
    p = proof.element_prime
    raise RSA::ACC::Error, 'Bad witness.' unless proof.witness.pow(p, n) == value
    [p, proof.witness]
  end

  current_value = value
  proof_product = witnesses.first[0]
  new_value = witnesses.first[1]
  if witnesses.size > 1
    witnesses[1..-1].each do |w|
      new_value = shamir_trick(new_value, w[1], proof_product, w[0], n)
      proof_product *= w[0]
    end
  end
  self.products = self.products / proof_product if hold_elements
  self.value = new_value
  RSA::ACC::MembershipProof.new(proofs.map{|p|p.element}.flatten, value, current_value, RSA::ACC::PoE.prove(value, proof_product, current_value, n))
end

#member?(proof) ⇒ Boolean

Check whether proof#element include in accumulator.

Parameters:

Returns:

  • (Boolean) —

    If element exist in acc return true, otherwise false.



81
82
83
 
# File 'lib/rsa/accumulator.rb', line 81

def member?(proof)
  RSA::ACC::PoE.verify(proof.witness, proof.element_prime, value, proof.proof, n)
end

#non_member?(elements, proof) ⇒ Boolean

Verifies a non-membership proof against the current accumulator and elements whose non-inclusion is being proven.

Parameters:

Returns:

  • (Boolean) 


89
90
91
92
93
 
# File 'lib/rsa/accumulator.rb', line 89

def non_member?(elements, proof)
  x = elements_to_prime(elements)
  RSA::ACC::PoKE2.verify(value, proof.v, proof.poke2_proof, n) &&
      RSA::ACC::PoE.verify(proof.d, x, proof.gv_inv, proof.poe_proof, n)
end

#prove_membership(*elements) ⇒ RSA::ACC::MembershipProof

Generate membership proof for elements. This method is only available if hold_elements is set to true when the accumulator is initialized.

Parameters:

  • elements (Array[String]) —

    The elements for which you want to generate an membership proof.

Returns:

Raises:

  • RSA::ACC::Error.new This exception is raised when hold_elements is set to false.



100
101
102
103
104
105
106
 
# File 'lib/rsa/accumulator.rb', line 100

def prove_membership(*elements)
  raise RSA::ACC::Error.new 'This accumulator does not hold the product of the elements.' unless hold_elements
  x = elements_to_prime(elements)
  return nil unless products.modulo(x) == 0
  witness = g.pow(products / x, n)
  RSA::ACC::MembershipProof.new(elements, witness, value, RSA::ACC::PoE.prove(witness, x, value, n))
end

#prove_non_membership(members, non_members) ⇒ RSA::ACC::NonMembershipProof

Generate non-membership proof using set of elements in current acc and non membership elements.

Parameters:

  • members (Array[String]) —

    The entire set of elements contained within this accumulator.

  • non_members (Array[String]) —

    Elements not included in this accumulator that you want to prove non-membership.

Returns:

Raises:

  • (ArgumentError) 


112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/rsa/accumulator.rb', line 112

def prove_non_membership(members, non_members)
  s = elements_to_prime(members)
  x = elements_to_prime(non_members)

  a, b = egcd(s, x)
  raise ArgumentError, "Inputs not co-prime." unless a * s + b * x == 1

  v = value.pow(a, n)
  d = g.pow(b, n)
  gv_inv = (g * v.pow(-1, n)) % n

  poke2_proof = RSA::ACC::PoKE2.prove(value, a, v, n)
  poe_proof = RSA::ACC::PoE.prove(d, x, gv_inv, n)

  RSA::ACC::NonMembershipProof.new(d, v, gv_inv, poke2_proof, poe_proof)
end

#root_factor(*f) ⇒ Array{Integer}

Computes an xi-th root of y for all i = 1, …, n in total time O(n log(n)).

Parameters:

  • f (Array[Integer]) —

    factorizations of the exponent x = x1, …, xn.

Returns:

  • (Array{Integer}) —

    array of xi-th root



158
159
160
161
162
163
164
165
166
 
# File 'lib/rsa/accumulator.rb', line 158

def root_factor(*f)
  return [value] if f.size == 1
  half_n = f.size / 2
  g_l = RSA::Accumulator.new(n, value.pow(f[0...half_n].map.inject(:*), n), g, false)
  g_r = RSA::Accumulator.new(n, value.pow(f[half_n..-1].map.inject(:*), n), g, false)
  l = g_r.root_factor(*f[0...half_n])
  r = g_l.root_factor(*f[half_n..-1])
  [l, r].flatten
end