stealthcopter.com

I’ve rewritten the functions in my previous two posts (caesar and substitution ciphers) using the maketrans function from the strings module in python (With thanks to wumzi for pointing this out).

maketrans takes an input alphabet and an output alphabet and can then be used on a string. This can be used to greatly simplify the two ciphers I produced previously. Example below:

input_alphabet="abcde"
output_alphabet="12345"
trantab = maketrans(input_alphabet,output_alphabet)
text="translate abcdefg"
print text.translate(trantab)
# This will output:
# tr1nsl1t5 12345fg

This nows means my code can be rewritten in just a fraction of what it was before:

from random import shuffle
from string import maketrans

alphabet="abcdefghijklmnopqrstuvwxyz" + \
	 "1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ"+ \
         ":.;,?!@#$%&()+=-*/_<> []{}`~^"

def translator(text,alphabet,key):
	trantab = maketrans(alphabet,key)
	return text.translate(trantab)

def caesar_encode(plaintext,s,alphabet):
	return translator(plaintext,alphabet,alphabet[s:]+alphabet[:s])

def caesar_decode(ciphertext,s,alphabet):
	return translator(ciphertext,alphabet,alphabet[-s:]+alphabet[:-s])

def substitution_encode(plaintext,alphabet):
	randarray=range(0,len(alphabet))
	shuffle(randarray)
	key=""
	for i in range(0,len(alphabet)):
		key+=alphabet[randarray[i]]

	return translator(plaintext,alphabet,key),key

def substitution_decode(ciphertext,key,alphabet):
	return translator(ciphertext,key,alphabet)

# Example useage
plaintext="The wheels on the bus go round and round. round" + \
" and round. round and round. The wheels on the bus go round and"+ \
" round, all through the town!"

print
print "SUBSTITUTION"
ciphertext,key=substitution_encode(plaintext,alphabet)
print "Key: ", key
print "Plaintext:", plaintext
print "Cipertext:", ciphertext
print "Decoded  :", substitution_decode(ciphertext,key,alphabet)

print
print "CAESAR SHIFT"
ciphertext=caesar_encode(plaintext,5,alphabet)
print "Key: ", 5
print "Plaintext:", plaintext
print "Cipertext:", ciphertext
print "Decoded  :", caesar_decode(ciphertext,5,alphabet)

This will output the following

SUBSTITUTION
Key: &fywQ.%!lmx_sRGu:{<(5jqAXvMFgk]SIY[4iK+3P8pcV$2da@DT/ZnOJ*E>-r},BH16zUb#L?N`e7C ~9t)oW^=;h0
Plaintext: The wheels on the bus go round and round. round and round.round and round. The wheels on the bus go round and round, all through the town!
Cipertext: O!Q)q!QQ_<)GR)(!Q)f5<)%G){G5Rw)&Rw){G5Rw,){G5Rw)&Rw){G5Rw,{G5Rw)&Rw){G5Rw,)O!Q)q!QQ_<)GR)(!Q)f5<)%G){G5Rw)&Rw){G5RwH)&__)(!{G5%!)(!Q)(GqR6
Decoded : The wheels on the bus go round and round. round and round.round and round. The wheels on the bus go round and round, all through the town!

CAESAR SHIFT
Key: 5
Plaintext: The wheels on the bus go round and round. round and round.round and round. The wheels on the bus go round and round, all through the town!
Cipertext: Ymj`2mjjqx`ts`ymj`gzx`lt`wtzsi`fsi`wtzsi@`wtzsi`fsi`wtzsi@wtzsi`fsi`wtzsi@`Ymj`2mjjqx`ts`ymj`gzx`lt`wtzsi`fsi`wtzsi$`fqq`ymwtzlm`ymj`yt2s&
Decoded : The wheels on the bus go round and round. round and round.round and round. The wheels on the bus go round and round, all through the town!

Conclusion
maketrans is awesome

This post builds upon the Caesar shift presented previously; converting it to a full substitution cipher. The substitution cipher will practically remove bruteforce style methods of defeating the encryption and provide a basis for more complicated ciphers.

Subsitution Cipher
Because a Caesar shift only rotates the alphabet there are only 25 possible unique solutions, this leaves the cipher quite vulnerable to brute force. If rather than just rotating the alphabet and keeping it ‘linear’ we can shuffle it to create a substitution cipher. This improves the number of possible solutions to a shocking
(26! – 1) = 4.03291461126605635584e26 (unfortunatly, the substitution cipher is alot weaker than it seems as it is vunerable to several different cryptanalysis attacks).

Substitution Cipher Diagram

We start with the simple Caesar shift function with the following changes:

• A new array is introduced filled with the numbers 0 – the length of the alphabet. This array is shuffled using shuffle from the random module. The alphabet substitution dictionary is created using this array to decide which letters go where (this is probably clearer in the code than in my explanation).
• With the Caesar shift we only needed to know the number of rotations in order to decrypt the text, now we need a full list of the letter substitutions. This is stored as the key and will be needed in order to decode our substitution cipher.
• We also now store the alphabet outside of the function so that it can be used in a decode function. This function was added along with some example usage to make the full process more understandable

from random import shuffle

alphabet="abcdefghijklmnopqrstuvwxyz"

def substitution(alphabet,plaintext):

	# Create array to use to randomise alphabet position
	randarray=range(0,len(alphabet))
	shuffle(randarray)

	key=""

	#Create our substitution dictionary
	dic={}
	for i in range(0,len(alphabet)):
		key+=alphabet[randarray[i]]
		dic[alphabet[i]]=alphabet[randarray[i]]

	#Convert each letter of plaintext to the corrsponding
	#encrypted letter in our dictionary creating the cryptext
	ciphertext=""
	for l in plaintext:
		if l in dic:
			l=dic[l]
		ciphertext+=l
	for i in alphabet:
		print i,
	print
	for i in key:
		print i,
	print
	return ciphertext,key

# This function decodes the ciphertext using the key and creating
# the reverse of the dictionary created in substitution to retrieve
# the plaintext again
def decode(alphabet,ciphertext,key):

	dic={}
	for i in range(0,len(key)):
		dic[key[i]]=alphabet[i]

	plaintext=""
	for l in ciphertext:
		if l in dic:
			l=dic[l]
		plaintext+=l

	return plaintext

# Example useage
plaintext="the cat sat on the mat"
ciphertext,key=substitution(plaintext)
print "Key: ", key
print "Plaintext:", plaintext
print "Cipertext:", ciphertext
print "Decoded  :", decode(ciphertext,key)

Running this will output the following (This will be different on each run due to the use of random to generate the key).

Key: miylbsowutgdkfvjepqhazrncx
Plaintext: the cat sat on the mat
Cipertext: hwb ymh qmh vf hwb kmh
Decoded : the cat sat on the mat

Improvement by using additional characters
Adding additional characters into the substitution will it more difficult to solve. For example if we change our alphabet from:

alphabet=”abcdefghijklmnopqrstuvwxyz”

If we include capital letters, numbers from 0 -9 and special characters:

alphabet=”ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890″+ \
“:.;,?!@#$%&()+=-*/_<> []{}`~^”+ \
“abcdefghijklmnopqrstuvwxyz”

We increase the number of possible solutions from (26!-1) to (63!-1) which is 1.98260831540444006412e87. This also has the added benefit of making the encrypted text alot cooler and harder to guess at by eye (unfortunately still very easy to see what character represents space).

Key: MXjAarLzWqFePI7E botO5f1kym29RZd3Sh8JTiQGKVDp6YBCsU4nucNgwlx0vH
Plaintext: this plaintext will be much more of a challenge to decode compared to the Caesar shift cipher
Cipertext: tzWoHEeMWIta1tHfWeeHXaHPOjzHP7baH7rHMHjzMeeaILaHt7HAaj7AaHj7PEMbaAHt7HtzaHjMaoMbHozWrtHjWEzab
Decoded : this plaintext will be much more of a challenge to decode compared to the caesar shift cipher

Future
The substitution cipher is a lot more secure than Caesar shift cipher but unfortunately is very insecure towards frequency analysis. In future posts I will address using frequency analysis and methods to prevent this type of attack as well as improving on this cipher by creating multiple-dicitionary based ciphers to create Vigenère style ciphers.

I imagine most people reading this will enjoy the simple challenge of solving some encrypted text. I have used this code to make some ciphertext, try and decode it! (extra points for knowing where it is from):

^’VtuBbtv3vut1u-w.G^’Vt&vnu-tZBtZnuIvwvtwn
-qbtuB6GN3vutbqBS-qt.BSt&wB~vtV.tqv1wbG}u5t
~nDDv5tVvG}u5tbBwvtVvtbBt@nvIvZG}u5tbqwv6tv
3vw.t@nvIvtnubBt1tUnwvG}Ztbqv.t&Swuv5tnbtqS
wbt&vI1SZvt^t61ZtZBtq1@@.tUBwt.BSm)B6tbqvZv
t@BnubZtBUt51b1tV1~vt1t&v1SbnUSDtDnuvG}u5t6
v’wvtBSbtBUt&vb1GQv’wvtwvDv1Znu-tButbnVvG

(note: newlines were placed to make it fit and do not represent a character)

Update: Made code a little cleaner by moving dictionary outside of functions.

I have always had a keen interest in cryptography and rather than give a brief history of cryptography I will recommend reading Simon Singh’s The code book or for a modern and hands on approach Applied Cryptography by Bruce Schneier (Who also made a brilliant book on security, more of descriptive approach but very interesting Secrets and Lies: Digital Security in a Networked World).

This post aims to detail the creation (in python) of one of the simplest forms of encryption; the simple Caesar shift (or shift cipher). The Caesar shift takes the normal alphabet and maps it to a an identical alphabet with a rotation. The cipher will be written in such a way that it can be easily expanded on to create more complex encryption schemes with little modification.

Caesar shift alphabet diagram

The above image shows a diagrammatic representation of a Caesar shift of 3 (alphabet transposed onto a rotation of itself with a displacement of 3). Below shows the entire alphabet in plaintext and in ciphertext, followed by a simple sentence in plaintext and in cipher text.

Below is the code to convert plaintext into ciphertext along with an example of the usage:

def caesar(plaintext,shift):

	alphabet=["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"]

	#Create our substitution dictionary
	dic={}
	for i in range(0,len(alphabet)):
		dic[alphabet[i]]=alphabet[(i+shift)%len(alphabet)]

	#Convert each letter of plaintext to the corrsponding
	#encrypted letter in our dictionary creating the cryptext
	ciphertext=""
	for l in plaintext.lower():
		if l in dic:
			l=dic[l]
		ciphertext+=l

	return ciphertext

#Example useage
plaintext="the cat sat on the mat"
print "Plaintext:", plaintext
print "Cipertext:",caesar(plaintext,3)
#This will result in:
#Plaintext: the cat sat on the mat
#Cipertext: wkh fdw vdw rq wkh pdw

Explanation
Here we have written a function that is given the plaintext and an arbitary rotation (including negative) and returns a ciphertext. The function creates a dictionary, mapping each letter to another letter that is ‘shift’ letters away from it in the alphabet (the modulus (%) is used so to wrap the alphabet back to the start if it falls off the end). It then converts each letter of the plain text into the corresponding encrypted letter using the dictionary.

Future
In the next post I will discuss methods to improve the Caesar shift and how to turn it into a full substitution cipher (where the alphabet is shuffled rather than rotated). The Caesar shift is very susceptible to brute forcing and frequency analysis which I shall explain and create a program to defeat these encryptions in a future post.

The chaps over at the modaco forums have detailed how to backup and replace the firmware on the android T-mobile pulse. This post aims to consolidate and link all the information in these posts and provide a few explanations.

tmobile pulse

Definitions
Rom – a file which contains the image for a particular version of android
Nand memory – the internal memory of the phone which contains android
flashing – replacing the contents of the Nand memory
root – superuser or admin

Gaining root access
This follows the forum post here

• Download superboot and unzip.
• Reboot your phone into bootloader mode (Power off your phone then turn it on with volume down and the red button pressed). You should be presented with a blue screen and some information, connect your pulse to your computer via the usb cable.
• Windows – Run ‘install-superboot-windows.bat’
• Mac – Run ‘./install-superboot-mac.sh’, You may need to make the script executable by using ‘chmod +x install-superboot-mac.sh’
• Linux – Same as above ‘./install-superboot-linux.sh’ and ‘chmod +x install-superboot-linux.sh’. These commands will most likely need root access so you may need to prepend these commands with ‘sudo ‘.
• You should now see your pulse has some text on the screen with information about how much data was transfered.
• Reboot (by taking the battery out) and you should now have root access on your phone

Installing and running recovery tool
This follows the forum post here.

• The process is the same as above but using a different zip file: recovery
• Once rebooted, you will need to install the ‘quickboot’ program from the market app. This will allow you to boot into recovery mode (this require root access which we have previously attained)
• Using the recovery tool you can backup your android using Nandroid, this will only save the Nand memory not any of your settings.
• The backup will by default save the backup to your SD card, you can then enable usb transfer in the recovery menu and save this to your computer.

Partitioning your SD card
The SD card may need to be partitioned in preparation for the custom rom.

• From the recovery menu you can partition your SD card.
• By default the size of the swap partition (used as “extra”-RAM by android) is 32mb however the current MoDaCo Custom ROM’s will not boot properly if there is a swap drive on the SD card
• The MoDaCo roms also allow an ext2 partition to be made for applications in order to free internal memory.

Installing Custom Roms
Now the SD card is partitioned we can go about installing the new version of android to our pulse. We simply upload the rom zip onto the SD card and select the update option from the recovery mode. The first boot after this is done will take a while to transfer all the apps to your SD card.

Currently there are two roms from MoDaCo, one Customised Vanilla android 1.5 and a Customised T-mobile 1.5. They contain useful extra tools and include ssh access (with the password for ssh contained in the about screen).

Future
Hopefully there will soon be a rom will be release with a updated version of android 1.6 or 2.0 which can be flashed onto the pulse to bring all the new and improve features described here. Recent discussions have hinted at multi-touch becoming a reality once the kernel sources are released (they are now released)

Often in newspapers there is a wordwheel or some variant, whereby you have to find as many words greater than 3 letters long, containing the centre word and using the letters no more than once. I have created a webpage that generates a “WordCube” daily for people to peruse at their leisure (www.stealthcopter.com/wordcube). This post contains the code and explanation of the solutions to wordcube’s (and all other word<insert shape here>).

Example WordCube image for the 12th December 2009 from www.stealthcopter.com/wordcube/2009/12/12

Below is a function I wrote to check if an input was a valid anagram (or partial anagram, as it isn’t essential to use every letter). The function works by cycling over each letter of word we are testing (word), and checks if the letter is valid (checked against chkword). If the letter is valid then it removes the letter from the original word and moves to the next letter until we run out of letters (returns True) or if the letter is invalid (returns False).

def anagramchk(word,chkword):
	for letter in word:
		if letter in chkword:
			chkword=chkword.replace(letter, '', 1)
		else:
			return False
	return True

f=open('english', 'r')
word=raw_input('Input letters (starting with mandatory letter) :')
minlen=4
count=0
for l in f:
	l=l.strip()
	if len(l)<=len(word) and len(l)>=minlen and word[0] in l and anagramchk(l,word):
		if len(l)==len(word):
			print l,'  <-- Long word'
		else:
			print l
		count+=1
f.close()
print count

This will output a list of the possible words, along with a total. The results can be seen for the WordCube in the example above here (To prevent spoiling it if you’d like to have a go at it yourself).

As always I’d be interested to see if anyone knows any faster methods or any other general improvements or comments.

The dictionary file can be found here (not perfect):
here

Finding the highest common factor is useful in mathematics and cryptography.

It would be computationally expensive to calculate all the common factors of two numbers and then compare to find the highest factor in common. Instead (as usual) there is a mathematical theory that can be used to speed up this process, in this case it’s the Euclidean algorithm.

The Euclidean algorithm subtracts the smaller number from the larger number, then using this new number and the smaller number repeats this process until the numbers are equal and hence the subtraction goes to zero. This is the highest common factor.

Example:
Find the highest common factor of 252 and 105

252-105=147
147-105=42
105-42=63
63-42=21
42-21=21
21-21=0

Below is the python code to preform this

def hcf(no1,no2):
	while no1!=no2:
		if no1>no2:
			no1-=no2
		elif no2>no1:
			no2-=no1
	return no1

This method is quite quick even and scales well for larger numbers. If you know of a faster method or can see any improvements to make then please let me know.