You are currently browsing the tag archive for the ‘code breaking’ tag.

isbn

Cracking ISBN and Credit Card Codes

ISBN codes are used on all books published worldwide. It’s a very powerful and useful code, because it has been designed so that if you enter the wrong ISBN code the computer will immediately know – so that you don’t end up with the wrong book. There is lots of information stored in this number. The first numbers tell you which country published it, the next the identity of the publisher, then the book reference.

Here is how it works:

Look at the 10 digit ISBN number. The first digit is 1 so do 1×1. The second digit is 9 so do 2×9. The third digit is 3 so do 3×3. We do this all the way until 10×3. We then add all the totals together. If we have a proper ISBN number then we can divide this final number by 11. If we have made a mistake we can’t. This is a very important branch of coding called error detection and error correction. We can use it to still interpret codes even if there have been errors made.
If we do this for the barcode above we should get 286. 286/11 = 26 so we have a genuine barcode.

Check whether the following are ISBNs

1) 0-13165332-6
2) 0-1392-4191-4
3) 07-028761-4

Challenge (harder!) :The following ISBN code has a number missing, what is it?
1) 0-13-1?9139-9

Answers in white text at the bottom, highlight to reveal!

Credit cards use a different algorithm – but one based on the same principle – that if someone enters a digit incorrectly the computer can immediately know that this credit card does not exist.  This is obviously very important to prevent bank errors.  The method is a little more complicated than for the ISBN code and is given below from computing site Hacktrix:

creditcard2credit card 4creditcard3credit card 6credit card 5credit card 8credit card 7

credi card 9 You can download a worksheet for this method here. Try and use this algorithm to validate which of the following 3 numbers are genuine credit cards:

1) 5184 8204 5526 6425

2) 5184 8204 5526 6427

3) 5184 8204 5526 6424

Answers in white text at the bottom, highlight to reveal!


ISBN:
1) Yes
2) Yes
3) No
1) 3 – using x as the missing number we end up with 5x + 7 = 0 mod 11. So 5x = 4 mod 11. When x = 3 this is solved.
Credit Card: The second one is genuine

If you liked this post you may also like:

NASA, Aliens and Binary Codes from the Stars – a discussion about how pictures can be transmitted across millions of miles using binary strings.

Cracking Codes Lesson – an example of 2 double period lessons on code breaking

Screen Shot 2015-11-22 at 6.36.36 PM

Crack the Beale Papers and find a $65 Million buried treasure?

The story of a priceless buried treasure of gold, silver and jewels (worth around $65 million in today’s money) began in January 1822. A stranger by the name of Thomas Beale walked into the Washington Hotel Virginia with a locked iron box, which he gave to the hotel owner, Robert Morriss.  Morriss was to look after the box for Beale as he went off on his travels.

In May 1822 Morriss received a letter from Beale which stated that the  box  contained papers of huge value – but that they were encoded for protection.  Beale went on to ask that Morriss continue to look after the box until his return.  He added that if he did not return in the next 10 years then he had instructed a close friend to send the cipher key on June 1832.  After that time Morriss would be able to decipher the code and learn of the box’s secrets.

Well, Beale never returned, nor did Morriss receive the promised cipher key.  Eventually he decided to open the box.  Inside were three sheets of paper written in code, and an explanatory note. The note detailed that Beale had, with a group of friends discovered a seam of gold and other precious metals in Santa Fe. They had mined this over a number of years – burying the treasure in a secret location for safe keeping.  The note then explained that the coded messages would give the precise location of the treasure as well as detailing which men were due a share.

Screen Shot 2015-11-22 at 6.37.27 PM

Morriss devoted many years to trying to decipher the code in vain – before deciding at the age of 84 in 1862 that he should share his secret with a close friend.  That friend would later publish the Beale Papers in 1885.  The pamphlet that was published stirred huge interest in America – inspiring treasure hunters and amateur cryptographers to try and crack the code.  The second of the 3 coded messages was cracked by the author of the pamphlet using what is known as a book code.  The United States Declaration of Independence was used as the book to encode the message above.

Screen Shot 2015-11-22 at 6.51.08 PM

The first number 115 refers to the 115th word in the Declaration of Independence, which is the word “instituted”.  Therefore the first letter of the decoded message is “I”.  The second number is 73, which refers to the 73rd word in the declaration – which is “hold”, so the second letter of the decoded message is “h”.  Following this method, the following message was revealed:

I have deposited in the county of Bedford, about four miles from Buford’s, in an excavation or vault, six feet below the surface of the ground, the following articles, belonging jointly to the parties whose names are given in number three, herewith:

The first deposit consisted of ten hundred and fourteen pounds of gold, and thirty-eight hundred and twelve pounds of silver, deposited Nov. eighteen nineteen. The second was made Dec. eighteen twenty-one, and consisted of nineteen hundred and seven pounds of gold, and twelve hundred and eighty-eight of silver; also jewels, obtained in St. Louis in exchange for silver to save transportation, and valued at thirteen thousand dollars.

The above is securely packed in iron pots, with iron covers. The vault is roughly lined with stone, and the vessels rest on solid stone, and are covered with others. Paper number one describes the exact locality of the vault, so that no difficulty will be had in finding it. Source

After the pamphlet was published there was great interest in cracking the 2 remaining papers, an interest which has persisted into modern times.  One of the uncracked papers is shown below:

Screen Shot 2015-11-22 at 6.37.03 PM

In 1983 2 amateur treasure hunters were jailed for trying to dig up graves in Bedford, sure that they were about to find the missing gold.  In 1989 a professional treasure hunter called Mel Fisher secretly bought a large plot of land after believing that the treasure was buried underneath.  However nothing was found.  Up until now all efforts to crack the code above have  ended in failure.  Perhaps the pamphlet was a giant hoax?  Or perhaps the treasure is still waiting to be found.

Screen Shot 2015-11-30 at 9.52.12 PM

The town of Bedford still receives visitors from around the world, keen to try and crack this centuries old puzzle.  You can hire metal detectors and go looking for it yourself.  The map above from 1891 shows the 4 mile radius from Buford’s tavern which is thought to contain the treasure.  Maybe one day Beale’s papers will finally be cracked.

For more information on this topic read Simon Singh’s excellent The Code Book – which has more details on this case and many other code breaking puzzles throughout history.

If you want to try your own codebreaking skills, head over to our Schoolcodebreaking site – to test your wits against students from schools around the world!

Screen Shot 2015-06-22 at 2.04.35 PM

The one time pad is a very secure way of encoding messages – so secure in fact that it is unbreakable as long as the agents using it don’t make any mistakes. It was a very popular method of sending coded messages during the Second World War – and persisted well into the Cold War, when secret agents on the ground in a foreign country could encode their reports without fear that they would be broken by the enemy.

The picture above is from a one time pad code sheet which was used in the Second World War. What would happen is that the secret agent would be issued with a code book with lots of pages such as the page shown above. The person who was to receive the coded message would have an identical copy of this book kept securely in the home country. Now, the secret agent would infiltrate a foreign country and start to gather data. To encode it he would choose a page from the codebook, encode his message using the method will look at in a minute, and then the receiver would once he knew which page of the codebook had been used, would be able to decipher very quickly.

The one time pad is uncrackable as long as the codebook uses truly randomly generated numbers (not easy!) and as long as each page from the codebook is only used once – and is never discovered by the enemy. Sometimes this code was cracked because agents became lazy and reused the same pages, other times because the agent was captured and their codebook discovered. Nevertheless, in the age before digital communications it was a very secure method of encoding data.

How does the one time pad work?

It’s all based on Modulo arithmetic (mod 26). This sounds complicated, but basically we just work out the remainder when we divide by 26. For example 4 is still 4 mod 26, because 4 divided by 26 is 0 remainder 4. 30 is also 4 mod 26 because 30 divided by 26 is 1 remainder 4. For negatives we just keep adding 26 until we get a positive number. eg. -10 = 16 mod 26.

Now, say I want to encode the message ” Attack”. I assign each letter in the alphabet a value between 0 and 25 (A = 0, B = 1 etc).

Screen Shot 2015-06-22 at 2.25.45 PM

So Attack = 0 19 0 2 10

Next I use my one time pad. Let’s use the one pictured at the top of the page. The first 5 random numbers are 54048, so I add these in turn working in mod 26 if required.

0 + 5 = 5

19 + 4 = 23

0 + 0 = 0

2 + 4 = 6

10 + 8 = 18

Now I convert these new number back into the alphabet using A = 0, B = 1 etc as before. This gives my code word as:

FXAGS

I can then send this back home using my chosen method (e.g. in a letter perhaps hidden as the first word of every sentence etc). The person receiving the code simply has to work in reverse using the same code pad. He converts FXAGS to numbers:

5 23 0 6 18

and he notes the numbers in his code pad are 54048 so he takes away to reveal the message:

5 – 5 = 0

23 – 4 = 19

0 – 0 = 0

6 – 4 = 2

18 – 8 = 10

Screen Shot 2015-06-22 at 2.25.45 PM

This reveals the hidden message, Attack!

Screen Shot 2015-06-22 at 3.58.28 PM

The beauty of this code is that it can even be done without a code pad – indeed deep cover secret agents were often too scared of being caught with a code book that they used ordinary books. This works in the same way, as long as both parties have agreed in advance on what copy book to use. Say I choose to use John Le Carre’s spy classic The Honourable Schoolboy, page 1 paragraph 1. This can sit innocuously on my bookshelf and yet I can create an equivalent to a code pad by taking each word in turn to make a number. In this case the first word is Afterwards – which would give me the code pad numbers 0 5 19 4 17 22 0 17 3 18. I could then use this to encode in the same manner as above.

mmd1

International School Code Breaking Challenge

We’re now running a huge school code breaking competition.  There are a total of 7 competitions to enter – each one with a number of codes to crack.  Each time a code is cracked this gives the password to access the next clue.  Students who break all codes will be entered onto the leaderboard of fame.  Levels of codes range from upper KS2 to post 16 – so there should be something for everyone.

Choose your level, and good luck!

codeimage4

Level 1: Easy, Age 11-16.  This is intended to be a gentle introduction to code breaking.  Hints provided throughout.

codeimage3

Level 2: Easy, Age 11-16.  This builds on some of the skills from the Level 1 code and includes a mixture of common codes, from Morse Codes to substitution ciphers.

Screen Shot 2015-02-12 at 3.38.30 PM

Level 3: Murder mystery, Medium, Age 11-16.  A murder has been committed in the Maths Department!  Solve the clues to uncover the murderer, the weapon and the room.
Level 4: Murder mystery, Medium, Age 11-16.  Another murder has been committed!  Who can solve it first?

sherlock

Level 5: Medium, Age 11-16.  This level combines knowledge of a variety of codes and methods of solving them.  Caesar shifts, transposition codes and more.

codeimage6

Level 6: Hard, Age 15-18.  This is a real tough challenge – not for the faint hearted!  It is primarily aimed at post 16 students and you can expect to look at binary codes, RSA codes and modulo arithmetic.

Level Extra: Easy, Age 11-16.  A bonus code breaking challenge in case you solve all the others!

mmd1

Murder in the Maths Department

A murder has been committed in the maths department! A body has been discovered surrounded by mathematical objects and only the hardworking maths teachers were in school, doing long division sums for fun at the weekend. One of them must be the murderer.  (The wall of fame of successful detectives will be posted here)

Your task, should you choose to accept it, is to find:

1) The murderer
2) The room
3) The murder weapon

The murder suspects are:

1) Al Jabra – who was wearing a white, T-shirt with 2 stripes and ripped jeans on the day of the murder.
2) Polly Gon – who was wearing a knee-length green skirt, white blouse and gold watch.
3) Lisa Perbound- who was wearing a blue Adidas T-shirt with 3 stripes on the sleeves, Bermuda shorts and a baseball cap.
4) May Trix- who was wearing a black and white pin-stripe suit with shiny black shoes.
5) Ella Ment- who was wearing a blue knitted jumper with a picture of pi on the front, and brown cords.

The possible rooms are:

The possible rooms are:

1) The Canteen
2) The Tuck-shop
3) Room 20
4) Room 18
5) Room 17
6) Room 7

The possible murder weapons are:

1) A wooden metre ruler
2) A large metal stapler
3) A dusty trundle wheel
4) A sharp compass
5) A large maths textbook
6) An oversized calculator

Clue Number 1

mmd12

When you have solved this clue – click here, and enter the last word only of the decoded message (no capital letters).

 

crypto4

This is inspired from the great site,  Practical Cryptography which is a really good resource for code making and code breaking.  One of their articles is about how we can use the Chi Squared test to crack a Caesar Shift code.  Indeed, if you use an online program to crack a Caesar shift, they are probably using this technique.

crypto

This is the formula that you will be using for Chi Squared.  It looks more complicated than it is.  Say we have the following message (also from Practical Cryptography):

AOLJHLZHYJPWOLYPZVULVMAOLLHYSPLZARUVDUHUKZPTWSLZAJPWOLY ZPAPZHAFWLVMZBIZAPABAPVUJPWOLYPUDOPJOLHJOSLAALYPUAOLWSH PUALEAPZZOPMALKHJLYAHPUUBTILYVMWSHJLZKVDUAOLHSWOHILA

We first work out the frequency of each letter which we do using the Counton site.

crypto2

We next need to work out the expected values for each letter.  To do this we first need the expected percentages for the English language:

crypto3

Then we can count the number of letters in the code we want to crack (162 – again we can use an online tool)

Now, to find the expected number of As in the code we simply do 162 x 0.082 = 13.284.

The actual number of As in the code is 18.

Therefore we can do (13.284-18)2/18  following the formula at the top of the page.

We then do exactly the same for the Bs in the code.  The expected number is 162 x 0.015 = 2.43.  The actual number is 3.

Therefore we can do (3-2.43)2 /2.43

We do this same method for all the letters A-Z and then add all those numbers together.  This is our Chi Squared statistic.  The lower the value, the closer the 2 distributions are.  If the expected values and the observed values are the same then there will be a chi squared of zero.

If you add all the values together you get a Chi Squared value of ≈1634 – which is quite large!   This is what we would expect – because we already know that the code we have received has letter frequencies quite different to normal English sentences.  Now, what a Caesar Shift decoder can do is shift the received code through all the permutations and then for each one find out the Chi Squared value.  The permutation with the lowest Chi Squared will be the solution.

For example, if we shift every letter in our received code back by one – using the Counton tool (so A goes to Z etc) we get:

ZNKIGKYGXIOVNKXOYUTKULZNKKGXROKYZQTUCTGTJYOSVRKYZIOVNKX YOZOYGZEVKULYAHYZOZAZOUTIOVNKXOTCNOINKGINRKZZKXOTZNKVRG OTZKDZOYYNOLZKJGIKXZGOTTASHKXULVRGIKYJUCTZNKGRVNGHKZ

We can then do the same Chi Squared calculations as before.  This will give a Chi Squared of ≈3440 – which is an even worse fit than the last calculation.  If we carried this on so that A goes to T we would get:

THECAESARCIPHERISONEOFTHEEARLIESTKNOWNANDSIMPLESTCIPHER SITISATYPEOFSUBSTITUTIONCIPHERINWHICHEACHLETTERINTHEPLA INTEXTISSHIFTEDACERTAINNUMBEROFPLACESDOWNTHEALPHABET

and a Chi Squared on this would show that this has a Chi Squared of ≈33 – ie it is a very good fit.  (You will get closer to zero on very long code texts which follow standard English usage).  Now, obviously we could see that this is the correct decryption without even working out the Chi Squared value – but this method allows a computer to do it, without needing the ability to understand English.  Additionally a codebreaker who spoke no English would still be able to decipher this code, on mathematics alone.

The Practical Cryptography site have a tool for quickly working out Chi Squared values from texts – so you can experiment with your own codes.  Note that this is a slightly different use of Chi-Squared as here we are not comparing with a critical value, but instead comparing all Chi Squared to find the lowest value.

If you liked this post you might also like:

Code Breakers Wanted by the NSA – A look at some other code breaking techniques.

RSA Public Key Encryption – The Code that Secures the internet – How understanding RSA code is essential for all people involved in internet security.

Website Stats

  • 3,904,404 views

Recent Posts

Follow IB Maths Resources from British International School Phuket on WordPress.com