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

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

Algebraic Curves

Vocabulary

ring

set closed on addition and multiplication

$\mathbb{\mathbb{Z}}/n\mathbb{\mathbb{Z}}$

field

set closed on division

$\mathbb{\mathbb{Z}}/6\mathbb{\mathbb{Z}}$ is not a field since $\frac{1}{2}$ makes no sense mod 6

$\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}}$ for prime $p$

group

set closed on multiplication

EX: in El Gamal, we used ${(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^{*}$

Foundations

Moving to more general groups enables more and better cryptography

Example: The points $(x,y)\in {(\mathbb{\mathbb{Z}}/p\mathbb{\mathbb{Z}})}^2$ satisfying $y^2=x^3+bx+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:

1. $x^2+y^2=1x,y\in \mathbb{ℝ}$ forms a circle of radius 1
2. $x^2+y^2=-1x,y\in \mathbb{ℝ}$ is the empty set, BUT
3. $x^2+y^2=-1x,y\in \mathbb{ℂ}$ can be deformed into a sphere
4. $y^2=x^3-2x,y\in \mathbb{ℝ}$ 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{array}{rl}x& =\frac{1-t^2}{1+t^2}\\ y& =\frac{2t}{1+t^2}\end{array}$

Big Result

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

For Example, elliptic curves $y^2=x^3+bx+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{\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

1. 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{\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+bx+c$, for $b$ and $c$ not both 0, in some field, and points $(x,y)$ and $(x^{\prime },y^{\prime })$ on $E$, we define

$\begin{array}{rl}(x,y)\oplus (x^{\prime },y^{\prime })& =(m^2-x-x^{\prime },m(x-\mathbb{𝕏})-y)\\ (x,y)\oplus (x^{\prime },y^{\prime })& =(m^2-x-x^{\prime },-m^3+2mx-m{x}^{\prime })-y)\end{array}$

• $m=\{\begin{array}{ll}\frac{y^{\prime }-y}{x^{\prime }-x}& x\ne x^{\prime }\\ \frac{3x^2+b}{2y}& x=x^{\prime }\end{array}$
• $\mathbb{𝕏}=m^2-x-x^{\prime }$
• This addition (⊕) is also known as the chord-tangent, and goes back to Bachet in 1621

$E$ thus becomes a group, which means that

1. there must be a "0" ("the point at infinity")
2. there must be a "negative" ($\ominus (x,y):=(x,-y)$

Illustration of Elliptic Curve Addition

How many rational numbers $x$ and $y$ satisfy $y^2=x^3-2$?

The answer: infinitely many, and you can build them all via elliptic curve addition!

For the given equation, $(x,y)=(3,5)$ is a solution, so the negative, (3,-5) is also a solution.

What if we add the point to itself?

$(3,5)\oplus (3,5)=[2](3,5)=(\frac{129}{100},\pm \frac{383}{1000})$

Equivalent to

• Taking the tangent line at the point
• Finding the intersection of that point with the elliptic curve

This can be doubled again, giving huge, complicated numbers very quickly

Finite Fields

Chord tangent no longer makes sense, but algebraic formulae still work:

For example, $y^2=x^3+1(x,y)\in {(\mathbb{\mathbb{Z}}/5\mathbb{\mathbb{Z}})}^2$

How do we draw this curve? How do we find points?

A: Use square roots mod 5

Squares mod 5 = { 0, 1, 4 }

$x$	$x^3+1(\mathrm{mod}5)$	$y$ exists
0	1	Yes
1	2	No
2	4	Yes
3	3	No
4	0	Yes

Therefore, this elliptic curve has exactly 5 points in ${(\mathbb{\mathbb{Z}}/5\mathbb{\mathbb{Z}})}^2$:

1. (0, ±1)
2. (2, ±2)
3. (4, 0)