Math 502
Written Assignment No. 5

1.1.  Representing characters by points on a curve

As before, characters may be represented by numbers; in particular, characters and standard symbols in U.S. English may be represented by their ASCII codes, which are integers from $0$ to $127$. The question here is how to represent a number $N$ in this range by a point of $E$. In the first place $l$ must be large enough that $E$ contains at least $127$ points. Since for a point $\left(x,y\right)$ of $E$ the second coordinate $y$ is the root of a quadratic polynomial in the first coordinate $x$, letting $x$ be $N$ and then solving for $y$ will not lead to a root $y$ in ${\mathbf{F}}_l$ unless the discriminant of the corresponding quadratic equation is the square of an element of ${\mathbf{F}}_l$. Precisely half of the non-zero elements of ${\mathbf{F}}_l$ are squares, so the discriminant will be a square roughly half the time. Because of that $x$ cannot simply be $N$ but rather something determined by $N$ that offers a range of possible values of $x$.

One chooses an integer $m$ so that $1/2^m$ is an acceptably small probability of failure to find a $y$ for given $x$. The idea then is, for a given number $N$, to try as many as $m$ different values of $x$ until there is found a $y$ with $\left(x,y\right)$ on $E$. The values of $x$ one tries are $$x=mN+j,1\le j\le m\text{.}$$ The event that one does not find a $y$ after trying all $m$ of these values has probability $1/2^m$. If a $y$ is found, then the point $p=\left(x,y\right)$ becomes the point of the curve representing the number $N$. There is no secrecy in this. The original number $N$ may be recovered from $p$ as the largest integer strictly smaller than $x/m$ or $$N=\mathrm{floor}\left(\frac{x-1}{m}\right)\text{.}$$ It is necessary that $l\ge 128m$ if this method is to be viable for representing integers $0\le N\le 127$ by a point on a given curve $E$ over ${\mathbf{F}}_l$.

1.2.  Encoding points on a curve

Here the question is encoding for secrecy the points on a curve. As with the earlier foray into cryptography the method discussed here - which is named El Gamal - involves public knowledge of how to encrypt with only secret knowledge of how to decrypt. One wants a curve having a base point $b$ of large order relative to the arithmetic on $E$. For example, if the number of all points $\left|E\right|$ of $E$ happens to be prime, which is far from always true, then there will be a point $b$ of $E$ having order $\left|E\right|$. As suggested above, for any $E$ the number $\left|E\right|$ of its points is usually somewhere around $l$ since there are two points on $E$ for each of the roughly $l/2$ values of $x$ for which there is a $y$ except for the case when $x$ leads to a quadratic equation for $y$ having discriminant $0$. In this scheme a single point $p$ on $E$ will be encrypted by a pair $\left(q,r\right)$ where both $q$ and $r$ are points of $E$.

The designer of the scheme picks the prime $l$, the curve $E$, a “base point” $b$ on $E$ of large order, all of which are to be public, and a secret element $j$ of ${\mathbf{F}}_l$. With those items fixed, the designer publishes one more point $c$ on $E$ that is determined by the formula $c=jb$. For given $l$ and $E$, the scheme's “public key” is the pair of points $b$ and $c$ on $E$.

A user of this scheme may encode a point $p$ of $E$ as follows: (i) draw a non-zero random value $k$ mod $l$ and then (ii) produce the pair of points $\left(q,r\right)$ using the formulae: $$\begin{array}{}& \hfill q& \hfill =\hfill & kb\hfill & \hfill r& \hfill =\hfill & p+kc\hfill \end{array}$$ Anyone who knows the secret value $j$ as well as the published data may recover the original point $p$ from the pair $\left(q,r\right)$ using the simple formula $$p=r-jq\text{.}$$ Security for this system relies on it being difficult to ascertain $j$ even though $b$ and $c$ are both known.