Réf. : ASCII, RSA AND BIGNUM

[tad.bochan]

--0__=4EBBE593DFA10B4C8f9e8a93df938690918c4EBBE593DFA10B4C
Content-type: text/plain; charset=iso-8859-1
Content-transfer-encoding: quoted-printable



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=3D(25800**100 mod 257)


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

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

Now calculate,

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

Then,

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

A=3D ( 241 * 15) mod 257

So, the answer is A=3D17

You can see that that no calculation above requires more
than 5 digits (257**2 =3D 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
(e-mail address removed) - 27/08/2004 23:07


Veuillez r=E9pondre =E0 (e-mail address removed)

Pour : ruby-talk

cc :


Objet : ASCII, RSA AND BIGNUM


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.=20
If you receive this message in error, please delete it and=20
immediately notify the sender. Any use not in accord with=20
its purpose, any dissemination or disclosure, either whole=20
or partial, is prohibited except formal approval. The internet
can not guarantee the integrity of this message.=20
BNP PARIBAS (and its subsidiaries) shall (will) not=20
therefore be liable for the message if modified.=20

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

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


--0__=4EBBE593DFA10B4C8f9e8a93df938690918c4EBBE593DFA10B4C
Content-type: application/octet-stream;
name="pic29358.pcx"
Content-Disposition: attachment; filename="pic29358.pcx"
Content-transfer-encoding: base64

CgUBCAAAAAAGARMAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAABBwEBAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAD////////m/9P/yf/F/8L/wf/////////m/9P/yf/F/8L/wf/////////m
/9P/yf/F/8L/wf/////////m/9P/yf/F/8L/wf/////////m/9P/yf/F/8L/wf/G/8IA1P/CAMX/
xADE/8QA0P/FAMX/xADH/wDS/8IAxP/FANH/xQDD/8UAw//FAND/xQDE/8UAxP/EANP/wgDH/8QA
z//FAMP/xQDG/8QAwv/B/8T/wgDB/wDS/8IAwf8AxP8AxP8Awv8AxP8Azv8Axf8Awv/CAMT/AMX/
wgDQ/8IAwf8AxP8A1P8Axf8Awf8Axf8Awv8A0/8Axf8Aw/8Axv/CAMT/AND/wgDB/wDG/wDS/wDF
/wDC/wDJ/wDE/8L/wf/H/wDV/wDE/wDE/wDC/wDE/wDO/wDF/wDI/wDE/wDB/wDT/wDE/wDU/wDF
/wDB/wDF/wDC/wDT/wDF/wDD/wDM/wDT/wDF/wDT/wDF/wDC/wDI/wDF/8L/wf/H/wDV/wDE/wDE
/wDC/wDE/wDU/wDI/wDD/wDC/wDT/wDE/wDa/wDH/wDC/wDZ/wDD/wDM/wDT/wDE/wDY/8L/AML/
AMf/AMX/w//B/8f/ANX/AMT/AMT/AML/AMT/ANP/AMb/wwDE/wDC/wDT/wDE/8UA1f8Ax/8Aw//F
ANT/AMT/xQDF/8MA1P8AxP8Awf/EANT/AMP/xQDD/wDB/8QAw//B/8f/ANX/AMT/AMT/AML/AMT/
ANH/wgDJ/wDD/wDD/wDT/wDJ/wDS/8IAxv/CAMn/ANH/wgDK/wDG/wDU/wDE/8IAxP8A0f/CAMn/
AML/wgDE/wDC/8H/x/8A1f8AxP8AxP8Awv8AxP8A0P8AzP8Awv/GANL/AMn/ANH/AMf/AMv/AND/
AMz/AMf/ANP/AMT/AMX/AND/AMv/AML/AMX/AML/wf/H/wDG/8IAzf8AxP8AxP8Awv8AxP8Aw//C
AMr/AM3/AMb/AMT/wgDN/wDJ/wDE/8IAyv8Ax/8AzP8Aw//CAMr/AM3/AMf/AMP/wgDO/wDE/wDF
/wDD/8IAyv8AzP8Awv8Axf8Awv/B/8f/AMb/AM7/AMT/AMT/AML/AMT/AMP/AMr/AMX/AML/AMX/
AMb/AMT/AM7/AMP/AMX/AMT/AMr/AMX/AMH/AMX/AMH/AMX/AMP/AMr/AMX/AML/AMX/AMH/AMX/
AMP/AM//AMT/AMX/AMP/AMr/AMX/AMH/AMX/AML/AMX/AML/wf/E/8cAwv/CAMv/xwDC/8QAxP/E
AMP/wgDK/8cAw//FAMX/xADC/8IAy//HAMH/xQDE/8IAyv/HAMH/xwDC/8UAw//CAMr/xwDD/8UA
w//FAMP/wgDM/8cAwv/FAMP/wgDK/8cAwv/FAMT/xQDD/8H/zf8A5P8A5f8A3f8A5P8A5f8A3v8A
1P/K/8X/wv/B/83/AOT/AOX/AN3/AOT/AOX/AN7/ANT/yv/F/8L/wf/////////m/9P/yf/F/8L/
wf/////////m/9P/yf/F/8L/wf/////////m/9P/yf/F/8L/wf8MAAAAgAAAAIAAgIAAAACAgACA
AICAwMDAwNzApsrwQCAAYCAAgCAAoCAAwCAA4CAAAEAAIEAAQEAAYEAAgEAAoEAAwEAA4EAAAGAA
IGAAQGAAYGAAgGAAoGAAwGAA4GAAAIAAIIAAQIAAYIAAgIAAoIAAwIAA4IAAAKAAIKAAQKAAYKAA
gKAAoKAAwKAA4KAAAMAAIMAAQMAAYMAAgMAAoMAAwMAA4MAAAOAAIOAAQOAAYOAAgOAAoOAAwOAA
4OAAAABAIABAQABAYABAgABAoABAwABA4ABAACBAICBAQCBAYCBAgCBAoCBAwCBA4CBAAEBAIEBA
QEBAYEBAgEBAoEBAwEBA4EBAAGBAIGBAQGBAYGBAgGBAoGBAwGBA4GBAAIBAIIBAQIBAYIBAgIBA
oIBAwIBA4IBAAKBAIKBAQKBAYKBAgKBAoKBAwKBA4KBAAMBAIMBAQMBAYMBAgMBAoMBAwMBA4MBA
AOBAIOBAQOBAYOBAgOBAoOBAwOBA4OBAAACAIACAQACAYACAgACAoACAwACA4ACAACCAICCAQCCA
YCCAgCCAoCCAwCCA4CCAAECAIECAQECAYECAgECAoECAwECA4ECAAGCAIGCAQGCAYGCAgGCAoGCA
wGCA4GCAAICAIICAQICAYICAgICAoICAwICA4ICAAKCAIKCAQKCAYKCAgKCAoKCAwKCA4KCAAMCA
IMCAQMCAYMCAgMCAoMCAwMCA4MCAAOCAIOCAQOCAYOCAgOCAoOCAwOCA4OCAAADAIADAQADAYADA
gADAoADAwADA4ADAACDAICDAQCDAYCDAgCDAoCDAwCDA4CDAAEDAIEDAQEDAYEDAgEDAoEDAwEDA
4EDAAGDAIGDAQGDAYGDAgGDAoGDAwGDA4GDAAIDAIIDAQIDAYIDAgIDAoIDAwIDA4IDAAKDAIKDA
QKDAYKDAgKDAoKDAwKDA4KDAAMDAIMDAQMDAYMDAgMDAoMDA//vwoKCkgICA/wAAAP8A//8AAAD/
/wD/AP//////

--0__=4EBBE593DFA10B4C8f9e8a93df938690918c4EBBE593DFA10B4C--

 

[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 // (e-mail address removed)

-----Original Message-----
From: Barry Sperling [mailto:[email protected]]
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 )

 

[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.