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:

Interesting Identity

Sage Example

Further Resources

• Links to

• Other interesting

• Resources

Introduction

Thinking not over the integers as a whole but modulo some integerinstead 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.

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.

About this project

CryptoBook is a community project, developed by members of 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 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

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

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

Number Theory

Mainly thinking things like

• Prime decomposition and distribution

• Primality testing

• Euler's theorem

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

Elliptic Curves

• Weierstrass

• Montgomery

• Edwards

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

Security background

• Basic Concepts

  • Confidentiality, Integrity etc

  • Encryption, Key generation

Asymmetric Cryptography

RSA

• Textbook protocol

• Padding

  • Bleichenbacher's 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

Isogeny Based Cryptography

• Isogenies

• Isogeny graphs

• Torsion poins

Cryptographic Protocols

Zero-knowledge proofs

• Schnorr proof of knowledge for dlog

• Core definitions

• Proof of equality of dlog

Formal Verification of Security Protocols

• Definition of Formal Verification

• Uses of Formal Verification

• Handshake protocols, flawed protocols

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)

Wilson's Theorem

A positive integer is a prime if and only if:

Working together

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

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

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

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.

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

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.

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

Example: - multiples of

Remarks:

1. we have

2. is an ideal

Example: Consider . This ideal contains

Greatest common divisor

Let be 2 integers. If

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

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.

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 $\mathcal{M}, \mathcal{K}$ and $\mathcal{C}$.

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

The study of sets, and different types of operations on them is the target of abstract algebra. In this chapter we will learn the underlying building blocks of cryptosystems and some of the hard problems that the cryptosystems are based on.

Definition

A setpaired with a binary operation is a group if the following requirements hold:

• Closure: For all - Applying the operation keeps the element in the set

• Associativity: For all

• Identity: There exists an elementsuch that

For , means when and when . For , .

If , then is commutative and the group is called abelian. We often denote the group operation by instead of and we typically use instead of .

Remark

• The identity element of a group is also denoted with or just if only one groups is present

Examples of groups

Integers modulo (remainders) under modular addition . Let's look if the group axioms are satisfied

1. . Because of the modulo reduction

2. Modular addition is associative

3. is the identity element

Therefore we can conclude that the integers mod with the modular addition form a group.

Example of non-groups

is not a group because we can find the element that doesn't have an inverse for the identity . is not a group because we can find elements that don't have an inverse for the identity

Exercise

Is a group? If yes why? If not, are there values for that make it a group?

sɹosᴉʌᴉp uoɯɯoɔ puɐ sǝɯᴉɹd ʇnoqɐ ʞuᴉɥ┴ :ʇuᴉH

Proprieties

1. The identity of a group is unique

2. The inverse of every element is unique

3. . The inverse of the inverse of the element is the element itself

Orders

In abstract algebra we have two notions of order: Group order and element order

Group order

The order of a group is the number of the elements in that group. Notation:

Element order

The order of an element is the smallest integer such that . If such a number doesn't exist we say the element has order . Notation:

Subgroups

Definition

Let be a group. We say is a subgroup of if is a subset of and forms a group. Notation:

Proprieties

1. The identity of is also in

2. The inverses of the elements in are found in

How to check ? Let's look at a 2 step test

1. Closed under operation:

2. Closed under inverses:

Generators

Let be a group,an element and . Consider the following set:

This set paired the group operation form a subgroup of generated by an element .

Example

For now, trust us that if given a prime , a value and we compute for a secret , finding is a hard problem. We will tell you why a bit later.

Examples

// subgroups, quotient groups

// cyclic groups

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.

// symmetric polynomials

// discriminants

// resultants

// Visual

// Symmetries

// Permutations

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.