MATH 470 Lecture 1

« previous | Tuesday, January 15, 2013 | next »

MATH 470 J. Maurice Rojas MILN 206 rojas@math.tamu.edu

Course Web Page

Homework 1 is online.

Critical Things

Grades

• 10% HW (some from in the book)
• 20% Quizzes
• 35% Midterm
• 35% Final (May 3 15:00—17:00)

There will be some number theory

Textbook: Ch. 1–3, parts of 6, 7, 9, 16

Groups:

• Name
• Email picture of me

Cryptology

κρυπτο(acute) = hidden or secret λογι(acute);α

Broadest sense: Protecting information from

• adversaries
• corruption
• noise

Other etymology (main concerns of course)

• Cryptography = making codes
• Cryptonalysis = breaking codes

Caesar Cipher

ca. 100–44 BC (Julius Caesar)

During this time, a code like the following was used:

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 \mathbb{Z}/26 \mathbb{Z} := \{ 0, 1, 2, \ldots, 25 \}}

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} f : \mathbb{Z}/26 \mathbb{Z} &\to \mathbb{Z}/26 \mathbb{Z} \\ x &\mapsto x+3 \\ f(\{0,1,2,\ldots,23,24,25\}) &= \{3,4,5,\ldots,0,1,2\} \end{align}}

Let each number correspond to a letter (A=0, B=1, etc.) and put it through the function:

• HELLO → (7,4,11,11,13) → (10,7,14,14,16) → KHNNP

To decode, invert the function 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 f} by subtracting 3

This is called a Caesar cipher, where the key is 3

1. take plain text (no punctuation or spaces)
2. convert to a vector $m$ in $\left(\mathbb {Z} /26\mathbb {Z} \right)^{N}$
3. Add a key mod 26 to each element: 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 + k \pmod{26}}
4. Convert back to letters

Modern View

"The core of cryptography is building and applying one-way functions."

Function should be easy to evaluate, but very hard to invert.

Example: Sound file

• Numbers between -16,383 and 16,384 represent amplitude
• Work 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 \mathbb{Z}/32768\mathbb{Z} = \{0,\ldots,32768\}}
• Caesar cipher does not hide music at all
• More sophisticated examples do very well.

Moral: The best encryption is (provably) a one-time random pad

• BUT on a computer, random is anything but...

Decoding vs. Breaking

In decoding, you know what you're doing. In breaking, you don't know the exact means of deciphering, but "hack" it

Decoding a Caesar cipher requires the recipient ("Bob") to know about the sender's ("Alice") key 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} .

But how would an adversary ("Eve") break a "Caesar" cipher?

• Frequency analysis : The most commonly used letter is probably a masked version of 'E'
• Brute Force: just try 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 = \{0,1, \ldots, 25 \}}

Vigenere Cipher

Giovan Battista Bellaso (1553)

• Describes what would later and incorrectly be called a "Vigerere Cipher"

Use multiple Caesar ciphers at once:

1. Take plain text (FOURSCOREANDSEVENYEARSAGO)
2. Convert to vector 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( x_1, x_2, \ldots, x_25 \right)}
3. Key is now a vector 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 \vec{k} = \left( 7,1,3,4,2 \right)}
4. Cipher text becomes 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( x_1, \ldots, x_5 \right) + \vec{k}, \left(x_6, \ldots, x_10 \right) + \vec{k}, \ldots}

Brute force is now more difficult since there are $26^{\left|k\right|}$

Breaking the Vigenere and Beyond

1. Charles Babbage (ca. 1853–1856) finds ways to break Vigenere
2. Confederates (ca. 1861–1865) use Vigenere
3. Kasiski (1863) publishes volume showing how to break vigenere
4. Scientific American (1917) says "Vigenere is impossible to break"
5. Clifford Cocks (1973) at GCHQ discovers "RSA"
6. Rivest Shamir Adleman (1977) "invent" RSA (named after them)

Number Theory

"To speak of cryptography well, we need to know some number theory" because it is the language of modern cryptography

What about multiplying instead of adding? (e.g. use 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 f(x) = 3x \pmod{26}}

• HELLO → (7,4,11,11,13) → (21,12,7,7,13) → VMHHO

Now what is 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 f^{-1}(x) = \frac{x}{3} \pmod{26}} ?

• Quick answer: Just multiply by 9 mod 26. That is, the unique solution to x 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 3x=1 \pmod{26}} is 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 = 9}
• 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 f^{-1}(x) = 9x \pmod{26}}

We say that $a\equiv b{\pmod {n}}\iff n\div (b-a)$

Note: Any Integer is congruent 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} to some number 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 \{0, \ldots, n-1\}}

In general: 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 \equiv \left( \text{remainder of division of}\ x\ \text{by}\ n \right) = x - \left\lfloor \frac{x}{n} \right\rfloor} , where 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\lfloor y \right\rfloor} is the "floor of 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} ", or the greatest integer 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 \le y}

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 180 \equiv 14 \pmod{26}} since ${\tfrac {180}{24}}=6+{\tfrac {24}{26}}$ 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 24 = 180 - 6 \cdot 26}

How do you invert 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} ? (e.g. 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}{a} \pmod{n}} )

• Solve 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 ax \equiv 1 \pmod{n}}
• $ax\equiv 1{\pmod {n}}\iff n\div (ax-1)$, so 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 ax - 1 = yn}
• To solve, find 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 \mathbb{Z}} 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 ax + ny = 1}
• Extended Euclidean algorithm makes this easy

Extended Euclidean Algorithm

Standard wikipedia:Euclidean Algorithm is a way to compute GCD

For example: What is GCD(3,26)?

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 26 = 8 \cdot 3 + 2}
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 3 = 1 \cdot 2 + 1}
3. GCD is 1

The Extended Euclidean Algorithm involves the following:

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{bmatrix}26&3\end{bmatrix}} becomes 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{bmatrix}1&0\\0&1\\26&3\end{bmatrix}} (put identity matrix on top)

Repeat division steps on the entire matrix:

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{bmatrix}1&0\\0&1\\26&3\end{bmatrix} \rightarrow \begin{bmatrix}1&0\\-8&1\\2&3\end{bmatrix} \rightarrow \begin{bmatrix}1&-1\\-8&9\\2&1\end{bmatrix}}

This means that ${\begin{bmatrix}2&1\end{bmatrix}}={\begin{bmatrix}26&3\end{bmatrix}}\cdot {\begin{bmatrix}1&-1\\-8&9\end{bmatrix}}$

From this, we can find that 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 26(-1) + 3(9) = 1}