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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_1 = [x]\,B \oplus [s] \, R} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_2 = [m]\,A}
3. Accept if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_1 = V_2} .

Bracket arithmetic is mod Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} because Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E} has Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} points, and thus forms a group of order Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} Therefore, the points eventually wrap around if multiplied by a number greater than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} : Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [n+17]A = [17]A} .

Note: verifier only performs elliptic curve operations

Proof. Check that a valid signature indeed implies Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V_1 = V_2} :

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} 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{align}}

Q.E.D.

Now if an evil party knew Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} , they could forge signatures. However, finding Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} appears to boild down to solving Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B = [a]A} for Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} , which is the elliptic curve discrete log problem.

Practice final is up on the course website!