Monthly Archives

January 2013

Passwords

Authentication of Users and Passwords in Python

January 29, 2013

Before we dive in to the topic, I would like to apologies. Over the past 10 days, I have had multiple matters that require my attention. While I try to allocate some time for everything, this blog has not been on the top of my priorities. This was a mistake, I now realize. I should have anticipated some of the issues and plan ahead accordingly. The opposite is what happened. I cannot say this will not happen again, I can only apologies and try to do better in the future. So let us get started.

The last post I wrote talked about how to password protect your python program. Although this is very neat and sufficient in most cases, what you really need is a method to authenticate users and password. This post will be rather simple and straight to the point. Much of the work it relies on we have done already. Recall at this point we are storing the password as encrypted strings in a file, independent of our python program. Now we just have 2 things we have to do. We will start by recognizing a single user and allow him/her accesses. Then, we will expand the program to allow multiple allowed users accesses. As noted before, we are going to use Python2.7, I strongly encourage referring to the documentation or download the documentation for python2.7 for offline reference.

As we did previously, before we can authenticate any user we have figure out how we want to store the data we are comparing to. You may recall we used a support program to create a file and store the password. Now we will extend the “helper” script to store a user name on a single line, followed by the encrypted password in the next line. This format may be modified at your discretion. For example, you may choose to encrypt both the user name and the password. You may also choose to have all the information as a single line, separated by a vertical line, ‘|’, or a comma, ‘,’. The options are multiple, but the principle is the same. Assuming we follow the first suggested format, here is how the code to store a user name and password will look like:


import sys
import hashlib
import getpass

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: store_user_pass.py <file_name>')

	print '\nUser & Password Storage Program v.01\n'
	
	if raw_input('The file ' + sys.argv[1] + ' will be erased or overwrite if exsting.\nDo you wish to continue (Y/n): ') not in ('Y','y') :
		sys.exit('\nChanges were not recorded\n')
	
	user_name = raw_input('Please Enter a User Name: ')
	password = hashlib.sha224(getpass.getpass('Please Enter a Password: ')).hexdigest()

	try:
		file_conn = open(sys.argv[1],'w')
		file_conn.write(user_name + '\n')
		file_conn.write(password + '\n')
		file_conn.close()
	except:
		sys.exit('There was a problem writing to the file!')

	print '\nPassword safely stored in ' + sys.argv[1] + '\n'		
			
if __name__ == "__main__":
	main(sys.argv[1:])

Note that the changes from our previous version, store a single encrypted password, have not changed much. The main thing we have done is added a user_name variable that gets written to the file. As before, we warn the user from alteration of a file might already exist. Here is an example output of the program:

wpid-userandpasswordstorage-2013-01-21-16-37.png

Here are the content of the file pass_db.txt:


cptdeadbones
99fb2f48c6af4761f904fc85f95eb56190e5d40b1f44ec3a9c1fa319

Now we are ready to see how the other side of this program might look like. Since we know how to verify the password, adding the user name option is not much change. For our application purpose, we will terminate the program if the user name is not known or x password attempts have been made. Here is how the code for this will look like:


import sys
import hashlib
import getpass

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: user_pass.py <file_name>')

	print '\nUser & Password Authentication Program v.01\n'

	try:
		file_conn = open(sys.argv[1])
		user_name = file_conn.readline()[:-1]
		password = file_conn.readline()[:-1]
		file_conn.close()
	except:
		sys.exit('There was a problem reading the file!')
		
	pass_try = 0 
	x = 3
	
	if raw_input('Please Enter User Name: ') != user_name:
		sys.exit('Incorrect User Name, terminating... \n')
	
	while pass_try < x:
		user_input = hashlib.sha224(getpass.getpass('Please Enter Password: ')).hexdigest()
		if user_input != password:
			pass_try += 1
			print 'Incorrect Password, ' + str(x-pass_try) + ' more attemts left\n'
		else:
			pass_try = x+1
			
	if pass_try == x and user_input != password:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'		
			
if __name__ == "__main__":
	main(sys.argv[1:])

Running the code with the file we generated before, pass_db.txt:

wpid-userpassverify-2013-01-21-16-37.png

Like previous programs, the user is prompt for a password 3 times. At each trial the user is notified the number of password attempts reaming. At this point, if you have been following along, you should be able to pice together how this might be extended to multiple users. For our final version we will have 2 python files, one to generate a password file and the other to log the user in. The modification for the storage code needed at this point are minimal, all we need to change is the mode we write to the file. In previous versions we used ‘w’ for write mode. Now we are going to use ‘a’, which is only going to append the new information to the end of the file. If the file is not yet created, the file will be created.You can look users and password storage program.

Last but not least, here is our final version of the authentication module. First the code:


import sys
import hashlib
import getpass

def process_file(file_name):
	
	user_names = []
	passwords = []
	
	try:
		file_conn = open(file_name)
		data = file_conn.readlines()

		for i in range(len(data)): 
			if i%2 == 0:
				user_names.append(data[i][:-1])
			else:
				passwords.append(data[i][:-1])
			
		file_conn.close()
	except:
		sys.exit('There was a problem reading the file!')
		
	return user_names, passwords

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: user_pass.py <file_name>')

	print '\nUser & Password Authentication Program v.01\n'

	user_names, passwords = process_file(sys.argv[1])
		
	pass_try = 0 
	x = 3
	
	user = raw_input('Please Enter User Name: ')
	
	if user not in user_names:
		sys.exit('Unkown User Name, terminating... \n')
		
	while pass_try < x:
		user_input = hashlib.sha224(getpass.getpass('Please Enter Password: ')).hexdigest()
		if user_input != passwords[user_names.index(user)]:
			pass_try += 1
			print 'Incorrect Password, ' + str(x-pass_try) + ' more attemts left\n'
		else:
			pass_try = x+1
			
	if pass_try == x:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'		
			
if __name__ == "__main__":
	main(sys.argv[1:])


So what is different? Now instead of just reading one user name and password, we read more. The information is stored in 2 (2things) lists that have corresponding indexes. So the user name at index 1 has an encrypted password stored at index 1 of the password list. All other operation are the same as any previous example. I do not think there is a need to include an input, it is the same as before.

For a final remark, I realize that the method I discussed in this and the previous post and this one are not very secure or useful outside of an educational exercise. In ‘real world’ applications the information will be stored in a database. There are some software that has already been pre written for user authentication in python. The bottom line is that user authentication is not enough to protect an application. There are several more methods we may or may not cover in the future. For the near time, we will start to look into security algorithms and application.

Cool Stuff

I Have to Build One of These Someday

January 20, 2013

Cool Stuff

Tablet that is More Than a Touch Screen

January 18, 2013

http://www.youtube.com/watch?feature=player_embedded&v=2N0E4Y991zc#!

Passwords

Password Protecting Your Python Application

January 18, 2013

Couple weeks back we talked about how to generate passwords in python. Now, I would like to explore how to password protect your application. We will be using Python again, only this time I will upgrade to Python2.7 due to popular demand. You can reference to Python2.7 the documentation or download Python2.7 documentation.

There are many situations in which you would like to password protect the application. It could be just a simple application you do not want anyone else to run, or it could be an application that stores sensitive data. The two things you need to keep in mind is that authentication is independent of the application and that we are discussing application authentication. That is, the ideas may apply to web, mobile & other applications, however, we are going to limit this discussion to python application.

Lost You Password?<a href="http://c9d568r8ox3aii95ujuky1vcxo.hop.clickbank.net/" target="_top">Click Here!</a>

Let us start by assuming there is an application we wish to secure. For demonstration purpose, the application will simply print out:

User is logged in!

Otherwise an appropriate error message will be displayed. We can agree that the print statement can be replaced with a function call to start an application. We are going to start with the simplest case. We have a string password that is stored in a variable. We prompt the user for a password. If the user input does not match the stored password, we terminate the application without letting the user log in. Here is what that would look like in code:


import sys

def main():

	print '\nPassword Request Program v.01\n'

	password = 'abcd'
	user_input = raw_input('Please Enter Password: ')

	if user_input != password:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'

if __name__ == &quot;__main__&quot;:
	main()

And the output of the program in both cases:

password auth 1_1

password auth 1_2

You can see that the first time the user entered ‘password’ for the password. The program recognizes an incorrect password and is terminated. The second time the user entered the correct password ‘abcd’ and the user was successfully logged in. For a simple application, this might be enough. However, we are going to take this idea much further. To start, let us add the ability for the user to try to enter a password x amount of times before the program is terminated. For now, let us assume x is 3. You might change the value of x to any number you wish. Our modifed program might look like this:


import sys

def main():

	print '\nPassword Request Program v.02\n'

	password = 'abcd'
	pass_try = 0
	x = 3

	while pass_try &lt; x:
		user_input = raw_input('Please Enter Password: ')
		if user_input != password:
			pass_try += 1
			print 'Incorrect Password, ' + str(x-pass_try) + ' more attempts left\n'
		else:
			pass_try = x + 1

	if pass_try == x and user_input != password:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'

if __name__ == &quot;__main__&quot;:
	main()

Sample output:

password auth 2_2_2

password auth 2_2_1

If you examine the code you might notice a few different things. We have a while-loop that runs for x amount of times. This might be replaced with a simple for-loop, but keep in mind that there is no guarantee that the user will need any incorrect attempts. In addition, if you do use a for loop, you might need to use a break statement, which is not a good programming habit. You might also notice that that the program notifies the user how many attempts he or she has left. This is not required, but as a user it is nice to know.

As you examine the code, you will soon realize that storing the password in the code as a string is not the best practice. Let us move the password into a file. This way we can separate the password from the program. The path for the file will be given as a command line argument. The file can by anywhere in the file system, including on a USB drive. Without it, the program will not run and terminate immediately. For this example, we will store the password in a plain txt file called pass_file1.txt. Here is the content of the text file:


abcd

Here is our new version, using the file to store the password:


import sys

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: pass_auth3.py &lt;file_name&gt;')

	print '\nPassword Request Program v.03\n'

	try:
		file_conn = open(sys.argv[1])
		password = file_conn.readline()[:-1]
		file_conn.close()
	except:
		sys.exit('There was a problem reading the file!')

	pass_try = 0
	x = 3

	while pass_try &lt; x:
		user_input = raw_input('Please Enter Password: ')
		if user_input != password:
			pass_try += 1
			print 'Incorrect Password, ' + str(x-pass_try) + ' more attempts left\n'
		else:
			pass_try = 4

	if pass_try == x and user_input != password:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'

if __name__ == &quot;__main__&quot;:
	main(sys.argv[1:])

And here is some sample output. Notice that the first try is without giving the program a path to a file.

password auth 3_2_1
password auth 3_2_2
password auth 3_2_3

Take a closer look at the code. You will notice that there is more than one way the program can might terminate. If a file is not provided the program will terminate immediately. If there are any issues reading the file the program will terminate. Finally, if the password is incorrect more than x times the program will terminate. When reading from the file we use the readline() method. This will read an entire line from the file, including the newline character ‘\n’. This is why there is an added [:-1] to trim the string to not include the newline character.

So far we have seen how to ask for a simple password. However, this is far from a real-world application strength. The problem is that the password is stored as a plain text file. This means that if anyone was to open it, they will know your password immediately. As a good programmer, you do not want a client to find out their secure passwords are stored in plain text. Much less a user finding that out. Or worse. To solve this problem we will introduce 2 (2things) new ideas. First a method to avoid seeing the characters as the user types. Second, we will encrypt the password we store in the file using one way encryption.

In order to hide the password while the user is typing, we will use a python standard library named getpass. The library is quite small, but provides exactly what the name suggests and nothing else. Here is a simple example of how the library works:

wpid-getpassexample-2013-01-17-20-47.png

Basically, getpass.getpass() is equivalent to using raw_input(), but hides the typed characters. I think it is rather straight forward why you should use this library when asking a user for a password. Moving on to the second thing, we need a way to encrypt our password. Furthermore, we want our password encrypted using a one way encryption method. This means that once we encrypt the data, there is no simple function to retrieve the data. Python has a multiple ways to achieve this using standard library functions. We will use a built-in library called hashlib that provides many encryption methods. I choose to follow on of the examples and use sha224 with conversion to hex. Here is an example of using sha224:

wpid-shaexample-2013-01-17-20-47.png

You can see that the encrypted string has nothing to do with the string ‘password’. So how are we going to use one way encryption? Simple, we are going to store the original encrypted password in the file. Then when the user enters a password we will encrypt the user input exactly the same way and compare the encrypted string from the file. If we do not use the same encryption algorithm, this method will not work. You may change the encryption algorithm to what every method you like. Since we need to encrypt the passwords, we will need a helper program to store the password before we modify the authentication program. Here is an example program to store the an encrypted password:


import sys
import hashlib
import getpass

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: store_pass.py &lt;file_name&gt;')

	print '\nPassword Storage Program v.01\n'

	if raw_input('The file ' + sys.argv[1] + ' will be erased or overwrite if existing.\nDo you wish to continue (Y/n): ') != 'Y' :
		sys.exit('\nChanges were not recorded\n')

	password = hashlib.sha224(getpass.getpass('Please Enter a Password: ')).hexdigest()

	try:
		file_conn = open(sys.argv[1],'w')
		file_conn.write(password + '\n')
		file_conn.close()
	except:
		sys.exit('There was a problem writing to the file!')

	print '\nPassword safely stored in ' + sys.argv[1] + '\n'

if __name__ == &quot;__main__&quot;:
	main(sys.argv[1:])

Here is an example output for this program:

wpid-storepass1-2013-01-17-20-47.png

The program is fairly simple. First we verify that the user acknowledges that if the file exists already it will be erased. There are other ways around this, but this is one of the simple solutions. You do not want to assume the user entered the right file name the first time. If you were to use a file name that already exists, the file will be permanently altered. Since we opened the file in write mode, we will erase any information already there. This is why you should double check that the user entered the correct file name. Of course, you do not have to do it and you may erase the associated if statement.

As a last note, we do not store the plain value of the password in a variable. Instead it is transferred directly to the encryption method. This offers some extra security to you program. Finally, we write the information to the file and terminate the program. If we were to look at the content of pass_file2.txt we will see something like this:


a76654d8e3550e9a2d67a0eeb6c67b220e5885eddd3fde135806e601

Now we are ready for our final version of password authentication, using the encrypted password file. Here is the code for it:


import sys
import hashlib
import getpass

def main(argv):

	if len(argv) != 1:
		sys.exit('Usage: pass_auth3.py &lt;file_name&gt;')

	print '\nPassword Request Program v.04\n'

	try:
		file_conn = open(sys.argv[1])
		password = file_conn.readline()[:-1]
		file_conn.close()
	except:
		sys.exit('There was a problem reading the file!')

	pass_try = 0
	x = 3

	while pass_try &lt; x:
		user_input = hashlib.sha224(getpass.getpass('Please Enter Password: ')).hexdigest()
		if user_input != password:
			pass_try += 1
			print 'Incorrect Password, ' + str(x-pass_try) + ' more attempts left\n'
		else:
			pass_try = 4

	if pass_try == x and user_input != password:
		sys.exit('Incorrect Password, terminating... \n')

	print 'User is logged in!\n'

if __name__ == &quot;__main__&quot;:
	main(sys.argv[1:])

Notice that not much has changed. What we have added is applying the same encryption method we did to the file, to the user input. Here is how the program looks like when it runs:

password auth 4_1

password auth 4_2

We have explored adding a password security to your python program. If you really want to use it, you will need to conceal your code. One way to conceal your code is to compile code to a pyc file. This is just one way you might do this. There are other methods you could explore to create executable from p a py file. We will not explore them within this post. For the moment, I will leave you with a pyc file and a file containing an encrypted password. The application will have a unique output. Can you make the application run?

pyc riddle file
passwod file

Cool Stuff

PaperTab - Behold the Future is Near

January 16, 2013

Mathematics

The Easy Way to Solve Equations in Python

January 15, 2013

Over the past few days I was debating what I should write about next. I really enjoy sharing my thoughts and have been getting great responses from my readers. I thanks you for your comments. At your request I have decided to cover another math topic, solving equations using python. Equation solving is something fundamental in computing, mathematics and other scientific applications. Using computers enables users to solve a wider range of equations than we could by non-computer methods. However, there is a cost at hand, accuracy. Although computers can solve equations using a few methods, we will witness that accuracy will change between methods. In some cases you might not get to a solution at all.

Before we dive into code behind solving equations, let us step back. A good programmer should always consult other resources to see what else has been done already. The Internet (and Google) have given us great tools to research any topic our heart desires. There are many tools available to solve equations and do almost any other mathematical calculations. Matlab and Matamatica are both great mathematical softwares that can do amazing things. However, they are paid distributions. I do not have anything against paid software, but for the sake of educational useage I would like to keep everything in the realm of free (open source preferred). I like to post code that anyone can download, run, modify, distribute or do anything else they would like to do with it. Using paid languages will be counter productive to such goals and limit the readers of this blog. That being said, if there is a request I will put up Matlab code for the algorithms discussed in this post.

On another note, we will be using Python2.6 for all the examples that are to follow. We will not be using NumPy or SciPy. Both are great scientific math tools but an over kill for what we are trying to do. Our mission is simple, solving an equations. More precisely, we want to figure out where a given function intersect the x-axis without using “the big guns”, including Wolfram-Alpha. So let us get to it.

The Bisection Method:

At out first stop, the most fundamental approach to solving equations is the Bisection Method. Here is the theory in a nutshell:

“If f is a continues function on [a,b], where f(a)f(b) < 0, there must be a point r between a and b where f(r) = 0”

So what does this means? It means that if we have a function that cross the axises between point a and b, then the value of the function at f(a), multiplied by the value of the function at b, f(b), must be smaller that 0. Further more between a and b there is a point where the function f is 0. Here is a picture describing such event:

wpid-bisectiongraph-2013-01-15-18-58.png

Here is a general solution in code that does exactly that:


def bisection(a,b,tol):
	c = (a+b)/2.0
	while (b-a)/2.0 > tol:
		if f(c) == 0:
			return c
		elif f(a)*f(c) &lt; 0:
			b = c
		else :
			a = c
		c = (a+b)/2.0
		
	return c

Notice that we have a while loop that runs while we are within tolerance and that we assume function f(x). The latter part can be solved by writing a function f that outputs the desired function. Here is the function we are going to work with:

 x^3 + x - 1

And here is the python equivalent:


def f(x):
	return x**3 + x -1

Once we add the code together we can run it and get a solution within tolerance. What is the tolerance? The Bisection method literally cuts in half the solution at each iteration, assuming the mid point between a and b is the solution. So in theory we can keep asking for a more accurate solution by setting a lower tolerance. The “real” solution to the function according to Wolfram Alpha is 0.6823278... We will use this solution as a guide to compare the accuracy of solutions we compute. Here are a few outputs for our code, for a solution between 0 and 1 using various tolerances:

(The full code for the Bisection Methon in Python)

wpid-bisectionoutput2-2013-01-15-18-58.png

As you can see, the first solution is only accurate to 2 decimal places. If we tried a lower tolerance we would have got maybe one or none of the digits correct. When we increased our tolerance we arrive to a more accurate solution, within tolerance range. Bisection is a good method to use when it applies. The Bisection method will not work on all functions, but is a quick solution to many equations.

Fixed Point Iteration (FPI)

Fixed point iteration is another method of solving equations. The definition of a fixed point r is when g(r)=r. Using this definition, we start with some initial guess, x and plug it into the function. However, unlike bisection, this method does require us to do some math work before code. We have to transform our function to be in the form x=g(x). This is where the heart of FPI is. Based on your setup and initial guess, you may reach a solution really fast, or not at all. Here is how the code for FPI looks like:


def fpi(x, k):
	for i in range(k):
		x = g(x)
	return x

You will note that now we are no longer using a while loop. FPI could be setup in a smilier way to Bisection, but for simplicity is setup in a fixed i-loop. Using the same function as before, let us say we transform the function to be like this:

 x = \sqrt[3]{1-x}

And in python (using python’s math library):


def g(x):
	return math.pow(1-x,1/3.0)

You will notice that python only has a square root function. For any other roots we use python’s power function. Please remember that 1/3 in integer division is 0. Therefore, we have to use 1/3.0 to get the cubic root. Running the program for 10 iterations starting at 0.5 yields the following output:

(The full code for Fixed Point Iteration in Python)

wpid-fpiroot-2013-01-15-18-58.png

This is not very close, we only have 1 digit and we started close to the solution. If we let the program run for 100 iterations we get really close to the solution:

wpid-fpiroot100-2013-01-15-18-58.png

How many iteration do you need? It depends on your function. A variation on this function might solve it in 7 iterations (can you find the function?). Again, in FPI it depends on the setup and the initial guess. As a rule of thumb, it will either conversation very fast, or not at all. But then again, sometimes it just needs one or more steps.

Newton’s Method

Our next stop, and the basis for our next method, is Newton’s method. In this case, like FPI we start with an initial guess and keep redefining x, however, we use this function to find the next x :

 x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}

Newton’s method adds another math task we will have to do outside of our code, taking the derivative. We will see that the last method will take care of this, but at another cost. Here is how Newton’s method will look like in code:


def newt(x,n):
	for i in range(n):
		x = x - f(x)/f_prime(x)
	return x

This means we will have to define our original function as well as a derivative (prime) function. Not a problem, we can use the same function we have been solving all along. This is what it will look like:

 f(x) = x^3 + x - 1
 f'(x) = 3x^2 + 1

And in Python:


def f(x):
	return x**3 + x - 1

def f_prime(x):
	return 3*x**2 + 1

Before we run our code, we need to take care of one special case. What if the derivative is 0 or end up computing to 0? Than we will have a division by zero error. This can be simply avoided by a couple of if statements. Like so:


def newt(x,n):
	for i in range(n):
		if f_prime(x) == 0:
			return x
		x = x - f(x)/f_prime(x)
	return x

This should take care of any division by zero errors. However, do not take my word for it, try it out for yourself!

And now running the code, using -0.7 as our initial x for 10 iterations will yield:

(The full code for Newton’s Method in Python)

wpid-newtonsmethod-2013-01-15-18-58.png

If you add some debug statements and examine the output you will note that the solutions was found after only 7 iterations. That is really fast and a lot better than 100 iterations of FPI. You might have output like this:

wpid-newt_output-2013-01-15-18-58.png

Secant Method

Although Newton’s method works really well, taking derivatives is not always an option. For that, there is another method, mathematically based on Newton’s method and the definition of derivatives. This time we start off with 2 initial guesses and move forward by using one of the guess and a new point. The new point is calculated from the formula:

 x_{i+2} = x_{i+1} - \frac{f(x_{i+1})(x_{i+1}-x_i)}{f(x_{i+1}) - f(x_i)}

In Python the Secant Method might look like this:


def secant(x0,x1,n):
	for i in range(n):
		x_temp = x1 - (f(x1)*(x1-x0)*1.0)/(f(x1)-f(x0))
		x0 = x1
		x1 = x_temp
	return x1

Note that there is a chance that we will be dividing by 0, again we must add a check to ensure that this does not happen. Also note that we use a temp variable to swap values around. This is so we do not require much memory. A new, modified version of the Secant method might look like this:


def secant_2(x0,x1,n):
	for i in range(n):
		if f(x1)-f(x0) == 0:
			return x1
		x_temp = x1 - (f(x1)*(x1-x0)*1.0)/(f(x1)-f(x0))
		x0 = x1
		x1 = x_temp
	return x1

As before, we are using for loops, which might be swapped to while loops. I recommend you try it your self, but remember, while loops must terminate at some point. Running the Secant code starting with 0 and 1 for 10 iterations, on out “famous” function yields the following output:

(The full code for Secant Method in Python)

wpid-secantoutput-2013-01-15-18-58.png

We have gone over 4 basic methods of solving equations. There are many more approaches to solve equations, this is by no means a complete survey. I trust that if you are in need for more information you can find it using a friendly search engine. Note that there is still much to say about the accuracy of the solutions computed by these methods. Also note that there are some programming “tricks” that can be done to shorten calculation. For more accurate mathematical definitions and information please seek out a mathematician.

This post was made possible by Numerical Analysis by Timothy Sauer

Cool Stuff

Morse Code and Dictionaries in Python (with Sound)

January 8, 2013

Mose Code is an old method of transmitting text messages. Morse Code dated back to around mid 1800s. The basics of morse code is timing and pulse. Each combination corresponds to an Latin alphbet character or number. Morse Code can also be transmitted visually using a light source by alternating the light on and off. If you are in need of more information about Morse Code I suggest Wikipedia Morse Code entry a a good starting place.

So why implement morse code? Well, because we can. Programming Morse Code is very easy and a great challenge for beginners. I also found very little resource that implemented Morse Code with sound. There is a lot of code around the web to print out Morse Code in python, but I could not find one that outputs sound. As an added benefit you get exposed to something you might need in the future. Morse code is still in use and may save your life. (I know, this is a little extreme). We represent Morse Code on the screen by a dots and dashes. Dots are one unit length, while dashes are three. Here is an example of SOS, the international distress signal:

wpid-SOS_morse_code-2013-01-8-08-28.png

Although there is an international agreement about SOS signal, some of symbols in Morse Code have no standard. For the scope of this article let us limit our discussion to the International Morse Code, which is limited to alphabet and the numbers 0 to 9. As you will see, the program can be modified to represent more symbols to your wishes. Here is the guideline to Morse Code as we will use it:

wpid-450px-International_Morse_Code.svg-2013-01-8-08-28.png
Let us deal with the latter part first, the letters and digits. We will get to the top part in a little bit. Different languages have different data types at you disposal. Python has a tool that fits this problem like a glove, dictionaries. You can read up on python’s dictionaries documentation or download python2.6 documentation. The idea behind dictionaries is that we can map keys to values. Lists in python are numeric indexed from 0 up (lists are also reversed indexed). Dictionaries store data by assigning a key and a particular value. So for example we can initiate an empty dictionary and store the value ‘.-‘ for the key ‘A’. Then we can retrieve the value for key ‘A’ via indexing.

wpid-dictionariesinpythonexample1-2013-01-8-08-28.png

We can also initiate a dictionary with values:

wpid-dictionariesinpythonexample2-2013-01-8-08-28.png

Note that since there was no value for key ‘C’ we got an error. If we want our program to run correctly, we will need to address this issue, but not at the moment. So using a dictionary for our alphabet and numbers and using python’s string properties we can write a fairly simple program that will output text Morse Code. Lets look at the basic implementation of Morse Code:


CODE = {'A': '.-',     'B': '-...',   'C': '-.-.', 
        'D': '-..',    'E': '.',      'F': '..-.',
        'G': '--.',    'H': '....',   'I': '..',
        'J': '.---',   'K': '-.-',    'L': '.-..',
        'M': '--',     'N': '-.',     'O': '---',
        'P': '.--.',   'Q': '--.-',   'R': '.-.',
     	'S': '...',    'T': '-',      'U': '..-',
        'V': '...-',   'W': '.--',    'X': '-..-',
        'Y': '-.--',   'Z': '--..',
        
        '0': '-----',  '1': '.----',  '2': '..---',
        '3': '...--',  '4': '....-',  '5': '.....',
        '6': '-....',  '7': '--...',  '8': '---..',
        '9': '----.' 
        }


def main():
	
	msg = raw_input('MESSAGE: ')
	
	for char in msg:
		print CODE[char.upper()],
		
if __name__ == &quot;__main__&quot;:
	main()


python morse code example

You will notice that we use a string method named upper() to force the input to match our keys. There is a big difference between ‘A’ and ‘a’ in computer programs, they two different keys. So now that we have a basic python morse code script, let us try to improve on it. In our first program we really cannot transfer more than one word. All the words will be concatenated together. According to our code from above we need to modify our script to the following rules:

  1. The length of a dot is one unit
  2. A dash is three units
  3. the space between parts of the same letter is one unit
  4. the space between letters is three units
  5. the space between words is seven units

Until we move on to sound, the first 4 rules are implicitly implemented. What we really need is a space between the words. To do this we will add 7 space for every 1 space in the input, like so:


CODE = {'A': '.-',     'B': '-...',   'C': '-.-.', 
        'D': '-..',    'E': '.',      'F': '..-.',
        'G': '--.',    'H': '....',   'I': '..',
        'J': '.---',   'K': '-.-',    'L': '.-..',
        'M': '--',     'N': '-.',     'O': '---',
        'P': '.--.',   'Q': '--.-',   'R': '.-.',
     	'S': '...',    'T': '-',      'U': '..-',
        'V': '...-',   'W': '.--',    'X': '-..-',
        'Y': '-.--',   'Z': '--..',
        
        '0': '-----',  '1': '.----',  '2': '..---',
        '3': '...--',  '4': '....-',  '5': '.....',
        '6': '-....',  '7': '--...',  '8': '---..',
        '9': '----.' 
        }


def main():
	
	msg = raw_input('MESSAGE: ')
	
	for char in msg:
		if char == ' ':
			print ' '*7,
		else:
			print CODE[char.upper()],
		
if __name__ == &quot;__main__&quot;:
	main()


wpid-pythonmorsecode4-2013-01-8-08-28.png

You can also modify the program to print a newline after each word and more spaces between letters. This will look like this: (full morse code code)

for char in msg:
	if char == ' ':
		print 
	else:
		print CODE[char.upper()] + '  ',

wpid-pythonmorsecode5-2013-01-8-08-28.png

Before we move on to sound, there is one more thing I would like to address, errors. Since we do not have all possible input, our program might raise and error. Foe example, if we tried to convert and email address to Morse Code we will have an error since ‘@‘ and ‘.’ are not keys in the dictionary. Here is what will happen if we tried to convert ’cpt@thelivingpearl.com’ to Morse Code:

wpid-pythonmorsecode6-2013-01-8-08-28.png

That is not good. You can see that the program started to translate, but got stuck along the way. There are several way to handle this, including non at all. A simple way to solve this issue is by scanning the output and checking its values against the dictionary keys. We can do this by using a keys() function of our CODE dictionary. If we find values that we cannot translate to Morse Code, we will notify the user and terminate the program.


import sys

CODE = {'A': '.-',     'B': '-...',   'C': '-.-.', 
        'D': '-..',    'E': '.',      'F': '..-.',
        'G': '--.',    'H': '....',   'I': '..',
        'J': '.---',   'K': '-.-',    'L': '.-..',
        'M': '--',     'N': '-.',     'O': '---',
        'P': '.--.',   'Q': '--.-',   'R': '.-.',
     	'S': '...',    'T': '-',      'U': '..-',
        'V': '...-',   'W': '.--',    'X': '-..-',
        'Y': '-.--',   'Z': '--..',
        
        '0': '-----',  '1': '.----',  '2': '..---',
        '3': '...--',  '4': '....-',  '5': '.....',
        '6': '-....',  '7': '--...',  '8': '---..',
        '9': '----.' 
        }

def verify(string):
	keys = CODE.keys()
	for char in string:
		if char.upper() not in keys and char != ' ':
			sys.exit('Error the charcter ' + char + ' cannot be translated to Morse Code')

def main():
	
	msg = raw_input('MESSAGE: ')
	
	verify(msg)
	
	for char in msg:
		if char == ' ':
			print ' '*7,
		else:
			print CODE[char.upper()],
		
if __name__ == &quot;__main__&quot;:
	main()

wpid-pythonmorsecode7-2013-01-8-08-28.png

Now we have a complete morse code program. How about we add some sound to this? To add the sound we will utilize PyGame (download PyGame). We can download sound files for Morse Code from wikimedia commons. I have conviently downloaded all the sound files and made them available to download Mose Code Sounds in zip format. There is an example python script inside the zip file that plays a sound example called play_ogg.py, here is what it looks like:


import pygame
import time
pygame.init()

pygame.mixer.music.load(&quot;A_morse_code.ogg&quot;)
pygame.mixer.music.play()
time.sleep(1)

This script will output the letter ‘A’ in morse code. Make sure you have your speakers on. Here is how are program will look like with the added sound files.


import sys
import pygame
import time

CODE = {'A': '.-',     'B': '-...',   'C': '-.-.', 
        'D': '-..',    'E': '.',      'F': '..-.',
        'G': '--.',    'H': '....',   'I': '..',
        'J': '.---',   'K': '-.-',    'L': '.-..',
        'M': '--',     'N': '-.',     'O': '---',
        'P': '.--.',   'Q': '--.-',   'R': '.-.',
     	'S': '...',    'T': '-',      'U': '..-',
        'V': '...-',   'W': '.--',    'X': '-..-',
        'Y': '-.--',   'Z': '--..',
        
        '0': '-----',  '1': '.----',  '2': '..---',
        '3': '...--',  '4': '....-',  '5': '.....',
        '6': '-....',  '7': '--...',  '8': '---..',
        '9': '----.' 
        }
        
ONE_UNIT = 0.5
THREE_UNITS = 3 * ONE_UNIT
SEVEN_UNITS = 7 * ONE_UNIT
PATH = 'morse_sound_files/'

def verify(string):
	keys = CODE.keys()
	for char in string:
		if char.upper() not in keys and char != ' ':
			sys.exit('Error the charcter ' + char + ' cannot be translated to Morse Code')

def main():
	
	msg = raw_input('MESSAGE: ')
	verify(msg)
	
	pygame.init()
	
	for char in msg:
		if char == ' ':
			print ' '*7,
			time.sleep(SEVEN_UNITS)
		else:
			print CODE[char.upper()],
			pygame.mixer.music.load(PATH + char.upper() + '_morse_code.ogg')
			pygame.mixer.music.play()
			time.sleep(THREE_UNITS)
		
if __name__ == &quot;__main__&quot;:
	main()


Here is a short video demonstrating ‘SOS’ in Morse Code:

Here is another video transmitting ‘HELLO WORLD’ in Morse Code:

As a last note. We have gone through how to successfully encode and transmit a message into Morse Code. That is only half the problem. To decode a text message in Morse Code, you can reverse the dictionary and have the Morse Code as keys and alphabet as values. This is rather trivial and you can see this as a challenge. To decode the sound waves, this will require more effort. Maybe one day I will have the time to write some code for that. For now, you can write your own code to decode morse code, or you can decode it using the image from the top of this post. Either way, this was fun.

Mathematics

How to Find Prime Numbers in Python

January 6, 2013

To mathematicians prime numbers represent a certain Nobel challenge. They have been studying prime numbers for a while, trying to learn their properties. Some mathematicians actually made progress. Others have gone insane trying to prove a pattern or how to generate the nth prime. Some are actively looking for the largest prime they can find. For computer scientists and programmers prime numbers have properties that can be utilized in many areas. Cryptography and pseudo-random number generators are 2 examples applications of prime numbers. Let us take a dive into the world of prime numbers. We will look at how we can generate and validate prime numbers in python.

Any valid math discussion must begin with a definition. Here is a definition of prime numbers I like to use:

“A natural number p > 2 is called prime if and only if the only natural numbers that divide p [without reminder] are 1 and p. A natural n > 1 that is not prime is called composite. Thus,, n > 1 is composite if n = ab, where a and b are natural numbers with a > 1 and b < n. “ Discrete Mathematics with Graph Theory

What does this means? It means that a number, for example 17, is prime if and only if it can be divided only by 17 and 1. On the other hand, 18 is not prime. 18 is a composite number that can be written as 2 x 9 or 3 x 6. This will prove to be a very useful property.

So how do we find prime number? Well, we do not. Or not exactly. Since the natural number are infinite and a prime number can be any number greater then 2, by definition there are infinite prime numbers. Many mathematicians have tried to prove a formula or correlation among prime numbers. None to date have succeeded. The best we can do is to generate a number and check if it is prime. However, there are some tricks we can do to speed things up, but we will get to that.

Here is our basic problem. We want to generate all the prime numbers between x and y. For starts, let us think about the numbers between 2 and 100. The straight forward, brute force, approach will be to check every number in that range and see if any number up to it can divide it without a reminder. If we find such number then it is not prime. Let us take a look at a simple program that can do this for us:


import sys

def is_prime(num):
	for j in range(2,num):
		if (num % j) == 0:
			return False
	return True

def main(argv):

	if (len(sys.argv) != 3):
		sys.exit('Usage: prime_numbers.py <lowest_bound> <upper_bound>')

	low = int(sys.argv[1])
	high = int(sys.argv[2])

	for i in range(low,high):
		if is_prime(i):
			print i,

if __name__ == "__main__":
	main(sys.argv[1:])

And the output for prime numbers between 2 and 100:

wpid-pythonfirst100primes-2013-01-6-09-56.png

Now for some tricks. First, we don’t have to check every second number. All the even numbers will be divisible by 2 by definition of even numbers. So our first loop can be rewritten to jump by 2 and start at an odd number. That way we are just checking the odd numbers. By this hypothesis, all odd number are potentially a prime number. This takes away half the numbers we need to check. If we were to ask for all the prime numbers between 100 and 10,000 it might take a while. Lets look at how long it will take my computer (Intel core duo 2 2.53GHz with 8GB ram) to run this program using the unix time command.

The original script from before:

wpid-pythontimetocalculateprimes1-2013-01-6-09-56.png

Modified script to take out the evens numbers:


import sys
import math

def is_prime(num):
	for j in range(2,num):
		if (num % j) == 0:
			return False
	return True

def main(argv):

	if (len(sys.argv) != 3):
		sys.exit('Usage: prime_numbers2.py <lowest_bound> <upper_bound>')

	low = int(sys.argv[1])
	high = int(sys.argv[2])

	if (low == 2):
		print 2,

	if (low % 2 == 0):
		low += 1

	for i in range(low,high,2):
		if is_prime(i):
			print i,

if __name__ == "__main__":
	main(sys.argv[1:])

wpid-pythontimetocalculateprimes2-2013-01-6-09-56.png

This modification cut the program time by nearly half, but we can do better. According to the Sieve of Eratosthenes we do not need to check if all the numbers will divide our potential prime, we only need to check up to the floor of the square root of the number. So our next version of the code will look like this:


import sys
import math

def is_prime(num):
	for j in range(2,math.sqrt(num)):
		if (num % j) == 0:
			return False
	return True

def main(argv):

	if (len(sys.argv) != 3):
		sys.exit('Usage: prime_numbers3.py <lowest_bound> <upper_bound>')

	low = int(sys.argv[1])
	high = int(sys.argv[2])

	if (low % 2 == 0):
		low += 1

	for i in range(low,high,2):
		if is_prime(i):
			print i,

if __name__ == "__main__":
	main(sys.argv[1:])

And the time to find all the primes between 100 to 10,000:

wpid-pythontimetocalculateprimes3-2013-01-6-09-56.png

This is really great. We have improved our program by another half and nearly a quarter than the original run. Let us examine 2 (2 things) variations of this program. First we will calculate the nth prime number. Second we will try to get a random prime number for a given length.

In order to calculate the nth prime we will have to modify them main() loop into a while loop. We will also modify the program to accept only 1 number, the nth prime we want to calculate. Once we reach the nth prime we will print it out.


import sys
import math

def is_prime(num):
	for j in range(2,int(math.sqrt(num)+1)):
		if (num % j) == 0:
			return False
	return True

def main(argv):

	if (len(sys.argv) != 2):
		sys.exit('Usage: prime_numbers4.py <nth_prime>')

	i = 0
	num = 2
	nth = int(sys.argv[1])

	while i < nth:
		if is_prime(num):
			i += 1
			if i == nth:
				print 'The ' + str(nth) + ' prime number is: ' + str(num)
		num += 1

if __name__ == "__main__":
	main(sys.argv[1:])

Sample output:

wpid-pythontimetocalculateprimes4-2013-01-6-09-56.png

For many application computing a prime number is not enough. For some we want a specific length of prime number. Lets say we need a 5 digit prime number. How are we to calculate this? The simple approach is to generate all 5 digits prime numbers and choose 1 of them randomly. Let us look at how to do this:


import sys
import math
import random

def is_prime(num):
	for j in range(2,int(math.sqrt(num)+1)):
		if (num % j) == 0:
			return False
	return True

def main(argv):

	if (len(sys.argv) != 2):
		sys.exit('Usage: prime_numbers5.py <num_digits>')

	digits = int(sys.argv[1])
	low = int('1' + '0' * (digits-1))
	high = int('9' * digits)
	prime_number_list = []

	if (low == 1):
		prime_number_list.append(2)
		low = 3

	if (low % 2 == 0):
		low += 1

	for i in range(low,high,2):
		if is_prime(i):
			prime_number_list.append(i)

	print 'A random ' + str(digits) + ' digits prime number is: ' + str(random.choice(prime_number_list))

if __name__ == "__main__":
	main(sys.argv[1:])

Output:

wpid-pythontimetocalculateprimes57-2013-01-6-09-56.png

If you were to run the program, you will notice that the it will take longer and loner as n gets larger. I found that for any n grater than 6 digits, it is very demanding on the hardware. I do not recommend letting this program try to calculate a high digit prime. You will also notice if you try to ask for 10 digits, python will raise an error in the range function. So how do we compute n digit prime for a large n? One way I found is by using a random number and checking if it is prime. This seems to work reasonably well with numbers less than 15, but then again it is random.


import sys
import math
import random

def is_prime(num):
	for j in range(2,int(math.sqrt(num)+1)):
		if (num % j) == 0:
			return False
	return True

def main(argv):

	if (len(sys.argv) != 2):
		sys.exit('Usage: prime_numbers6.py <num_digits>')

	digits = int(sys.argv[1])
	low = int('1' + '0' * (digits-1))
	high = int('9' * digits)
	done = False

	if (low == 1):
		low = 2

	while not done:
		num = random.randint(low,high)
		if is_prime(num):
			print 'A random ' + str(digits) + ' digits prime number is: ' + str(num)
			done = True

if __name__ == "__main__":
	main(sys.argv[1:])

wpid-pythontimetocalculateprimes58-2013-01-6-09-56.png

So how about really large primes? That is where time becomes an enemy and computational complexity goes up. I found a few modules that can help compute large primes in python but I have yet to try to run anything. Once I get a chance I will try to run them and put a post up. If you really need prime numbers I would advise you to either download a list of them or generate a list of primes and save them to a text file. Prime numbers will show up every once in a while. They come up in cryptography and other encryption methods. Most usage of prime numbers is due to the nature of the numbers. For more information about prime numbers I would suggest seeking out a mathematician, which I am clearly not.

Cool Stuff

Animatronic Hand and Glove

January 6, 2013

Personal

Captain DeadBones Manifesto

January 5, 2013

There are somethings I guess no one can explain. 20 years ago no one knew what the Internet might become. It was built a page at a time. Websites going up and down, popular and abandoned. The rate of physical and functional growth of computing and the Internet in particular is astonishing. Among other thing the Internet has made the world a much smaller place. Arming humanity with devices enable us to update the internet instantly and communicate across the global without a losing a second. The Internet provides us with the ability to create information and an infinite supply of information, but that is not knowledge and information is not always true (or valuable). Just because someone else did it on YouTube does not mean you can do it. Or maybe it does?

wpid-BlankMap-World-noborders-2013-01-5-06-41.png

One of the notable Internet trends has been in social networks. Social sharing sites are at the core of the Internet and are the most visited websites. Google+, Facebook, Tweeter, Linkedin. The list goes on and on. We have somehow grown accustom of hearing these names. We also learned to associate a different functionality with each service. One is for friends, the other for strangers. Some are for professional work other for large corporation communication. Each with their own unique traits, they still have at least one thing in common. They each enable us to share a part of our personality with others. “We all wear masks” is something everyone has to agree to at some point in their life. One does not act the same way with their friends as the act with their parents. For good or for worse, we all have an idea of what privacy means to us. Some like to share more than others, but we share based on context and who sees it, or more precise who might see it.

wpid-Social_Network-2013-01-5-06-41.png

There are many more things the Internet is good for. The 2 things that are going to stick around is memory and searching. The Internet “remembers”. Everything. I am not sure if it is a good or bad thing, but once something “goes viral”, there is no ‘taksies backsies’. Since the Internet size is enormous, search engines are the only way to find something. I remember when I had a list of website I went to each time I was looking for something. Google, Bing, DuckDuckGo, LexisNexis and other search sites allows us to sift through the ‘mist’ and locate what we are looking for. Remember this, if someone wants to know about you, they will search your name. Whether it is an employer, parent, lover, teacher, a random person, etc. They will find you, and everything you ever did or put online. Be careful, the Internet “remembers”.

wpid-searchengines-2013-01-5-06-41.png

With all this in mind, it is easy to lose where ones self begins and ends. This is why I blog. This blog gives me the ability keep a journal of me. I have come to terms long ago that there are many parts of me. This blog represent who I perceive myself to be as a scientist. It is my belief that the term scientist has been somewhat lost and replaced with ‘I googled it’. Just the other day I was talking to one of my younger professors who was telling me he wished he could Google something in their office. I told him they are working on it. To me it is sad that experimentation has been replaced with search. Innovation is turning into modification. We are falling behind. The idea of the inventor, researcher, scientist is being lost. That is what I am trying to bring back.

To not be a hypocrite, I do use Google. A lot. There is nothing wrong with looking up information. It is what you do with the information. There is a distinct difference between information and knowledge. There is also a difference between fragile knowledge and concrete knowledge. I use search result to build knowledge. To build a solution. I look for a problem. I look for things others might have missed. I look for things that might have been lost to time. I take it back to try to move forward. I am a scientist, regardless of computer. What drives me is exploration, not exploitation.

wpid-The-Scientists-Manifesto-2013-01-5-06-41.jpg

In effort to stay true to my cause, I have started this blog. Maybe I started to late. For the past 5 years I have been in a constant research. I still am. I have a ton of information that I want to explore and some free time at the moment. This blog give me a chance to try to make some order in the chaos that is in my mind. Maybe then I can see the light. There are 2 goals in my mind that make a scientist solid. The first is the ability to transpose information. The second is to convey it. This blog is to suffice the latter. I can go through information on my own in my spare time. But without a log, without a journal, what is the point. Is the journey not the best part? Is the path not more interesting than the goal? In this blog I try to describe my journey and share it so others might learn. There are many thing that bring joy to my life. Teaching others and engaging minds is one I value more the others.

Inspired by Why keep a blog?

This is the 1st version of the Captain’s Manifesto.

Education

Digital Aristotle: Thoughts on the Future of Education

January 4, 2013

Latex

Bringing Colors to TeXShop

January 4, 2013

In an effort to continue posts with colors in common I want to bring up TeXShop. TeXShop is a latex editor of Mac that comes with MacTex distributions. In my mind it is the only Latex editor you will need, but what do I now. For those of you who do not know about Latex, it is a markup typeset base on Donald Knuth’s TeX typesettings. Latex has the ability to handle just about anything: math symbols, algorithms, flow charts, you name it. I have learned how to use Latex about 3 years ago, and I cannot recall a document I wrote that has not been typed in Latex. That is a whle other story for another time.

Here is a Simple Latex document I found online. I had made just available here just in case you could not find it. I also had to add comments to show you how annoying the color scheme can get. Here is a screen shot of what the file would look like with the default TexShop color scheme:

wpid-texshop_default_1-2013-01-4-07-42.png

I think this is just awful. So, lets change it. In order to change the colors you will have to run some terminal command. I know, one would think that by now you could change it through preferences. Nope. There are 7 items you could change the colors to. For each you would have to run 3 commands, one for each RGB value. The RGB values have to be in a float RGB scale. You can consult this float RGB color chart if you need. The 7 items you could color are:

background
commands
comments
foreground
index
insert_point
marker

For example, say we want to change the comments from that horrible red to something more easy on the eye. Lets go with some light purple, like <0.8, 0.0, 1.0>. The commands will be:


defaults write TeXShop commentred 0.8
defaults write TeXShop commentgreen 0.0
defaults write TeXShop commentblue 1.0

You will have to restart TeXShop and now comments will look like this:

wpid-texshop_default_2-2013-01-4-07-42.png

In a similar way you can change the rest of the colors to match you style. Here is a bash script to change all the colors on TexShop. The colors are set for the default colors. You can change any of the colors to match you style. If you want to go back to the original simply download the file and run it. I would suggest you keep a local copy of your settings just in case. In order to run the code you will have to change the permissions to 700 by running this command:


sudo chmod 700 texshop_colors.sh

Now you can change any of the colors at by running the file instead of running multiple commands.


./teschop_colors.sh

Cool Stuff

Drive a Lamborghini With Your Keyboard

January 4, 2013

A few months ago I was talking to a friend of mine about robotics and hardware. He mentioned something called an Arduino Uno board and I was intrigued. After doing some DIY search online I found out this little prototype platform has a whole family of boards. I also found out that the web is filed with neat things you can do with it. An Arduino cost about $15 on Amazon. I had to have one. So I typed in my password to Amazon and about a week later I promptly got my new toy. I immediately took it out of the little box, examined it and went through the Arduino tutorials. Since then my Arduino has been collecting dust. I bought it thinking if I had it I will find a use for it. Following “if you build it, they will come”. Nothing came to mind. That is until I was walking down an aisle at the store yesterday and I saw a neat orange looking remote controlled Lamborghini. It was on sale for $15. I bought it on the spot.

wpid-orangelookingremotecontrolledlamborgini-2013-01-3-07-38.jpg

When I got home and opened up this new toy I was deeply disappointed. The remote for this car has to be an example of the worst human interface known to man. I know this remote comes with a lot of RC cars, but from some reason I just could not take it. I could barley control the thing. And then The idea came to me. How cool would it be if I were to control the car via my Bluetooth keyboard? After all, I have lot of experience driving with my keyboard from GTA. Hours later it turned out to be very cool indeed...

wpid-Arduino_CarControl_00-2013-01-3-07-38.jpg

So what went in to this cool little thing? A night worth of work, and about 270 lines of code. You can download the code for Arduino CarControl, but unless you follow what I did on the hardware part you might find it useless. Here is the “big picture” overview of what I did. I took apart the remote control and wired the connection to the Arduino pins. Then I use python’s serial module (download pyserial) to communicate with the Arduino. I used PyGame (download pygame) to get key pressed information. And finally, I had to write the code that is on the Arduino to accept serial input and output the correct command to the remote control. It seems like a lot, but it is really fairly simple.

Here is a video of the whole thing in action:

Step 0: Get comfortable with the Arduino.

The Arduino is programmed using an its own language. It is a set of c/c++ and was really easy to pickup. You will need to download from Arduino’s site an IDE that was designed to communicate with the board. The software contains a few examples. At the bare minimum, you should try out the blink example.


// Pin 13 has an LED connected on most Arduino boards.
// give it a name:
int led = 13;

// the setup routine runs once when you press reset:
void setup() {
  // initialize the digital pin as an output.
  pinMode(led, OUTPUT);
}

// the loop routine runs over and over again forever:
void loop() {
  digitalWrite(led, HIGH);   // turn the LED on (HIGH is the voltage level)
  delay(1000);               // wait for a second
  digitalWrite(led, LOW);    // turn the LED off by making the voltage LOW
  delay(1000);               // wait for a second
}

If you were to wire up an LED to pin 13 of the Arduino and run the code, the LED diode will blink at fixed intervals. The main part I found useful was to understand the structure of the program.

* Before the first functions there are setup variables.
* After the variables there are functions.

There are two (2 things) functions that make the whole thing run. First there is a setup function. This will be executed as son as the Arduino powers up. The second is the main loop. Opposite from programming, electronic run on a while(1) loop. Any code you have in the loop function will run again, and agin, and again ...

Step 1: Taking apart the remote

For some people the thought of taking apart something brand new might be hard, not for me. I have been taking things apart since I was 3. This is what I found in the RC remote ‘under the hood’:

wpid-Arduino_CarControl_01-2013-01-3-07-38.jpg

Here is a closer look:

wpid-Arduino_CarControl_02-2013-01-3-07-38.jpg

Neat. The small board is wired to 4 things. Positive and negative are near the middle. On the right there is the antenna connection. Near the top-middle there is a red LED diode to indicate power-on. Note the positive wire run through a power switch, which is your remote control on-off switch. Here are some more photos of it disassembled from the remote housing:

wpid-Arduino_CarControl_04-2013-01-3-07-38.jpg

One of the most imperative things I have learned from taking things apart is always stop and check your work. There is nothing more then going a few steps forward and then when a problem arises to trace back. There is no ‘control-z’ in hardware, so be careful. At this point I wired up to remote board to check that it still turns on. It did.

wpid-Arduino_CarControl_06-2013-01-3-07-38.jpg

Being who I am, I also looked around for some housing so It will look nice. I found a pice of foam laying around that fit the task. I mounted the board and this is what I got.

wpid-Arduino_CarControl_09-2013-01-3-07-38.jpg

wpid-Arduino_CarControl_10-2013-01-3-07-38.jpg

Step 2: Reverse engineer the remote board.

This was the part I thought will be the most difficult. It turned out not as bad as I thought. I am not an electrical engineer by any means, but I will try to explain it. The basic idea is that an electronic circuit is either closed or open. When the circuit is open, electricity cannot power what ever is connected to the circuit. When the circuit is closed (and somewhere along the circuit there is a power source), electricity can move around the circuit and power everything along the way. What you will need to do is figure out how the board work. I managed to send a single to the car by emulating the original remote control switch using a small wire. In connecting the to spots in the picture I closed the circuit and indeed the car was moving.

wpid-Arduino_CarControl_05-2013-01-3-07-38.jpg

Step 3: Send out a test single

In order for the Arduino to communicate with the board, you will need to find a better way to move the car. If you can try to follow the logic on the board to figure out which pins are associated with which command. There are a total of 4 command you can give to the car:

  • Forward
  • Reverse
  • Left
  • Right

The forward - reverse command and left-right can only be executed one option at a time. However you could say turn left and move forward at the same time. This came back to bite me later on in the first version. Since I am not an electrical engineer, I had to take the long route to figure things out. I checked each one of the top connectors until I found all four (4) movement controls.

wpid-Arduino_CarControl_13-2013-01-3-07-38.jpg

Step 4: The Python code

The python part is really simple. Get keyboard input using PyGame Library, and output a command using the serial library. The complete carControl.py file is available. Let us look at the main() function:


def main():

    clear_screen()

    print '\nStarting Car Control v.0.3\n';

    ser = serial.Serial('/dev/tty.usbmodem411', 115200, timeout=1);

    pygame.init();
    run = [True,0];
    previous = -1

    while run[0]:
        run = getOrder(run);

        #debug
        #print 'current orders: ' + str(run[1]);

        if (run[1] != previous):
            previous = run[1];
            ser.write(chr(run[1] + 65));
            print run[1];

    ser.close();

We start by opening a serial port to the Arduino. We do that using serial.Serial() passing in the path, bandwidth (and timeout is optional). The path to your usb device is found by running ‘ls /dev/tty.usb*’ in the terminal or you may find it on the Arduino IDE in the bottom right corner.

wpid-pathtoArduino-2013-01-3-07-38.png

We continue to initiate PyGame and some variables and run a main loop. Notice the run variable contains 2 elements. The first indicates whether or not we should keep the loop running, the second is the command. For each iteration of the loop we write the appropriate command to the serial port using the write function. When we exist the loop we close the serial port and end the program.

The second function we need is getOrder. This is where we handle all the keyboard input cases. You can check out the complete code. Here is a snippet of what it looks like:


def getOrder(run):
        for event in pygame.event.get():
            if (event.type == KEYDOWN):
                keyinput = pygame.key.get_pressed();

                #complex orders
                if keyinput[pygame.K_UP] and keyinput[pygame.K_RIGHT]:
                    run[1] = 21;
                elif keyinput[pygame.K_UP] and keyinput[pygame.K_LEFT]:
                    run[1] = 22;
                elif keyinput[pygame.K_DOWN] and keyinput[pygame.K_RIGHT]:
                    run[1] = 23;
                elif keyinput[pygame.K_DOWN] and keyinput[pygame.K_LEFT]:
                    run[1] = 24;

#a few lines later...

return run

For each keyboard input we modify our run variable and at the end return it.

Step 5: The Arduino code

The Arduino part of the code is very similar to the python code. Let us take a look at it part by part. Here is a link to the complete car.ino file.


int reversePin = 9;
int forwardPin = 8;
int leftPin = 7;
int rightPin = 6;

int order = 55;
int time = 75;

//control flag
int flag = 0;

We have our output pins, similar to the blinking LED example. We have 4 output pins, one for each car movement. An initial order that is not a real order. A time variable for delay purposes and a flag to indicate the start of the python program. Now let us look at the setup function:


void setup() {
  // initialize the digital pins as an output.
  pinMode(rightPin, OUTPUT);
  pinMode(leftPin, OUTPUT);
  pinMode(forwardPin, OUTPUT);
  pinMode(reversePin, OUTPUT);

  Serial.begin(115200);
  Serial.print(&quot;\n\nStart...\n&quot;);
}

We initialize the pins to be in output mode and initialize a serial connection. Now let us look at the main loop:


void loop() {

  //Turn everything off...
  off();

  //get input
  if (Serial.available() &gt; 0){
    order = Serial.read() - 65;
    Serial.print(&quot;I received: &quot;);
    Serial.println(order);
    flag = 1;
  }

  if(flag){
    //complete orders
    orderControl(order,time);
  }

At the stat of every loop we turn everything off. If we have serial command we try to read the command. At the end as long as the flag has been raised, meaning we started the python program, we execute what ever command we got using orderControl(). This function takes a order number and a time. Then, using a switch statement, it invokes smaller functions that can execute simple, complex and demo commands.

Here is an example of a simple command function forward:


void forward(int time){
  Serial.println(&quot;This is forward...&quot;);
  digitalWrite(forwardPin, LOW);
  delay(time);
  digitalWrite(forwardPin,HIGH);
}

A more complex command leftTurnReverse:


void leftTurnReverse(int time){
  digitalWrite(reversePin, LOW);
  digitalWrite(leftPin, LOW);
  delay(time);
  off();
}

And a demo function:


void demoOne(){

  int demoTime = 500;

  forward(demoTime);
  reverse(demoTime);
  left(demoTime);
  right(demoTime);
}

Notice that the functions uses reverse magnitude, LOW setting to activate a command. If you were to connect an LED to the command wire, you would need a not gate to invert the signal.

Step6: Wire everything togther

The final step is to put all the wires together, load the Arduino and run the python code. If everything goes well, it should work flawlessly.

wpid-Arduino_CarControl_11-2013-01-3-07-38.jpg

After a night of paying around with the Arduino and the car I have to say this is one of the coolest things I put together. I think the same principles could apply for nearly any out of the box RC vehicle. Maybe I will get an air vehicle (Quad Copter) next time and test my flying skills using a keyboard. Or maybe I will try to get a joystick. In the mean time I have a cool toy setting in the corner that I can use to scare off my dogs when they start bothering me too much.

wpid-Arduino_CarControl_12-2013-01-3-07-38.jpg

Terminal

Syntax Highlighting in the Mac OS X Terminal

January 2, 2013

In your programming career, sooner or later you will come across the command line text editor. In the beginning it will look and feel wired, but with time you will get used to it. After a while you will get used to not having the IDE and fancy auto complete. You will even get used to the fact that the syntax is not highlighted, but you do not have to. As it turns out, you can 'activate' your terminals syntax highlighting features. This will help you a lot down the road and can be applied for Mac (yes, even servers, no I do not know about Windows.

So I created a simple program in python to see what my terminal will display now if I were to open the file via vi. Here is the file content:


import time

def main():
	print 'hello'
	x = 42

main()

If I were to run the following command (assuming the file is named syntax.py):


vi syntax.py

The output:

syntax highlight off

We can do better than that. First of all navigate to your home folder. We are going to add some color highlighting to the ls function. This will make it easy to recognize file types in the command line. That is the folder that opens up when you open up the terminal. Now run the following command to create (or modify if exsiting) your .profile file.


vi .profile

If you have File Vault turned on, you might have to add sudo at the beginning of the command and type your password at the prompt. Once the file is open type 'i' to switch to vi insert mode. Then type the following into the file:


alias ls='ls -G'

After you are done typing hit the 'esc' key followed by 'wq' and enter. This will switch you out of insert mode, save (write) & quit. See An Extremely Quick and Simple Introduction to the Vi Text Editor for more information about vi. This command will add some syntax highlighting to your terminal ls function. So now your directory list will be colorful. To add the syntax highlight to vi we will need to do a little more work.

First, change the directory like so:


cd /usr/share/vim

Then open a file called vimrc using sudo. Like this:


sudo vi vimrc

This will take you back into the vi enviorment. Now you are going to go into insert mode again by pressing 'i' key. Add the following code after the line:


backspace = 2

The code to add:


set ai                  " auto indenting
set history=100         " keep 100 lines of history
set ruler               " show the cursor position
syntax on               " syntax highlighting
set hlsearch            " highlight the last searched term
filetype plugin on      " use the file type plugins

" When editing a file, always jump to the last cursor position
autocmd BufReadPost *
\ if ! exists("g:leave_my_cursor_position_alone") |
\ if line("'\"") > 0 && line ("'\"") <= line("$") |
\ exe "normal g'\"" |
\ endif |
\ endif

Save and exit again, by pressing 'esc' and 'wq'. Restart your terminal session and everything should be all colorful. If you were to go back to view your vimrc file you should see something similar to this:

vim color configure

And out python file from before should look like this when you open it:

vim python color highlight

Much better.

Note that at any point you can disable this feature by removing the added line of code. You can also disable terminal syntax highlighting by typing in the following command from within vi:

 :syntax off 
Random

The Only Asian Martial Arts Secret You need...

January 2, 2013

http://www.youtube.com/watch?v=YiYOsIn0dSU

Cool Stuff

Generating and Checking Passwords in Python

January 2, 2013

During my typical day I find myself logging in to about a dozen or more services. Good password habits tell us to keep the passwords different for each service or username. Not only that, most websites require you to use special characters, upper and lower case, keep changing the password and my top 'favorite', replace your password every X amount of time. As computers are getting faster, cracking passwords is becoming easier. To compensate, we are told to use longer passwords, great. So in theory, we all have 32-64 character passwords that are supper strong and our privacy is kept safe. In reality, we have maybe a handful of passwords and the forgot password link (in hope that we used an email we actually have). So in a time where we have all our information online and kept by passwords we hope not to be cracked, so what can we do with this 'too many passwords' problem?

The answer to this question is short and simple, we do what we can. In this post we will look at how to randomly generate passwords and how to check their security level to some degree. So let us get to it. Generating passwords is something that is rather straight forward. To sum it all up, randomly choose X characters from a given set. We will look at a few ways to generate passwords starting from a simple one. All of them follow that same basic rule.


import random
import sys

def main(argv):

	if (len(sys.argv) != 2):
		sys.exit('Usage: simple_pass.py <password_length>')
    
	password = ''
	for i in range(int(argv[0])):
		password += chr(random.randint(33,126))
	
	print 'You new password is: ' + password

if __name__ == "__main__":
	main(sys.argv[1:])

Using the python random module and passing in via command line the length of the password, we are able to randomly generate a unique password. The passwords are built from all printable ASCII characters randomly chosen. Later we will come back to this example to test a checking password strength program. Here are some example runs of this program.

wpid-pythongenrandompassword1-2013-01-2-02-24.png

This is a nice and simple script anyone can write and by all means use and distribute. It might be a quick hack, but still is not enough to get to be a true generator. Before we move on to another, more sophisticated password generator, lets actually look at a really unique generator using python's lambda.


import random
import string

pass_gen = lambda length, ascii =  string.ascii_letters + string.digits + string.punctuation: "".join([list(set(ascii))[random.randint(0,len(list(set(ascii)))-1)] for i in range(length)])

To use this lambda simply call it with the length required, like so:

wpid-pythongeneratepasswordex2.2.1-2013-01-2-02-24.png

Most password requirements today specify the number of special characters, uppercase, lowercase and numbers require in a password. Using the python string library, we can use string attributes to choose a number of specific characters from each set. Now we can modify our password generator to accept the number of uppercase, lowercase, digits and special charcters. The new code and example output will look like this:


import random
import sys
import string

def main(argv):

	if (len(sys.argv) != 5):
		sys.exit('Usage: simple_pass.py <upper_case> <lower_case> <digit> <special_characters>')
    
	password = ''
	
	for i in range(len(argv)):
		for j in range(int(argv[i])):
			if i == 0:
				password += string.uppercase[random.randint(0,len(string.uppercase)-1)]
			elif i == 1:
				password += string.lowercase[random.randint(0,len(string.lowercase)-1)]
			elif i == 2:
				password += string.digits[random.randint(0,len(string.digits)-1)]
			elif i == 3:
				password += string.punctuation[random.randint(0,len(string.punctuation)-1)]
	
	print 'You new password is: ' + ''.join(random.sample(password,len(password)))

if __name__ == "__main__":
	main(sys.argv[1:])


wpid-pythongeneratepasswordex3-2013-01-2-02-24.png

So at this point we can generate randomize and customize passwords. Let us now move to checking a password strength algorithm and check what kind of passwords we are generating. We will start by using a modified version of a password checker found on Password Advisor. I had to modify the code to get it to run and to create some output. Take a look.


import re

def CheckPassword(password):
    strength = ['Blank','Very Weak','Weak','Medium','Strong','Very Strong']
    score = 1

    if len(password) < 1:
        return strength[0]
    if len(password) < 4:
        return strength[1]

    if len(password) >=8:
        score = score + 1
    if len(password) >=10:
        score = score + 1
    
    if re.search('\d+',password):
        score = score + 1
    if re.search('[a-z]',password) and re.search('[A-Z]',password):
        score = score + 1
    if re.search('.,[,!,@,#,$,%,^,&,*,(,),_,~,-,]',password):
        score = score + 1

    return strength[score]
    
def main():
	
		
	user_input = raw_input("Check: ")

	while(user_input != 'quit'):
		print CheckPassword(user_input)
		user_input = raw_input("Check: ")

if __name__ == "__main__":
	main()


wpid-pythonpasswordstrengthchecker2-2013-01-2-02-24.png

The program uses length and python's regular expressions to determine a score for the password. This is a fairly straight forward calculation. A password longer than 8 characters is awarded 1 point, longer than 10 is awarded an additional point. Then, for each character from a character set the password is awarded another point. The points corresponding to an index on the strength list and an appropriate rating is determined. Let us see how our three password generators from before hold up to this checker standards. (The code has been slightly modified for testing).


import passwordadvisor
import random
import string
import re
import sys 

def ex1(num):

	password = ''
	for i in range(int(num)):
		password += chr(random.randint(33,126))
	
	return password
	
ex2 = lambda length, ascii =  string.ascii_letters + string.digits + string.punctuation: "".join([list(set(ascii))[random.randint(0,len(list(set(ascii)))-1)] for i in range(length)])

def ex3(argv):
    
	password = ''
	
	for i in range(len(argv)):
		for j in range(int(argv[i])):
			if i == 0:
				password += string.uppercase[random.randint(0,len(string.uppercase)-1)]
			elif i == 1:
				password += string.lowercase[random.randint(0,len(string.lowercase)-1)]
			elif i == 2:
				password += string.digits[random.randint(0,len(string.digits)-1)]
			elif i == 3:
				password += string.punctuation[random.randint(0,len(string.punctuation)-1)]
	
	return ''.join(random.sample(password,len(password)))
	
def checker(argv):

	example_1 = ex1(argv[1])
	print example_1 + ' ' + passwordadvisor.CheckPassword(example_1)
	
	example_2 = ex2(int(argv[2]))
	print example_2 + ' ' + passwordadvisor.CheckPassword(example_2)
	
	example_3 = ex3([argv[3],argv[4],argv[5],argv[6]])
	print example_3 + ' ' + passwordadvisor.CheckPassword(example_3)
		
def main(argv):
	if (len(sys.argv) != 7):
		sys.exit('Usage: ex4.py <length1> <length2> <upper_case> <lower_case> <digit> <special_characters>')
		
	checker(sys.argv)

if __name__ == "__main__":
	main(sys.argv[1:])

python exp 3

Test runs have shown that any password of length 8 is considered medium to strong by this measures. Notably the third generator has generated the strongest password at all test runs when 2 characters were chosen from each set. I have tested out the passwords generated using the website appropriately named HowSecureIsMyPassword. I do not advise nor condemn you trying to type your real password, but I have checked our generated passwords using this site. It seems that by their standards any 8 characters long password will take anywhere for a day to 20 days for a desktop PC to crack. For a 16 characters long password it seems that it will take 412 trillion years. So we are still safe on that side. It was shocking to know that some other sites that rank passwords, like ThePasswordMeter ranked any 8 character password we generated as high while HowSecureIsMyPassword claims it will take a day to crack the same password. However, 16 character long passwords were considered strong at both sites.

wpid-howsecure1.1-2013-01-2-02-24.png

wpid-thepassmeter-2013-01-2-02-24.png

wpid-howsecure1.2-2013-01-2-02-24.png

wpid-thepassmeter2-2013-01-2-02-24.png

Let us look at least at one more measure of password strength called bit strength, used to measure the strength of random generated passwords. it follows a formula where each character contributes an amount of bits calculated by the following formula:

 log_{2}(N)

The results is multiplied by the number of characters and a final bit strength is calculated. The threshold recommend, according to Wikipedia, for most secure systems is 80-bits. Let us look at how this will look in code and how our generated passwords measure up to this threshold. The code is very similar to the previous example, only replacing the checker function. (Download code for password generator and checker)


def bit_strength(password):
	return str(math.floor(len(password)*math.log(94,2)))


python exp 4

Since the character set we have include 94 possible characters in all generators, we have a constant log value (~6.55). This means that no matter what password we generate, even 88888888 will have the same ‘bit strength’ as ‘1.U*1!lh’. We can all recognize that the latter one will be much harder to crack than the first one. This is because the formula applies for randomly generated passwords. I will let the statistician among us calculate the odds of generating 88888888 out of 8 characters with 94 possible values for each character. I will "guesstimate" that it is very close to 0. We can draw a graph following this information to determine the length threshold required for a randomly generated password to pass the bit strength threshold.

wpid-lengthofpasswordvstrength2-2013-01-2-02-24.png

You will notice that any password above 15 characters is over 100 on the bit strength index. This means that it will comply with the secure password guideline as indicated on Wikipedia. It also means that if you can remember a randomly generated password, you will need less than 32 characters to secure your password. Keep in mind that this is limited to random generated password and not human created passwords.

So what can you do? In the mean time keep remembering that regardless of the source of password, the length is a directly proportional to the password strength according to any calculation. At this point I have no real solution to the ‘too many passwords’ problem, but I do have hope. I will continue with my work on the matter and post any changes I might have. Keep your passwords secure and safe.