## Chapter 1: Modular arithmetic

- euclidean algorithm: find $g(a,b)$.
- extended euclidean: find $p,q$ such that $ap+bq=g(a,b)$
- euler’s totient function: $ϕ(m)=#(Z/mZ)_{∗}=#{0≤a<m:g(a,m)=1}$

## Chapter 2

### Hardness of DLP

A very important thing to note is hardness of DLP depends heavily on the groups used. For example: DLP for an additive group in $F_{p}$ can be solved in $O(gp)$ using Extended-Euclidean algorithm while the best known solution for DLP in $F_{p}$ has sub-exponential time algorithm. Elliptic curves has DLP solution computable in $O(p )$ which is exponential time.

### Shanks Babystep-Giantstep

Can solve DLP in a multiplicative group in $O(N gN)$.

- let $n=1+N $.
- create two lists:
- L1: $e,g,…,g_{n}$
- L2: $h,h⋅g_{−n},h⋅g_{−2n},…,h⋅g_{−n_{2}}$

- find match between two lists, let $g_{i}=h⋅g_{−jn}$
- $x=i+jn$ solves $g_{x}=h$

### CRT

### Pohlig-Hellman Algorithm

In a group $G$, suppose that you have an algorithm to solve discrete logarithm $g_{x}=h$ in a group of prime power order, i.e. $q_{e}$ in $O(S_{q_{e}})$ steps, then it’s possible to solve discrete logarithm in a group with order $N=q_{1}⋅q_{2}…q_{t}$ in $O(∑_{i∈[0,t]}S_{q_{i}}+g(N))$ steps.

Basic steps are to divide the algorithm for each prime power factor and find discrete logarithm and then use CRT to solve for $x$ in $N$:

- let $N_{i}=q_{i}N $. Note that, each $N_{i}$ is pairwise co-prime. Now, let $g_{i}=g_{N_{i}}$ and $h_{i}=h_{N_{i}}$
- for any prime power $i$, let $x=y_{i}+q_{i}z_{i}$
- taking it to multiplicative group $g$:

- each of the previous step takes $O(S_{q_{i}})$ steps.
- now use CRT, to solve for $x$ in each $N_{i}$ in $g(N)$ steps.

### Polynomial Rings

$F[X]:a_{0}+a_{1}x+a_{2}x_{2}…$, where $a_{i}∈F$ form a ring with $(+,⋅)$.

- write $a$ as $a=b⋅k+r$ where $g(b)>g(r)$ and $b=0$ and $b,k,r∈F[X]$
- arithmetic on polynomial rings
- $g(a.m)=a⋅u+m⋅v=d$, then there is a common divisor $d$ of $a,b$.
- extended euclidean algorithm to compute $u,v$.

- every element of ring can be factored into monic irreducible polys.

**Quotient ring**: let $m∈F[X]$ be an irreducible poly, then every congruence class has representation $aˉ∈F[X]/(m)$ such that $a=m⋅k+r$.

- unit in a quotient ring: $aˉ$ exists iff $g(a,m)=1$
- go in both direction, let $aˉ$ exists and then prove that gcd(a,m)=1
- let $g(a,m)=1$, then $aˉ$ exists.

- every element in the field created by quotient ring has a multiplicative inverse.
- take help of $g(a,m)$, if gcd=1, then unit exists
- if gcd=d, then d divides m, but m is irreducible and monic, then d = m, and d divides a, so m divides a. if m divides a then $aˉ=0$.

prove that there exists an irreducible polynomial $m∈F_{p}[X]$ of degree $d>1$.

### Exercises

- prove lagrange’s theorem, i.e. $G$ has subgroup of $d$ such that $d∣k$, if $∣G∣=k$ and $G$ is a finite group.
- 2.11-2.15: how do I prove if a group is commutative? and if a group is commutative, does $g_{1}∗g_{2}$ lie inside group? prove?
- 2.14: how to prove if a map is group homomorphism?
- prove map holds for $ϕ(a+b)=ϕ(a)+ϕ(b)$
- identity element is preserved

- 2.22: show a map is homomorphism of rings.
- shown by representing an element in quotient ring as a+my and then mapping to product of rings and checking ring operations (+,*).

- 2.25: if you know the square root solution, how to use it to factorise $n=pq$?
- 2.29: prove a ring with non-zero element is a field. use the map to map element from a → a.b. prove that map is 1-1. then for $a∈R:a.b=1$. thus inverse exists.
- 2.40: couldn’t find the starting point to compose the proofs. i + (1+…+1) = j + (1+…+1)

## Chapter 3: Integer factorisation and RSA

- diffie-hellman and el-gamal cryptosystem is based on hardness of DLP, i.e. $a_{x}≡bmodp$, where a, b and p are public values and x is the secret.
- in RSA cryptosystem, $x_{e}≡cmodN$, where e, c, and N are public values. In short, RSA is based on hardness of finding eth roots modulo N.
- theorem: let $p,q$ be distinct primes, and $g=g(p−1,q−1)$, then $a_{((p−1)(q−1))/g}≡1modpq$
- proof is using Fermat’s Little Theorem, as $a_{p−1}≡1modp⟹a_{p−1}≡1modpq$

let $p$ be a prime and let $e≥1$ be an integer satisfying $g(e,p−1)≡1$, then $de≡1modp−1$

$de−1=(p−1)c⟹de−(p−1)c=1⟹g(e,p−1)=1$ $g(e,p−1)=1⟹ed+(p−1)c=1(using extended euclidean)⟹ed=1modp−1$

- let $p$ be a prime, and $e≥1$ such that $g(e,p−1)=1$, then there exists $d$ such that $de=1modp−1$. Now, let $x_{e}≡cmodp$, then unique solution to congruence is $x≡c_{d}modp$
- prove existence and uniqueness of solution.

- let $p,q$ be distinct primes, and such that $g(e,(p−1)(q−1))=1$, then $ed=1mod(p−1)(q−1)$. Now, let $x_{e}≡cmodpq$, then unique solution to congruence is $x≡c_{d}modpq$.
- prove existence and uniqueness of solution.

### RSA encryption

- let Alice and Bob be two participants.
- Bob chooses two distinct primes $p,q$ and calculates $N=pq$.
- choose public encryption key $e$ such that $g(e,(p−1)(q−1))=1$, send $N,e$ to Alice.

- Alice chooses the message m and encrypt as $c=m_{e}modpq$. Send ciphertext $c$ to Bob.
- Bob knowing p and q, finds $d$ such that $de≡1mod(p−1)(q−1)$, decrypts ciphertext as $c_{d}modpq$
- security of RSA doesn’t depend on adversary Eve knowing private key $d$, but, it depends on hardness of finding solution to $de≡1mod(p−1)(q−1)$. Thus, even if Eve knows $p+q$, it’s easier to find solution.
- Also, bob has two choices, either make encryption key larger and decryption key smaller, or vice versa. making decryption key smaller is usually insecure.
**Man in the middle attack**: these are attacks that are not directly related to cryptosystem’s problem hardness but on other factors like communication between parties involved.- For example: in RSA, attacker Eve can intercept Alice’s ciphetext $c=m_{e}modpq$ and send $c_{′}=c.k_{e}modpq$ to Bob.
- Bob, then decrypts $m_{′}=c_{′d}=(c.k_{e})_{d}=m.kmodpq$ and send $m_{′}$ to Eve which she can decrypt easily knowing $k$.
- similarly, using
**multiple encrpytion keys**is also**not secure**, as Eve can find $e_{1}⋅u+e_{2}⋅v=g(e_{1},e_{2})$, $e_{1},e_{2}$ being two encryption keys, and $c_{1},c_{2}$ being ciphertexts sent by Alice to Bob. Eve can compute, $c_{1}⋅c_{2}=c_{e_{1}u}⋅c_{e_{2}⋅v}=c_{e_{1}u+e_{2}v}=c_{gcd(e_{1},e_{2})}$. if, $g(e_{1},e_{2})=1$, then Eve has ciphertext.

### Primality testing

- Fermat’s little theorem can be used to prove
**compositeness**of a number, but can’t prove primality of it. i.e. if $a_{n}≡a$ - Carmichael numbers: that are composite but exhibit FLT.
**Miller-Rabin test**: checks whether a number is composite or not, and gives*Miller-Rabin witness*for a number $n$- get a test subject : $n$, a witness suspect $a$:
- check whether $n$ is even, or $1<g(a,n)<n$, return Composite
- factorise $n−1=2_{k}q$, with $q$ as odd number.
- write $a=a_{q}modn$
- if $a≡1modn$, then return failure (i.e. not sure if prime)
- loop: $i={0,…,k−1}$:
- if $a≡−1modn$, return failure
- set $a=a_{2}modn$

- return composite

- Proof of Miller-Rabin test: for an odd prime: if $p−1=2_{k}q$, then either $a_{q}=1$, or $a_{q},a_{2q},…,a_{2_{k−1}q}≡−1modp$ must hold.

### Distribution of primes

**distribution of primes**: very interesting mathematical results that check how prime numbers are distributed across ranges.**prime number theorem**: $lim_{X→∞}X/ln(X)π(X) =1$, where $π(X)$ represents number of primes between ${2,…,X}$.- TODO: read proof of prime number theorem
- using prime number theorem, one can estimate the probability of finding a prime number in a range, and can use miller-rabin test to be confident that the chosen number is prime.
- riemann hypothesis: is used to explain distribution of prime numbers
- riemann zeta function: $ζ(s)=∑_{n=1}n_{s}1 $, is also equal to the product: $∏_{p prime}(1−p_{s}1 )_{−1}$, and thus, incorporates information about set of prime numbers.
- using generalised riemann hypothesis, every composite number $n$ has a miller-rabin witness $a$ for its compositeness satisfying $a≤2(lnn)_{2}$. but even Riemann hypothesis hasn’t been proven let alone it’s generalised version.
- Ask primality test: proposed an unconditional polynomial time algorithm for checking primality based on the relation $(x−a)_{n}≡x_{n}−amodn$

### Pollard’s $p−1$ factorisation

- main logic to break RSA lies in the factorisation of either $pq$ or $(p−1)(q−1)$. pollard’s $p−1$ factorisation gives factors of $pq$ using $p−1$.
- it’s concept lies in the fact that if we find a number $L$ such that $p−1∣L$ and $q−1∤L$ implies for a number $a$, $a_{L}−1≡0modp$ and $a_{L}−1≡0modq$.
- then $g(a_{L}−1,N)=p$, hence we can find $p$, if we have a number $L$.
**Pollard’s observation**: $n!$ is the number that $p−1$ divides, if p is product of small primes.

how small should the primes be?

**pollard’s $p−1$ factorisation algorithm**: Integer $N$ to be factored- set $a=2$ (can be any a)
- loop: $i={2,3,…}$
- set $a=a_{j}modN$
- find $d=g(a−1,N)$
- if $1<d<N$, then success, return $d$
- else loop for next $i$

- thus, to save such attacks in RSA, user has to choose $p,q$ such that neither is product of small primes.
**$B−$smooth number**refers to a number $n$ such that all prime factors of $n$ are less than or equal to $B$.- conversely, a number $n$ is $B−$smooth number if all its prime factors are less than or equal to $B$.

### factorisation via squares

- to factorise N, find $a,b$ such that $a_{2}≡b_{2}modN⟹a_{2}≡b_{2}+kN⟹kN=(a−b)(a+b)$, then it’s highly probable that N factors into $(a−b)$ or $(a+b)$, so you can find factors of N from $g(N,a+b)$ or $g(N,a−b)$.

a square number is always 0 (if even) or 1 (if odd) modulo 4. Why?

- a method to find correct $a_{2},b_{2}$:
- find $a_{i}s$ such that relation $c_{i}≡a_{i}modN$ factors into small primes (2,3,5,7,11)
- take $c_{i}s$ such that product $c_{i_{1}},c_{i_{2}},…,c_{i_{s}}$ form a square (i.e. power of every prime in product is even) $c_{i_{1}}c_{i_{2}}…c_{i_{s}}=b_{2}modN$
- compute $d=g(N,a−b)$, then $d$ can be nontrivial factor of $N$.