MATH 470 Lecture 3

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

Homework 2 will be online later today.

Deciding whether

$a\equiv b{\pmod {n}}$

takes one division step: $n\mid (a-b)$

Deciding whether

$a\,x\equiv b{\pmod {n}}$

has a solution iff $\mathrm {GCD} (a,n)\mid b$ and takes 5 × (number of digits in smaller of $a$ and $n$) + 1

From Homework 1

Problem 18b

When is the matrix ${\begin{bmatrix}1&1\\b&1\end{bmatrix}}{\pmod {26}}$ invertible?

The inverse should be

${\begin{bmatrix}a&b\\c&d\end{bmatrix}}^{-1}={\frac {1}{\mathrm {det} }}\,{\begin{bmatrix}d&-b\\-c&a\end{bmatrix}}$

As long as the determinant has a multiplicative inverse, then the formula still works.

Working in $\mathbb {Z} /26\mathbb {Z}$, the determinant ${\frac {1}{1-b}}$ has to be relatively prime to 26, or $\mathbb {GCD} (1-b,26)=1$.

...

When is ${\begin{bmatrix}3&5\\7&3\end{bmatrix}}^{-1}{\pmod {p}}$ undefined for prime number $p$?

${\begin{vmatrix}3&5\\7&3\end{vmatrix}}=-26$

Therefore, ${\tfrac {1}{-26}}$ only makes sense mod $p$ when $\mathrm {GCD} (p,26)=1$, so $p\in \{2,13\}$ makes ${\tfrac {1}{26}}$ nonsensical.

Complexity

Caesar cipher $x\mapsto x+b{\pmod {26}}$ can be broken by looking at 26 possible shifts (where $b$ = key) of plaintext.

Vigenere cipher ${\vec {x}}_{j}\mapsto {\vec {x}}_{j}+{\vec {b}}$ or equivalently, $(x_{i},\ldots ,x_{k})\mapsto (x_{i}+b_{1},\ldots ,x_{k}+b_{k-i})$ can be broken with brute force by looking at $26^{k-i}$ possible keys/shifts

Page Under Construction
This page still needs revision. Please edit this page to finish it.

Frequency of letters in English: Table 2.1 on page 17

Both are examples of symmetric ciphers, where the decryption key is easy to obtain from the encryption key.

Disadvantages:

1. If an enemy knows the encryption key, he/she gets the decryption key (almost) for free.
2. You must still send the key to your partner somehow

Vigenere Cipher

easier to break if key length is known and plaintext is long enough (sufficiently large samles of English text have predictable letter frequencies)

1. Decimate your sequence: $(x_{1},\ldots ,x_{k},x_{k+1},\ldots ,x_{2k},\ldots )\to {\begin{cases}(x_{1},x_{k+1},x_{2k+1},\ldots )&{\text{index}}\equiv 1{\pmod {k}}\\(x_{2},x_{k+2},x_{2k+2},\ldots )&{\text{index}}\equiv 2{\pmod {k}}\\\vdots \end{cases}}$
2. Perform frequency analysis on decimations: most frequent in each is likely the letter 'E'

• If plaintext consists of $n$ symbols, you're going to spend $C\,n$ time reading anyway, so adversary should spend $C^{n}$ time breaking code.
• IF we know $k$, we need $O(n)$ time to break the cipher
• If we don't know $k$, finding it is nontrivial.

In practice, $1<k<N$, perhaps $k=n^{p\in (0,1)}$.

Dearrangement Inequality

Discovered in 1952 by Hardy-Little???, this inequality will help us find $k$

Given any sequences $x_{1}\leq \dots \leq x_{n}$ and $y_{1}\leq \dots \leq y_{n}$ of the same length and any permutation $\sigma :\{1,\ldots ,n\}\to \{1,\ldots ,n\}$, we have

$x_{1}\,y_{1}+\dots x_{n}\,y_{n}\geq x_{1}\,y_{\sigma (1)}+\dots +x_{n}\,y_{\sigma (n)}$

In particular, if both sequences are strictly increasing, then equality occurs only for $\sigma ={\text{identity}}$

For example, if ${\vec {x}}=\left({\frac {1}{4}},{\frac {1}{4}},{\frac {1}{2}}\right)$ and ${\vec {y}}=\left({\frac {1}{9}},{\frac {1}{7}},{\frac {1}{6}}\right)$, then ${\frac {1}{4}}\,{\frac {1}{9}}+{\frac {1}{4}}\,{\frac {1}{6}}+{\frac {1}{2}}\,{\frac {1}{6}}\geq {\frac {1}{4}}\,{\frac {1}{6}}+{\frac {1}{4}}\,{\frac {1}{9}}+{\frac {1}{2}}\,{\frac {1}{7}}$

Finding Key Length

Given $x_{1},x_{2},\ldots$, do the following:

1. Get frequency info for symbols in your language (e.g. English)
2. for $i$ from 1 to $n^{p}$, compare the frequency of a collision between $x_{j}$ and $x_{j+1}$ for $j\in \{1,\ldots ,n-i\}$. This yields $p_{i,a},\ldots ,p_{i,z}$

To be continued …

Next Time

Dr. Rojas will be in Washington D.C.

Guest lecture Catherine Yan on Fermat's Little Theorem