Monthly Archives

June 2013

For the most part, all of us take for granted that the cpu can do multiplication in a timely matter. However, there are some systems that do not have multiplication. Furthermore, how is multiplication actually done? Multiplication is nothing more than repeated applications of additions. For example, if we want to compute 5 x 4 we can add 5 4 times or add 4 5 times and keep track of the sum. Let’s take a look how this might look like in Python 2.7.

import sys

def main(argv):

if len(argv) != 2:
sys.exit('Usage: simple_multi.py <a> <b>')

a = int(sys.argv[1])
b = int(sys.argv[2])
sum = 0

for i in range(a):
sum += b

print "The result of " + str(a) + " times " + str(b) + " is: " + str(sum)

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

And the output:

Sweet. Now for most of you this will be it. Trust me, for me the multiplication symbol is it. I never thought I will have to code multiplication. That is until it came up. I have a friend who happens to be a mathematician with a particular fascination to numbers and counting. So he came up to me claiming that he has this fast way to do multiplication that has to do with the ten’s places and basic multiplication. Basic multiplication being the 10 x 10 grid (or 12 x 12) we all had to memorize at some point. So I decided to put him up for the test, I wrote his algorithm in Python as well as the one above and Russian Multiplication. I won’t spend time trying to explain the algorithms. If you want to, you will find the link helpful enough to explain Russian Multiplication. If you want to find out more about my friend’s Ten’s Multipication, send him a message on his blog DeadEndMath. All in python, running on the same computer with the same Linux time command measuring their performance. Before we get to the data, let’s take a look at the code:

Ten’s Multiplication:

import sys

def main(argv):

if len(argv) != 2:
sys.exit('Usage: tens_multi.py <a> <b>')

a = sys.argv[1]
b = sys.argv[2]
sum = 0;
c = len(a) - 1;

for i in a:
d = len(b) - 1;
for j in b:
sum += int(i)*int(j)*(10**c)*(10**d);
d -= 1;
c -= 1;

print "The result of " + a + " times " + b + " is: " + str(sum)

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

And the output for verification:

Well, at least we got the same results. Let us look at the Russian Multiplication in Python:

import sys

def main(argv):

if len(argv) != 2:
sys.exit('Usage: russian_multi.py <a> <b>')

a = int(sys.argv[1])
b = int(sys.argv[2])

sum = 0;

if a == 0 or b == 0:
print 0;
exit();

if b%2 == 1:
sum += a;

while b != 1:
a = a*2;
b = b/2;
if b%2 == 1:
sum += a;

print "The result of " + str(a) + " times " + str(b) + " is: " + str(sum)

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

The output:

Again, good thing we got the same results. Now we know we have all three versions of multiplication and they are all computing products of 2 numbers correctly. Now let us look at their time compression. I have organized the data in a table for convince:

 Simple Ten's Russian 4 x 5 0.013 0.013 0.014 22 x 54 0.014 0.014 0.014 5142 x 9810 0.014 0.014 0.014 716234 x 847263 0.040 0.014 0.014 817263548 x  827461930 NaN 0.014 0.014

So what can we see? Well first of all the data gathered is from the linux time command. When execute any program in a Linux shell, you can add the command time before the program. This will return you with an output similar to the one below after the command is complete. the times shown are subjective to your computer specifications and current status (i.e. running programs). Here is an example of a Linux time output:

So what does all this mean? The real time is total execution time. The user time is how long it took the user to key in the input. The sys time is the time your command was running on the cpu. In the table above, the time was taken from the sys value of execution of each command. You will notice that simple multiplication gets more cpu consuming as the length of the input increases, while the time for Ten’s and Russian Multiplication remained constant. This means that either algorithm could work as a substitute to multiplication if you happen to work in an environment that does not support multiplication natively. As a final note let me add that even a basic multiplication in Python operates within the same time as Ten’s and Russian multiplication, if not a second faster.

How math is done

Computer games and python are like a perfect match, it just works. Python is simple enough and powerful to provide game designer and programers a common ground for them to meet up and create awesome stuff. In fact, Python has the PyGame library that is dedicated to creating games. There are many games for Python, buy I thought it would be beneficial to start off with a simple version of Hangman. As before, we will be using Python 2.7 for our examples.

Before we take off with it, let us agree to the rules of the game:

• The computer will randomly chose a secret word.
• For each user guess, all occurrences of the same letter in the word will be revealed to the player.
• The computer will draw the “hangman digram” as outlined bellow for each turn.
• The user may guess letters at each turn until the word is completed or the “hangman digram” is complete.
• We can assume that all user input and word letters are lowercase alpha numeric without errors.

The last one is made to simplify the code and the constrains for the problem. In reality we should always account for errors, but I am going to et this one slide. For now. Let us first look and the “hangman digram”. Some people think this is the hardest thing, but it is actually the easiest. Here are the 7 possibilities of the board in ASCII art form.

+---+
|   |
|
|
|
|
=========

+---+
|   |
0   |
|   |
|
|
=========

+---+
|   |
0   |
/|   |
|
|
=========

+---+
|   |
0   |
/|\  |
|
|
=========

+---+
|   |
0   |
/|\  |
/    |
|
=========

+---+
|   |
0   |
/|\  |
/ \  |
|
=========

This was generated by this short Python code:

board = [
'  +---+   \n  |   |   \n      |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n  |   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n /    |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n / \\  |   \n      |   \n========= \n'
]

print board[i]

This will take care of any of the board configurations. All we need to worry about is how many letters the user has got wrong and we can immediately print out the corresponding “hangman diagram”. Let us make it a little more nice and wrap it in a class. Classes are objects in Python, very similar to Objects in Java. We can encapsulate the board configuration, word to be guessed, missed letters and guessed letters in 1 object. Lets take a look:

board = [
'  +---+   \n  |   |   \n      |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n      |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n  |   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|   |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n      |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n /    |   \n      |   \n========= \n',
'  +---+   \n  |   |   \n  0   |   \n /|\\  |   \n / \\  |   \n      |   \n========= \n'
]

class Hangman:
def __init__(self,word):
self.word = word
self.missed_letters = []
self.guessed_letters = []

Sweet. Let us move on and create a print function. Print functions are useful for debugging and will take care of our user interface. When we want to print our Hangman object, we really want to know all the information, how the board looks like (or how much of the diagram is complete), the letter we missed, the blank splits for the words and letters we already found. Let us take a look:

def print_game_status(self):
print board[len(self.missed_letters)]
print 'Word: ' + self.hide_word()
print 'Letters Missed: ',
for letter in self.missed_letters:
print letter,
print
print 'Letters Guessed: ',
for letter in self.guessed_letters:
print letter,
print

And the output for an empty board:

Upon close inspection, you will notice that there is another method I am calling name hide_word(). By the concatenation with the string before, you can assume the function is defined and returns a string. What we really need, is a function that can take a word and print out only the letters the user has already guessed. Let’s take a look:

def hide_word(self):
rtn = ''
for letter in self.word:
if letter not in self.guessed_letters:
rtn += '_'
else:
rtn += letter
return rtn

That seems good enough. Before we can move on to the game play and logic, we need a method in the Hangman object to update a current guess. That is straight forward and looks like so:

def guess(self,letter):
if letter in self.word and letter not in self.guessed_letters:
self.guessed_letters.append(letter)
elif letter not in self.word and letter not in self.missed_letters:
self.missed_letters.append(letter)
else:
return False
return True

So if the letter is in the word we are trying to guess and we haven’t tried to guess it before, we are going to mark it and return 1 for successful update or if the letter is not in our word, but has not been asked again. If either of these conditions is a failure, we have a repeat input we have already accounted for and we will return 0 to notify the game handler of a problem. The last method we are really missing is to check for win condition. Here is how we can check for hangman win condition in our case:

def hangman_won(self):
if '_' not in self.hide_word():
return True
return False

Notice that we are reusing methods we already have, making things simple. Now our Hangman game object is complete. You will think that we are over, but there is one more method we are missing for the game to be complete. We have a method to check if the game has been won, but we do not have a method to check if the game is over. What happens when the “hangman digram” is complete? For this we will add just a one liner method:

def hangman_over(self):
return self.hangman_won() or len(self.missed_letters) == 7

Sweet. Now all we need is a main driver and some helper function and we are all done. Our main method can look like this:

def main():

game = Hangman(rand_word())
while not game.hangman_over():
game.print_game_status()
user_input = raw_input('\nEnter a letter: ')
game.guess(user_input)

game.print_game_status()
if game.hangman_won():
print '\nCongratulations! You are the winner of Hangman!'
else:
print '\nSorry, you have lost in the game of Hangman...'
print 'The word was ' + game.word

print '\nGoodbye!\n'

You will be now notice that we are almost done, just 1 more function and we are clear, the rand_word() function. Now you can get very fancy with this, read from a file and randomly choose and such. However, I want to keep things simple, so I limited the word bank into a small list from which I randomly choose 1 word. Check it out:

def rand_word():

return bank[random.randint(0,len(bank))]

That’s all folks. That is the simple way you can get a game started in python. Now you might think this is very complex. If you are looking for a more simple approach, there is a whole chapter about hangman in python I recommend you check out. The reason we set it up like this is so we can add some GUI events or make it more complex without a lot of hassle. You can download the Python code for Hangman or code it yourself. I hope this gave you some flavor to how games and python could work together. What game can you come up with?

Here are some output screen shots:

Today I want to talk to you about ciphers, more in particular Caesar Ciphers. Encryption and Decryption of secret messages date back a long time before computers. Countless Nations have utilized ciphers to communicate secrets across distances. For example, lets say I have soldier on the other side of the planet and I am relaying them a message that might put their life at risk. Do we want that message falling into the wrong hands? No. So what can we do? Well, the simple answer is to encrypt the message. Today almost every message is encrypted and packet into protocols several of times. For example, your computer encrypts packets it sends back and forth with your WiFi router all the time. Computers, for better or worse, require us to come up with new encryption methods on a daily basis. However, everyone has to start somewhere. Before you can plunge in and understand things like AES and RSA encryption, we need to start in something basic, like Caesar Ciphers.

Caesar Cipher is pretty simple. It is a substitution cipher that people like to think was user by Julius Caesar. In this cipher we follow a formula to encrypt a message and another to decrypt. Let us take a look at what that means mathematically.

Here is our encryption formula:

And here is decryption:

And thats it folks. Wait, what does this actually mean? Well, lets first start with out assumptions:

1. The alphabet we are working with contains 26 letters (English)
2. n is is a number less than or equal to 25.

These assumptions can be modified for any alphabet language of you choosing. If the alphabet contains m letters, than n has to be less than or equal to m-1. As long as you keep both conditions, you will be fine. Here is a general outline and picture of how the algorithm works. You should be aware that normally n is set to 3, but it will work with any number.

1. Assign numeric values to each letter in the alphabet.
2. Encrypt:
• for each letter in plain_text
• new letter is letter_numeric_value + n
3. Decrypt:
• for each letter in cipher
• plain_text_letter is letter_numeric_value - n

For it to make some sense, here is a visual picture from Wikipedia:

So the letter E in our message (plain text) is 5 and n=3, so our encrypted value of E is B. Now that we have some background and a simple example, let us implement it in Python. Like always, we will use Python 2.7. Here is how Caesar Cipher looks like in Python:

First lets look at a simple encryption module:

import sys

def main(argv):
if (len(sys.argv) != 2):
sys.exit('Usage: sub.py <k>')

plaintext = list(raw_input('Enter message: '))
alphabet = list('abcdefghijklmnopqrstuvwxyz')
k = int(sys.argv[1])
cipher = ''

for c in plaintext:
if c in alphabet:
cipher += alphabet[(alphabet.index(c)+k)%(len(alphabet))]

print 'Your encrypted message is: ' + cipher

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

In this example we define the alphabet and make use of Python List and Indexing. We ask the user to pass in a key of length k and preform the substation. Here is an example run:

Now let us up the stakes to something more complex. After all, this is an encryption that people used to do by hand all the time. Take a look at this program:

import sys

def encrypt(k):
plaintext = raw_input('Enter plain text message: ')
cipher = ''

for each in plaintext:
c = (ord(each)+k) % 126

if c < 32:
c+=31

cipher += chr(c)

print 'Your encrypted message is: ' + cipher

def decrypt(k):
cipher = raw_input('Enter encrypted message: ')
plaintext = ''

for each in cipher:
p = (ord(each)-k) % 126

if p < 32:
p+=95

plaintext += chr(p)

print 'Your plain text message is: ' + plaintext

def main(argv):
if (len(sys.argv) != 3):
sys.exit('Usage: ceaser.py <k> <mode>')

if sys.argv[2] == 'e':
encrypt(int(sys.argv[1]))
elif sys.argv[2] == 'd':
decrypt(int(sys.argv[1]))
else:
sys.exit('Error in mode type')

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

The first question you might ask is why is the mod 126? Well, this version of Caesar Cipher was adapted to take full use of the ASCII Printable Character map, minus the first 32 characters that are not printable. With this program, we can chose a larger n and create a “harder” to break ciphers. You will also notice that now we can do Encryption and Decryption in the same program. Let us try to decrypt ‘khoor’ and see what we get:

Sweet. Now let’s try to encrypt something a little longer with a different key.

And Decryption:

Caesar ciphers are nice to play around with and to learn basic concepts, but is really impractical. The number of combination you can get is really small compared to what the computer can generate. Brute force attacks can always crack the code with very little human intervention. Consider a 26 letter alphabet. There are only 25 options for selecting a unique n. That means that if I can generate all the 25 permutations, 1 of them has to be the correct plain text. Let us look brute force braking using the following script:

import sys

def decrypt(k,cipher):
plaintext = ''

for each in cipher:
p = (ord(each)-k) % 126

if p < 32:
p+=95

plaintext += chr(p)

print plaintext

def main(argv):
if (len(sys.argv) != 1):
sys.exit('Usage: brute_ceaser.py')

cipher = raw_input('Enter message: ')

for i in range(1,95,1):
decrypt(i,cipher)

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

I will spare you the entire 94 lines that got printed out, here are a few. Can you guess what the message originally was?

Here is another one:

I will let you come to your own conclusions as to how “hard” it is to brake Caesar Ciphers. Personally, I wouldn’t use them for anything simple. Than again, I do not know how many people would check if you used it. I hoped you gain some understanding to how cipher works, substitution ciphers in particular. Next time I might dig a little farther into security algorithms and play around with another step up in encryption-decryption algorithms.

Happy Hacking