Class: Rb25519::FField

Inherits:
Object
  • Object
show all
Defined in:
lib/rb-pure25519.rb

Defined Under Namespace

Classes: EC, EC25519, FFieldValue, MontgomeryEC

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(size) ⇒ FField

Returns a new instance of FField.

Raises:

  • (RuntimeError) 


200
201
202
203
 
# File 'lib/rb-pure25519.rb', line 200

def initialize(size)
  raise RuntimeError.new("Field must be prime") unless size.ferm_is_prime?
  @p = size
end

Instance Attribute Details

#p ⇒ Object

Returns the value of attribute p.



198
199
200
 
# File 'lib/rb-pure25519.rb', line 198

def p
  @p
end

Class Method Details

.eea(i, j) ⇒ Object 



176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
 
# File 'lib/rb-pure25519.rb', line 176

def self.eea(i,j)
  s,t,u,v = 1,0,0,1
  while (j != 0)
    q,    r    = i / j,   i % j
    unew, vnew = s    ,   t
   
    s = u - (q * s)
    t = v - (q * t)

    i,  j    =  j,    r
    u,  v    =  unew, vnew


  end
  d, m, n = i, u, v

  return [d, m, n]
end

.rosetta_mod_exp(b, exp, mod) ⇒ Object

Class methods



164
165
166
167
168
169
170
171
172
173
174
 
# File 'lib/rb-pure25519.rb', line 164

def self.rosetta_mod_exp(b, exp, mod)
  exp < 0 and raise ArgumentError, "negative exponent"
  prod = 1
  base = b % mod
  until exp.zero?
    exp.odd? and prod = (prod * base) % mod
    exp >>= 1
    base = (base * base) % mod
  end
  prod
end

Instance Method Details

#[](v) ⇒ Object 



206
207
208
 
# File 'lib/rb-pure25519.rb', line 206

def [](v)
  FFieldValue.new(self, v)
end

#add(a, b) ⇒ Object 



210
211
212
213
214
 
# File 'lib/rb-pure25519.rb', line 210

def add(a,b)
  nv = a.to_i + b.to_i
  nv -= @p if nv >= @p
  nv
end

#div(a, b) ⇒ Object

rv = (a / b)



237
238
239
 
# File 'lib/rb-pure25519.rb', line 237

def div(a,b)
  a.to_i * inv(b.to_i)
end

#exp(b, e) ⇒ Object

rv = b^e



245
246
247
 
# File 'lib/rb-pure25519.rb', line 245

def exp(b,e)
  self.class.rosetta_mod_exp(b.to_i, e.to_i, @p)
end

#inv(v) ⇒ Object 



227
228
229
230
 
# File 'lib/rb-pure25519.rb', line 227

def inv(v)
  #puts "Inversion"
  return self.class.eea(@p, v.to_i)[1]
end

#mul(a, b) ⇒ Object 



222
223
224
225
 
# File 'lib/rb-pure25519.rb', line 222

def mul(a,b)
  # Naive implementation of multiply
  (a.to_i * b.to_i) % @p
end

#sqrt(n) ⇒ Object 



249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
 
# File 'lib/rb-pure25519.rb', line 249

def sqrt(n)
  n = n.to_i
  return nil if exp(n, (@p-1)/2) != 1

  if (@p % 4) == 3
    r = exp(n, (p+1) / 4)
    return [ r, -r % @p ]
  end



  ##
  ## Implement Tonelli-Shanks (from https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm )
  ## 

  # Factor out Q and S
  #
  #
  p1 = @p-1

  q,s = nil,nil

  p1.bit_length.times.each do |_s|

    _q, _res = p1.ferm_ndiv(1 << _s)
    ## puts [_s, _q, _res].inspect

    if _res == 0 and _q.odd?
      q,s = _q, _s
    end
  end

  ## puts "q,s: #{[q,s].inspect}"

  # Find `z` such that Legendre ( z | p ) == -1
  z = nil
  (1..@p).each{|_z| (z = _z; break) if self.exp(_z, (@p-1)/2) > 1 }
  ## puts "Found z: #{z}"

  c = exp(z, q)
  ## puts "Calculated c: #{c}"

  r = nil
  _r = exp(n, (q+1) / 2 )
  t = exp(n, q)
  m = s


  @p.times do

    if (t == 1)
      r = _r
      ## puts "R is #{r}"
      break
    end

    # Modify t and R
    #

    # find i such that 0 < i < M, such that t**2**i == 1 (mod p)
    i = nil
    i = (1..(m-1)).find{|_i| exp(t, (1<<_i)) == 1 }
    ## puts "Found i: #{i}"

    b = exp(c, (1 << (m - i - 1)))
    _r = mul(_r, b)
    t = mul(t, exp(b, 2) )
    c = exp(b, 2)

    m = i

    ## puts({:b => b, :r => _r, :t => t, :c => c}.inspect)

  end
  

  [r, @p - r] if r
end

#sub(a, b) ⇒ Object 



216
217
218
219
220
 
# File 'lib/rb-pure25519.rb', line 216

def sub(a,b)
  nv = a.to_i - b.to_i
  nv += @p if nv < 0
  nv
end