All of the elliptic curves we work with in this chapter are elliptic curves mod However, it is helpful use the graphs of elliptic curves with real numbers in order to visualize what is happening with the addition law, for example, even though such pictures do not exist mod
Let’s graph the elliptic curve We’ll specify that and and make sure that x
and y
are cleared of previous values.
> x:=’x’;y:=’y’;implicitplot(2=x*(x-1)*(x+1), x=-1..3,y=-5..5)
Add the points (1, 3) and (3, 5) on the elliptic curve
> addell([1,3], [3,5], 24, 13, 29)
[26,1]
You can check that the point (26, 1) is on the curve:
Add (1, 3) to the point at infinity on the curve of the previous example.
> addell([1,3], ["infinity","infinity" ], 24, 13, 29)
[1,3]
As expected, adding the point at infinity to a point returns the point
Let be a point on the elliptic curve Find
> multell([1,3], 7, 24, 13, 29)
[15,6]
Find for on the curve of the previous example.
> multsell([1,3], 40, 24, 13, 29)
[[1,[1,3]],[2,[11,10]],[3,[23,28]],[4,[0,10]],[5,[19,7]],[6,[18,19]],
[7,[15,6]],[8,[20,24]],[9,[4,12]],[10,[4,17]],[11,[20,5]],
[12,[15,23]],[13,[18,10]],[14,[19,22]],[15,[0,19]],[16,[23,1]],
[17,[11,19]],[18,[1,26]],[19,["infinity","infinity"]],[20,[1,3]],
[21,[11,10]],[22,[23,28]],[23,[0,10]],[24,[19,7]],[25,[18,19]],
[26,[15,6]],[27,[20,24]],[28,[4,12]],[29,[4,17]],[30,[20,5]],
[31,[15,23]],[32,[18,10]],[33,[19,22]],[34,[0,19]],[35,[23,1]],
[36,[11,19]],[37,[1,26]],[38,["infinity","infinity"]],[39,[1,3]],
[40,[11,10]]]
Notice how the points repeat after every 19 multiples.
The previous four examples worked mod the prime 29. If we work mod a composite number, the situation at infinity becomes more complicated since we could be at infinity mod both factors or we could be at infinity mod one of the factors but not mod the other. Therefore, we stop the calculation if this last situation happens and we exhibit a factor. For example, let’s try to compute where is on the elliptic curve
> multell([1,3], 12, -5, 13, 11*19)
["factor=",19]
Now let’s compute the successive multiples to see what happened along the way:
> multsell([1,3], 12, -5, 13, 11*19)
[[1,[1,3]],[2,[91,27]],[3,[118,133]],[4,[148,182]],[5,[20,35]],
[6,["factor=",19]]]
When we computed we ended up at infinity mod 19. Let’s see what is happening mod the two prime factors of 209, namely 19 and 11:
> multsell([1,3], 12, -5, 13, 19)
[[1,[1,3]],[2,[15,8]],[3,[4,0]],[4,[15,11]],[5,[1,16]],
[6,["infinity","infinity"]],[7,[1,3]],[8,[15,8]],[9,[4,0]],
[10,[15,11]],[11,[1,16]],[12,["infinity","infinity"]]]
> multsell([1,3], 24, -5, 13, 11)
[[1,[1,3]],[2,[3,5]],[3,[8,1]],[4,[5,6]],[5,[9,2]],[6,[6,10]],
[7,[2,0]],[8,[6,1]],[9,[9,9]],[10,[5,5]],[11,[8,10]],[12,[3,6]],
[13,[1,8]],[14,["infinity","infinity"]],[15,[1,3]],[16,[3,5]],
[17,[8,1]],[18,[5, 6]],[19,[9, 2]],[20,[6,10]],[21,[2,0]],
[22,[6,1]],[23,[9,9]],[24,[5,5]]]
After six steps, we were at infinity mod 19, but it takes 14 steps to reach infinity mod 11. To find we needed to invert a number that was 0 mod 19 and nonzero mod 11. This couldn’t be done, but it yielded the factor 19. This is the basis of the elliptic curve factorization method.
Factor 193279 using elliptic curves.
SOLUTION
First, we need to choose some random elliptic curves and a point on each curve. For example, let’s take and the elliptic curve
For to lie on the curve, we take We’ll also take
Now we compute multiples of the point We do the analog of the method, so we choose a bound say and compute
> multell([2,4], factorial(12), -10, 28, 193279)
["factor=",347]
> multell([1,1], factorial(12), 11, -11, 193279)
[13862,35249]
> multell([1,2], factorial(12), 17, -14, 193279)
["factor=",557]
Let’s analyze in more detail what happened in these examples.
On the first curve, ends up at infinity mod 557 and is infinity mod 347. Since it has a prime factor larger than so is not infinity mod 557. But 35 divides so is infinity mod 347.
On the second curve, mod 347 and mod 557. Since and we don’t expect to find the factorization with this curve.
The third curve is a surprise. We have mod 347 and mod 557. Since is prime and we don’t expect to find the factorization with this curve. However, by chance, an intermediate step in the calculation of yielded the factorization. Here’s what happened. At one step, the program required adding the points (184993, 13462) and (20678, 150484). These two points are congruent mod 557 but not mod 347. Therefore, the slope of the line through these two points is defined mod 347 but is 0/0 mod 557. When we tried to find the multiplicative inverse of the denominator mod 193279, the gcd algorithm yielded the factor 557. This phenomenon is fairly rare.
Here is how to produce the example of an elliptic curve ElGamal cryptosystem from Section 21.5. For more details, see the text. The elliptic curve is and the point is Alice’s message is the point
Bob has chosen his secret random number and has computed
> multell([4,11], 3, 3, 45, 8831)
[413,1808]
Bob publishes this point. Alice chooses the random number and computes and
> multell([4,11], 8, 3, 45, 8831)
[5415,6321]
> addell([5,1743],multell([413,1808],8,3,45,8831),3,45,8831)
[6626,3576]
Alice sends (5415,6321) and (6626,3576) to Bob, who multiplies the first of these point by
> multell([5415,6321], 3, 3, 45, 8831)
[673,146]
Bob then subtracts the result from the last point Alice sends him. Note that he subtracts by adding the point with the second coordinate negated:
> addell([6626,3576], [673,-146], 3, 45, 8831)
[5,1743]
Bob has therefore received Alice’s message.
Let’s reproduce the numbers in the example of a Diffie-Hellman key exchange from Section 21.5: The elliptic curve is and the point is Alice chooses her secret and Bob chooses his secret Alice calculates
> multell([3,5], 12, 1, 7206, 7211)
[1794,6375]
She sends (1794,6375) to Bob. Meanwhile, Bob calculates
> multell([3,5], 23, 1, 7206, 7211)
[3861, 1242]
and sends (3861,1242) to Alice. Alice multiplies what she receives by and Bob multiplies what he receives by
> multell([3861,1242], 12, 1, 7206, 7211)
[1472,2098]
> multell([1794,6375], 23, 1, 7206, 7211)
[1472,2098]
Therefore, Alice and Bob have produced the same key.