Definition

Let $\pi_i$as the projection to the orthogonal complement of $\left\{b_j\right\}_{j=1}^{i-1}$.Then the basis is HKZ-reduced if it is size-reduced and $||b_i^*||=\lambda_1\left(\pi_i(L)\right)$. This definition gives us a relatively simple way to compute a HKZ-reduced basis by iteratively finding the shortest vector in orthogonal projections.

Bounds

Wiener's attack is an attack on RSA that uses continued fractions to find the private exponent $d$ when it's small (less than $\frac{1}{3}\sqrt[4]{n}$, where $n$ is the modulus). We know that when we pick the public exponent $e$ to be a small number and calcute its inverse $d \equiv e^{-1} \mod \phi(n)$

Wiener's theorem

Wiener's attack is based on the following theorem:

Let $n = pq$, with $q < p < 2q$. Let $d < \frac{1}{3}\sqrt[4]{n}$. Given $n$ and $e$ with $ed \equiv 1 \mod \phi(n)$, the attacker can efficiently recover .

Some observations on RSA

In order to better understand Wiener's Attack, it may be useful to take note of certain properties of RSA:

We may start by noting that the congruence can be written as the equality for some value , we may additionally note that , since both and are much shorter than , we can say that .

Dividing the former equation by gives us , and using the latter approximation, we can write this as . Notice how the left-hand side of this equation is composed entirely of public information, this will become important later.

It is possible to quickly factor by knowing and . Consider the quadratic polynomial , this polynomial will have the roots and . Expanding it gives us , and substituting for the variables we know we can write this as . Applying the quadratic formula gives us and : , where , , and .

Wiener's attack works by expanding to a continued fraction and iterating through the terms to check various approximations of . In order to make this checking process more efficient, we can make a few observations (this part is optional):

• Since is even, and and are both by definition coprime to , we know that is odd.

• Given the above equations and the values of , , , and , we can solve for with the equation , thus we know that has to be divisible by .

• If our

The Attack

Suppose we have the public key , this attack will determine

1. Convert the fraction into a continued fraction

2. Iterate over each convergent in the continued fraction:

3. Check if the convergent is by doing the following:

Here's a sage implementation to play around with:

//TODO: Proof of Wiener's theorem

Automation

The Python module owiener simplifies the scripting process of Wiener's attack:

Here is a Wiener's attack template:

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

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

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

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

• : denotes the set of rational numbers

• 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

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

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

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

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

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

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.

• 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

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.

Discrete log problem

Given any groupand elementssuch that , the problem of solving foris known as the disctete log problem (DLP). In sage, this can be done for general groups by calling discrete_log

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.

Overview

Given a composite integer , 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 such that or programmatically n%p==0

Seems like its an

// symmetric polynomials

// discriminants

// resultants

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.