Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class String
- # Convert String to a string of binary digits, similar to Integer.to_s(2).
- def to_bin
- n = self.to_str
- s = ''
- n.each_byte do |b|
- s << b.to_s(2)
- end
- s
- end
- # Do I need a Integer#to_integer and a String.to_integer? Strings should be
- # allowed as inputs to a lot of the crypto APIs, but they will be treated as
- # integers, internally! How to deal with this?
- def to_integer
- Integer.from_unsigned_bytes(self)
- end
- def to_bytes
- self
- end
- end
- class Integer
- # +bytes+ is a sequence of octets in network byte order (most significant
- # byte first) that comprises an unsigned integer.
- def self.from_unsigned_bytes(bytes)
- bytes = bytes.to_str
- n = 0
- bytes.each_byte do |b|
- n <<= 8
- n |= b
- end
- n
- end
- # Return self as a String of bytes in network byte order.
- def to_bytes
- a = []
- n = self.to_int
- while n != 0
- a.unshift( (n & 0xff).chr )
- n >>= 8
- end
- a.join
- end
- # Return self.
- #
- # Purpose is to allow a set of classes to declare themselves to be "duck-typed"
- # to Integer. This set of classes includes String, see String#to_integer.
- def to_integer
- self
- end
- # Why isn't this a standard ruby method?
- def []=(position, value)
- bit = 2 ** position
- i = self.to_int
- if value
- i |= bit
- else
- i &= ~bit
- end
- i
- end
- # Determine size of +self+ in bits.
- def bit_size
- i = self.to_int
- hibit = i.size * 8 - 1
- while( i[hibit] == 0 ) do
- hibit = hibit - 1
- break if hibit < 0
- end
- hibit + 1
- end
- end
- class Integer
- # Calculate the inverse of an Integer modulo +n+. The modular inverse of +a mod n+,
- # +a^-1 mod n+, is a number +a^-1+ such that:
- #
- # a^-1 * a = 1 mod n
- #
- # There may not be such a number, in which case a RangeError is raised.
- #
- # Uses the 'Extended Euclidean Algorithm' implementation
- # from Figure 4.1, +Cryptography Theory and Practice+, Stinson.
- def modular_inverse(n)
- n = n.to_int
- b = self.to_int
- n0 = n
- b0 = b
- t0 = 0
- t = 1
- q = (n0/b0).floor
- r = n0 - q * b0
- while r > 0 do
- temp = t0 - q * t
- if temp > 0 then temp = temp.modulo(n); end
- if temp < 0 then temp = n - ((-temp).modulo(n)); end
- t0 = t
- t = temp
- n0 = b0
- b0 = r
- q = (n0/b0).floor
- r = n0 - q * b0
- end
- if b0 != 1
- raise RangeError, "#{b} has no inverse modulo #{n}"
- else
- t.modulo(n)
- end
- end
- # Calculate +self+ ** +exp+ modulo +n+.
- #
- # This method uses the "square and multiply" approach. Why should be fairly
- # obvious from the code, see +Cryptography Theory and Practice+, Stinson,
- # Chapter 4.4 for a description of the method.
- def modular_exp(exp, n)
- # x ** b mod n
- x = self.to_int
- b = exp.to_int
- n = n.to_int
- z = 1
- (n.bit_size - 1).downto(0) do |i|
- z = z ** 2 % n
- if b[i] == 1 then
- z = z * x % n
- end
- end
- z
- end
- # Return whether +self+ is even, that is, evenly divisible by 2.
- def even?
- self[0] == 0
- end
- # True if +self+ is probably prime, false otherwise. Probabalistic primality
- # test is the Miller-Rabin algorithm, aka "strong pseudo-prime test".
- #
- # +accuracy+ is the number of times to try the test, and error probablity
- # will be aproximately 1 time out of 4**+accuracy+. Default is 10, wich gives
- # an error rate of 1 in 1,048,076.
- def prime?(accuracy = 10)
- miller_rabin_prime?(accuracy)
- end
- # Determines if an odd number is prime, with an error probability of 1/4, at
- # most. Implementation from Stinson, Figure 4.9.
- def miller_rabin_prime?(accuracy)
- # Two is prime
- return true if self == 2
- # Not prime if its even!
- return false if self.even?
- n = self.to_int
- # Find k, m such that n - 1 = (2 ** k) * m, where m is odd
- m = n - 1
- k = 0
- # Since n is odd, n-1 is even, and this will loop at least once
- while m.even?
- m >>= 1
- k += 1
- end
- # Answers of 'composite' are always correct - n is not prime. Answers of
- # 'prime' are not necessarily true, so we try again. If we answered 'prime'
- # accuracy number of times, then maybe it is prime.
- accuracy.times do
- catch(:isprime) do
- # Choose a, 1 <= a <= n - 1
- a = Kernel.rand(n - 1) # 0..(n-2)
- a = a + 1 # 1..n-1
- # Compute b = a ** m mod n
- b = a.modular_exp(m, n)
- # puts "n #{n} m #{m} k #{k} a #{a} b #{b}"
- # If b == 1 mod n, n is prime
- if( b == 1 )
- throw :isprime
- end
- # For i = 0 to k - 1 do
- k.times do
- # if b == -1 (mod n), n is prime
- if( b == (n - 1) )
- throw :isprime
- else
- b = b.modular_exp(2, n)
- end
- end
- # It's composite.
- return false
- end
- end
- return true
- end
- end
Add Comment
Please, Sign In to add comment