Elliptic Curves – Part 2

This post aims to clarify some of the background on elliptic crves over finite fields. I want to give some intuition on what an elliptic curve is, where the point at infinity comes from, and some cool things you can do with elliptic curves. In this post, we are working over a field , and its multiplicative group .

Elliptic curves are defined over the projective plane . Simply put, on a regular plane, parallel lines never intersect. The projective plane can be thought of as a regular plane, with an extra point called the point at infinity where parallel lines intersect. We need to define what we mean by a curve on . We need that if is on the curve, then also is, for all . In particular, if is the equation of a projective curve, then must satisfy . So needs to be a homogeneous polynomial.

For now, we will assume that , that is, . Then one can simplify the general homogeneous polynomial of degree 3 as follows: . You can see that this looks similar to the equation for an elliptic curve I gave last time.

First, we want to find the point at infinity. We want , and we know that the point at infinity is where . But this implies that , so the point at infinity is , since scalar multiples are the same point. We call this point , and it is on every elliptic curve.

The one additional condition we place on an elliptic curve is that the points must be non-singular. This means that is non-zero. Again, we work with . We can calculate . Then we have that , which is non-zero. Hence the point at infinity is on every elliptic curve.

Now, let’s get back to finding the equation of a general elliptic curve. For all the affine points, . Hence . Thus . This is called the of an elliptic curve. Now we have almost managed to properly define elliptic curves.

For the affine points, we have that . Hence a point is non-singular if and only if or . Using this, we can deduce that the equation defines an elliptic curve if and only if . We call the discriminant of the elliptic curve.

To finish up, I will mention two applications of elliptic curves. They can be used to share a secret key with a similar method as the discrete logarithm Diffie-Hellman key exchange. They can also be used to factor large integers, using an algorithm called Lenstra Elliptic Curve Factorisation. This method is based on adding points of elliptic curves. A basic outline of the algorithm is as follows. Given an integer , choose an elliptic curve over and a point on this curve. Add this point to itself until calculating the sum gives a non-invertible denominator . Then applying Euclid’s Algorithm, you get as a non-trivial factor of .

Breaking the Vigenere Cipher

The Vigenere cipher was first described in 1553 by an Italian mathematician, Giovan Battista Bellaso. It was misattributed to a French mathematician, Blaise de Vigenere in the 19th century (see Stigler’s Law), and that is where the name comes from. As you saw in the previous post, the cipher is easy to describe and implement, and yet it went unbroken for 300 years.

The main weakness of the Vigenere cipher is that the keyword is repeated. If one can find out the length of the key, it is possible to treat the Vigenere cipher as interwoven additive ciphers, breaking the additive cipher for each letter in the key separately.

The first published way to break the cipher, published in 1863 by Friedrich Kasiski, exploits this weakness. In a ciphertext of some length, it is highly likely that the same word or sequence of letters is encrypted by the same piece of the keyword. One simply finds all identical sequences of length at least 3 in the ciphertext and calculates the distances between them. The length of the keyword is likely to be this greatest common divisor. Then the rest of the cipher can be broken as described above.

I find it remarkable that this simple cipher went unbroken for such a long time. It is one of my favourite examples of how simple and elegant mathematics can be. Both the encryption and Kasiski’s method are very simple and yet so effective. Today, this version of the Vigenere cipher is not in use, as it can be broken very easily. However, on trying to improve it, the mathematician Willian Friedman stumbled on the one-time pad.

The one-time pad is theoretically unbreakable. Mathematically, that means that the given a ciphertext and two possible decryptions, an adversary cannot tell which decryption is correct. What Friedman did was show that if the keyword is of the same length as the plaintext, then the cipher is unbreakable. Today, the one-time pad is implemented as follows. The plaintext is written in binary, and then a random binary string of the same length as the plaintext is generated. The plaintext and the key are then ‘added’ using the XOR operation bit by bit.

This resulting cipher is theoretically unbreakable. It should be considered though that it is also massively inconvenient. To actually use it, you have to transmit a secret key of the same length as the message to the recipient, and if you can do that securely, you might as well send the original message through that channel.

This was a little bit on cryptography. I’m taking two courses on cryptography and two that contain some cryptography, so there will probably be some more posts about that. I’m still in the waiting for more information from my university stage. I really thought that all this waiting and uncertainty would be over once I decided on U. But, then again, not being able to do anything is making my revision incredibly productive 🙂

Waiting and Vigenere ciphers

I am right now waiting for U to get back to me about all the paperwork needed for my visa application. I’m really anxious to get started with everything.

In the mean time, revision is keeping me busy. Here at my university, our final grade in every class taken this year is decided during our exam term. I have 8 exams during the next month that completely determine my degree classification, so there is a lot of revision to be done. The course I’m revising right now is on cryptography.

One of the more interesting components in the course is Vigenere ciphers. It is a fairly simple, polyalphabetic cipher. That means that each letter can be mapped to several other letter. Let me explain why they are interesting. One of the simplest ciphers that we have all worked with as children is the additive cipher. We simply let each letter correspond to a number 0-25 (we are working in ). Then, add a fixed number to each letter. Translate the numbers back to letters to get the ciphertext.

For example, using an additive cipher we first rewrite the plaintext MATHEMATICS to numbers as 12 0 19 7 4 12 0 19 8 2 18. If we choose the key the ciphertext becomes 16 4 23 11 8 16 4 23 12 6 22 which corresponds to QEXLIQEXMGW.

This is an example of a monoalphabetic cipher. Each letter in the plaintext maps onto exactly one letter in the ciphertext. It is also very simple to break. It can be done fairly easily by hand, given a ciphertext that is long enough. The additive cipher preserves language statistics, so in a sufficiently long ciphertext you know for example that the most common letter will be an E, two letter words will be IS, AN or IT and three letter words will be THE, SHE, HIM or HER most often. Using these kinds of language statistics, one can find a few words and then deduce the key.

With a computer it is even easier to break an additive cipher. Since the keyspace only consists of 26 possible keys, a computer (or a person with some patience) can search them all in essentially no time to find the one that yields English text.

In monoalphabetic ciphers, one always preserves language statistics. To avoid this, we introduce polyalphabetic ciphers where one letter in the plaintext can be mapped to several different letters in the ciphertext. The idea behind the Vigenere cipher is to pick a keyword and use it to encrypt the plaintext block by block. Say the chosen plaintext is SAY HELLO TO MY LITTLE FRIEND. We also choose the key to be ABACUSES. Then we transcribe the plaintext to numbers and write the keyword repeatedly under the plaintext.

We get the ciphertext by adding, in the same way as for the additive cipher, the value of the plaintext letter to the value of the letter in the keyword written directly below.

So the cipher text is SBY JYDPG TP MA FAXLLF FTCWRV. This cipher system eliminates the language statistics that make the additive cipher so simple to break. Take for example the letter E which is mapped to letters Y, F and W. This means that there are no easy clues in the ciphertext about the structure of the plaintext. Also, the keyspace is much larger than for the additive cipher. The key can be any combination of letters of length less than or equal to the length of the plaintext. Hence an exhaustive search is very difficult, not to say impossible to do by hand. There are ways to break Vigenere ciphers by hand, and I will explain one of them in my next post.