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

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 \mathbb{Z} / n \mathbb{Z}}

field

set closed on division

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 \mathbb{Z}/6 \mathbb{Z}} is not a field since 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 \tfrac{1}{2}} makes no sense mod 6

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 \mathbb{Z}/p \mathbb{Z}} for 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 p}

group

set closed on multiplication

EX: in El Gamal, we used 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)^*}

Foundations

Moving to more general groups enables more and better cryptography

Example: The points 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,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:

1. $x^{2}+y^{2}=1\quad \quad x,y\in \mathbb {R}$ forms a circle of radius 1
2. $x^{2}+y^{2}=-1\quad \quad x,y\in \mathbb {R}$ is the empty set, BUT
3. $x^{2}+y^{2}=-1\quad \quad x,y\in \mathbb {C}$ can be deformed into a sphere
4. $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 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 \mathbb{C}} to 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 \mathbb{R}} to 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 \mathbb{Q}} to 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 \mathbb{Z}} ...

For Example, elliptic curves 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 y^2 = x^3 + b\,x + c} 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 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 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

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 \int \frac{\mathrm{d}x}{\sqrt{O(x^2)}}}

These are called elliptic integrals.

Detecting roots is really hard 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 \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 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 \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 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 : (x,y) \mapsto y^2 = x^3 + b \, x + c} , 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 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 c} not both 0, in some field, and points 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,y)} 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 (x', y')} 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} , we define

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} (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{align}}

• 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 = \begin{cases} \frac{y'-y}{x'-x} & x \ne x' \\ \frac{3x^2+b}{2y} & x = x'\end{cases}}
• 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 \mathbb{X} = m^2 - x - x'}
• This addition (⊕) is also known as the chord-tangent, and goes back to Bachet in 1621

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} thus becomes a group, which means that

1. there must be a "0" ("the point at infinity")
2. there must be a "negative" (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 \ominus(x,y) := (x,-y)}

Illustration of Elliptic Curve Addition

How many rational numbers 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} 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 y} satisfy 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 y^2 = x^3 - 2} ?

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

For the given equation, 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,y) = (3,5)} is a solution, so the negative, (3,-5) is also a solution.

What if we add the point to itself?

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 (3,5) \oplus (3,5) = [2](3,5) = \left( \frac{129}{100}, \pm \frac{383}{1000} \right)}

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, 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 y^2 = x^3 + 1 \quad \quad (x,y) \in \left( \mathbb{Z} / 5 \mathbb{Z} \right)^2}

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

A: Use square roots mod 5

Squares mod 5 = { 0, 1, 4 }

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}	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^3 + 1 \pmod{5}}	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 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 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} / 5 \mathbb{Z} \right)^2} :

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