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

$\begin{array}{rl}f:\mathbb{\mathbb{Z}}/26\mathbb{\mathbb{Z}}& \to \mathbb{\mathbb{Z}}/26\mathbb{\mathbb{Z}}\\ x& \mapsto x+3\\ f(\{0,1,2,\dots ,23,24,25\})& =\{3,4,5,\dots ,0,1,2\}\end{array}$

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 $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 ${(\mathbb{\mathbb{Z}}/26\mathbb{\mathbb{Z}})}^N$
3. Add a key mod 26 to each element: $m+k(\mathrm{mod}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 $\mathbb{\mathbb{Z}}/32768\mathbb{\mathbb{Z}}=\{0,\dots ,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 $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 $k=\{0,1,\dots ,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 $(x_1,x_2,\dots ,x_{2}5)$
3. Key is now a vector $\overrightarrow{k}=(7,1,3,4,2)$
4. Cipher text becomes $(x_1,\dots ,x_5)+\overrightarrow{k},(x_6,\dots ,x_{1}0)+\overrightarrow{k},\dots$

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 $f(x)=3x(\mathrm{mod}26)$

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

Now what is $f^{-1}(x)=\frac{x}{3}(\mathrm{mod}26)$?

• Quick answer: Just multiply by 9 mod 26. That is, the unique solution to x in $3x=1(\mathrm{mod}26)$ is $x=9$
• $f^{-1}(x)=9x(\mathrm{mod}26)$

We say that $a\equiv b(\mathrm{mod}n)⟺n÷(b-a)$

Note: Any Integer is congruent mod $n$ to some number in $\{0,\dots ,n-1\}$

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

Example: $180\equiv 14(\mathrm{mod}26)$ since $\frac{180}{24}=6+\frac{24}{26}$ and $24=180-6\cdot 26$

How do you invert mod $n$? (e.g. $\frac{1}{a}(\mathrm{mod}n)$ )

• Solve $ax\equiv 1(\mathrm{mod}n)$
• $ax\equiv 1(\mathrm{mod}n)⟺n÷(ax-1)$, so $ax-1=yn$
• To solve, find $x,y\in \mathbb{\mathbb{Z}}$ with $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. $26=8\cdot 3+2$
2. $3=1\cdot 2+1$
3. GCD is 1

The Extended Euclidean Algorithm involves the following:

$\left[\begin{array}{cc}26& 3\end{array}\right]$ becomes $\left[\begin{array}{cc}1& 0\\ 0& 1\\ 26& 3\end{array}\right]$ (put identity matrix on top)

Repeat division steps on the entire matrix:

$\left[\begin{array}{cc}1& 0\\ 0& 1\\ 26& 3\end{array}\right]\to \left[\begin{array}{cc}1& 0\\ -8& 1\\ 2& 3\end{array}\right]\to \left[\begin{array}{cc}1& -1\\ -8& 9\\ 2& 1\end{array}\right]$

This means that $\left[\begin{array}{cc}2& 1\end{array}\right]=\left[\begin{array}{cc}26& 3\end{array}\right]\cdot \left[\begin{array}{cc}1& -1\\ -8& 9\end{array}\right]$

From this, we can find that $26(-1)+3(9)=1$