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 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/\mathbb{F}_p} with 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 p > 10^k \, n} , add on 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 k} extra digits, and pick the last 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 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 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 \left(\mathbb{Z}/p \mathbb{Z}\right)^*} and was based on the discrete log problem.

Elliptic Curve El Gamal is defined over 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(\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
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 p} = large prime	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 \in \{1,\ldots,n-1\}}
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} = (nonsingular) elliptic curve
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} = number of points on $E$
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} = point on 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}
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}

To sign a message (or message hash) 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 m} , the signer does this:

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

Note: step 1 performed an elliptic curve operation, namely computing 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 x} as a point on the elliptic curve. Everyithing else is integer arithmetic

To verify the signature, the verifier does this:

1. downloads 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 (p, E, n, A, B)} 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 (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!