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.