iPython Notebook HowTo's


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)





LaTeX in Markdown:

$e^{i \omega t}$

e^{i \omega t}


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:

In [1]:
#Enable LaTeX printing
from IPython.core.display import *

global MathJax 
MathJax = True
def MDPL(string): display(Math(string)) if MathJax else display(Latex(string))

import IPython.core.display  
div.input {
width: 105ex; /* about 80 chars + buffer */
div.text_cell {
width: 105ex /* instead of 100%, */
div.text_cell_render {
/*font-family: "Helvetica Neue", Arial, Helvetica, Geneva, sans-serif;*/
font-family: "Charis SIL", serif; /* Make non-code text serif. */
line-height: 145%; /* added for some line spacing of text. */
width: 105ex; /* instead of 'inherit' for shorter lines */
/* Set the size of the headers */
div.text_cell_render h1 {
font-size: 18pt;
div.text_cell_render h2 {
font-size: 14pt;
.CodeMirror {
 font-family: Consolas, monospace;

div.input { width: 105ex; /* about 80 chars + buffer */ } div.text_cell { width: 105ex /* instead of 100%, */ } div.text_cell_render { /*font-family: "Helvetica Neue", Arial, Helvetica, Geneva, sans-serif;*/ font-family: "Charis SIL", serif; /* Make non-code text serif. */ line-height: 145%; /* added for some line spacing of text. */ width: 105ex; /* instead of 'inherit' for shorter lines */ } /* Set the size of the headers */ div.text_cell_render h1 { font-size: 18pt; } div.text_cell_render h2 { font-size: 14pt; } .CodeMirror { font-family: Consolas, monospace; }


Notes and code derived from CSCI 466 Cryptography

School: Liberty University

Professor: Mark Shaneck

In [16]:
#Basic Encryption/Decryption Algorithms
#Code Block
from binascii import *        #Hex conversion
from collections import deque #Queue
from collections import defaultdict as dd #Dynamic Dictionary
from string import Template   #Output formatting
from heapq import heappush, heappop #Minheap
from functools import reduce as reduce
import re

def type2(a):
    return b

def remDups(seq):
    seen = set()
    seen_add = seen.add
    return reduce(lambda x,y:x+y,[ x for x in seq if x not in seen and not seen_add(x)])

class Cipher:
    def __init__(self):
    def enc(self,s):
        print("No Encryption Algorithm Added")
    def dec(self,s):
        print("No Decryption Algorithm Added")

class MAS(Cipher):
    """Monoalphabetic (Affine) Substitution Cipher"""
    def __init__(self,a,b):
    def enc(self,s):
        return reduce(lambda x,y:x+y,[chr(((ord(p)-97)*self.a+self.b)%26+97) if (ord(p)>=97 and ord(p)<=122) else p for p in s])
    def dec(self,s):
        return reduce(lambda x,y:x+y,[chr((((ord(p)-97)-self.b)*self.an)%26+97) if (ord(p)>=97 and ord(p)<=122) else p for p in s])
class PF(Cipher):
    """Playfair Cipher"""
    def __init__(self,s):
        for i in range(5):
    def printTable(self):
        for i in self.Table:
            print ('{0}'.format(str(i)))

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


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^n=a*a* \dots *a$ ($n$ times)


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


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$


$(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$


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

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


$\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).





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$


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

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


GOTO Step $1$

At any time, $aB1+bB2 = B3$

Extended Euclidean Algorithm Running Example

In [20]:
#(Extended) Euclid Algorithm
#Code Block
#Derived from Algorithm by Robert W. Sebesta
def Euclid(a,b,ans=0,pt=0,retA=1):
    """Finds the greatest common divisor of a and b and x,y
    such that a*x+b*y=gcd(a,b)
    Three flags vary the output (Any number may be true):
    ans: If true will print the equation a*x+b*y=gcd(a,b)
    pt: If true will show the table method for finding the solution
    retA: If true will return the list [a,x,b,y,gcd(a,b)]
    if ans:
        print ('\n({0})({1})+({2})({3})={4}'.format(a,T[0],b,T[1],T[2]))
    if pt: 
        for x in Temp[1]: print ('{0}\t{1}\t{2}\t{3}\t{4}\t{5}'.format(x[0][0],x[0][1],x[0][2],x[1][0],x[1][1],x[1][2]))
    if retA:
        return [a,T[0],b,T[1],T[2]]
def _Euc(a,b,s):
    """Main recursive loop for Extended Euclidean Algorithm"""
    if b[2]==0: return [b[0],b[1],a[2]],s
    if b[2]==1: return b,s
        t=[a[n]-Q*b[n] for n in range(3)]
        return _Euc(a,b,s+[[a,b]])
def MI(a,b):
    """Returns the multiplicative inverse of a mod b"""
    temp = Euclid(a,b,ans=0,pt=0,retA=1)[1]
    if temp<0:temp+=b
    return temp

In [21]:
#Extended Euclidean Algorithm
#Test Block

A1	A2	A3	B1	B2	B3
1	0	139	0	1	91
0	1	91	1	-1	48
1	-1	48	-1	2	43
-1	2	43	2	-3	5
2	-3	5	-17	26	3
-17	26	3	19	-29	2
19	-29	2	-36	55	1

[139, -36, 91, 55, 1]

Multiplicative Inverses


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).


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


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.


$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)$ )


$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$.


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:

In [24]:
#Chinese Remainder Theorum
#Code Block
def CRT(A,ptable=0):
    """A is a list of lists such that [[a1,a2],[b1,b2],...] is equivalent to 
    x = a1 mod a2, x = b1 mod b2,... where a,b,... are integers
    The flag ptable if true will output the work to find the solution"""
    M=reduce(lambda x,y:x*y,[i[1] for i in A])
    if ptable: pprint( 'M={0}'.format(M))
    for i in A:
        #print 'a({0})={1} m({0})={2} M/M({0})={3} c({0})={4}'.format(Ans[count-1][0],Ans[count-1][1],Ans[count-1][2],Ans[count-1][3],Ans[count-1][4])
        if ptable: pprint('a_{{{0}}}={1},\ m_{{{0}}}={2},\ \\frac{{M}}{{M_{{{0}}}}}={3},\ c_{{{0}}}={4}'.format(Ans[count-1][0],Ans[count-1][1],Ans[count-1][2],Ans[count-1][3],Ans[count-1][4]))
    if ptable: 
        pprint( outS[:-1] + ' = {0}'.format(sumS) )
        pprint( '= {0}\ mod\ {1}'.format(sumS%M,M) )
    return sumS%M

$$a_{1}=5,\ m_{1}=8,\ \frac{M}{M_{1}}=5,\ c_{1}=5$$
$$a_{2}=3,\ m_{2}=5,\ \frac{M}{M_{2}}=8,\ c_{2}=2$$
$$(5*5*5)+(8*2*3) = 173$$
$$= 13\ mod\ 40$$

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}$


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^*$ 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


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^*$.


\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^*|$


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$


$\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$


\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$


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...


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 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$


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)$


$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!

In [25]:
#Primality Tests
##Code Block
from random import randint as ri
class PTest:
    def __init__(self):
    def TryDiv(self,a):
        return [(i,a//i) for i in range(2,int(a**.5)) if a%i==0]
    def Fermat(self,a):
    def Carmic(self,a):
def MilRab(n,rep=5,showwork=0):
    if n<=3: return 1
    if n%2==0: 
        if showwork: ppt("{0}\ is\ even".format(n))
        return 0
    while q%2==0:
    d,s=q,k #Other explanations use this notation
    if showwork: ppt("{2}-1 = 2^{0} {1}".format(k,q,n)) #Show n-1 factored
    if q==1: return 1
    def _MRHelp(a):
        if pow(a,d,n)==1: return 0
        for i in range(s): #Witness Loop   
            if temp2==n-1: return 0
        return 1
    for temp in range(rep):
        if _MRHelp(a): return 0
    return 1 #Since nothing says otherwise, return probably prime

In [26]:
#Primality Tests
##Test Block
outS={0:'Composite',1:'Probably Prime'}
for a in range(20):
    print (rnd)
    print (outS[MilRab(rnd,showwork=1)])
    print ("Factor for verification: ",fc(rnd), "\n\n")
#for i in [["Trial Division",TEST.TryDiv],["Fermat",TEST.Fermat],["Carmichael",TEST.Carmic],["Miller-Rabin",TEST.MilRab],["Universal Exponent Factorization",TEST.Univ]]:
#    print i[0]+": ",i[1](a)
#    if Timer:
#        %timeit TEST.TryDiv(a)

$$18377-1 = 2^3 2297$$
NameError                                 Traceback (most recent call last)
<ipython-input-26-1e6597442269> in <module>()
      6     print (rnd)
      7     print (outS[MilRab(rnd,showwork=1)])
----> 8     print ("Factor for verification: ",fc(rnd), "\n\n")
      9 #Timer=0
     10 #a=42

NameError: name 'fc' is not defined


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+3^3 = 65$

$n+4^2 = 72$

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


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$


$ 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

In [7]:
#Code Block
class Factorizer:
    def __init__(self):
    def TryDiv(self,a):
        return [(i,a/i) for i in range(2,int(a**.5)) if a%i==0]
    def Fermat(self,a):
        for i in range(1,100):
            if temp==int(temp):
        return ret
    def Pollard(self,a):
    def QuadSieve(self,a):

In [8]:
#Factorization Tests
##Test Block
for i in [["Trial Division",TEST.TryDiv],["Fermat",TEST.Fermat],["Pollard p-1",TEST.Pollard],["Quadratic Sieve",TEST.QuadSieve]]:
    print i[0]+": ",i[1](a)
    if Timer:
        %timeit TEST.TryDiv(a)

  File "<ipython-input-8-84f65d38f9c6>", line 7
    print i[0]+": ",i[1](a)
SyntaxError: invalid syntax

Discrete Logarithms


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$)


$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

In [28]:
#Pohlig Hellman Discrete Log
#Code Block
#Source: http://www-math.ucdenver.edu/~wcherowi/courses/m5410/phexam.html
from sympy import factorint as fc
ppt=MDPL #LaTeX-style print function
def DLog(g,p,y,ShowWork=0):
    """Prompt for a generator g, prime p, and y=g^x value.
    Essentially finds x
    Compute x using the Pohlig Hellman algorithm."""
    pf=fc(p-1) #Factor p-1
    if ShowWork: 
        ppt("Pollig-Hellman\ Discrete\ Log\ Example")
        ppt("Given\ p={0},g={1},\ and\ y={2}\ such\ that\ {1}^x\equiv {2}\mod {0} \equiv {3}\mod {0},\ find\ x:".format(p,g,y,y%p))
        ppt("$p-1={0}-1={1}$".format(p,"".join([str(i[0])+"^"+str(i[1])+" * " for i in pf.iteritems()]))[:-3])
        ppt("Now\ we\ need\ to\ find\ a\ congruency\ for\ each\ factor:")
    for i in pf.iteritems(): #For each factor
        q=i[0] #Factor
        r=i[1] #Power
        if ShowWork: 
            ppt("Find\ x_{{{0}}} \mod {1}\ [x_{{{0}}}={2}]:".format(q,q**r,"".join(["c_{{{0}}}*({{{1}}})+".format(ii,q**ii) for ii in range(r)])[:-1]))
        yy=y #Initially set base to y for each factor
        NewCLast=dict((pow(g,ii*(p-1)/q,p),ii%q) for ii in range(1,q+1)) #Dictionary of possible values for c_? to hit
        if ShowWork: ppt("y^{{ k \\frac{{p-1}}{{q^{{c_0}}}} }}\ must\ be\ one\ of\ these:\ {0}".format("".join(["{2}^{{{0}*\\frac{{p-1}}{{{3}}}}} \equiv {1},\ ".format(NewCLast[ii],ii,g,q) for ii in NewCLast.keys()])[:-3] ) )
        xTemp=0 #Using cumulative sum for finding each c_?
        for k in range(r): #For each c_?
            for j in range(1,q+1): #Try values until temp is in the NewCLast dictionary
                j=j%q #Since it would normally start with 0, making 0 last by wrapping with mod
                trypow=j*(p-1)/(q**(k+1)) #Generate power to raise yy by
                if temp in NewCLast.keys():
                    j=NewCLast[temp] #Find the power of yy that makes temp
                    xTemp+=(q**k)*j #Add the cumulating sum for x
                    if ShowWork: ppt("$ y^{{ k \\frac{{p-1}}{{q^{{{9}}}}} }} \equiv {0}^{{ {7} \\frac{{{1}}}{{{2}}} }} \equiv {0}^{{{3}}} \equiv {4} \mod {6},\ so\ c_{{{8}}} = {7} $".format(yy,p-1,q**(k+1),trypow,temp,temp-p,p,j,k,k+1))
                    if k<r-1: #Skip division if unneccessary
                        if ShowWork: ppt("We found\ c_{{{1}}},\ so\ divide\ {0}\ by\ {3}^{{{2}*c_{{{1}}} }}\ ({3}^{{ -{5}*{4} }} \equiv {6})".format(yy,k,q**k,g,j,q**k, (MI(g,p)**(q**j))%p ) )
                        yy=( yy*MI(g,p)**( q**(k)*(j) ) )%p
        if ShowWork: ppt("So,\ x_{{{0}}}={1} \mod {2}".format(q,xTemp,q**r))
        x+=[[xTemp,q**r]] #Add equivalence to list for CRT
    if ShowWork: 
        ppt("Now\ use\ the\ Chinese\ Remainder\ Theorem:")
    return CRT(x,ptable=ShowWork)

In [29]:
#Pohlig Hellman
#Test Block
#g is a
#p is p
#y is a^x

$$Pollig-Hellman\ Discrete\ Log\ Example$$
$$Given\ p=41,g=7,\ and\ y=12\ such\ that\ 7^x\equiv 12\mod 41 \equiv 12\mod 41,\ find\ x:$$
AttributeError                            Traceback (most recent call last)
<ipython-input-29-db09ae57325a> in <module>()
      5 #y is a^x
      6 #DLog(g,p,y)
----> 7 DLog(7,41,12,1)#(6,8101,7531,1)#(7,41,12)

<ipython-input-28-a9b11fd35d97> in DLog(g, p, y, ShowWork)
     12         ppt("Pollig-Hellman\ Discrete\ Log\ Example")
     13         ppt("Given\ p={0},g={1},\ and\ y={2}\ such\ that\ {1}^x\equiv {2}\mod {0} \equiv {3}\mod {0},\ find\ x:".format(p,g,y,y%p))
---> 14         ppt("$p-1={0}-1={1}$".format(p,"".join([str(i[0])+"^"+str(i[1])+" * " for i in pf.iteritems()]))[:-3])
     15         ppt("Now\ we\ need\ to\ find\ a\ congruency\ for\ each\ factor:")
     16     x=[]

AttributeError: 'dict' object has no attribute 'iteritems'

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

In [10]:
#Code Block
from sympy import factorint as fc
from sympy import randprime as rp
from random import randint as ri
from binascii import hexlify
from binascii import unhexlify
def isProbablyPrime(a,b=5):
    """Uses Miller-Rabin to return if a is prime using b repititions"""
    return MilRab(a,rep=b,showwork=0)
def getProbablePrime(a,b,speedup=0):
    """Return a prime of bit length a using b repititions of Miller-Rabin"""
    if speedup: r=rp(2**(a-1),2**(a))
        while not(isProbablyPrime(r,b)): 
            r=ri(2**(a-2),2**(a-1))*2-1#int(reduce(lambda x,y:x+y,[str(ri(0,1)) for i in range(a)]),2)
    return r
def Gcd(a,b):
    """Returns gcd of integers a and b"""
    return Euclid(a,b,ans=0,pt=0,retA=1)[4]
def MultiplicativeInverse(a,b):
    """Returns the inverse of a mod b"""
    temp = Euclid(a,b,ans=0,pt=0,retA=1)[1]
    if temp<0:temp+=b
    return temp
def GenerateRSAKeyPair():
    """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)."""
    while Gcd(e,phiN)!=1: e=ri(3,2**10+3)
    return (e,n),(d,n)
def RSAEncrypt(p,e):
    if len(m)%2==1: m='0'+m
    return m
def RSADecrypt(c,d):
    return RSAEncrypt(c,d)
def PohligHellmanDiscreteLogarithm(g,p,y):
    """Prompt for a generator g, prime p, and y=g^x value.
    Essentially finds x
    Compute x using the Pohlig Hellman algorithm."""
    return DLog(g,p,y)

ImportError                               Traceback (most recent call last)
<ipython-input-10-8731d4376228> in <module>()
      1 #P3
      2 #Code Block
----> 3 from sympy import factorint as fc
      4 from sympy import randprime as rp
      5 from random import randint as ri

ImportError: No module named 'sympy'

In [ ]:
#Test Block
import locale
def commafy(a): return locale.format("%d",a,grouping=True)
import re
#def commafy(q): reduce(lambda x,y:x+', '+y,re.findall(r'[0-9]{3}|[0-9]+','0'*(len(str(q))%3-1)+str(q)))

outS={0:'Composite',1:'Probably Prime'}
rnd=ri(1,1000000)*2-1;print "\nisProbablyPrime ({0})\n".format(rnd),outS[isProbablyPrime(rnd,5)]
print "\nRandom Prime: ",getProbablePrime(1024,5,1)
print "\nGcd (5,89)\n",Gcd(5,89)
print "\nMultiplicative Inverse (5,89)\n",MultiplicativeInverse(5,89)
print "\nRSA Key Pair"
print "e: {0}".format(commafy(e[0]))
print "d: {0}".format(commafy(d[0]))
print "n: {0}".format(commafy(d[1]))
print "\nRSA Encrypt: \n",c
print "\nRSA Decrypt: \n",p
print "\nPohlig-Hellman Discrete Logarithm (6,8101,7531)\n",PohligHellmanDiscreteLogarithm(6,8101,7531)

In [ ]:
%load_ext sympy.interactive.ipythonprinting
import sympy
def GCD2():
    a,x,b,y,d=sympy.symbols('a x b y d')

In [ ]: