MATH 470 Lecture 26

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

Encoding Plain-Text on Elliptic Curves

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

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

$\mathbb{\mathbb{Z}}/n\mathbb{\mathbb{Z}}=\{1,\dots ,p-1,p+1,\dots ,q-1,q+1,\dots ,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{𝔽}}_p$, where $p=1,159,531$.

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

Can we efficiently encode $\{1,\dots ,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{𝔽}}_p$ with $y^2=(193120{)}^3-9(193120)+1(\mathrm{mod}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 $\lfloor \frac{x}{10}\rfloor$.

Note, when encoding $\{1,\dots ,n\}$ as elements of $\mathbb{\mathbb{Z}}/n\mathbb{\mathbb{Z}}$ for $n=pq$, 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{𝔽}}_p^{*}$ are squares, a random $x$ results in $\left(\frac{x^3+bx+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,\dots ,n\}$ as points on $E/{\mathbb{𝔽}}_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 ${(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$ and was based on the discrete log problem.

Elliptic Curve El Gamal is defined over $E(\mathbb{𝔽})$ 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,\dots ,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,\dots ,n-1\}$ with $\mathrm{g}\mathrm{c}\mathrm{d}(k,n)=1$ and compute $R=[k]A=(x,y)$.
2. compute $s=k^{-1}(m-ax)(\mathrm{mod}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{array}{rl}{V}_1& =[x]B\oplus [s]R\\ & =[x][a]A\oplus [k^{-1}(m-ax(\mathrm{mod}n))][k]A\\ & =[xa(\mathrm{mod}n)]A\oplus [m-ax(\mathrm{mod}n)]A\\ & =[\cancel{xa}+m\cancel{-ax}(\mathrm{mod}n)]A\\ & =[m]A=V_2\end{array}$

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!