MATH 470 Lecture 26

« previous | Tuesday, April 23, 2013 | next »

Encoding Plain-Text on Elliptic Curves

Using $\mathbb {Z} /n\mathbb {Z}$ for $n$ large makes it easy to encode messages:

if $n=p\,q$ for primes $p<q$, then

$\mathbb {Z} /n\mathbb {Z} =\{1,\ldots ,p-1,p+1,\ldots ,q-1,q+1,\ldots ,n-1\}$

You'd like to do the same on an elliptic curve. e.g.

• 1 ⟼ first point on curve
• 2 ⟼ second point on curve
• …

Unfortunately, there is no known poly-time algorithm for enumerating points on an elliptic curve over a finite field.

N. Koblitz came up with the following trick:

To transmit $m$, add a few digits and use square roots.

Consider $y^{2}=x^{3}-9x+1$ over $\mathbb {F} _{p}$, where $p=1,159,531$.

According to Hasse's Theorem, The number of points $n$ on $E$ satisfies $\left|n-(p+1)\right|\leq 2{\sqrt {p}}$, so there are about a million points on this curve.

Can we efficiently encode $\{1,\ldots ,10^{5}-1\}$ as points on $E$? What about $19312$?

Koblitz proposed adding a few ($z$) digits:

$19312=19312*10^{z}+d_{1}\cdot 10^{z-1}+d_{2}\cdot 10^{z-2}+\dots +d_{z}$

In our cose, let's just add a single digit 0:

$19312\to 193120$

Now is there a $y\in \mathbb {F} _{p}$ with $y^{2}=(193120)^{3}-9(193120)+1{\pmod {p}}$? Compute legendre symbol $\left({\frac {(193120)^{3}-9(193120)+1}{p}}\right)=1$: YES

Decoding: If you see $(x,y)\in E$, then your message is just $\left\lfloor {\frac {x}{10}}\right\rfloor$.

Note, when encoding $\{1,\ldots ,n\}$ as elements of $\mathbb {Z} /n\mathbb {Z}$ for $n=p\,q$, there were just 2 failures. When encoding on an elliptic curve, how many failures are there?

Koblitz's Heuristic

Since exactly half the elements of $\mathbb {F} _{p}^{*}$ are squares, a random $x$ results in $\left({\frac {x^{3}+b\,x+c}{p}}\right)=1$ with probability approx. 50%

So then, among all 193120–193129, we'll find at least one with probability $1-{\frac {1}{2^{10}}}$

Thus, the general trick is to encode $\{1,\ldots ,n\}$ as points on $E/\mathbb {F} _{p}$ with $p>10^{k}\,n$, add on $k$ extra digits, and pick the last $k$ digits randomly

with probability at least $1-{\frac {1}{2^{10^{k}}}}$, you've encoded successfully.

Elliptic Curve Analogues of Cryptosystems

El Gamal

Formerly worked over $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$ and was based on the discrete log problem.

Elliptic Curve El Gamal is defined over $E(\mathbb {F} )$ and is based on the elliptic curve discrete log, an even harder problem than discrete log! Thus the fancier cryptosystem allows for smaller keys

Public	Private
$p$ = large prime	$a\in \{1,\ldots ,n-1\}$
$E$ = (nonsingular) elliptic curve
$n$ = number of points on $E$
$A$ = point on $E$
$B=[a]\,A$

To sign a message (or message hash) $m$, the signer does this:

1. pick a random $k\in \{1,\ldots ,n-1\}$ with $\mathrm {gcd} (k,n)=1$ and compute $R=[k]\,A=(x,y)$.
2. compute $s=k^{-1}(m-a\,x){\pmod {n}}$
3. send $(m,R,s)$

Note: step 1 performed an elliptic curve operation, namely computing $x$ as a point on the elliptic curve. Everyithing else is integer arithmetic

To verify the signature, the verifier does this:

1. downloads $(p,E,n,A,B)$ and $(m,R,s)$
2. compute $V_{1}=[x]\,B\oplus [s]\,R$ and $V_{2}=[m]\,A$
3. Accept if $V_{1}=V_{2}$.

Bracket arithmetic is mod $n$ because $E$ has $n$ points, and thus forms a group of order $n$ Therefore, the points eventually wrap around if multiplied by a number greater than $n$: $[n+17]A=[17]A$.

Note: verifier only performs elliptic curve operations

Proof. Check that a valid signature indeed implies $V_{1}=V_{2}$:

${\begin{aligned}V_{1}&=[x]\,B\oplus [s]\,R\\&=[x][a]A\oplus [k^{-1}(m-a\,x{\pmod {n}})][k]A\\&=[x\,a{\pmod {n}}]A\oplus [m-a\,x{\pmod {n}}]A\\&=[{\cancel {x\,a}}+m{\cancel {-a\,x}}{\pmod {n}}]A\\&=[m]A=V_{2}\end{aligned}}$

Q.E.D.

Now if an evil party knew $a$, they could forge signatures. However, finding $a$ appears to boild down to solving $B=[a]A$ for $a$, which is the elliptic curve discrete log problem.

Practice final is up on the course website!