From: Evan Webb <evan@...>
Date: 2004-09-10T03:28:02+09:00
Subject: RE: Réf. : ASCII, RSA AND BIGNUM

As a side note, check out Crypt::RSA (http://dark-ruby.org). It uses MBignum
(available at the same place) for the more difficult math, provides a simple
look at the RSA algorithm without cluttering up the code with slow math.

Evan Webb // evan@fallingsnow.net

> -----Original Message-----
> From: Barry Sperling [mailto:barry@angleinc.com]
> Sent: Thursday, September 09, 2004 9:25 AM
> To: ruby-talk ML
> 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 )