From: Barry Sperling <barry@...>
Date: 2004-09-10T01:24:37+09:00
Subject: Re: Réf. : ASCII, RSA AND BIGNUM

	My work load lightened considerably, so I went back to the problem of 
coding the RSA algorithm, and I finished it.  Thanks to Tad Bochan for 
his algorithm simplifying the work with powers! Also, Markus and Roland 
for their comments.
	I'm pasting in the code, below, since, as a nuby, I recognize that I am 
probably writing it all "wrong". It is written in an obvious "C" style 
so if someone could take the time to point out the correct Ruby styling, 
I'd appreciate it!
	Barry


include Math   # FOR SQRT

# PRINTS ASCII OF ARRAY, CURRENTLY BACKWARDS AND 8 CHARACTERS SPECIFICALLY
def convert_to_text( num )
	ar = Array.new
	while num > 0 do
		last_two = num % 100
		ar.push( last_two )
		num /= 100
	end
	ar.reverse!   # SINCE AR.PUSH MAKES THE LAST ONE FIRST
	character = Array.new   # HOLD THE SINGLE CHARACTER FOR PACK("C")
	for num in 0..(ar.length - 1 ) do   # PRINT EACH CHARACTER
		character[ 0 ] = ar[ num ]
		print( character.pack("c") )
	end
	puts
end

# USE ONLY THE VALUES FROM THE ARRAY OF MODDED SQUARES
#  THAT MATCH THE "SET" BITS OF THE BASE.  CALLED FROM FIND_BASE_BITS
def find_mod_powers( bit_array, power_array, mod_num )
	len = bit_array.length
	prod_bit_powers = 1
	for num in 0..(bit_array.length - 1) do
		prod_bit_powers = ( prod_bit_powers * power_array[ bit_array[ num ] ] 
) % mod_num
	end
	return prod_bit_powers
end

# FIND AN ARRAY TO HOLD THE "SET" BITS OF THE BASE-2 REPRESENTATION OF 
THE "BASE" NUMBER
#  AND AN ARRAY TO HOLD THE SEQUENTIAL MODDED SQUARES OF THE BASE
#  CALLED TWICE FROM MAIN CODE: ONCE FOR DECRYPTION AND ONCE FOR ENCRYPTION
def find_base_bits( base, mod_num, power )
	bit_pos = 0   # INIT BIT POSITION OF POWERS OF 2
	bit_array = Array.new   # HOLD BIT POSITIONS OF EXPONENT
	power_array = Array.new   # HOLD MODDED POWERS OF EXPONENT
	modded_base = base % mod_num
	while power >= 1 do    # WHILE SOME BITS ARE LEFT TO SHIFT
		power_array.push( modded_base )
		p = power % 2
		if ( p == 1 ) then   # IF THE LEAST SIGNIFICANT BIT IS 1
			bit_array.push( bit_pos )   # SAVE BIT POSITIONS
		end
		modded_base = ( modded_base * modded_base ) % mod_num
		power >>= 1   # SHIFT RIGHT TO CHECK NEXT BIT
		bit_pos += 1   # NEXT BIT POSITION
	end
	
	find_mod_powers( bit_array, power_array, mod_num )
end

# CALLED FROM MAIN CODE TO FIND THE SMALLEST DIVISOR OF A COMPOSITE
#  AND AN ASSOCIATED DIVISOR, BOTH OF WHICH ARE RETURNED.
#  IF A PRIME IS RETURNED
#  YOU MUST SEND ANOTHER MULTIPLE OF de TO THIS FUNCTION.
#  THESE FACTORS WILL BE THE POWERS OF THE BASE ASCII TEXT NUMBER
#  FOR ENCRYPTION AND DECRYPTION
def find_factors( composite )
	finish = sqrt( composite )	# LARGEST DIVISOR TO CHECK
	finish = finish.to_i
	
	prime = true
	divisor = 2
	while divisor <= finish		# ONLY CHECK DIVISORS UP TO SQRT
		if composite % divisor == 0
			prime = false
			print( "One factor: " ); puts divisor
			print( "Second factor: " ); puts composite / divisor
			break		# QUIT WHILE-LOOP IF COMPOSITE
		end
		
		divisor += 1
	end
	
	if prime == true
		print( 'Prime: ' ); puts composite
	end
	
	return [ divisor, composite / divisor ]
end

# THE TEXT, TO BE ENCRYPTED AND SENT ALONG WITH THE PUBLIC KEY
#  LIMITED TO 8 CHAR, ALL WITH ASCII VALUES BELOW 100
s = "GO SKINS"
asc_of_text = 0
s.each_byte do |a|   #TAKING EACH CHAR AS A 2-DIGIT NUM AND CREATING A
   print( a ); print( ' ' )     # LARGE NUM WITH EACH PAIR OF DIGITS
				# BEING THE ASCII
   asc_of_text *= 100          # OF THE STRING, LEFT-MOST 2 DIGITS BEING
				#THE FIRST LETTER
   asc_of_text += a
end
puts

# 2 PRIMES CHOSEN TO BE LARGE ENOUGH
# TO BE USED AS mod FOR THE 8-CHAR TEXT
prime_1 = 100000007
prime_2 = 100000969
mod_num = prime_1 * prime_2

# FINDING d AND e SUCH THAT (de-1) IS DIVISIBLE BY
# (SOME_PRIME - 1)(ANOTHER_PRIME - 1)
de = ( prime_1 - 1 ) * ( prime_2 - 1 ) + 1
factor_pair = find_factors( de )
e = factor_pair[ 0 ]
d = factor_pair[ 1 ]

encryp = find_base_bits( asc_of_text, mod_num, e )
print("encryp: " ); puts encryp

decryp =find_base_bits( encryp, mod_num, d )
print("decryp: " ); puts decryp
convert_to_text( decryp )