You are currently browsing the tag archive for the ‘codes’ tag.

Elliptical Curve Cryptography

This post builds on some of the ideas in the previous post on elliptical curves. This blog originally appeared in a Plus Maths article I wrote here.  The excellent Numberphile video above expands on some of the ideas below.

On a (slightly simplified) level elliptical curves they can be regarded as curves of the form:

y² = x³ +ax + b

So for example the curve below is an elliptical curve.  This curve also has an added point at infinity though we don’t need to worry about that here.  Elliptical curve cryptography is based on the difficulty in solving arithmetic problems on these curves.  If you remember from the last post, we have a special way of defining the addition of 2 points.

elliptical1

Let’s say 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.

elliptical3

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

elliptical4

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

Trying another example, y² = x³ -5x + 4 (below), with A = (1,0) and B = (0,2) we have C = (3,-4) and C’ = (3,4). Therefore (1,0) + (0,2) = (3,4).

elliptical5

We also need to have a definition when A and B define the same point on the curve. This will give us the definition of 2A.  In this case we take the tangent to the curve at that point, and then as before find the intersection of this line and the curve, before reflecting the point.  This probably is easier to understand with another graph:

elliptical10

Here we used the graph y² = x³ -5x + 4 again.  This time point A = B = (-1.2, 2.88) and we have drawn the tangent to the curve at this point, which gives point D, which is then reflected in the x axis to give D’. D’ = (2.41, -2.43).  Therefore we can say 2A = D’, or 2(-1.2, 2.88) = (2.41, -2.43).

Now addition of points is defined we can see how elliptical curve cryptography works.  The basic idea is that given 2 points on the curve, say A and B, it takes a huge amount of computing power to work out the value a such that aA = B.  For example, say I use the curve y² = x³ -25x to encrypt, and the 2 points on the curve are A = (-4,6) and B = (1681/144 , -62279/1728).  Someone who wanted to break my encryption would need to find the value a such that a(-4,6) = (1681/144 , -62279/1728).   The actual answer is a =2 which we can show graphically.  As we want to show that 2(-4,6) = (1681/144 , -62279/1728) , we can use the previous method of finding the tangent at the point (-4,6):

elliptical12

We can then check with Geogebra which shows that B’ is indeed (1681/144 , -62279/1728).  When a is chosen so that it is very large, this calculation becomes very difficult to attack using brute force methods – which would require checking 2(4,-6), 3(4,-6), 4(4,-6)… until the solution (1681/144 , -62279/1728) was found.

elliptical14

NSA and hacking data

Elliptical curve cryptography has some advantages over RSA cryptography – which is based on the difficulty of factorising large primes – as less digits are required to create a problem of equal difficulty.  Therefore data can be encoded more efficiently (and thus more rapidly) than using RSA encryption.  Currently the digital currency Bitcoin uses elliptical curve cryptography, and it is likely that its use will become more widespread as more and more data is digitalised.  However, it’s worth noting that as yet no-one has proved that it has to be difficult to crack elliptical curves – there may be a novel approach which is able to solve the problem in a much shorter time.  Indeed many mathematicians and computer scientists are working in this field.

Government digital spy agencies like the NSA and GCHQ are also very interested in such encryption techniques.  If there was a method of solving this problem quickly then overnight large amounts of encrypted data would be accessible – and for example Bitcoin currency exchange  would no longer be secure.  It also recently transpired that the NSA has built “backdoor” entries into some elliptical curve cryptography algorithms which have allowed them to access data that the people sending it thought was secure.   Mathematics is at the heart of this new digital arms race.

If you enjoyed this post you might also like:

RSA Encryption – the encryption system which secures the internet.

Circular inversion – learn about some other geometrical transformations used in university level mathematics.

IB Revision

Screen Shot 2018-03-19 at 4.35.19 PM

If you’re already thinking about your coursework then it’s probably also time to start planning some revision, either for the end of Year 12 school exams or Year 13 final exams. There’s a really great website that I would strongly recommend students use – you choose your subject (HL/SL/Studies if your exam is in 2020 or Applications/Analysis if your exam is in 2021), and then have the following resources:

Screen Shot 2018-03-19 at 4.42.05 PM.pngThe Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and each area then has a number 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!

Screen Shot 2019-07-27 at 10.02.40 AM

The Practice Exams section takes you to ready made exams on each topic – again with worked solutions.  This also has some harder exams for those students aiming for 6s and 7s and the Past IB Exams section takes you to full video worked solutions to every question on every past paper – and you can also get a prediction exam for the upcoming year.

I would really recommend everyone making use of this – there is a mixture of a lot of free content as well as premium content so have a look and see what you think.

code2

Crypto Analysis to Crack Vigenere Ciphers

(This post assumes some familiarity with both Vigenere and Ceasar Shift Ciphers.  You can do some background reading on them here first).

We can crack a Vigenere Cipher using mathematical analysis.  Vigenere Ciphers are more difficult to crack than Caesar Shifts, however they are still susceptible to mathematical techniques.  As an example, say we receive the code:

VVLWKGDRGLDQRZHSHVRAVVHZKUHRGFHGKDKITKRVMG

If we know it is a Vigenere Cipher encoded with the word CODE then we can create the following decoding table.

VIGENERE4

Here we have 4 alphabets, each starting with the letters of the code word.  To decode we cycle through the alphabets.  The first code letter is V so we find this in the C row and then look at the letter at the top of the column – this is T.  This is our first letter.  Next the second code letter is also V, but this time we find it the O row.  The column letter corresponding to this is H.  We continue this method which gives the decoded sentence:

THIS IS AN EXAMPLE OF HOW THE VIGENERE CIPHER WORKS

How do we know what cipher to use? 

In any kind of crypto-analyis we need to decide which technique has been used.  Say for example we receive the message:

GZEFWCEWTPGDRASPGNGSIAWDVFTUASZWSFSGRQOHEUFLAQVTUWFV
JSGHRVEEAMMOWRGGTUWSRUOAVSDMAEWNHEBRJTBURNUKGZIFOHR
FYBMHNNEQGNRLHNLCYACXTEYGWNFDRFTRJTUWNHEBRJ

In real code breaking we won’t have a message alongside it saying, “Use a Vigenere Cipher.”  A large part of the skill of code breaking is deciding which encoding technique has been used.  For our received message we have the frequency:

VINEGERE7

So, in this case is it best to do look for a Caesar Shift or a Vigenere Cipher?  To find this out, we could do with finding out how “smooth” the bar chart is and how it compares with the expected frequencies.  The expected values in English are:

vigenere3

A Caesar Shift simply shifts every letter in the message by a given number of letters in the alphabet, so we would expect a frequency barchart for a Caesar Shift to have the same peaks and troughs (just shifted along).  The Vigenere makes frequency analysis more difficult because it “smooths out” the frequencies – this means that the bar chart for the frequency will be less spiky and more uniform.

Incidence of Coincidence

A mathematical method to check how smooth the bar chart is, is to use the Incidence of Coincidence – this method is outlined in this post on Practical Cryptography, and uses this formula:

VIGENERE5

There is also a script on the site to work out the I.C for us.  If we enter our received code we get an I.C of 0.045.  We would expect an I.C of around 0.067 for a regular distribution of English letters (which we would find in a Caesar Shift for example).  Therefore this I.C value is a clue that we have a Vigenere Cipher rather than a Caesar shift.

Exploiting the cyclic nature of the Vigenere Cipher

So, we suspect it is a Vigenere Cipher, next we want to find out what the code word that was used to generate the code table is.  To do this we can look at the received code for repeating groups of letters.   There is a cyclic nature to the Vigenere Cipher, so there will also be a cyclic nature to the encoded message.

Using the site Crypto Corner we can analyse the text for repeating patterns of letters.  This gives us:

VINEGER8

This clearly indicates that there are a lot of letters repeating with period of 3.  Therefore it is a good guess that the keyword is also length 3.

So, next we can split the received message into 3 separate messages:

GFEPRPGAVUZFRHFQUVGVAOGURADEHRBNGFRBNQRNYXYNRRUHR
ZWWGAGSWFAWSQELVWJHEMWGWUVMWEJUUZOFMNGLLATGFFJWEJ
ECTDSNIDTSSGOUATFSREMRTSOSANBTRKIHYHENHCCEWDTTNB

Here we have simply generated the first line by taking the first, fourth, seventh, tenth etc. letters.

Cracking the code

Now we can do three separate Cesar Shift tests on these separate lines:

The first line has frequency:

vigg1

which strongly suggests that R in the cipher text is going to E.  This gives us the following Caesar Shift:

vigenere10

The second line has the following frequency:

VINEGER11

Which strongly suggests that W in the cipher text is going to E.  This gives us:

vigenere11

Lastly we notice that this will give us the codeword NS_.  Well NSA, (the American digital spy agency) would be a good guess so for the third Caesar Shift we try:

vigg2

Putting these together we have the Vigenere Cipher:

vigg3

and this decodes our received code as:

THE SECRET CODE IS CONTAINED IN THIS MESSAGE.  YOU MUST ADD THE FIRST PRIME NUMBER TO THE SECOND SQUARE NUMBER TO CRACK THIS. WHEN YOU HAVE DONE THAT CLICK BELOW AND ENTER THE NUMBER.

We have done it!  We have cracked the Vigenere Cipher using a mixture of statistics, logic and intuition.  The method may seem long, but this was a cipher that was thought to be unbreakable – and indeed took nearly 300 years to crack.  Today, using statistical algorithms it can be cracked in seconds.  Codes have moved on from the Vigenere Cipher – but maths remains at the heart of both making and breaking them.

If you enjoyed this post you might also like:

The Maths Code Challenge – three levels of codes to attempt, each one providing a password to access the next code in the series.  Can you make it onto the leaderboard?

RSA public key encryption – the code that secures the internet.

 

 

gchq

GCHQ – the British cyber spy agency – have had a rough few months following some staggering revelations from Edward Snowden, so they’re doing some positive PR at the moment to highlight the importance of mathematics and computing skills in code-breaking.  There are 4 codes to solve (the first one posted above) – each answer leading on an internet treasure-hunt to the next clue.  Those who can solve all 4 clues stand a chance of winning a Google Nexus and Raspberry Pi – and possibly could lead to a job opportunity with GCHQ.

The competition started two days ago (10th September) – and there is a six week deadline to solve all clues.  So, get cracking!

If you liked this post you might also like:

Cracking Codes Lesson. An example of 2 double period lessons on code breaking

Cracking ISBN and Credit Card Codes. The mathematics behind ISBN codes and credit card codes

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.

IB Revision

Screen Shot 2018-03-19 at 4.35.19 PM

If you’re already thinking about your coursework then it’s probably also time to start planning some revision, either for the end of Year 12 school exams or Year 13 final exams. There’s a really great website that I would strongly recommend students use – you choose your subject (HL/SL/Studies if your exam is in 2020 or Applications/Analysis if your exam is in 2021), and then have the following resources:

Screen Shot 2018-03-19 at 4.42.05 PM.pngThe Questionbank takes you to a breakdown of each main subject area (e.g. Algebra, Calculus etc) and each area then has a number 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!

Screen Shot 2019-07-27 at 10.02.40 AM

The Practice Exams section takes you to ready made exams on each topic – again with worked solutions.  This also has some harder exams for those students aiming for 6s and 7s and the Past IB Exams section takes you to full video worked solutions to every question on every past paper – and you can also get a prediction exam for the upcoming year.

I would really recommend everyone making use of this – there is a mixture of a lot of free content as well as premium content so have a look and see what you think.

code

Code breaking is a good activity to introduce problem solving skills and real world careers for mathematicians. 

Code Cracking worksheets

Marcus De Satouy video explaining codes

Counton website to generate different codes

Nice Morse Code Generator

Numberphile also have a good introduction to public key encryption using prime numbers.

Website Stats

  • 7,331,621 views

IB Maths Exploration Guide

IB Maths Exploration Guide

A comprehensive 63 page pdf guide to help you get excellent marks on your maths investigation. Includes:

  1. Investigation essentials,
  2. Marking criteria guidance,
  3. 70 hand picked interesting topics
  4. Useful websites for use in the exploration,
  5. A student checklist for top marks
  6. Avoiding common student mistakes
  7. A selection of detailed exploration ideas
  8. Advice on using Geogebra, Desmos and Tracker.

Available to download here.

IB Exploration Modelling and Statistics Guide


IB Exploration Modelling and Statistics Guide

A 60 page pdf guide full of advice to help with modelling and statistics explorations – focusing in on non-calculator methods in order to show good understanding. Includes:

  1. Pearson’s Product: Height and arm span
  2. How to calculate standard deviation by hand
  3. Binomial investigation: ESP powers
  4. Paired t tests and 2 sample t tests: Reaction times
  5. Chi Squared: Efficiency of vaccines
  6. Spearman’s rank: Taste preference of cola
  7. Linear regression and log linearization.
  8. Quadratic regression and cubic regression.
  9. Exponential and trigonometric regression.

Available to download here.

Recent Posts

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