MATH 470 Lecture 21

« previous | Thursday, April 4, 2013 | next »

"Surprise" quiz on Tuesday: Pohlig-Hellman or Jacobi Symbols

Random Number Generators

Generating "random" sequences from a "simple" deterministic scheme remains a mystery.

Polynomial Congruential generators

Loooong periods from very simple recurrences.
Applications: require more speed than security, e.g. cable TV

Algebraic Curves

Vocabulary

ring: set closed on addition and multiplication; $\mathbb {Z} /n\mathbb {Z}$
field: set closed on division; $\mathbb {Z} /6\mathbb {Z}$ is not a field since ${\tfrac {1}{2}}$ makes no sense mod 6; $\mathbb {Z} /p\mathbb {Z}$ for prime $p$
group: set closed on multiplication; EX: in El Gamal, we used $\left(\mathbb {Z} /p\mathbb {Z} \right)^{*}$

Foundations

Moving to more general groups enables more and better cryptography

Example: The points $(x,y)\in \left(\mathbb {Z} /p\mathbb {Z} \right)^{2}$ satisfying $y^{2}=x^{3}+b\,x+c$ for $p\nmid b,c$ can be turned into a group.

Such groups form backbone of cryptological algorithms used by Microsoft, Certicom, Matsushita (松下), Siemens, etc

Algebraic geometry is the area of mathematics that studies solutions to polynomial equations

Number theory and relativity will likely be useless, even years from now. G.H. Hardy (1940)

Algebraic Curves

The set of solutions of a polynomial equations, in 2 variables, over a field.

Examples:

$x^{2}+y^{2}=1\quad \quad x,y\in \mathbb {R}$ forms a circle of radius 1
$x^{2}+y^{2}=-1\quad \quad x,y\in \mathbb {R}$ is the empty set, BUT
$x^{2}+y^{2}=-1\quad \quad x,y\in \mathbb {C}$ can be deformed into a sphere
$y^{2}=x^{3}-2\quad \quad x,y\in \mathbb {R}$ is an elliptic curve (not in the sense that it is an ellipse

Curves can be parameterized in many ways:

$x^{2}+y^{2}=1$ has parameterization
${\begin{aligned}x&={\frac {1-t^{2}}{1+t^{2}}}\\y&={\frac {2t}{1+t^{2}}}\end{aligned}}$

Big Result

Detecting and computing points on algebraic curves gets harder as you go from $\mathbb {C}$ to $\mathbb {R}$ to $\mathbb {Q}$ to $\mathbb {Z}$ ...

For Example, elliptic curves $y^{2}=x^{3}+b\,x+c$ for $b$ and $c$ not both 0, do not admit rational parameterizations

Came about as desire to find arc length of an elliptic curve, which turned out to be of the form

\int {\frac {\mathrm {d} x}{\sqrt {O(x^{2})}}}

These are called elliptic integrals.

Detecting roots is really hard over $\mathbb {Z}$ .

Theorem

Davis, Putnam, Robinson, Matiyasevic (1970)

In general, detecting integer solutions to polynomial equations is undecidable.

That is, a "no" answer cannot be guaranteed by any finite computation.

K. GÖdel (1940s)

How does this Connect to Cryptography

Polynomial equations are "rich enough" to do a lot

Let's focus on elliptic curves:

Elliptic Curves

1950s: Alan Baker showed that, for elliptic curves, you can detect $\mathbb {Z}$ solutions in finite time.
1986: H.W. Lenstra, Jr. proved that Elliptic curves (over finite fields) could be used to factor integers!
1990s: Elliptic curves over finite fields enable new cryptosystems!

Elliptic Curves Admit an addition (operation) that turns them into groups useful for cryptography!

Definition. Given an elliptic Curve $E:(x,y)\mapsto y^{2}=x^{3}+b\,x+c$ , for $b$ and $c$ not both 0, in some field, and points $(x,y)$ and $(x',y')$ on $E$ , we define

{\begin{aligned}(x,y)\oplus (x',y')&=(m^{2}-x-x',m(x-\mathbb {X} )-y)\\(x,y)\oplus (x',y')&=(m^{2}-x-x',-m^{3}+2m\,x-m\,x')-y)\end{aligned}}

$m={\begin{cases}{\frac {y'-y}{x'-x}}&x\neq x'\\{\frac {3x^{2}+b}{2y}}&x=x'\end{cases}}$
$\mathbb {X} =m^{2}-x-x'$
This addition (⊕) is also known as the chord-tangent, and goes back to Bachet in 1621