Greetings all. Does anyone have a clue how to use Ruby to do modular exponentiation using the binary left-to-right method? I looked through the documentation and searched the forums and found the String.each_byte method. However I had no luck finding anything showing how one might manipulate bits of bytes. Below is an example of what I am talking about. The calculation a = b^e mod n (or in Ruby: a = (b ** e).modulo(n) )is known as modular exponentiation. One efficient method to carry this out on a computer is the binary left-to-right method. To solve y = x^e mod n let e be represented in base 2 as e = e(k-1)e(k-2)...e(1)e(0) where e(k-1) is the most significant non-zero bit and bit e(0) the least. set y = x for bit j = k - 2 downto 0 begin y = y * y mod n /* square */ if e(j) == 1 then y = y * x mod n /* multiply */ end return y Thanks for looking, Doug

on 2006-05-10 00:14

on 2006-05-10 04:17

# ## Use Fixnum#[] - Bit Reference # def modexp x, e, n return 1%n if e.zero? # k - most significant bit posistion ee, k = e, 0 # linear search (ee>>=1;k+=1) while ee>0 y = x (k-2).downto(0) do |j| y=y*y%n # square (y=y*x%n) if e[j] == 1 # multiply end y end __END__ Btw: do you know how to find most significant bit faster? Sergey V. doug meharry wrote: > Greetings all. > > Does anyone have a clue how to use Ruby to do modular exponentiation > using the binary left-to-right method? I looked through the > documentation and searched the forums and found the String.each_byte > method. However I had no luck finding anything showing how one might > manipulate bits of bytes. > > Below is an example of what I am talking about. > > The calculation a = b^e mod n (or in Ruby: a = (b ** e).modulo(n) )is > known as modular exponentiation. One efficient method to carry this out > on a computer is the binary left-to-right method. To solve y = x^e mod n > let e be represented in base 2 as > > e = e(k-1)e(k-2)...e(1)e(0) > > where e(k-1) is the most significant non-zero bit and bit e(0) the > least. > set y = x > for bit j = k - 2 downto 0 > begin > y = y * y mod n /* square */ > if e(j) == 1 then > y = y * x mod n /* multiply */ > end > return y > > > Thanks for looking, > > Doug

on 2006-05-10 04:59

On Wed, May 10, 2006 at 05:15:06AM +0900, doug meharry wrote: > for bit j = k - 2 downto 0 > begin > y = y * y mod n /* square */ > if e(j) == 1 then if e[j] == 1 > y = y * x mod n /* multiply */ > end > return y > > > Thanks for looking, > > Doug Integers in ruby has a [] method that returns the bit at the specified offset (0 for lsb)

on 2006-05-10 09:36

> > Does anyone have a clue how to use Ruby to do modular exponentiation > > using the binary left-to-right method? I looked through the > > documentation and searched the forums and found the String.each_byte > > method. However I had no luck finding anything showing how one might > > manipulate bits of bytes. No, but in case its useful (a long shot), I have some source that does it using the "square and multiply" method. Used it to implement RSA in pure ruby. In the hopes it will be useful, here it is. -------------------------------------------------------------------------------- # $Id: modn.rb,v 1.3 2004/12/04 20:39:41 sam Exp $ 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

on 2006-05-10 11:02

2006/5/10, Sergey V. <removed_email_address@domain.invalid>: > Btw: do you know how to find most significant bit faster? Dunno whether any of these is faster >> require 'mathn' => true >> x=1<<40 => 1099511627776 >> k=("%b" % x).length - 1 => 40 >> x[k] => 1 >> k=Math.log(x)/Math.log(2) => 40.0 >> x[k] => 1 Kind regards robert