iPython Notebook HowTo's

Graphs

x = numpy.arange(0,2 * math.pi, 0.1)

f1=map(lambda x: 5 * math.sin(x), x)

f2=map(lambda x: 2 math.sin(2x), x)

f3=map(lambda x: 1 math.sin(3x), x)

pylab.plot(x,f1)

pylab.plot(x,f2,'ro')

pylab.plot(x,f3,'g--')

pylab.show()

LaTeX in Markdown:

$e^{i \omega t}$

e^{i \omega t}

Ideas:

General Ideas: https://github.com/ipython/ipython/tree/master/examples/notebooks#a-collection-of-notebooks-for-using-ipython-effectively

Cython integration: http://nbviewer.ipython.org/urls/raw.github.com/ipython/ipython/3607712653c66d63e0d7f13f073bde8c0f209ba8/docs/examples/notebooks/cython_extension.ipynb

iPython Display Modifications:

Cryptography

Notes and code derived from CSCI 466 Cryptography

School: Liberty University

Professor: Mark Shaneck

Necessary Number Theory

Many concepts in Crypto are built on concept from Number Theory

Many Crypto analyses are rooted in probability and statistics

Let's take a moment and go over the fundamentals that we need for the class

Groups

Group $G$

binary operator $*$: Mapping from $G \times G \mapsto G$ (closed under $*$)

Group named $(G,*)$

Mapping has properties

Associative: $\forall a,b,c \in G a*(b*c) = (a*b)*c$

Identity: $\exists e \in G$ such that $\forall a \in G, a*e = e*a = a$

Inverse: $\forall a \in G \exists a^{-1} \in G $ s.t. $ a*a^{-1} = a^{-1}*a = e$

Abelian if commutative

Commutative: $\forall a,b \in G $ $ a*b=b*a$

Finite group if $G$ has finite number of elements

$|G|$ is the order of $G$

Exponentiation: repeated application of operation

$a^0=e$

$a^1=a$

$a^2=a*a$

$a^n=a*a* \dots *a$ ($n$ times)

$a^{-n}=(a^{-1})^n$

Cyclic if $\exists a \in G $ s.t. $ \forall b \in G $ $ \exists k\in \mathbb{Z} $ s.t. $ a^k=b$

$a$ is called a generator

Rings

Set with two operations: $(R,+,*)$ s.t.

$(R,+)$ is an abelian group (Identity $0$ and Inverse $-a$)

$*$ is closed under $R$ (i.e. $R \times R \mapsto R$)

$*$ is associative

$*$ distributes over $+$

Commutative Ring

$*$ is commutative

Integral Domain

$\exists 1 \in R $~ s.t. ~$ \forall a \in R $~~$ a1=1a=a$ (Multiplicative Identity)

No zero divisors: If $a,r \in R$ and $ab=0$ then either $a=0$ or $b=0$

Fields

$(F,+,*)$ is a field if

$F$ is an integral domain

$\forall a \in F, $ $ a \neq 0, $~~$ \exists a^{-1} \in F $ s.t. $ a * a^{-1} = a^{-1}*a=1$ (i.e., Multiplicative Inverse)

Modular Arithmetic

We can do $+, * $ and modulo reduce the answer ($\mod n$)

Wraps around

Can reduce at any point (as long as reduction also takes place at end)

$\mod n$ defines a mapping from $\mathbb{Z}$ to $\{0,1,\dots,n-1\} = \mathbb{Z}_n$

Why is $\mathbb{Z}_n$ not a field? Zero divisors exist.

e.g. In $\mathbb{Z}_6$, $4*3 = 0 \mod 6$

Divisibility

$a,b \in \mathbb{Z}, $ $ a \neq 0$

$a|b $ if $ \exists k \in \mathbb{Z} $ s.t. $ b=ak$

Properties

$\forall a \neq 0, $ $ a|0$ and $a|a$

$1|b $ $ \forall b$

If $a|b$ and $b|c$ then $a|c$

If $a|b$ and $a|c$ then $a|(sb+tc)$ $ \forall s,t \in \mathbb{Z} $

Prime Numbers

Number divisible only by $1$ and itself

Not prime - composite

How many primes? Infinite!

Assume otherwise, the $\exists$ largest prime $p$ (well ordered)

Consider integer $Q=(2*3*5*\dots*p)+1$

$Q$ cannot be prime (bigger than largest prime $p$)

$Q$ must be composite - i.e. has prime factors

But $2, 3, 5, \dots, p$ cannot divide $Q$ (always remainder of $1$

Thus, $\exists $ prime $q > p$ s.t. $q|Q$. Contradiction!

Prime Number Theorem

$\pi(x) $ is the number of primes $<x$. $\pi(x) \approx \frac{x}{\ln x}$

Estimate the number of primes, i.e. every $\ln x$ numbers is a prime

Sometimes closer

Twin Prime Conjecture: There are an infinite number of twin primes

i.e. $x$ and $x+2$ are both prime

Arbitrarily large gaps

Given $k$, find $k$ consecutive compositie numbers

Consider $(k+1)!+2, (k+1)!+3, \dots, (k+1)!+k+1$

Greatest Common Divisor

Largest positive integer that divides both $a$ and $b$ is $\gcd(a,b)$

$d = \gcd(a,b) $ if

$d|a$ and $d|b$

$\forall c, $ $ c|a $ and $c|b \Rightarrow c|d$

If $\gcd(a,b)=1$ then $a$ and $b$ are relatively prime (coprime).

Examples:

$\gcd(6,4)$

$\gcd(5,7)$

$\gcd(24,60)$

How To Find gcd?

Brute Force: get prime factorization, take all common factors

e.g. $576=2^63^2$, ~~ and ~~$135=3^35$, ~ $\gcd(576,135)=3^2=9$

Problem: factor $1024$ bit numbers.

Fortunately, Euclid was pretty smart

Observed that $\gcd(a,b) = \gcd(b, a\mod b)$

Proof: $\gcd(a,b) = \gcd(b, a\mod b)$

Let $d=\gcd(a,b)$

By def, $d|a$ and $d|b$

Also, $a=kb+r = r \mod b$ and $a\mod b = r$ for $k,r \in \mathbb{Z}$

Thus, $a \mod b = a-kb$

Since, $d|b$, then $d|kb$. Also, $d|a$.

Thus, $d|(a \mod b)$

This shows that $d$ is a common divisor of $b$ and $a\mod b$.

How to show its the largest?

If $e|b$ and $e|(a\mod b)$ then $e|kb$ and thus $e|(kb + a \mod b) = a$ so $e|a$.

This means that the set of all common divisors of $a$ and $b$ is equal to the set of all

divisors of $b$ and $a\mod b$. The greatest of one is the same as the greatest of the other.

How Does That Help?

Euclidean Algorithm - repeatedly apply until $b=0$ ($a$ will be the gcd)

$\gcd(7,5) = \gcd(5,2) = \gcd(2,1) = \gcd(1,0) = 1$

$\gcd(1970,1066) = \gcd(1066,904) = \gcd(904,162) = \gcd(162,94)$

$ = \gcd(94,68) = \gcd(68,26) = \gcd(26,16) = \gcd(16,10) = \gcd(10,6)$

$ = \gcd(6,4) = \gcd(4,2) = \gcd(2,0) = 2$

Also, $\gcd(a,b)=d$ means that $d$ is the smallest integer that can be written in the form $d=ax+by$

How to find $x$ and $y$?

Extended Euclidean Algorithm

$(A1,A2,A3) = (1, 0, a)$

$(B1, B2, B3) = (0,1,b)$

If $B3=0$, $\gcd(a,b)=A3$

If $B3=1$, $\gcd(a,b)=1$

$Q=A3/B3$

$(T1,T2,T3) = (A1-QB1, A2-QB2, A3-QB3)$

$(A1,A2,A3) = (B1,B2,B3)$

$(B1,B2,B3)=(T1,T2,T3)$

GOTO Step $1$

At any time, $aB1+bB2 = B3$

Extended Euclidean Algorithm Running Example

Multiplicative Inverses

$ax+by=\gcd(a,b)$

If $\gcd(a,b)=1$ then $ax+by=1$

$ax+by = ax \mod b = 1$

Thus, $x = a^{-1} \mod b$

Only elements $a$ in $\mathbb{Z}_n$ where $\gcd(a,n)=1$ have multiplicative inverses $\mod n$.

Back To Primes

If $p$ is prime, and $p|ab$ then $p|a$ or $p|b$ (or both).

Proof:

Suppose $p$ prime and $p|ab$.

Either $p|a$ or $p \nmid a$.

If $p \nmid a$, then $\gcd(a,p)=1$

Why? Only divisors of $p$ are $p$ and $1$

If $\gcd(a,p)=1$ $\exists x,y$ ~s.t. $ax+py=1 \Rightarrow bax+bpy=b$

So $p|bpy$ (obviously) and $p|bax$

Why? Since $p|ab$

So $p|b$

Fundamental Theorem of Arithmetic

Every positive integer is a unique product of primes

Proof:

Suppose otherwise, that $n$ has two different factorizations

$n = p_1p_2\dots p_r = q_1q_2\dots q_s$

Divide out common factors so prime appears on both sides

But $p_1|n \Rightarrow p_1|q_1q_2\dots q_s \Rightarrow p_1|q_i$ for at least one $i$

Thus $p_1=q_i$. Contradiction.

Congruences

$a,b,n \in \mathbb{Z}$ with $n\neq 0$

$a \equiv b \mod n$ if $a-b$ is a multiple of $n$ (or $n|(a-b)$ )

Properties:

$a \equiv 0 \mod n \Leftrightarrow n|a$

$a \equiv a \mod n$

$a \equiv b \mod n \Leftrightarrow b \equiv a \mod n$

$a \equiv b \mod n$ and $ b\equiv c \mod n \Rightarrow a \equiv c \mod n$

$a,b,c,d,n \in \mathbb{Z}$, $n\neq 0$, $a\equiv b \mod n$ and $c \equiv d \mod n$, then

$a+c \equiv b+d \mod n$

$a-c \equiv b-d \mod n$

i.e. arithmetic is well defined in $\mathbb{Z}_n$

Division $\mod n$

$a,b,c,n \in \mathbb{Z}$, $n\neq 0$, and $\gcd(a,n)=1$

$ab \equiv ac \mod n \Rightarrow b \equiv c \mod n$

Since $\gcd(a,n)=1$, $\exists x,y$ ~s.t.~ $ax+ny=1$

Thus $(ab-ac)x + n(b-c)y = b-c$

Since left side is multiple of $n$ then $b-c$ is a multiple of $n$

Thus $b\equiv c \mod n$

I.e., we can divide by $a$ if $a$ has an inverse.

What If?

What if $\gcd(a,n) > 1$, i.e. $\gcd(a,n)=d$

Solve $ax\equiv b \mod n$

If $d\nmid b$, there is no answer.

e.g. $2x\equiv 5 \mod 6$

If $d|b$

Consider $\frac{a}{d}x_0 \equiv \frac{b}{d} \mod \frac{n}{d}$

Note $\gcd(\frac{a}{d}, \frac{n}{d})=1$

Solve for $x_0$

Original solutions are $x_0, x_0+\frac{n}{d}, x_0+\frac{2n}{d}, \dots, x+0+\frac{(d-1)n}{d}\mod n$

e.g. Solve $12x \equiv 21 \mod 39$ ~~ $\gcd(12,39)=3 \Rightarrow 3$ solutions

Solving $x^2\equiv a \mod n$

What about $x^2\equiv 1 \mod 7$?

Answers? $x=1,6$, (or $x=\pm 1 \mod 7$)

Exactly $2$ solutions when $n$ is odd prime

What about composite? Can have more

e.g. $x^2\equiv 1 \mod 8$? Try all. Hint: $4$ solutions.

Before we can compute, some extra techniques are needed.

Chinese Remainder Theorem

Figured out by Sun Tzuin 3$^{rd}$ century (Not ``Art of War'' guy).

Main purpose: speed up modular computations

Reverse of following: let $x\equiv 25 \mod 42$

Since $42=6*7$ we get two equations:

$x\equiv 25 mod 7 \equiv 4 \mod 7$

$x \equiv 25 \mod 6 \equiv 1 \mod 6$

So we now have a system of modular equations

CRT lets us solve for $x \mod 6*7$

Let $M = m_1m_2\dots m_k$ where all $m_i$ are pairwise coprime

(i.e. $\forall i,j $,~~$ 1\leq i,j \leq k$, ~~$i\neq j$, ~~ $\gcd(m_i,m_j)=1$)

If $x\equiv a_1 \mod m_1$, $x \equiv a_2 \mod m_2$, $\dots$, $x\equiv a_k \mod m_k$

then there is a unique solution for $x \mod M$.

Proof:

Consider $\frac{M}{m_j}$. $\gcd(\frac{M}{m_j})=1$ (Why?)

Thus, $\exists (\frac{M}{m_j})^{-1} \mod m_j$. Call it $c_j$.

Thus we have $(\frac{M}{m_j})(c_j) \equiv 1 \mod m_j$ and $(\frac{M}{m_j})(c_j) \equiv 0 \mod m_i (i\neq j)$ (Why?)

Consider $x_0 = \sum^{k}_{j=1}(\frac{M}{m_j})(c_j)(a_j)$.

It solves all the conguences:

$x_0 \equiv \frac{M}{m_i}c_ia_i \equiv a_i \mod m_i$

Thus $x_0$ is a solution - Is it unique?

Assume another solution exists: $x_1$

$x_0 \equiv x_1 \mod m_i $~~$ \forall i$ thus $m_i|(x_0-x_1) \forall i$

Since all $m_i$ are pairwise coprime:

$\pi(m_i)|(x_0-x_1) \Rightarrow M|(x_0-x_1) \Rightarrow x_0 \equiv x_1 \mod M$

So yes, unique $\mod M$.

Chinese Remainder Theorem Running Example:

So What's The Point?

We can do arithmetic on smaller numbers then recombine later using CRT to get full answer.

Consider: $973 \mod 1813$ where $1813 = 37*49$.

$m_1 = 37$ $ a_1=11\mod 37$

$m_2 = 49$ $ a_2=42\mod 49$

Let's write $973$ as $(11,42)$

Similarly, $678 = (12,41)$

To add $973 + 678$, instead add $(12+11 \mod 37, 41+42 \mod 49) = (23,34)$

Use CRT to recombine:

$m_1=37$$a_1=23$$\frac{M}{m_1}=49$~~$49^{-1}\mod 37 = 34$

$m_2=49$$a_2=34$$\frac{M}{m_2}=37$~~$37^{-1}\mod 49 = 4 $

$x=(49*34*23)+(37*4*34) = 43350 \equiv 1651 \mod 1813$

Check: $678+973 = 1651 \mod 1813$

Turns out, operations $\mod m_1,m_2$ are much more efficient (more noticable when $M$ is $1024$ bits or more).

Modular Exponentiation

Point $1$: modular reduction can be distributed

So $x^{1024}\mod 5$ never needs to be fully exponentiated and then reduced $\mod 5$. All operations need digits $1-4$.

Point $2$: how to compute $x^{16}$?

Option $1$: $\underbrace{x*x*\dots*x}_{16 ~\text{times}}$?

Option $2$: $(((x^2)^2)^2)^2$? Much fewer computations this way.

This is known as Fast Exponentiation or Square and Multiply.

$k=10 ~ a=5 ~ a^k = 5^{10} = 5^85^2 = 5^{2^3}5^2$

$10$ in binary is $1010$.

Fast Modular Exponentiation Algorithm ($s=a^k$)

Start with $s=1$.

Step through exponent $k$ bit by bit (MSB to LSB).

Always square.

If exponent bit is $1$, multiply by $a$.

Example: $5^{10} = 5^{1010_2}$

$s=1$

square ($1$). bit is $1$, $s = s*5 = 5$

square ($5^2$). bit is $0$.

square ($5^{2^2}$). bit is $1$. $s = (5^{2^2})5$

square ($(5^{2^{2^2}})5^2$). bit is $0$.

$\mathbb{Z}_m^*$

$\mathbb{Z}_m^*$ is the set of all integers $k$, $0 < k < m$ s.t. $\gcd(k,m)=1$

E.g. $\mathbb{Z}_6^* = \{1, 5\}$

E.g. $\mathbb{Z}_7^* = \{1, 2, 3, 4, 5,6\}$

E.g. $\mathbb{Z}_{10}^* = \{1, 3, 7, 9\}$

Fermat's Little Theorem

Now that we have some Number Theory under our belts, let's look at the meat.

If $p$ is prime and $\gcd(a,p)=1$ then

a^{(p-1)} \equiv 1\mod p

Proof:

Consider $\mathbb{Z}_p^* = \{1,2,\dots,p-1\}$

Multiply each element in $\mathbb{Z}_p^*$ by $a\mod p$ to get $S=\{a\mod p, 2a\mod p, \dots, a(p-1)\mod p\}$

No element in $S$ is $0$. (Why?)

Now check if any two elements in $S$ are the same (Is there $x,y \in S$, s.t. $x=y$?)

If $x=y$ then $aj\equiv ak \mod p$ for some $j,k$. Since $\gcd(a,p)=1$, then $a^{-1} \mod p$ exists, thus $j\equiv k \mod p$.

Thus, $S$ has all distinct elements with no $0$.

Thus, $S$ is a permutation of $\mathbb{Z}_p^*$.

Thus,

\prod{x \in S} x = \prod{y \in \mathbb{Z}_p^*} y

$a * 2a * \dots * a(p-1) \equiv 1*2*\dots*(p-1) \mod p$

$a^{(p-1)}(p-1)! \equiv (p-1)! \mod p$

Since $p$ is prime, $(p-1)!^{-1}$ exists, so $a^{p-1}\equiv 1\mod p$

Euler's Totient Function $\phi(n)$

$\phi(n) = |\mathbb{Z}_n^*|$

Properties

If $p$ is prime, $\phi(p)=p-1$.

$\phi(n)$ is multiplicative. if $\gcd(m,n)=1$ then $\phi(mn)=\phi(m)\phi(n)$.

If $n=p^k$, then $\phi(n) = (1-\frac{1}{p})p^k = p^k-p^{k-1}$ (i.e. remove all multiples of $p$)

General case: If $n=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$ then $\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\dots (1-\frac{1}{p_k})$

Key point to remember for later - to compute $\phi(n)$ you need the prime factors of $n$.

Euler's Theorem

If $\gcd(a,n)=1$, then $a^{\phi(n)}\equiv 1 \mod n$

Proof:

$\mathbb{Z}_n^* = \{x_1,x_2,\dots,x_{\phi(n)}\}$

Multiply by $a$ to get $S=\{ax_1,ax_2\dots,ax_{\phi(n)}\}$

$S$ is a permutation of $\mathbb{Z}_n^*$. Why?

$\gcd(a,n)=1$ and $\gcd(x_i,n)=1$, so $\gcd(ax_i,n)=1$. So $ax_i \mod n \in \mathbb{Z}_n^*$

If $ax_i\equiv ax_j \mod n$, since $\gcd(a,n)=1$ then $x_i\equiv x_j \mod n$

So

\prod{x\in S}x = \prod{y\in \mathbb{Z}_n^*} y

$ax_1 * ax_2 * \dots * ax_{\phi(n)} \equiv x_1*x_2*\dots *x_{\phi(n)}$

$a^{\phi(n)}*x_1*x_2*\dots * x_{\phi(n)} \equiv x_1*x_2*\dots * x_{\phi(n)} \mod n$

$a^{\phi(n)} \equiv 1 \mod n$

Now Compute The Last $3$ Digits Of $7^{803}$

Last $3$ digits $\Rightarrow \mod 1000$

$\phi(1000) = 1000(1-\frac{1}{2})(1-\frac{1}{5}) = 400$

$7^{803} = 7^{800}7^3 = (7^{400})^27^3 \equiv 1^27^3 \equiv 343 \mod 1000$

In general, if $\gcd(a,n)=1$ then $a^k \mod n \equiv a^{k \mod \phi(n)}\mod n$

Compute: $2^{43210} \mod 101$

Square Roots $\mod n$

How to find?

e.g. $\sqrt{6} \mod 10 = 4,6 $

Let's start with roots $\mod p$.

In particular, let's look at roots $\mod p$ where $p\equiv 3 \mod 4$ (turns out $p\equiv 1 \mod p$ is a lot harder)

Proposition: Let $p\equiv 3 \mod 4$ be prime, $y\in \mathbb{Z}$. Let $x\equiv y^{\frac{p+1}{4}}\mod p$. Then,

If $y$ has a square root $\mod p$, they are $\pm x$

If $y$ has no square roots $\mod p$, then $-y$ does and they are $\pm x$

Proof:

Assume $y \not\equiv 0 \mod p$. Fermat says $y^{p-1}\equiv 1 \mod p$.

Thus, $x^4 \equiv y^{p+1} \equiv y^2y^{p-1} \equiv y^2 \mod p$

This implies that $(x^2+y)(x^2-y)\equiv 0 \mod p$

So $x^2 \equiv \pm y\mod p$

Can $x$ equal both? Can both $+y$ and $-y$ be squares?

If yes (and $y=a^2$, $-y=b^2$), then $\frac{y}{-y} \equiv -1 \equiv (\frac{a}{b})^2 \mod p \Rightarrow -1 $ is a square $\mod p$

This can't be if $p\equiv 3 \mod 4$ (Reason on next slide)

Only $y$ or $-y$ can be a square. Then $y=x^2 \Rightarrow \sqrt{y}=\pm x$ or $-y=x \Rightarrow \sqrt{-y}=\pm x$

Why can't $-1$ be a square $\mod p$ when $p \equiv 3 \mod 4$?

Suppose it is: $x^2\equiv -1 \mod p$.

Consider $(x^{\frac{p-1}{2}})^2 \equiv (-1)^{\frac{p-1}{2}} \mod p$

$x^{p-1} \equiv (-1)^{\frac{p-1}{2}} \mod p$

$x^{p-1} \equiv 1 \mod p$ by Fermat

So can $(-1)^{\frac{p-1}{2}} \equiv 1 \mod p$?

$\frac{p-1}{2}$ is odd, since $p\equiv 3 \mod 4$

$p \equiv 3 \mod 4 \Rightarrow p=4k+3 \Rightarrow \frac{(4k+3)-1}{2} = 2k+1$ which is odd

So how to find square roots?

Raise to the $\frac{p+1}{4}$ power.

e.g. $\sqrt{5} \mod 11$ (since $11 \equiv 3 \mod 4$)

$5^{\frac{11+1}{4}} = 5^3 \equiv 4 \mod 11$

Check: $4^2 \equiv 16 \equiv 5 \mod 11$

Check: $(-4)^2 \equiv 7^2 \equiv 49 \equiv 5 \mod 11$

Find $\sqrt{2} \mod 11$

What about square roots mod composite $n$?

If prime factors are $\equiv 3 \mod 4$, comptue roots mod each prime factor, recombine using CRT.

$x^2 \equiv 71 \mod 77=7*11$

So, $x^2 \equiv 71 \equiv 1 \mod 7$ and $x^2 \equiv 71 \equiv 5 mod 11$

From last slide: $x\equiv \pm 1 \mod 7$ and $x\equiv \pm 4 \mod 11$

CRT lets us recombine in $4$ ways to get $4$ roots.

Doing so gives us: $\pm 15, \pm 29$ as roots of $71 \mod 77$

So, knowing factors lets us take roots. Does knowing roots let us factor?

Roots $\Rightarrow$ Factoring

Let $x^2 \equiv y \mod n$ where $n=pq$, $p,q \equiv 3 \mod 4$

$x=\pm a, \pm b$

By last slide's construction, $a\equiv b \mod p$ and $a \equiv -b\mod q$

Thus, $p|(a-b)$ but $q \not| (a-b)$

Thus, $\gcd(a-b,n) = p$ which is a nontrivial factor of $n$

In other words, factoring is computationally equivalent to taking square roots $\mod n$

Primality Tests

They become rare as numbers get bigger

Trial Division

Requires $\sqrt{n}$ test divisions

For $1024$ bit prime, requires $2^{512}$ tests...

Fermat

Remember: $\gcd(a,p)=1 \Rightarrow a^{p-1}\equiv 1 \mod p$

Test it for a bunch of $a$ values

If any are not equal to $1$, output COMPOSITE

If all are equal to $1$, output (PROBABLY) PRIME

Carmichael

Carmichael number pass the Fermat test, but are composite.

They become rare as numbers get bigger

Miller Rabin

Very efficient, popular, effective

Gives positive proof of composite

Gives (adjustable) probability of primality

Based on fact that in $\mathbb{Z}_p$, $1$ only has $\pm 1$ as square roots

Let $n$ be odd - testing for primality

Write $n-1$ as $2^km$ where $m$ is odd

Why? If $n$ is odd, $n=2x+1$, so $n-1=2x$. Keep dividing until $x$ is odd

Important fact:

Let $p$ be a prime $>2$

Let $p-1 = 2^sr$ where $r$ is odd

Let $a$ be any integer s.t. $\gcd(a,p)=1$

Then one of the following is true:

$a^r\equiv 1 \mod p$

$a^{2^jr}\equiv -1 \mod p$ for some $j$, ~~ $0\leq j \leq s-1$

Proof

Fermat says that $a^{p-1}\equiv 1 \mod p$. Since $p-1=2^sr$, then $a^{2^sr}\equiv 1 \mod p$

Consider sequence $a^r, a^{2r}, a^{2^2r}, \dots, a^{2^{s-1}r}, a^{2^sr}$

The last item is $\equiv 1 \mod p$ by Fermat. Also, each item in the sequence is the square of the previous

We have two possibilities:

$a^r\equiv 1 \mod p$ (and thus all subsequent are also $1$)

Some number in the sequence is not $1$ but squares to $1$. i.e. it is $-1 \mod p \equiv p-1 \mod p$

This suggests an algorithm for primality testing

Miller Rabin Primality Test

Given $n$

Find: $k,q,k>0, q$ odd such that $n-1=2^kq$

Select random base $a$ between $1$ and $n-1$

If $a^q \equiv 1 \mod n$ reteurn ``Probably Prime''

For $j=0$ to $k-1$

~~ If $a^{2^jq} \equiv n-1 \mod n$ return ``Probably Prime''

Return ``Composite''

If ``Composite'' returned, $n$ is definitely composite

If $n$ is a prime, it will never return ``Composite''

For composite $n$, MR will return ``Probably Prime'' with probability $<\frac{1}{4}$

i.e. about $\frac{1}{4}$ of the possibilities for $a$ are MR liars

Solution? Run MR $t$ times. Composite $n$ will get verdict of ``Composite'' with probability $1-(\frac{1}{4})^t$

For more certainty, run it more iterations

Used by OpenSSL

Other tests include Solovay Strassen (uses number theory we didn't cover).

Interesting Observation

If composite $n$ and there are an intermediate pair of values $b_i=a^{2^iq}, b_{i+1}=a^{2^{i+1}q}$ such that $b_{i+1}\equiv 1 \mod n$ but $b_i \not\equiv \pm 1 \mod n$

Then $\gcd(b_i-1,n) = $ a nontrivial factor of $n$

Remember square roots $\mod n$?

If $x^2\equiv y^2 \mod n$ but $x\not\equiv \pm y\mod n$ then $\gcd(x-y,n)$ is a nontrivial factor of $n$

Recall: $x^2\equiv y^2 \mod n \Rightarrow x^2-y^2\equiv 0 \mod n \Rightarrow (x+y)(x-y) \equiv 0 \mod n \rightarrow n|(x+y)(x-y)$

Example

$n=561$, $n-1 = 560 = 16*35 = 2^4*35$

$a=2 , q=35, k=4$

$2^{35} \equiv 263 \mod 561$

$263^2 \equiv 166 \mod 561$

$166^2 \equiv 67 \mod 561$

$67^2 \equiv 1 \mod 561$

$67^2 \equiv 1^2 \mod 561$

$\gcd(67-1, 561) = 33$

Miller Rabin Primality Test Example

$n=221, n-1 = 220 = 2^2*55$

Randomly select $a=174$

$174^{55} \equiv 47 \mod 221$

$47^2 \equiv 220 \mod 221 \equiv -1 \mod 221$ - Probably Prime!

Randomly select $a=137$

$137^{55} \equiv 188 \mod 221$

$188^2 \equiv 205 \not\equiv -1 \mod 221$ - Composite!

Factorization

Trial Division

Trial Division - try all primes $<\sqrt{n}$ - SLOW!

Fermat Factorization

Express $n$ as a difference of squares

$n=x^2-y^2 = (x+y)(x-y) \Rightarrow x+y$ is a factor, $x-y$ is a factor

Example: factor $n=295927$

Compute $n+1^2, n+2^2, n+3^2, \dots$ until we find a square

In this case, $295927+3^2 = 295936 = 544^2$

Thus $n = (544-3)(544+3) = 541*547$

Example: Factor $n=56$

$n+1^2 = 57$

$n+2^2=60$

$n+3^3 = 65$

$n+4^2 = 72$

$n+5^2 = 81 = 9^2$

$56=(9+5)(9-5)$

Works very well for $n=pq$ when $p$ and $q$ are very close to each other

Security: In RSA pick $p$ and $q$ of slightly different sizes ($p$ of 513 bits and $q$ of 511 bits) - whats the complexity to factor?

Pollard $p-1$

Works when $p-1$ has only small prime factors

Find prime factors $p$ of $n$ when $p-1$ is $B$-smooth (i.e. all prime factors are $<B$)

Lots of variances in descriptions/explanantions

Basic Idea: If $p|n$ then $a^{K(p-1)}\equiv 1 \mod p$ (if $\gcd(a,n)=1$).

If $x\equiv 1 \mod p$ then $\gcd(x-1,n)=d$ is a factor of $n$

Why? $x-1\equiv 0 \mod p$, so $x-1$ is a multiple of $p$

Intuition: Compute $a^Q$ where $Q$ is a multiple of $p-1$

If $p-1$ is $B$-smooth, make it a product of powers of all small primes $< B$ [ Q = \prod_{\text{primes~} q<B} q^{\log_q n} ]

Select a random $a$, ~ $2\leq a\leq n-1$ where $\gcd(a,n)=1$

What to do if $\gcd(a,n) \neq 1$?

Compute $gcd(a^Q-1,n)=d$. If $d>1$ yay!

Else, increase $B$, add to $Q$ and retry

Repeat until you factor, or until you get bored and give up

Strong Primes! $n$ should be product of strong primes:

$p$ is large

$p-1$ has large factors: $p=a_1q_1+1$ for some integer $a_1$ and a large prime $q_1$

$q_1$ has large prime factors: $q_1=a_2q_2+1$ for some integer $a_2$ and large prime $q_2$

$p+1$ has large prime factors: $p=a_3q_3-1$ for some integer $a_3$ and large prime $q_3$

Caveat: strong prime do not protect against new, faster factorization methods, so often strong prime rules are not enforced. (Large size is most important)

Quadratic Sieve

Basis for modern factorization methods:

If $x^2\equiv y^2 \mod n$ and $x \not\equiv \pm y\mod n$ then $n$ is composite and $\gcd(x-y,n)=d$ is a non-trivial factor of $n$

Motivating example: $n=3837523$

Observe:

$ 9398^2 \equiv 5^5*19 \mod n\\ $

$ 19095^2 \equiv 2^2*5*11*13*19 \mod n\\ $

$ 1964^2 \equiv 3^2*13^3 \mod n\\ $

$ 17078^2 \equiv 2^6*3^2*11 \mod n $

Multiply all together

$ \[9398*19095*1964*17078 \equiv (2^4*3^2*5^3*11*13^2*19)^2 \mod n\] $

$ \[2230387^2 \equiv 2586705^2 \mod n\] $

Can factor by taking $\gcd(2586705-2230387, 3837523) = 1093$

What Did We Just Do?

Took a bunch of numbers that, when squared, were relatively small when reduced $\mod n$ and thus can be written as a product of small primes

Need to multiply together to get even powers of our small primes (called factor base)

Selecting factor base requires material we skipped...

How To Do?

This Is The Quadratic Sieve Part

Generate numbers of the form $\lceil \sqrt{in}+j \rceil$ for small $j$ and various $i$

When squared, $in+2j\sqrt{in}+j^2 \equiv 2j\sqrt{in}+j^2 \mod n$

For small $i,j$, this number is small and likely to be the product of small primes

Factor this small number using trial division and factor base

Interpret prime powers as rows in a matrix

$2^2 * 3 * 5^3 \Rightarrow (2,0,3) = (0,0,1) \mod 2$

Generate several lines and look for lines that add up to all zeros (Linear Algebra stuff)

If $x^2\equiv y^2\ mod\ n$ and $x\equiv ±y\ mod\ n$ then n is composite and $gcd(x-y,n)=d$ is a non-trivial factor of n

Discrete Logarithms

Intro

One more major topic related to public key

A Number Theory reference problem - Discrete Logarithms

Given prime $p$, $\alpha, \beta$ non zero integers in $\mathbb{Z}_p^*$ where $\beta \equiv \alpha^x \mod p$

Find $x$ (Book notation: $x=L_{\alpha}(\beta)$

e.g. $p=11, \alpha = 2, \beta = 9$, then $x=6$ since $2^6 \equiv 9 \mod 11$, or $L_2(9)=6$

In crypto protocols, usually $\alpha$ is a primitive root (or generator) $g$

This makes $L_g(\beta)$ defined for all $\beta \in \mathbb{Z}_p^*$

Believed to be hard (about as hard as factoring)

How to compute?

My notation for DLP: $y=g^x \mod p$

$x \mod 2$

Its easy to determine $x \mod 2$ (even/odd)

Note: $(g^{\frac{p-1}{2}})^2 \equiv g^{p-1} \equiv 1 \mod p$

So $g^{\frac{p-1}{2}} \equiv \pm 1 \mod p$

Since $p$ prime, no other exponent less than $p-1$ results in $1$, so $g^{\frac{p-1}{2}} \not\equiv 1 \mod p$

So $g^{\frac{p-1}{2}} \equiv -1 \mod p$

So $y^{\frac{p-1}{2}} \equiv (g^x)^{\frac{p-1}{2}} \equiv (g^{\frac{p-1}{2}})^x \equiv -1^x \mod p$

So if $y^{\frac{p-1}{2}} \equiv 1 \mod p$ then $x$ is even ($x \equiv 0 \mod 2$)

If $y^{\frac{p-1}{2}} \equiv -1 \mod p$ then $x$ is odd ($x \equiv 1 \mod 2$)

Example

$2^x \equiv 9 \mod 11$

$9^{\frac{11-1}{2}} \equiv 9^5 \equiv 1 \mod 11 \Rightarrow x$ is even

Recall: $x=6$

Pohlig Hellman

Extend that idea to get a way to compute DL when $p-1$ only has small factors.

Suppose $p-1 = \prod_i q_i^{r_i}$ where each $q_i$ is a prime

Compute $L_g(y) \mod q_i^{r_i}$ for all $i$ and recombine with CRT!

How to solve $L_g(y) \mod q^r$?

Write $x=x_0 + x_1q + x_2q^2 + \dots + x_{r-1}q^{r-1}$ with each $0 \leq x_i \leq q-1$

i.e. write $x$ in base $q$

Determine each $x_i$ successively to get $x\mod q^r$

Note that $x(\frac{p-1}{q}) = x_0(\frac{p-1}{q}) + (p-1)(x_1+x_2q+\dots x_{r-1}q^{r-2}) = x_0(\frac{p-1}{q}) + (p-1)n$ for some $n \in \mathbb{Z}$

Since $y\equiv g^x \mod p$ then

$ \[y^{\frac{p-1}{q}} \equiv g^{(x_0\frac{p-1}{q})}\underbrace{g^{n(p-1)} \equiv g^{x_0(\frac{p-1}{q})}}_{\text{By Fermat}} \mod p \] $

Find $x_0$ by looking at $g^{k\frac{p-1}{q}} \mod p$ for $k=0$

to $q-1$ until one matches $y^{\frac{p-1}{q}}$

Running Example

Project 3

For this assignment you will develop a number theory/public key encryption toolkit that implements several of the functions that we have discussed. You will need to provide an interface that allows me to choose which function to run and input the relevant parameters. The interface can be as simple or as complex as you like (from text based to GUI). It just needs to let me test your functions. You may use either any language. The programs should support arbitrarily large numbers so you will need to make use of appropriate libraries (e.g. gmp for C++ [hHp://gmplib.org/], or the BigInteger class in Java). Many of the functions that I ask you to write are provided already by the respective libraries, you may not use them, but rather you should implement them yourselves. You are of course free to use the low-level functions (add, mod, etc). The functions to be implemented are listed below. For each the user should be able to input the appropriate parameters.

1. isProbablyPrime – allow the user to input a number and run the miller rabin test. Should ask for a number of repetitions.

2. getProbablePrime – allow the user to input a bit length and number of repetitions and your program should generate a random number of appropriate bit length that is probably prime (using your function 1).

3. Gcd – allow user to input two numbers and your program will implement the Euclidean algorithm to find the gcd.

4. Multiplicative inverse – your program will allow the user to input a number and a modulus and it will implement the extended Euclidean algorithm to find the multiplicative inverse for the modulus.

5. Generate RSA key pair – generate large (probable) primes p and q, and appropriate e and d and print them to the screen. It would be helpful to allow interaction with a file (put the public key information into one file and private key information into another file for input into later functions).

6. RSA encrypt – prompt for a message and public key information (file I/O for faster input of large key) and should encrypt using underlying fast exponention from the respective libraries

7. RSA decrypt – prompt for ciphertext and private key info and should decrypt using underlying exponentiation library functions. Print the decrypted message to the screen.

8. Pohlig Hellman Discrete Logarithm – prompt for a generator g, prime p, and y=$g^x$ value, compute x using the Pohlig Hellman algorithm.

Extra Credit: (10 points) Implement CRT speedup for RSA decryption

https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/ http://stackoverflow.com/questions/4643647/fast-prime-factorization-module http://userpages.umbc.edu/~rcampbel/Computers/Python/numbthy.html