Réf. : ASCII, RSA AND BIGNUM

[Tadeusz_Bochan]

Hi Barry,
I'm a total ruby-nuby, so ther's not much ruby content here.

In the RSA algorithm, you need to be able to evaluate a**b mod n
using integer arithmetic only.
(Note : "mod n" means "remainder after division by n". )
The easiest way to describe the standard method is by a
somewhat contrived example.
Let's say you want to calculate A=(25800**100 mod 257)

First, note that 100 base 10 = 1100100 base 2,

so that 100**100 = (100**64) * (100**32) * (100**4)

Now calculate,

25800**1 mod 257 = 100
100**2 mod 257 = 100*100 mod 257 = 235
100**4 mod 257 = 235*235 mod 257 = 15
100**8 mod 257 = 15*15 mod 257 = 225
100**16 mod 257 = 225*225 mod 257 = 253
100**32 mod 257 = 253*253 mod 257 = 16
100**64 mod 257 = 16 * 16 mod 257 = 256

Then,

A = ((256 * 16) mod 257) * (15 mod 257)

A= ( 241 * 15) mod 257

So, the answer is A=17

You can see that that no calculation above requires more
than 5 digits (257**2 = 66049)

Specialized languages like Wolfram's Mathematica handle this sort of
calculation very efficiently for large values of a,b and n.

I hope this is useful to you.

Regards,
Tad

(Embedded image moved to file: pic29358.pcx)

Internet
barry@angleinc.com - 27/08/2004 23:07

Veuillez répondre à ruby-talk@ruby-lang.org

Pour : ruby-talk

cc :

Continuing on the track of the previous question about ASCII, I'm using
each_byte to change a string to ASCII for the purpose of encrypting it,
using the theory of the RSA algorithm ( to see if I can! ). Part of
this algorithm requires getting a power ( a**b ) in which the "a" is the
ASCII value of the string and the "b" is some large number that is
dictated by the RSA algorithm ( about 25,000,000,000,000 for my test
string ). However, when I do this I get the error

NaN
test_ascii.rbw:20: warning: in a**b, b may be too big

While I could simulate a power with a loop, doing this 25 trillion times
might take a little while. I could also simulate the power with logs,
but I'm sure that this would add inaccuracies and the integral number
has to be exact. Is there a way out or is this just a fundamental
limitation of Bignums in Ruby?
Barry

This message and any attachments (the "message") is
intended solely for the addressees and is confidential.
If you receive this message in error, please delete it and
immediately notify the sender. Any use not in accord with
its purpose, any dissemination or disclosure, either whole
or partial, is prohibited except formal approval. The internet
can not guarantee the integrity of this message.
BNP PARIBAS (and its subsidiaries) shall (will) not
therefore be liable for the message if modified.

pic29358.pcx (2.01 KB)

···

Objet : ASCII, RSA AND BIGNUM

                ---------------------------------------------

Ce message et toutes les pieces jointes (ci-apres le
"message") sont etablis a l'intention exclusive de ses
destinataires et sont confidentiels. Si vous recevez ce
message par erreur, merci de le detruire et d'en avertir
immediatement l'expediteur. Toute utilisation de ce
message non conforme a sa destination, toute diffusion
ou toute publication, totale ou partielle, est interdite, sauf
autorisation expresse. L'internet ne permettant pas
d'assurer l'integrite de ce message, BNP PARIBAS (et ses
filiales) decline(nt) toute responsabilite au titre de ce
message, dans l'hypothese ou il aurait ete modifie.

[Barry_Sperling]

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 )

[Evan_Webb]

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

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[

···

-----Original Message-----
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 )

[Olivier_D3 (Olivier D.)]

Be careful, I'm a nuby, but I've found a few things:

# PRINTS ASCII OF ARRAY, CURRENTLY BACKWARDS AND 8 CHARACTERS SPECIFICALLY
def convert_to_text( num )
...
end

If you want to convert ASCII chars from 0 to 99 in one line, you can do:

def convert_to_text(num)
    num.to_s.reverse.scan(/\d\d?/).map { |c|
        c.reverse.to_i.chr
    }.join.reverse
end

BUT it's dirty and you're limited to decimal values <= 99.
Why not use String#hex instead:

# give this function an hexa string
def hex_to_text(string)
    string.scan(/../).map { |c| c.hex.chr }.join
end
puts hex_to_text("61626364")

# 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

You can do this shorter:

s = "GO SKINS"
asc = s.split(//).map { |c| "%02d" % c[0] }.join

No comments for the crypto part, I'll have to read my lessons again...

And a last comment for the code: remove all the for loops, like
for i in 0..(string.length - 1) and change them into 'each' calls with
blocks associated.

With Strings you can use 'each'.
With Arrays you can use 'each', 'each_index'.
And with all the Enumerables (String, Array...): each_with_index.

···

On 2004-09-09, Barry Sperling <barry@angleinc.com> wrote:

--
Olivier D.