Society Investigating Mathematical Mind-Expanding Recreations
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.
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).Exercise 2 Find the solution set of
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.
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.