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

**Elliptical Curve Cryptography**

Elliptical curves are a very important new area of mathematics which have been greatly explored over the past few decades. They have shown tremendous potential as a tool for solving complicated number problems and also for use in cryptography.

Andrew Wiles, who solved one of the most famous maths problems of the last 400 years, Fermat’s Last Theorem, using elliptical curves. In the last few decades there has also been a lot of research into using elliptical curves instead of RSA encryption to keep data transfer safe online. So, what are elliptical curves? On a simple level they can be regarded as curves of the form:

y² = x³ +ax + b

If we’re being a bit more accurate, we also need 4a³ + 27b² ≠ 0. This stops the graph having “singular points” which cause problems with the calculations. We also have a “point at infinity” which can be thought of as an extra point added on to the usual x,y plane representing infinity. This also helps with calculations – though we don’t need to go into this in any more detail here!

**Addition of two **points **A and B**

What makes elliptical curves so useful is that we can create a group structure using them. Groups are very important mathematical structures because of their usefulness in being applied to problem solving. A group needs to have certain properties. For example, we need to be able to combine 2 members of the group to create a 3rd member which is also in the group. This is how it is done with elliptical curves:

Take 2 points A and B on y² = x³ -4x + 1. In the example we have A = (2,1) and B = (-2,-1). We now want to find an answer for A + B which also is on the elliptical curve. If we add them as we might vectors we get (0,2) – but unfortunately this is not on the curve. So, we define the addition A + B through the following geometric steps.

We join up the points A and B. This line intersects the curve in one more place, C.

We then reflect the point C in the x axis. We then define this new point C’ = A + B. In this case this means that (2,1) + (-2,-1) = (1/4, -1/8).

**Addition of 2 points when A = B**

We have to also be able to cope with the situation when the point A and B are the same. Here we create the line through A which is the tangent to the curve at that point:

We then use the same transformation as before to say that A+B = C’. For example with the curve y² = x³ -12x, if we start with the point A(-2,4) then this transformation tells us that A + A = (4,-4).

**Elliptical curves over finite fields**

For the purposes of cryptography we often work with elliptical curves over finite fields. This means we (say) only consider integer coordinate solutions and work in modulo arithmetic (mod prime).

Say we start with the curve y² = x³ +x+1, and just look at the positive integer solutions mod 7. (Plotted using the site here).

When x = 1,

y² = 1³ +1 + 1

y² = 3

So this has no integer solution.

Next, when x = 2 we have:

y² = 2³ +2 +1 = 11.

However when we are working mod 7 we look at the remainder when 11 is divided by 7 (which is 4). So:

y² = 4 (mod 7)

y = 2 or y = -2 = 5 (mod 7)

When x = 3 we have:

y² = 3³ +3 +1 = 31

y² = 3 (mod 7)

which has no integer solutions.

In fact, all the following coordinate points satisfy the equation (mod 7):

(2,2), (0,1), (0,6), (2,5).

**Addition under modulo arithmetic**

Let’s look at the coordinate points we calculated before for the elliptical curve y² = x³ +x+1 (integers solutions and mod 7) – they form a group under addition. (Table generated here)

In order to calculate addition of points when dealing with elliptical curves with integer points mod prime we use the same idea as expressed above for general graphs.

The table tells us that (0,1) + (0,1) = (2,5). If we were doing this from the graph we would draw the tangent to the curve at (0,1), find where it intersects the graph again, then reflect this point in the x axis. We can do all this algebraically.

First we find the gradient of the tangent when x = 0:

Next we have to do division modulo 7 (you can use a calculator here, and you can also read more about division modulo p here).

Next we find the equation of the tangent through (0,1):

Next we find where this tangent intersects the curve again (I used Wolfram Alpha to solve this mod 7)

We then substitute the value x = 2 into the original curve to find the y coordinates:

(2,2) is the point where the tangent would touch the curve and (2,5) is the equivalent of the reflection transformation. Therefore our answer is (2,5). i.e (0,1) + (0,1) = (2,5) as required.

When adding points which are not the same we use the same idea – but have to find the gradient of the line joining the 2 points rather than the gradient of the tangent. We can also note that when we try and add points such as (2,5) and (2,2) the line joining these does not intersect the graph again and hence we affix the point an infinity as (2,5) + (2,2).

**Using elliptical codes for cryptography**

Even though all this might seem very abstract, these methods of calculating points on elliptical curves form the basis of elliptical cryptography. The basic idea is that it takes computers a very long time to make these sorts of calculations – and so they can be used very effectively to encrypt data.

Say for example two people wish to create an encryption key.

They decide on an elliptical curve and modulo. Let’s say they decide on y² = x³ +x+1 for integers, mod 7.

This creates the addition group

Next they choose a point of the curve. Let’s say they choose P(1,1).

Person 1 chooses a secret number n and then sends nP (openly). So say Person 1 chooses n = 2. 2(1,1) = (1,1) + (1,1) = (0,2). Person 1 sends (0,2).

Person 2 chooses a secret number m and then sends mP (openly). So say Person 2 chooses m = 3. 3(1,1) = (1,1) + (1,1) + (1,1) = (0,2) + (1,1) = (0,5). Person 2 sends (0,5).

Both Person 1 and Person 2 can easily calculate mnP (the secret key).

Person 1 receives (0,5) and so does 2(0,5) = (0,5) + (0,5) = (1,1). This is the secret key.

Person 2 receives (0,2) and so does 3(0,2) = (0,2) + (0,2) +(0,2) = (1,1). This is the same secret key.

But for a person who can see mP and nP there is no quick method for working out mnP – with a brute force approach extremely time consuming. Therefore this method can be successfully used to encrypt data.

**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.

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.

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:

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.

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!

Essential resources for IB students:

Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams. I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.

There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions. What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial. Really useful!

The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers. These all have worked solutions and allow you to focus on specific topics or start general revision. This also has some excellent challenging questions for those students aiming for 6s and 7s.

Each course also has a dedicated video tutorial section which provides 5-15 minute tutorial videos on every single syllabus part – handily sorted into topic categories.

2) Exploration Guides and Paper 3 Resources

I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations. The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.

**Alan Turing Cryptography Competition**

Manchester University are running their 5th Alan Turing Cryptography Competition this January. It’s aimed at secondary and post 16 students. If you are in the UK and in year 11 or below you can register for the official prizes, for everyone else you can still register and see if you make it onto the leaderboard.

Read some of the introduction to the competition below:

*Do you like breaking codes and solving ciphers?*

*Can you, and your friends, unravel the mystery of the Artificial Adventure?*

*Would you like the chance to use your mathematical skills to win some great prizes?*

*The competition starts on Monday 25th January, and you can register your team (or join an existing team) here. A team consists of at most 4 members. It is also possible to register as a `non-competing’ team, for instance if you’re a teacher who would like to follow the competition or if some members of your team are too old to take part. Registration opens on Monday 30th November. *

*The competition follows the story of two young cipher sleuths, Mike and Ellie, as they get caught up in a crptographic adventure `The Tale of the Artificial Adventure’. Every week or two weeks a new chapter of the story is released, each with a fiendish code to crack. There are six chapters in total (plus an epilogue to conclude the story). Points can be earned by cracking each code and submitting your answer. The leaderboard keeps track of how well each team is doing. *

The competition starts on January 25th. Click on the competition website to register – and good luck!

**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.

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.

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:

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.

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!

Essential resources for IB students:

Revision Village has been put together to help IB students with topic revision both for during the course and for the end of Year 12 school exams and Year 13 final exams. I would strongly recommend students use this as a resource during the course (not just for final revision in Y13!) There are specific resources for HL and SL students for both Analysis and Applications.

There is a comprehensive Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and then provides a large bank of graded questions. What I like about this is that you are given a difficulty rating, as well as a mark scheme and also a worked video tutorial. Really useful!

The Practice Exams section takes you to a large number of ready made quizzes, exams and predicted papers. These all have worked solutions and allow you to focus on specific topics or start general revision. This also has some excellent challenging questions for those students aiming for 6s and 7s.

Each course also has a dedicated video tutorial section which provides 5-15 minute tutorial videos on every single syllabus part – handily sorted into topic categories.

2) Exploration Guides and Paper 3 Resources

I’ve put together four comprehensive pdf guides to help students prepare for their exploration coursework and Paper 3 investigations. The exploration guides talk through the marking criteria, common student mistakes, excellent ideas for explorations, technology advice, modeling methods and a variety of statistical techniques with detailed explanations. I’ve also made 17 full investigation questions which are also excellent starting points for explorations. The Exploration Guides can be downloaded here and the Paper 3 Questions can be downloaded here.

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).

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

This reveals the hidden message, Attack!

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.