Elliptic Curves, Characteristic 2

Characteristic 2

Why mess with characteristic 2? Isn't that rather obscure?

Not at all. Elliptic curves are used in public key cryptography - to send encrypted messages between computers. Now the software developers have their choice; they can use any elliptic curve over any field. However, fields of characteristic 2 are particularly amenable to computer algorithms. Adding two elements in such a field is merely an xor operation on the bits. Naturally, these have become the preferred fields - so we need to understand characteristic 2.

Since the tangent formula has a 2 in the denominator, and 2 = 0 in such a field, something has to give. The formula for an elliptic curve changes in characteristic 2. There are still two parameters a and b, but the cubic equation is different. (Note, b cannot equal 0.)

y2 + xy = x3 + ax2 + b

Let j,k be a solution to this equation. Plug j into the cubic on the right, and the result equals k2+jk. Now look what happens if k is replaced with k+j. Supstitute this in y2+xy and get k2+jk back again. This is the "other" root. (The left hand side is quadratic, and can only have two roots.) In some sense, this is the reflection of j,k. If two distinct points share the same x coordinate, reflections of each other, their y coordinates will differ by the x coordinate. These points, inverses of each other, sum to ω in G.

If j = 0 then j,k is its own reflection. In particular, k is the square root of b, and there is only one such animal.

Consider two distinct points, j,k and s,t, that are not equal to ω, and are not reflections of each other. In other words, j ≠ s. Let m be the slope of the chord, given by the usual formula (t-k)/(s-j). Of course t-k is the same as t+k, but I'll stick with t-k, because it's more familiar.

We want to intersect the line and the cubic curve to find the third point. replace y, in our elliptic equation, with m×(x-j)+k, and move everything to one side.

q(x) = x3 + (a-m-m2)x2 + (jm-k)x - j2m2 - k2 + b

Since x-j is a root of q(x), divide it out, leaving a remainder of j3+aj2+b-k2-jk, which is 0. With x-j factored out, the new polynomial looks like this.

q(x) = x2 + (a+j-m2-m)x - jm2 + aj + j2 - k

Since x-s is a root, divide it out, leaving this remainder. (I'm replacing - with + whenever I feel like it.)

m2(s+j) + a(s+j) + j2 + js + s2 + ms + k

m(t+k) + a(s+j) + j2 + js + s2 + ms + k

Multiply this by j+s.

(t+k)2 + a(s+j)2 + j3+s3 + (k+t)s + k(j+s)

k2+t2 + aj2+as2 + j3+s3 + jk+st

This is the elliptic equation evaluated at j,k, plus the elliptic equation evaluated at s,t, which is zero. We are once again comforted to know that our remainder is zero. So the quotient gives the third root: m2+m+a+j+s. This is the x cordinate of the third point on the line. The y coordinate is y1+m(x3-x1). Remember, however, that we use to negate the y coordinate. We want the reflection. In this case the reflection is produced by adding the x coordinate.

x3 ← m2+m + a + x1+x2
y3 ← y1 + m(x3-x1) + x3

Now we're ready to handle p1 = p2, that is, p1+p1 in G. We need something analogous to the tangent line. If the x coordinate is 0, the tangent line is "vertical", and p1+p1 = ω. Otherwise m = j + k/j. I'll present the aforementioned q(x) (with x-j factored out) for review, then substitute for m and multiply through by j2.

q(x) = x2 + (a+j-m2-m)x - jm2 + aj + j2 - k

(x+j) × (j4 + aj2 + jk + k2) + j4+j2x2

Since (x+j)2 = x2+j2, the second term is also divisible by x+j. The entire expression is divisible by x+j, and j is a double root. Factor it out and get this.

j2x + j2a + j4 + j3 + jk + k2

The third root doesn't change if we divide by something nonzero, like j2. The expression becomes x+a+m2+m.

We could write this as x3 = m2+m+a+x1+x1. This seems a bit silly, since x1+x1 = 0, but it does reveal an underlying symmetry. This expression is the same formula we saw earlier, when the two points were distinct; but this time x1 is equal to x2. Similarly, y3 is computed using the same formula as above. Substitute for m and write the simpler doubling formula.

x3 ← m2+m + a
y3 ← x12 + (m+1)x3

Congratulations - we have a well defined binary operator on G, with ω acting as identity. The inverse of x,y is its reflection x,(y+x), which works even if x = 0 (giving the same point back again). Since the operator is based on the intersection of a line and a cubic curve, the same "third point" is extracted for p1+p2 and p2+p1, hence the operator is commutative. It is also associative, but like last time, I'm not going to prove it. Lots and lots of algebra. Suffice to say, G is a group.

Public Key Cryptography

Alice and Bob agree on a finite field, and an elliptic curve, and a base point p on the curve. Alice generates a random number k, which is her private key, and computes kp, which is her public key. Bob does the same.

Alice sees Bob's public key, which is a point on the elliptic curve, and multiplies it by her private key. Bob does the same. Both parties now have a point on the curve which is p times the product of their private keys. They do not know each other's private keys, but they do know (kakb)p. This is a secret that they share - their "shared" key.

The secret that Alice and Bob know, that is inaccessible to everyone else, is typically used to run other, simpler encryption schemes that require a shared key. (These are not described here.) If repeated use of the shared key might jeopardize its security, Alice and Bob can renogotiate a new key any time they wish. They select new random numbers, which act as private keys, post the corresponding public keys, combine their results to create a new shared key, and off they go.

In summary, elliptic curves can be used to jump-start a public key cryptography system, where any party can communicate securely with any other party, and/or authenticate his own communications (digital signature). The security of elliptic curve cryptography relies on the difficulty of computing k, given kp. This is sometimes called the discrete log problem, and it seems to be intractable in many situations. Thus private keys remain private, and secure communication is assured.