Introduction

It's extended version will help us calculate modular inverses which we will define a bit later.

Euclidean Algorithm

Important Remark

Algorithm

We write the following:

Now here's the trick:

Example:

Code

def my_gcd(a, b):
    # If a < b swap them
    if a < b: 
        a, b = b, a
    # If we encounter 0 return a
    if b == 0: 
        return a
    else:
        r = a % b
        return my_gcd(b, r)

print(my_gcd(24, 15))
# 3

Exercises:

2. Implement the algorithm in Python / Sage and play with it. Do not copy paste the code

Extended Euclidean Algorithm

Bezout's identity

# In sage we have the `xgcd` function
a = 24
b = 15
g, u, v = xgcd(a, b)
print(g, u, v)
# 3 2 -3 

print(u * a + v * b)
# 3 -> because 24 * 2 - 15 * 3 = 48 - 45 = 3

Wilson's Theorem

A positive integer $n > 1$is a prime if and only if:

Euler's Theorem

Let $n \in \mathbb{Z}^{+}$ and $a \in \mathbb{Z}$ s.t. $gcd(a, n) = 1$, then:

Fermat's Little Theorem

Let $p$be a prime and $a \in \mathbb{Z}$, then:

or equivalently:

Reference

1. Wilson's Theorem - Brilliant

2. Euler's Theorem - Brilliant

3. Fermat's Little Theorem - Brilliant

// symmetric polynomials

// discriminants

// resultants

Lattices, also known as Minkowski's theory after Hermann Minkowski, or the geometry of numbers (deprecated!) allows the usage of geometrical tools (i.e. volumes) in number theory.

The intuitive notion of a lattice (perhaps surprisingly) matches its mathematical definition. For example, lattices are formed by

• points on an infinite checkerboard;

• centers of a hexagonal tessellation;

• integers on the real number line.

Definitions

A lattice $L$ is a subgroup of $\mathbb{R}^n$generated by $b_i$, i.e.

where $b_i$ are linearly independent vectors. Collectively, $\left\{b_i\right\}_{i=1}^d$ form a basis of$L$.

Taking a step back, this definition should resemble that of a vector space, with one exception: scalars are integers! The discrete nature of lattices comes from this restriction.

Some more terminology from linear algebra will be useful. The dimension of a lattice, denoted$\dim L$, is $d$. A lattice is complete if $d=n$. Note that we can always choose a subspace of $\mathbb R^n$such that the lattice is complete, namely the subspace generated by $b_i$.

The region

is known as the fundamental mesh.

In the image above, we see the points of a lattice in $\mathbb R^2$. The red vectors are one set of basis vectors and the shaded region is the corresponding fundamental mesh. The green vectors also form another set of basis vectors with its corresponding fundamental mesh. We see here that the basis vectors and fundamental mesh is not unique to a lattice.

Although the fundamental mesh is not unique, it turns out that the ($m$dimensional) volume of the fundamental mesh is constant for any given lattice. Hence we can define the volume of a lattice as the volume of a fundamental mesh. However this definition can be hard to handle hence we provide an equivalent definition via determinants:

Let$\mathcal B$be a$d\times n$matrix whose rows are given by the basis vectors. Then the volume of a fundamental mesh is given by

A subset $X$of $\mathbb R^n$is known as centrally symmetric if $x\in X$implies $-x\in X$. It is convex if for any $x,y\in X$, the line joining $x,y$ is contained in $X$, i.e. $\left\{tx+(1-t)y|0\leq t\leq1\right\}\subset X$. Finally we can introduce the most important theorem about lattices, the Minkowski's Lattice Point Theorem:

Let $L$be a complete lattice of dimension$n$ and $X$be a centrally symmetric convex set. Suppose

Then $X$contains at least one nonzero point of $L$. This result is primarily used to prove the existence of lattice vectors.

Throughout this section, $\left\lVert v\right\rVert=\sqrt{\sum_iv_i^2}$ denotes the $\ell_2$norm and $\langle a,b\rangle=\sum_ia_ib_i$ denotes the inner product.

Proof sketch of Minkowski's theorem

This proof is by some sort of a pigeonhole argument on volumes. Consider the set

We have $\text{vol}\left(\frac12 X\right)>\text{vol}(L)$, hence the inclusion $\frac12X\to\mathbb R^n/L$cannot be injective, thus we can find some $x_1=x_2+\ell$, $x_1,x_2\in\frac12 X,\ell\in L,x_1\neq x_2$. Hence $x_1-x_2\in L$is a nontrivial lattice point.

Exercises

1) Let $L$be the lattice generated by $\mathcal B=\begin{pmatrix}-1&9&8\\1&-8&-7\end{pmatrix}$(take the rows as basis vectors).

• Compute the volume of this lattice

• Show that $\mathcal B'=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}$generates the same lattice

• Show that each row in $\mathcal C=\begin{pmatrix}1&0&1\\0&2&2\end{pmatrix}$is in the lattice but$\mathcal C$does not generate the lattice. This is one key difference from the case of linear algebra (over fields).

2) Let$\mathcal B,\mathcal B'$be $d\times n$matrices whose row vectors are basis for lattices $L,L'$. Both lattices are the same iff there exists some $U\in\text{GL}_d(\mathbb Z)$ such that $\mathcal B'=U\mathcal B$. Find $U$for problem 1. Note that $\text{GL}_d(\mathbb Z)$is the group of invertible matrices with integer coefficients, meaning $U$and $U^{-1}$have integer coefficients.

3) Show that the condition in Minkowski's lattice point theorem is strict, i.e. for any complete lattice$L$of dimension $n$, we can find some centrally symmetric convex set$X$with$\text{vol}(X)=2^n\text{vol}(L)$but the only lattice point in$X$is the origin.

4*) Let$v$be the shortest nonzero vector for some lattice $L$with dimension$n$. Show that

Overview

Having introduced the LLL reduction, we now provide a more general notions of a reduced basis for a lattice as well as provide bounds for the basis vectors. The key idea behind introducing these definitions is that once we know some basis vector is []-reduced, we can bound the sizes of the basis, which is important when algorithms require short vectors in a lattice. For fast algorithms, LLL-reduction is typically the most important notion as it can be computed quickly. Two main definitions appear often when discussing lattice reductions, which we will provide here.

Definitions

A basis$\left\{b_i\right\}_{i=1}^d$is size-reduced if $\left|\mu_{i,j}\right|\leq\frac12$. Intuitively this captures the idea that a reduced basis being "almost orthogonal".

Let $L$be a lattice, $1\leq i\leq\dim L=d$, we define the $i^\text{th}$successive minima$\lambda_i(L)$ as

Intuitively, $\lambda_i(L)$is the length of the "$i^\text{th}$ shortest lattice vector". This intuition is illustrated by the definition of $\lambda_1$:

However this is not precise as if $v$is the shortest lattice vector, then $-v$is also the shortest lattice vector.

Unfortunately, a basis$b_i$for $L$where $\lambda_i(L)=\left\lVert b_i\right\rVert$for dimensions $5$ and above. This tells us that we can't actually define "the most reduced basis" in contrast to the 2D case (see Lagrange's algorithm) and we would need some other definition to convey this intuition.

An alternate definition of$\lambda_i(L)$that will be helpful is the radius of the smallest ball centered at the origin such that the ball contains at least$i$linearly independent vectors in$L$.

Exercises

1) Show that both definitions of $\lambda_i$ are equivalent

2) Consider the lattice $L=\begin{pmatrix}2&0&0&0&0\\0&2&0&0&0\\0&0&2&0&0\\0&0&0&2&0\\1&1&1&1&1\end{pmatrix}$. Show that the successive minima are all$2$but no basis$b_i$can satisfy $\left\lVert b_i\right\rVert=\lambda_i$.

We shall now provide a few instances where lattices are used in various algorithms. Most of these uses the LLL algorithm as it is quite fast.

Introduction

In this chapter we will study some specific types of lattices that appear in cryptography. These will help us understand how certain problems we base our algorithms on reduce to other hard problems. They will also give insight about the geometry of lattices.

Intuitively, if we have a problem (1) in some lattice space we can reduce it to a hard problem (2) in another related lattice space. Then if we can prove that if solving problem (1) implies solving problem (2) then we can conclude that problem (1) is as hard as problem (2)

Understanding this chapter will strengthen the intuition for the fututre when we will study what breaking a lattice problem means and how to link it to another hard lattice problem.

Dual lattice

Let $L \subset \mathbb R^n$be a lattice. We define the dual of a lattice as the set of all vectors $y \in span(L)$ such that $y \cdot x \in \mathbb Z \$for all vectors $x \in L$:

Examples:

1. $(\mathbb Z^n) ^ \vee = \mathbb Z^n$ because the dot product of all vectors in $\mathbb Z^n$stays in $\mathbb Z^n$

2. Scaling: $(k \cdot L)^\vee = \dfrac 1 k \cdot L$ Proof: If $y \in (kL)^\vee \Rightarrow y \cdot kx = k(x \cdot y) \in \mathbb{Z} \ \forall \ x \in L \Rightarrow y \in \dfrac 1 k L^\vee$ If $y \in \left (\dfrac 1 kL\right )^\vee \Rightarrow yv \in L^\vee \Rightarrow ky\cdot x = k(x \cdot y) = y \cdot kx \in \mathbb{Z} \ \forall \ x \ \in L \Rightarrow y \in (kL)^\vee$

Plot: $2\mathbb Z ^2$ - green, $\dfrac 1 2 \mathbb Z ^ 2$ - red

Intuition: We can think of the dual lattice $L^\vee$ as some kind of inverse of the initial lattice $L$

Basis of the dual lattice

We will now focus on the problem of finding the basis $B^\vee$ of the dual lattice $L^\vee$given the lattice $L$ and its basis $B$.

We have the following equivalences:

Therefore $L^\vee = (B^{-1})^T \cdot \mathbb Z^n$so we have found a base for our dual lattice:

n = 5 # lattice dimension

B = sage.crypto.gen_lattice(m=n, q=11, seed=42)
B_dual = sage.crypto.gen_lattice(m=n,  q=11, seed=42, dual=True)

B_dual_ = (B.inverse().T * 11).change_ring(ZZ) # Scale up to integers
B_dual_.hermite_form() == B_dual.hermite_form() # Reduce form to compare
# True

• https://en.wikipedia.org/wiki/Hermite_normal_form

Let's look at some plots. With green I will denote the original lattice and with red the dual. The scripts for the plots can be found in in the interactive fun section

Properties

1. ${L}_1 \subseteq {L}_2 \iff {L}^\vee_2 \subseteq {L}^\vee_1$

2. $({L}^\vee)^\vee ={L} =$The dual of the dual is the initial lattice (to prove think of the basis of $L^\vee$)

3. $\det(L^\vee) = \det(L) ^{-1}$ (to prove think of the basis of $L^\vee$)

4. For $x \in {L}, y \in {L}^\vee$consider the vector dot product and addition - $x \cdot y \in \mathbb{Z}$ - $x + y$ has no geometric meaning, they are in different spaces

Successive minima

We've seen that we can find the basis of the dual lattice given the basis of the original lattice. Let's look at another interesting quantity: the successive minima of a lattice $L$ and its dual $L^\vee$. Let's see what can we uncover about them.

Claim 1:

Proof: By Minkowski's bound we know:

$\lambda_1(L) \leq \sqrt{n} \cdot \det(L)^{1 / n}$ and $\lambda_1(L^\vee) \leq \sqrt{n} \cdot det(L^\vee)^{1 / n} = \dfrac {\sqrt{n}} {\det(L)^{1/n}}$. By multiplying them we get the desired result.

From this result we can deduce that the minima of the $L$ and $L^\vee$have an inverse proportional relationship (If one is big, the other is small).

n = 5 # lattice dimension

B = sage.crypto.gen_lattice(m=n, q=11, seed=42)
B_dual = sage.crypto.gen_lattice(m = n,  q=11, seed=42, dual=True)

l1 = IntegerLattice(B).shortest_vector().norm().n() 
l2 = IntegerLattice(B_dual).shortest_vector().norm().n() / 11

print(l1 * l2 < n)
# True

Claim 2:

Proof:

Let $x∈L$ be such that $\|x\|=λ_1(L)$. Then take any set $(y_1, . . . , y_n)$ of $n$ linearly independent vectors in $L^\vee$. Not all of them are orthogonal to $x$. Hence, there exists an $i$ such that $y_i \cdot x \neq 0$ . By the definition of the dual lattice, we have $y_i \cdot x \in \mathbb Z$ and hence $1 \leq y_i \cdot x \leq \|y_i\| \cdot \|x\| \leq \lambda_1 \cdot \lambda_n^\vee$

n = 5 # lattice dimension

B = sage.crypto.gen_lattice(m=n, q=11, seed=42)
B_dual = sage.crypto.gen_lattice(m = n,  q=11, seed=42, dual=True)

l1 = IntegerLattice(B).shortest_vector().norm().n() 

B_dual_lll = B_dual.LLL()
lnd = 0
for v in B_dual_lll:
    lv = v.norm()
    if lv > lnd:
        lnd = lv
lnd = lnd.n() / 11

print(lnd * l1 > 1) 
# True

Geometry + Partitioning

// TODO

Q-ary lattices

We've seen that in cryptography we don't like to work with infinite sets (like $\mathbb Z$) and we limit them to some finite set using the $\bmod$ operation ($\mathbb Z \to \mathbb Z/ q\mathbb{Z}$). We will apply the same principle to the lattices so let us define the concept of a q-ary lattice.

Definition:

For a number $q \in \mathbb{Z},\ q \geq 3$we call a lattice q-ary if

Intuition:

• $q\mathbb{Z^n} \subseteq \mathcal{L}$ is periodic $\bmod \ q$

• We use arithmetic $\bmod \ q$

We will now look at 2 more types of lattices that are q-ary. Let $A \in (\mathbb{Z}/q\mathbb Z)^{n \times m}$ be a matrix with $m > n$. Consider the following lattices: $L_q(A) = \{y \in \mathbb Z^m : y = A^Tx \bmod q \in \text{ for some } x \in \mathbb{Z}^n \} \subset \mathbb{Z^m}$ $L^\perp_q(A) = \{y \in \mathbb Z^m : Ay = 0 \bmod q \} \subset \mathbb{Z^m}$

Intuition:

• Think of $L_q(A)$ as the image of the matrix $A$, the matrix spanned by the rows of $A$

• Think of $L_q^\perp(A)$ as the kernel of $A$ modulo $q$. The set of solutions $Ax = 0$

Claim:

$L_q(A)$ and $L_q^\perp(A)$ are the dual of each other (up to scaling): $L_q(A) = \dfrac 1 q L_q^\perp(A)$

Proof:

Firstly we will show $L_q^\perp(A) \subseteq q(L_q(A))^\vee$

• Let $y \in L_q^\perp(A) \Rightarrow Ay \equiv 0 \bmod q \iff Ay = qz$for some $z \in \mathbb{Z}^m$

• Let $y' \in L_q(A)\Rightarrow y' \equiv A^Tx \bmod q \iff y' = A^Tx + qz'$ for some $x \in \mathbb Z^n, \ z' \in \mathbb Z^m$

Then we have:$y \cdot y' = y \cdot (A^Tx + qz') = y\cdot A^Tx + q (y \cdot z') = \underbrace{Ay}_{qz} \cdot x + q(y \cdot z') = qz \cdot x + q(y \cdot z')$

$\Rightarrow \dfrac 1 q y \cdot y' \in \mathbb{Z} \Rightarrow \dfrac 1 q y\in L_q(A)^\vee$

The second part is left as an exercise to the reader :D. Show $L_q^\perp(A) \supseteq q(L_q(A))^\vee$

Resources

• https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/DualLattice.pdf

• https://sp2.uni.lu/wp-content/uploads/sites/66/2019/06/DualLattice-Luca-Notarnicola.pdf

• https://simons.berkeley.edu/sites/default/files/docs/14953/intro.pdf

• https://cseweb.ucsd.edu/~daniele/papers/FOSAD11.pdf

The Coppersmith algorithm can be made even more general. There are two main extensions, first to an unknown modulus, then to multivariate polynomials.

Unknown modulus

This extension of Coppersmith allows one to find small roots modulo an unknown some unknown factor of a number. More specifically, suppose that we have some unknown factor$b$of$N$such that $b<N^\beta$and some monic polynomial$f$of degree$d$such that $f(x_0)=0\pmod b$for some $x_0<N^{\frac{\beta^2}d}$. Then we can find$x_0$in time polynomial in $\log N,d$.

One key reason why this is possible is because we dont need to explicitly know the modulus to determine if a small root exists, i.e. $\left\lVert f(Bx)\right\rVert_2\leq\frac b{\sqrt{d+1}}\leq\frac{N^{\beta}}{\sqrt{d+1}}$is sufficient for a root less than$B$to exist. The algorithm here is extremely similar to the Coppersmith algorithm, except we add more polynomials into the lattice. The polynomials that we will use are

The lattice$L$generated by these polynomials would have

As we require the shortest vector to have length at most $\frac{N^{\beta h}}{\sqrt{n}}$, repeating the computations from the previous section, we obtain

It turns out that the maxima of $\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}$is $\frac{\beta^2}d$as $n,h\to\infty$. One way to achieve this is by setting$n=\frac d\beta h$and we obtain

and this indeed achieves the $O\left(N^{\frac{\beta^2}d}\right)$bound. Similar to the Coppersmith algorithm, one chooses a sufficiently big $h,n$such that the remainding bits can be brute forced in constant time while the algorithm still remains in polynomial time.

Exercises

1) We show that the maximum of$\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}$is indeed $\frac{\beta^2}d$. We can assume that $d\geq2,h\geq1,0<\beta\leq1,n\geq2$. Since $\frac h{n-1}\left(2\beta-d\frac{h+1}{n}\right)$and $\frac h{n-1}<\frac{h+1}n$, the maximum occurs when $h,n\to\infty$and $\frac h{n-1},\frac{h+1}n\to x$, hence we have reduced this to maximizing $2\beta x-dx^2$which achieves its maximum of $\frac{\beta^2}d$ at $x=\frac\beta d$.

Motivation

Humans are fascinated with symmetries. The guiding star of theoretical physics is the study of dualities. How much one thing can be said to be another leads to strange and beautiful links between areas of mathematics that appear to be totally distinct.

A cruical piece of building this understanding is how one can map between objects which share structure. When we learn about topology, we are given the fun: "A doughnut is the same as a mug"; a statement which says within topology, we identify objects related by continuous functions.

Elliptic curves are beautiful mathematical objects. The fact that a geometric comes hand-in-hand with a algebraic group law is, to me, incredible. The study of isogenies is the study of maps (morphisms) between elliptic curves which preserves the origin. This condition is enough to preserve the group scheme of the elliptic curve.

In short, isogenies allow us to map between curves preserving their geometric properties (as projective varieties) and algebraic properties (the group associated with point addition).

Isogenies of Elliptic Curves

Definition: We say an isogeny $\phi : E_1 \to E_2$ between elliptic curves defined over a field $k$is a surjective morphism of curves which includes a group homomorphism $E_1(\bar{k}) \to E_1(\bar{k})$

References

• https://arxiv.org/pdf/1711.04062.pdf

• https://math.mit.edu/classes/18.783/2019/LectureNotes5.pdf

• https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/ell_curve_isogeny.html

• Isogeny graph (general definition, degree, duals...).

• Starting vertex (Bröker's algorithm).

• Isogeny Volcanos: Sutherland might be a good source https://arxiv.org/abs/1208.5370.

• Supersingular isogeny graphs

  • Size, everything is defined over GF(p^2). (*as long as the degree divides (p+1)^2 or (p-1)^2).

  • Random walks are probably the best motivation to define Ramanujanness, and are directly applicable to cryptography. A (perhaps too large) source is Hoory-Linial-Wigderson.

  • Consequence from Ramanujan + random walk convergence: O(log p) diameter.

Making this section as a motivation to make sure this is part of the book. Something to work towards.

Page Plan

• Describe that there is a drive towards post-quantum algorithms

• The incredible fact that paths within isogeny graphs commute (with the help of torsion points)

• Supersingular $\ell$ isogeny graphs are $(\ell + 1)$regular Ramanujan graphs

• Using paths through these graphs has spawned a whole bunch of protocols

  • SIKE / BIKE / ...

  • Hashes

  • ...

• First we will look at the fundementals that allow these protocols to be expected as good candidates for post-quantum

• Then we look at these protocols in more detail. Hopefully with SageMath implementations for each

References I plan to use

• Introduction by Craig Costello

  • https://eprint.iacr.org/2019/1321.pdf

• Mathematics of Isogeny Based Cryptography by Luca De Feo

  • https://arxiv.org/pdf/1711.04062.pdf-

• The Arithmetic of Elliptic Curves by Joseph H. Silverman

  • https://www.springer.com/gp/book/9780387094939

Working together

• If something doesn't make sense, make a comment using GitBook, or ask in the Discord.

• If you are confident that something is wrong, just fix it. There's no need to ask.

• If you think something doesn't have enough detail, expand on it, or leave a comment suggesting that.

• If a page is getting too long, break it down into new pages. If you're unsure, then leave a comment or talk in the discord

• If you want to write about something new and learn as you type, this is fine! But please leave a warning at the top that this is new to you and needs another pair of eyes.

• If there's big subject you're working on, claim the page and save it, show us that that's what you're doing so we don't overlap too much

General Tips

• Introduce new objects slowly, if many things need to be assumed, then try to plan for them to appear within the Book Plan somewhere.

• It is better to cover less, and explain something well, than it is to quickly cover a lot. We're not racing

• When explaining anything, imagine you are introducing it for a first time. Summaries exist elsewhere online, the goal of CryptoBook is education

• Contribute as much or as little as you want, but try to only work on topics that

  • You are interested in

  • You have some experience of thinking about

• External resources should be included at the end of the page. Ideally the book should be self-contained (within reason) but other resources are great as they offer other ways to learn

• Try and use the hints / tips blocks to break up dense text, for example:

Page Structure

• A page should have a clear educational goal: this should be explained in the introduction. References to prerequisites should be kept within the book and if the book doesnt have this yet, it should be placed into Book Plan.

• The topic should be presented initially with theory, showing the mathematics and structures we will need. A discussion should be pointed towards how this appears within Cryptography

• Within a discussion of a topic, a small snippet of code to give an example is encouraged

• If you write code better than you write maths, then just include what you can and the page will form around that

• An example page is given in Sample Page

Formatting

Mathematics notation

There's no "right or wrong" but it's good to be consistent, I think?

• All maths must be presented using $\LaTeX$using either both block and inline

• We seem to be using mathbb for our fields / rings. So let's stick with that? Maybe someone has a good resource for notation we can work from?

Code Blocks

• Make sure all code blocks have the right language selected for syntax highlighting

• Preference is to SageMath, then to Python, then others.

• Code should be cope-pastable. So if you include print statement, include the result of the output as a comment

# Example
a = 3
b = 6
print(a+b)
# 9

Algorithms

• Algorithms should be presented as??

// todo

Introduction

Throughout CryptoBook, discussions are made more concise by using various mathematical symbols. For some of you, all of these will feel familiar, while for others, it will feel new and confusing. This chapter is devoted to helping new readers gain insight into the notation used.

Mathematical Objects

Special Sets

Relation operators

Logical Notation

Operators

Philosophy

The aim of CryptoBook is to have a consolidated space for all of the mathematics required to properly learn and enjoy cryptography. The focus of any topic should be to introduce a reader to a subject in a way that is fun, engaging and with an attempt to frame it as an applied resource.

The second focus should be to cleanly implement the various topics using SageMath, so that there is a clear resource for a new reader to gain insight on how SageMath might be used to create the objects needed.

Proposed topics

This list is not complete so please add to it as you see fit.

Mathematical Background

Fundamentals

• Congruences

• GCD, LCM

  • Bézout's Theorem

  • Gauss' Lemma and its ten thousand corollaries

• Euclid's algorithm

• Modular Arithmetic

• Morphisms et al.

• Frobenius endomorphism

Number Theory

Mainly thinking things like

• Prime decomposition and distribution

• Primality testing

• Euler's theorem

• Factoring

• Legendre / Jacobi symbol

Abstract Algebra

Mainly thinking things like:

• Groups, Rings, Fields, etc.

• Abelian groups and their relationship to key-exchange

• Lagrange's theorem and small subgroup attacks

Basilar Cryptanalysis forms

• Introduction to Cryptanalysis

• A linear Approach to Cryptanalysis

• Matsui's Best biases algorithm

• A Differential Approach to Cryptanalysis

Elliptic Curves

• Weierstrass

• Montgomery

• Edwards

• Counting points (Schoof's algorithm)

• Complex multiplication

  • Good reference, thanks Joachim

Generating Elliptic Curves

• Generating Anomalous curves

• Generating curves of prime order

• Generating supersingular curves Wikipedia

• Generating non-supersinular curves of low embedding degree

• Generating curves of arbitary order (hard)

  • Thesis on the topic

  • Sage implementation ChiCube's script

Hyperelliptic curves

• Generalization of elliptic curves

• Recovering a group structure using the Jacobian

• Example: genus one curves, jacobian is isomorphic to the set of points

• Mumford representation of divisors

• Computing the order of the Jacobian

  • For characteristic 2^n: Example 56

  • Hyper Metroid example

Security background

• Basic Concepts

  • Confidentiality, Integrity etc

  • Encryption, Key generation

• Attacker goals + Attack games

• Defining Security - Perfect security, semantic security

• Proofs of security + Security Reductions

Asymmetric Cryptography

RSA

• Textbook protocol

• Padding

  • Bleichenbacher's Attack

  • OAEP

• Coppersmith

  • Håstad's Attack

  • Franklin-Reiter Attack

• Wiener's Attack

• RSA's Integer fattorization Attacks

• • Fermat Factoring Attack

  • Quadratic Sieve Attack

  • Number Fielde Sieve Attack

• RSA Digital Signature Scheme

• Timing Attacks on RSA

• RSA with Chinese Remainder Theorem (CRT)

  • Fault Attack on RSA-CRT

  • Bellcore Attack (Low Voltage Attack)

Paillier Cryptosystem

• Textbook protocol

ElGamal Encryption System

• Textbook protocol

• ElGamal Digital Signature Scheme

Diffie-Hellman

• Textbook protocol

• Strong primes, and why

Elliptic Curve Cryptography

• ECDSA

• EdDSA

Symmetric Cryptography

One Time Pad

• XOR and its properties

• XOR as One Time Pad

• Generalized One Time Pad

Block Ciphers

• AES

Stream Ciphers

• Affine

• RC4

Hashes

• Introduction

• Trapdoor Functions

• MD family

• SHA family

• BLAKE Hash family

• // TODO: Insert Attacks

Isogeny Based Cryptography

• Isogenies

• Isogeny graphs

• Torsion poins

• SIDH

• SIKE

• BIKE

Cryptographic Protocols

Zero-knowledge proofs

• Schnorr proof of knowledge for dlog

• Core definitions

• Proof of equality of dlog

• Proof of knowledge of a group homomorphism preimage

Formal Verification of Security Protocols

• Definition of Formal Verification

• Uses of Formal Verification

• Handshake protocols, flawed protocols

• The external threat: Man-In-The-Middle attacks

• Attacking the (flawed) Needham-Shroeder public key exchange protocol

Usefull Resources ( Books, articles ..) // based on my material

• Cryptanalytic Attacks on RSA (Yan, Springer, 2008)

• Algorithmic Cryptanalysis (Antoine Joux, CRC Press, 2009)

• Algebraic Cryptanalysis (Brad, Springer, 2009)

• RC4 stream Cipher and its variants (H. Rosen, CRC Press, 2013)

• Formal Models and Techniques for Analyzing Security Protocols (Cortier, IOS Press, 2011)

• Algebraic Shift Register Sequences (Goresky && Klapper, Cambridge Press, 2012)

• The Modelling and Analysis of Security Protocols (Schneider, Pearson, 2000)

• Secure Transaction Protocol Analysis (Zhang && Chen, Springer, 2008)

Thank you!

Our Writers

• ...

• You?

Join CryptoBook

If you would like to join the team, come over to our Discord Channel and talk with us about your ideas

About this project

CryptoBook is a community project, developed by members of CryptoHack to create a resource for people to learn cryptography. The focus of this project is to create a friendly resource for the mathematical fundamentals of cryptography, along with corresponding SageMath implementation.

Think of this as an alternative SageMath documentation source, where the focus is its application in solving cryptographic problems.

If you're interested in contributing, come chat to us in our Discord Channel

Example: Ideals of the integers

Remarks:

Greatest common divisor

Introduction

Two of the skills a cryptographer must master are:

1. Knowing his way and being comfortable to work with numbers.

2. Understanding and manipulating abstract objects.

This chapter of fundamentals proposes to prepare you for understanding the basics of number theory and abstract algebra .We will start with the most basic concepts such as division and build up knowledge until you, future cryptographer, are able to follow and understand the proofs and intricacies of the cryptosystems that make our everyday life secure.

We will provide examples and snippets of code and be sure to play with them. If math is not your strongest suit, we highly suggest to pause and ponder for each concept and take it slow.

For the math-savy people we cover advanced topics in specific chapters on the subjects of number theory and group theory.

So what are we waiting for? Let's jump right in!

Division

Definition - Divisibility

Example

Properties

Definition - Division with remainder

Examples:

Exercises:

1. Now it's your turn! Play with the proprieties of the division in Python and see if they hold.

Greatest common divisor

Definition

Examples:

Remark:

Things to think about