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) ⇒ RSA::Accumulator

Initialize accumulator

Parameters:

  • n (Integer) —

    modulus

  • value (Integer) —

    initial value



39
40
41
42
43
 
# File 'lib/rsa/accumulator.rb', line 39

def initialize(n, value)
  @n = n
  @value = value
  @g = value
end

Instance Attribute Details

#g ⇒ Object (readonly)

Initial value



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

def g
  @g
end

#n ⇒ Object (readonly)

Returns the value of attribute n.



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

def n
  @n
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) ⇒ RSA::Accumulator

Generate accumulator with random modulus.

Parameters:

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

    bit length of accumulator. Default: 3072 bits.

Returns:



30
31
32
33
 
# File 'lib/rsa/accumulator.rb', line 30

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

.generate_rsa2048 ⇒ RSA::Accumulator

Generate accumulator using RSA2048 modulus.

Returns:



23
24
25
 
# File 'lib/rsa/accumulator.rb', line 23

def self.generate_rsa2048
  new(RSA2048_MODULUS, RSA2048_UNKNOWN_ELEM)
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.



58
59
60
61
 
# File 'lib/rsa/accumulator.rb', line 58

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:



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

def add(*elements)
  current_acc = value
  p = elements_to_prime(elements)
  @value = value.pow(p, n)
  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:



104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
 
# File 'lib/rsa/accumulator.rb', line 104

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

  @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.



66
67
68
 
# File 'lib/rsa/accumulator.rb', line 66

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) 


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

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_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) 


84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/rsa/accumulator.rb', line 84

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



130
131
132
133
134
135
136
137
138
 
# File 'lib/rsa/accumulator.rb', line 130

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_r = RSA::Accumulator.new(n, value.pow(f[half_n..-1].map.inject(:*), n))
  l = g_r.root_factor(*f[0...half_n])
  r = g_l.root_factor(*f[half_n..-1])
  [l, r].flatten
end