Introduction

Thinking not over the integers as a whole but modulo some integer$n$instead can prove quite useful in a number of situation. This chapter attempts to introduce to you the basic concepts of working in such a context.

Congruences

For the following chapter, we will assumeis a natural integer, andandare two integers. We say thatandare congruent modulowhen, or equivalently when there is an integersuch that. We denote this byor . I will use the first notation throughout this chapter.

Remark: When, we have, whereis the remainder in the euclidean division ofby

This relation has a number of useful properties:

Seeing as addition and multiplication are well defined, the integers moduloform a ring, which we note. In sage, you can construct such ring with either of the following

Powering modulois relatively fast, thanks to the algorithm, so we needn't worry about it taking too much time when working with high powers

As a side note, remember that if an equality holds over the integers, then it holds modulo any natural integer. This can be used to prove that a relation is never true by finding a suitable modulus, or to derive conditions on the potential solutions of the equation.

Example: by choosing an appropriate modulus, show that not even god is able to find integersandsuch that

Modular Inverse

Since we can multiply, a question arises: can we divide? The answer is yes, under certain conditions. Dividing by an integeris the same as multiplying by its inverse; that is we want to find another integersuch that. Since, it is clear from that such an inverse exists if and only if. Therefore, the units moduloare the integers coprime to, lying in a set we call the unit group modulo:

Finding the modular inverse of a number is an easy task, thanks to the (that outputs solutions inandto the equationfrom above).

Example: Ideals of the integers

Definition - Ideal of $\mathbb{Z}$

$I \subseteq \mathbb{Z}$is an ideal $\iff \forall \ a, b \in I \text{ and} , z\ \in \mathbb{Z}$we have

$a + b \in I \text{ and } az \in I$

Example: $a\mathbb{Z} = \{az \ : \ z \in \mathbb{Z} \} \to 2\mathbb{Z}, 3\mathbb{Z}, 4\mathbb{Z}, \dots$ - multiples of

Remarks:

1. we have

2. is an ideal

Example: Consider . This ideal contains

Greatest common divisor

Let be 2 integers. If

Continued Fractions

Continued fractions are a way of representing a number as a sum of an integer and a fraction.

Mathematically, a continued fraction is a representation

$a_{i}, b_{i}$are complex numbers. The continued fraction with $b_{i} = 1\ \forall i$ is called a simple continued fraction and continued fractions with finite number of $a_{i}$ are called finite continued fractions.

Consider example rational numbers,

the continued fractions could be written as

Notation

A simple continued fraction is represented as a list of coefficients() i.e

for the above example

Computation of simple continued fractions

Given a number , the coefficients() in its continued fraction representation can be calculated recursively using

The above notation might not be obvious. Observing the structure of continued fraction with few coefficients will make them more evident:

SageMath provides functions continued_fraction and continued_fraction_list to work with continued fractions. Below is presented a simple implementation of continued_fractions.

Convergents of continued fraction

The convergent of a continued fractionis the numerical value or approximation calculated using the firstcoefficients of the continued fraction. The firstconvergents are

One of the immediate applications of the convergents is that they give rational approximations given the continued fraction of a number. This allows finding rational approximations to irrational numbers.

Convergents of continued fractions can be calculated in sage

Continued fractions have many other applications. One such applicable in cryptology is based on Legendre's theorem in diophantine approximations.

Theorem: if, thenis a convergent of.

Wiener's attack on the RSA cryptosystem works by proving that under certain conditions, an equation of the formcould be derived whereis entirely made up of public information andis made up of private information. Under assumed conditions, the inequalityis statisfied, and the value(private information) is calculated from convergents of(public information), consequently breaking the RSA cryptosystem.

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

• Polynomial GCD

  • Euclidean GCD

  • Half-GCD for speed when e=0x10001

  • demo application for that one RSA related message attack?

• Resultant

  • eliminate multivariate polynomials at the expense of increasing polynomial degree

  • demo application for that one RSA Coppersmith short padding related message attack?

• Groebner Basis

  • what if you did GCD and Resultants at the same time, like whoa

  • and what if it took forever to run!

// Visual

// Symmetries

// Permutations

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

• : denotes the set of complex numbers

• : denotes the set of real numbers

• : denotes the set of integers

• We refer to unit groups by or . Example:

• We refer to finite fields with elements by

• We refer to a general field by

Relation operators

• means is an element of (belongs to)

Logical Notation

• means for all

• means there exists. means uniquely exists

Operators

• means the probability of an event to happen. Sometimes denoted as or as

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

Number Theory

Mainly thinking things like

• Prime decomposition and distribution

• Primality testing

• Euler's theorem

• Factoring

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)

Generating Elliptic Curves

• Generating curves of prime order

• Generating supersingular curves

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

Security background

• Basic Concepts

  • Confidentiality, Integrity etc

  • Encryption, Key generation

• Attacker goals + Attack games

Asymmetric Cryptography

RSA

• Textbook protocol

• Padding

  • Bleichenbacher's Attack

  • OAEP

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

Isogeny Based Cryptography

• Isogenies

• Isogeny graphs

• Torsion poins

• SIDH

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

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)

Introduction

Since we can add, subtract, multiply, divide even... what would be missing? Powering! I'm not talking about some power fantasy here, but rather introduce some really really important theorems. Fermat little's theorem proves useful in a great deal of situation, and is along with Euler's theorem a piece of arithmetic you need to know. Arguably the most canonical example of using these is the RSA cryptosystem, whose decryption step is built around Euler's theorem.

Fermat's Little Theorem

Since we want to talk about powers, let's look at powers. And because I like 7, I made a table of all the powers of all the integers modulo 7.

On the last row, there is a clear pattern emerging, what's going on??? Hm, let's try again modulo 5 this time.

Huh, again?! Clearly, there is something going on... Sage confirms this!

Claim (Fermat's Little Theorem): Leta prime.

When, this is equivalent to what we observed:. There are several proofs of Fermat's Little Theorem, but perhaps the fastest is to see it as a consequence of the Euler's Theorem which generalizes it. Still, let's look a bit at some applications of this before moving on.

A first funny thing is the following:. When, this means we have found a non-trivial integer that when multiplied toyields 1. That is, we have found the inverse of, wow. Since the inverse is unique modulo, we can always invert non-zero integers by doing this. From a human point of view, this is really easier than using the extended euclidean algorithm.

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

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

• 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

Formatting

Mathematics notation

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

• All maths must be presented using 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

Algorithms

• Algorithms should be presented as??

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

Let be the set denoting the integers.

Definition - Divisibility

For we say that divides if there is some such that

Notation:

Example

For we have because we can find such that .

Properties

• and implies

  • Example: Let and

Definition - Division with remainder

Let with ,

There exists unique such that and

is called the quotient and the remainder

Examples:

• To find python offers us the divmod() function that takes as arguments

• If we want to find only the quotient we can use the // operator

• If we want to find the remainder we can use the modulo % operator

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

Let be 2 integers. The greatest common divisor is the largest integer such that and

Notation:

Examples:

Remark:

• for all other common divisors of we have

Things to think about

What can we say about numbers with ? How are their divisors?

Introduction

Give a description of the topic, and what you hope the reader will get from this. For example, this page will cover addition of the natural numbers. Talk about how this relates to something in cryptography, either through a protocol, or an attack. This can be a single sentence, or verbose.

Laws of Addition

For all integers, the addition operation is

• Associative:

• Commutative:

• Distributive:

• Contains an identity element:

Interesting Identity

Sage Example

Further Resources

• Links to

• Other interesting

• Resources

Thank you!

Our Writers

• ...

• You?

Join CryptoBook

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

Wilson's Theorem

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

Euler's Theorem

Let and s.t. , then:

Fermat's Little Theorem

Let be a prime and , then:

or equivalently:

Reference

Introduction

Although we have functions that can compute our $\gcd$easily it's important enough that we need to give and study an algorithm for it: the euclidean algorithm.

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

Euclidean Algorithm

Important Remark

If and then . Therefore

Algorithm

We write the following:

Or iteratively until we find a . Then we stop

Now here's the trick:

If then divides

Example:

Calculate

Code

Exercises:

1. Pick 2 numbers and calculate their by hand.

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

Extended Euclidean Algorithm

Bezout's identity

Let . Then there exists such that

The extended euclidean algorithm aims to find given

Overview

Given a composite integer $n$, can it be decomposed as a product of smaller integers (hopefully as a unique product of prime factors)?

As easy as it may sound, integer factorization in polynomial time on a classical computer stands one of the unsolved problems in computation for centuries!

Lets start dumb, all we need to do is check all the numbers $1 < p < n$ such that $p|n$or programmatically n%p==0

def factors(n):
    divisors = []
    for p in range(1,n):
        if n%p==0:
            divisors.append(p)
    return divisors

Seems like its an algorithm! whats all the deal about? By polynomial time, we mean polynomial time in when is a b-bit number, so what we looking at is actually a which is actually exponential (which everyone hates)

Now taking a better look at it, one would realize that a factor of can't be bigger than Other observation would be, if we already checked a number (say 2) to not be a divisor, we dont need to check any multiple of that number since it would not be a factor.

Discrete log problem

Given any group$G$and elements$a,b$such that $a^n=b$, the problem of solving for$n$is known as the disctete log problem (DLP). In sage, this can be done for general groups by calling discrete_log

Discrete log over

Typically, one considers the discrete log problem in , i.e. the multiplicative group of integers. Explicitly, the problem asks forgiven . This can be done by calling b.log(a) in sage:

This section is devoted to helping the reader understand which functions are called when for this specific instance of DLP.

Whenis composite and not a prime power, discrete_log() will be used, which uses generic algorithms to solve DLP (e.g. Pohlig-Hellman and baby-step giant-step).

When is a prime, Pari znlog will be used, which uses a linear sieve index calculus method, suitable for .

When , SageMath will fall back on the generic implementation discrete_log()which can be slow. However, Pari znlog can handle this as well, again using the linear sieve index calculus method. To call this within SageMath we can use either of the following (the first option being a tiny bit faster than the second)

Example

Given a small prime, we can compare the Pari method with the Sage defaults

We can also solve this problem with even larger primes in a very short time

Discrete log over

// elliptic curve discrete log functions

Authors: Ariana, Zademn Reviewed by:

Introduction

Modern cryptography is based on the assumption that some problems are hard (unfeasable to solve). Since the we do not have infinite computational power and storage we usually work with finite messages, keys and ciphertexts and we say they lay in some finite sets and .

Furthermore, to get a ciphertext we usually perform some operations with the message and the key.

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;

A setwith two binary operations is a ring if the following holds:

• is a commutative group with identity

• is a monoid (group without the inverse axiom) with identity.

A setwith two binary operations is a field if the following holds:

• is a commutative group with identity

• is a commutative group with identity.

Introduction

In this section, we hope to bring some intuitive understanding to the LLL algorithm and how it works. The LLL algorithm is a lattice reduction algorithm, meaning it takes in a basis for some lattice and hopefully returns another basis for the same lattice with shorter basis vectors. Before introducing LLL reduction, we'll introduce 2 key algorithms that LLL is built from, Gram-Schmidt orthogonalization and Gaussian Reduction. We give a brief overview on why these are used to build LLL.

As the volume of a lattice is fixed, and is given by the determinant of the basis vectors, whenever our basis vectors gets shorter, they must, in some intuitive sense, become more orthogonal to each other in order for the determinant to remain the same. Hence, Gram-Schmidt orthogonalization is used as an approximation to the shortest basis vector. However, the vectors that we get are in general not in the lattice, hence we only use this as a rough idea of what the shortest vectors would be like.

Lagrange's algorithm can be thought as the GCD algorithm for 2 numbers generalized to lattices. This iteratively reduces the length of each vector by subtracting some amount of one from another until we can't do it anymore. Such an algorithm actually gives the shortest possible vectors in 2 dimensions! Unfortunately, this algorithm may not terminate for higher dimensions, even in 3 dimensions. Hence, it needs to be modified a bit to allow the algorithm to halt.

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.