James Ellis’s papers declassified!

James Ellis is one of Britain’s great unsung heroes, whose work at GCHQ as a cryptographer and mathematician that led to the development of methods used to combat cyber terrorism and crime, has been largely forgotten. However, GCHQ has recently published a number of documents (1 | 2) written by Ellis in 1970 to highlight the key role he played in the online security used by ordinary individuals on a daily basis, for example in internet shopping.

In a speech given last week by the director of GCHQ, Robert Hannigan, at MIT University, large praise was given to Ellis and his accomplishments:

“The sheer boldness of Ellis’ concept, and of [fellow GCHQ cryptographers] Malcolm Williams and Clifford Cock’s subsequent work is still staggering, reversing centuries of assumptions about how communications could be protected… Strong, relatively cheap encryption became ‘democratised’ and enabled more secure communications on a global scale. Encryption went from being a tool of strategic advantage between super-power blocs, but to a key enabler of individual freedom and safety.”

So what did Ellis do?

Ellis found the solution to the problem of sending secret messages from one person to another without the need for a system of keys or codes, to allow the receiver to decode the message. In 1969, Ellis arrived at a solution whereby the receiver of the message would encode the message, not the sender.

This is now known as Public-Key Cryptography, which is one of the greatest breakthroughs in modern cryptography.

However, for years their discovery was classified as top-secret, preventing them from publishing their findings. Instead, researchers at Stanford University and MIT came up with a similar solution and published it, claiming the glory.

Public-Key Cryptography

 

I remember vaguely reading about James Ellis in Simon Singh’s book ‘The Code Book’, and I’m so happy that his papers were finally declassified! Hope you enjoyed this post. M x

Elliptic Curve Cryptography

What are Elliptic Curves?

An elliptic curve is a cubic curve whose solutions are confined to a region of space that is topologically equivalent to a torus (doughnut-like shape). It’s defined by an equation in the form:

where

as this ensures that the curve has no singular points (the curve is nice and smooth and doesn’t contain any sharp points or cusps).

They have shown potential as a tool for solving complicated number problems. Additionally, in the last few decades there has been a lot of research into using elliptic curves for encryption instead of  RSA encryption to keep data transfer safe online.

Elliptic Curve Cryptography

Elliptic Curve Cryptography is an example of public key cryptography. This is when the messages are encrypted using a public key. Decryption is then only possible using a mathematical private key, which is almost impossible to determine if you only know the public key.

Elliptic Curve cryptography is based on the difficulty of solving number problems involving elliptic curves.

Bellow are some examples of elliptic curves:

For uses in cryptography a and b are required to come from special sets of numbers called finite fields (a field that contains a finite number of elements).

Adding Points

Let’s consider the curve

and the two points A = (2,1) and B = (-2, -1), both of which lie on the curve. Now, we want to find an answer to A = B, which should also lie on the elliptic curve.

Thus, by joining the points A and B with a straight line, we can see that it intersects the curve in one more place, point C. We then reflect this point in the x – axis and define it as point C’. Therefore,

A + B = C’.

In our example this means that

(2,1) + (-2,-1) = (1/4, -1/8)

The only situation where C’ is not equal to A + B is when B is a reflection of A in the x-axis. In this case, the line we use to define the sum is vertical and there isn’t a third point at which it meets they curve.

Below is an image to depict the different cases which may arise with different points:

It turns out that, given two points A and B on an elliptic curve, finding a number n such that B = nA can take an enormous amount of computing power, especially when n is large. In elliptic curve cryptography points A and B can be used as a public key and the number n as the private key. Anyone can encrypt a message using the publicly available public key, but only the person in possession of the private key – the number n – can decrypt them.

Advantages

Elliptic curve cryptography has some advantages over RSA cryptography, which is based on the difficulty of factorising, as fewer digits are required to create a problem of equal difficulty. Therefore data can be encoded more efficiently and rapidly than using RSA encryption.

However, no one has proved that it has to be difficult to crack elliptic curves, and in fact there may be a novel approach that is able to solve the problem in a much shorter time. Indeed many mathematicians and computer scientists are working in this field.

So what are your thoughts on elliptic curve cryptography? M x