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