**Society Investigating Mathematical
Mind-Expanding Recreations**

Cryptography and Elliptic Curves

V. Kumar Murty

University of Toronto

This is a summary of what was presented and discussed
at the April 22nd **SIMMER** meeting, along with some problems and
questions to think about.

We can learn an unfamiliar language in many ways, but mostly by exposure to it. This is the idea behind immersion in a language, such as French immersion. It is the same principle in music or dance. What looks at first like meaningless sound or movement slowly becomes meaningful as we expose ourselves to it. The same applies to codes and that is why no code will live forever. People will learn the language in course of time and then we need a new secret language.

Sometimes, we can make a language difficult to understand by placing it in an inaccesible medium. For example, a smart card may contain all sorts of information about the holder. But unless you have a machine that can read the card, you cannot access that information. It is similar to experts in a field using technical jargon to explain things.

The mathematics of cryptography has to do with using numbers as a language whose meaning is difficult to decipher. Some may say that numbers themselves are difficult to decipher and so confusing that no additonal code is necessary! Nevertheless, cryptography looks for ways of expressing information that one wishes to communicate to selected or authorized people.

y^2 = x^3 + ax + bsuch that the cubic polynomial on the right hand side has three distinct roots. For example,

y^2 = x(x-1)(x+1)is an elliptic curve, but

y^2 = x(x-1)^2is not. The difference between the two is that when there are repeated roots, the curve is essentially a conic. For example, in the above case, making the change of variable

w = y/(x-1)the equation becomes

x = w^2which is the equation of a parabola. When the roots are distinct, there is no coordinate change that will identify the curve with a conic.

**Exercise 1**

On the elliptic curve

y^2 = x^3 - 36xadd the points P = (-3,9) and Q = (-2,8).

y^2 = x^3 + ax + bin a finite field. For example, we can consider the solution set to the congruence

y^2 congruent to x^3 + ax + b (mod p).

y^2 congruent to x^3 + x (mod 7).

On the other hand, if we are given a sequence of points on the curve, to decode it, we consider each point (x,y) and set m to be the greatest integer less than (x-1)/k. Then the point (x,y) decodes as the symbol m.

In order to actually carry this out one has to be able to solve the congruence

y^2 = a (mod p).There is an algorithm for this, but for tonight we will just use a table.

In actual applications, cryptography using elliptic curves is much more complicated. In fact, what we have discussed above is the "easy" part. One does some more operations on the points constructed so as to make them harder to decipher.

**Exercise 3**

Consider the elliptic curve

y^2 + y congruent to x^3 - x (mod 751).This curve has N = 727 points. Write the message

STOP007as a sequence of seven points on the curve. Decode the sequence of points

(361,383), (241,605), (201,380), (461,467), (581,395)into a reply message.

- Neal Koblitz,
*Elliptic Curves and Cryptography*, Springer-Verlag. - The site www.certicom.com has really good material on elliptic curves and cryptography, including a tutorial at http://www.certicom.com/ecc/index.htm.

Navigation Panel:

Switch to graphical version (better pictures & formulas)

Access printed version in PostScript format (requires PostScript printer)

Go to SIMMER Home Page

Go to The Fields Institute Home Page

Go to University of Toronto Mathematics Network Home Page