The butterfly effect

Last morning while re-analyzing Sunday’s SIMCAT 13 paper, I was leisurely going through one of the passages which could be titled as the “butterfly effect”. Well it was quite an interesting RC passage. The author said about something called butterfly effect, in a nutshell, he wanted to say that a hurricane in Brazil could be the result of a butterfly flapping its wings in Indonesia. Sounds interesting right ? How is this possible ? Read on 😉

the_butterfly_effect

 

Edward Lorenz an American meteorologist was using a computer model for weather prediction when he entered the decimal .506 instead of entering the full .506127 as his computer allowed only 3 decimals, ya computers were lousy back in 1961. Well what was the result, a perfect clear afternoon turned into a stormy one !!! So the phrase ‘butterfly effect’ was born, a bantam variation in the cause can lead to large variations in the effect. The tiny atmospheric changes created by the flapping of a butterfly’s wings in Indonesia can alter, avert or delay a hurricane in Brazil. I knew I would convince you 😀

 

 

Later this was the base of the Chaos Theory, which says that slight changes in the initial state of a deterministic system can make the final state random or chaotic. Chaos theory then moved on and contradicted Newton’s theory of a perfectly predictable universe. Indeed butterfly effect is awesome, after all a mere 0.000127 contradicted Newton’s theory of a perfectly ordered universe…

Random mystery … Solved

After a de-motivating disscussion last evening with my cousin, I decided to prove him wrong. Thats what I was thinking looking at my RSA security token (used for authenticated electronic logins) I decided to find out how it worked. A RSA token is a electronic device which produces random numbers, users key in these numbers to log into a internet site or such electronic device. What baffled me was if it was a random number then how was it authenticated ?

After some “googling” and a few rounds of wikipedia the answer was there. The concept behind this mysterious theory was a random number generation algorithm. All the algorithm had to do was generate a set of random numbers based on some input parameters. So if two machines run the same algorithm and the same input parameters are keyed in then “EUREKA”, you have the same set of random numbers. Although some people would say that it is a sin to utter random and same in the same line but it is the truth. The program needs to create same random numbers at two different places yet it should be flexible enough to create multiple set of numbers and should be robust enough so that a simple brute force algorithm should not break it. How do they do it ? No let me re-phrase it I want to do it ? was my next question.

Back to drawing board, some more googling and a quick refresh of college mathematics opened the doors. What I could conclude is demonstarted in the below mathematical formulas:

INPUT:  (Key, Seed)
OUTPUT: random_number, (Key’, Seed’)
   random_number = F(Key, Seed)
   Key’ = F(Key, Seed+1)
   Seed’ = F(Key’, Seed)
   return random_number
F -> Mathematical Function like :

F(a,b)
{
 return (a * b)
}

Key’ and Seed’ are new key and seed values to decide the next random number.

Anyone with knowledge of mathematics can understand the above formula’s. A function accepts two parametrs (key and seed) then produces a random number using a mathematical formula. The function is again used to create new seeds and keys which result in a fresh new random number. By resetting the key and seed values the random number is re-shuffled enough and will not repeat. So if a time-coupled system running such an algorithm is fed with the same key and seed values will keep generating the same random numbers. Say if both systems generate a random number every 60 secs that number can be used as a password which will expire in the next 60 secs. Thats what RSA security token is. The token keeps generating a random number and a server runs the same program and keeps generating the same numbers and is hooked on to an application. The user having the token enters it and it is checked with the number on the server if OK then you are in ! Each token starts for with its own key and seed value thus multiple tokens can be used by multiple users there by increasing the re-usability of the algorithm. This kind of technology is widely used in internet applications (particularly banking industry). 

Is this algoritm programable? Yes it was, below is a small shell script written by me to demonstrate the computer programability of the above discussed algorithm. The script uses a 5 digit key and a 1 digit seed to generate random numbers every 5 seconds. The below code has no copyrights and can be used by anyone.

Atlast I have proved my might and I stand a step closer to my goals. 

Code :

#!/bin/sh
### Author Prasanjit Tripathy (tripp0) 03/03/08 ###
### A shell script to create random numbers ###
### This script produces a random number every 5 seconds ###
### The key is the process id and seed is the last digit of the pid ###

#get seed and key
key=`echo $$`

seed=`expr $key % 10`
if [ $seed -eq 0 ]
        then
        seed=`expr $seed + 1`
fi

#create random function

randomize ()
{
        output=`expr $1 * $2`
        return $output
}

#Loop through
while [ 1 ]
do

 #Generate random number

 randomize $key $seed
 return_op=$?
 return_op=`echo $return_op | sed ‘s/^(…..).*$/1/’`
 echo “Next Random number is $return_op”

 #Create new key
 randomize $key `expr $seed + 1`
 key=$?
 key=`echo $key | sed ‘s/^(…..).*$/1/’`

 #Create new Seed
 randomize $key $seed
 seed=$?
 seed=`echo $seed | sed ‘s/^(.).*$/1/’`

 sleep 5
done

exit 0

All views expressed in the blog are the views of the Author at that instant of space-time continuum and Author reserves the right to change, invert or altogether deny any of the views.