Elliptic Curve Cryptography

Elliptic Curve Cryptography (ECC) is broadly used today in various applications, from small, constrained devices to large cloud servers. In the following tasks, you can use the open source software SAGE [1] (either at the server or download it in advance) and you need to calculate several values and properties of the curves. The goal is to understand ECC principles with a practical arithmetic example by calculate doubling/addition on a curve, finding tangent line, performing finite field arithmetic with the use of SAGE and with some tricks, that do not require SAGE, but some thinking and understanding of finite field arithmetic. Then we can see how an encryption protocol works on elliptic curves.

Task 1: Given the curve E:y^2 = x^3 + 2x + 3 on the finite field   verify that P=(6101065374528763628460436663049 : 2223659447177254506928398297998 : 1) and Q=(38121613438662105355168812344 : 3123847732620019127314512268740 : 1) belong on the curve. What is the order of point P? Compute the point R=P+Q and the tangent line passing from point P.

Task 2: ElGamal cryptosystem over elliptic curves of finite fields is a natural extension of the classical ElGamal over finite fields, based on the difficulty of solving the discrete logarithm problem over an elliptic curve (ECDLP). Such cryptosystems can be defined for encryption and signature schemes. One important point is how to define an optimal function F that maps messages to points in the field, is invertible and not hard to compute. Let p be an odd prime and  a finite field over which the elliptic curve E() is defined. The bijection [1,p-1] -> E(*) is an optimal injecting encoding, as described in [2].

Let us assume that Bob and Alice have agreed on the following parameters: elliptic curve $E: y^2=x^3+2x+3$ over , where q=673, a generator point P=(667:197:1) on the curve of order n=654.

• Suppose Bob has chosen a secret key x in [1,q-1] randomly and this is x=506. What is his public key?
• Alice used Bob's public key and encrypts for him the message m. They use the ElGamal scheme described by Koblitz in [3], with injecting encoding of messages m_2 -> m P = P_m (so the message m in binary format is transformed to integer and multiplied by P, to give the point on the curve P_m). On reception of ciphertext (C,D) = ((662:116:1), (70:68:1)) how can Bob decrypt the message? Use Sage or any other tool you need and show all the steps to decrypt the ciphertext.
• Describe a scenario where Bob cannot decrypt the message in polynomial time.