Only this pageAll pages
Powered by GitBook
1 of 80

CryptoBook

Loading...

Loading...

Loading...

Loading...

Loading...

Fundamentals

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Number Theory

Loading...

Loading...

Loading...

Loading...

Loading...

Abstract algebra

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Elliptic Curves

Loading...

Lattices

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Asymmetric Cryptography

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Loading...

Symmetric Cryptography

Loading...

Loading...

Loading...

Loading...

Loading...

Hashes

Loading...

Loading...

Isogeny Based Cryptography

Loading...

Loading...

Loading...

Appendices

Loading...

Loading...

Book Plan

A summary we plan to cover

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.

Write about what you love and this book will be a success.

Descriptions of attacks against cryptosystems are strongly encouraged, however full SageMath implementations should not be included, as this has the potential for destroying CryptoHack challenges, or making all attacks known by so many people that CTFs become a total nightmare!!

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)

CryptoBook

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

Division and Greatest common divisor

Author: Zademn

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 Z={…,−1,0,1,2,3… }\mathbb{Z} = \{\dots , -1, 0, 1, 2, 3 \dots \}Z={…,−1,0,1,2,3…}be the set denoting the integers.

Definition - Divisibility

For a,b,∈Za, b, \in \mathbb{Z} a,b,∈Zwe say that aaadivides bbbif there is some k∈Zk \in \mathbb{Z}k∈Zsuch that a⋅k=ba \cdot k = ba⋅k=b

Notation: a∣ba | ba∣b

Example

For a=2,b=6a = 2, b = 6a=2,b=6 we have 2∣62 | 62∣6 because we can find k=3k = 3k=3such that 6=2⋅36 = 2 \cdot 36=2⋅3.

Properties

  • a∣a, 1∣a and a∣0a | a, \ 1 | a \text{ and } a | 0a∣a, 1∣a and a∣0

  • a∣ba | ba∣b and a∣c a | c a∣c implies a∣(bu+cv) ∀u,v,∈Za | (bu + cv) \ \forall u, v, \in \mathbb{Z}a∣(bu+cv) ∀u,v,∈Z

    • Example: Let b=6,u=5b = 6, u = 5b=6,u=5 and c=9,v=2c = 9, v = 2 c=9,v=2

    • 3∣63 | 63∣6 and 3∣9⇒3∣(6⋅5+9⋅2)  ⟺  3∣483 | 9 \Rightarrow 3 | (6 \cdot 5 + 9 \cdot 2) \iff 3 | 483∣9⇒3∣(6⋅5+9⋅2)⟺3∣48 . We can find k=16k = 16k=16such that 48=3⋅1648 = 3 \cdot 1648=3⋅16

  • a∣ba | ba∣b and b∣c b | c b∣c implies a∣c a | ca∣c

  • if a∣ba|ba∣band b∣ab|ab∣a then a=±ba = \pm ba=±b

Definition - Division with remainder

Let a,b∈Za, b \in \mathbb{Z}a,b∈Zwith b≥1b≥1b≥1,

There exists unique q,r∈Zq, r \in \mathbb{Z}q,r∈Zsuch that a=bq+r\boxed{a = bq + r}a=bq+r​and 0≤r<b0 \leq r < b0≤r<b

qq q is called the quotient and rrr the remainder

Examples:

  • To find q,rq, rq,r python offers us the divmod() function that takes a,ba, ba,bas arguments

q, r = divmod(6, 2)
print(q, r)
# 3 0 

q, r = divmod(13, 5)
print(q, r)
# 2 3 
# Note that 13 = 2 * 5 + 3
  • If we want to find only the quotient qqq we can use the // operator

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

q = 13 // 5
print(q)
# 2

r = 13 % 5
print(r)
# 3

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 a,b∈Za, b \in \mathbb{Z}a,b∈Z be 2 integers. The greatest common divisor is the largest integer d∈Zd \in \mathbb{Z}d∈Zsuch that d∣ad | ad∣aand d∣bd | bd∣b

Notation: gcd⁡(a,b)=d\gcd(a, b) = dgcd(a,b)=d

Examples:

# In python we can import math to get the GCD algo
import math
print(math.gcd(18, 12)) # -> 6
# Sage has it already!
print(gcd(18, 12)) # -> 6

Remark:

  • for all other common divisors ccc of a,ba, ba,bwe have c∣dc | dc∣d

Things to think about

What can we say about numbersa,b a, ba,b with gcd⁡(a,b)=1\gcd(a, b) = 1gcd(a,b)=1? How are their divisors?

Style Guide

Work in progress

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

If anything on any page is unclear, then please leave a comment, or talk in the discord. We are all at different levels, and I want this to be useful for everyone. Let's work on this as a big team and create something beautiful.

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

To use LaTeX\LaTeXLATE​X, you can wrap your text in $$maths here$$. If this is at the beginning of a paragraph, it makes it block, otherwise it is inline

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

Motivating a new reader is the biggest challenge of creating a resource. People will be coming here to understand cryptography and SageMath, so keep pointing back to the goal!

  • 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\LaTeXLATE​Xusing 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

Modular Arithmetic

Authors: A~Z, perhaps someone else but not yet (or they've decided to remain hidden like a ninja)

Introduction

Thinking not over the integers as a whole but modulo some integernnninstead 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 assumennnis a natural integer, andaaaandbbbare two integers. We say thataaaandbbbare congruent modulonnnwhenn∣(b−a)n\mid (b-a)n∣(b−a), or equivalently when there is an integerkkksuch thata=b+kna=b+kna=b+kn. We denote this bya≡b [n]a\equiv b~ [n]a≡b [n]or a≡bmod  na \equiv b\mod na≡bmodn. I will use the first notation throughout this chapter.

Remark: Whenb≠0b\neq0b=0, we havea≡r [b]a\equiv r~[b]a≡r [b], whererrris the remainder in the euclidean division ofaaaby

This relation has a number of useful properties:

  • ∀c∈Z,a≡b [n]  ⟹  ac≡bc [n]\forall c\in \mathbb Z, a\equiv b~[n] \implies ac \equiv bc ~ [n]∀c∈Z,a≡b [n]⟹ac≡bc [n]

  • ∀c∈Z,a≡b [n]  ⟹  a+c≡b+c [n]\forall c \in \mathbb Z, a\equiv b~[n] \implies a+c\equiv b+c ~[n]∀c∈Z,a≡b [n]⟹a+c≡b+c [n]

  • ∀c∈Z,a≡b [n] and b≡c [n]  ⟹  a≡c [n]\forall c \in \mathbb Z, a \equiv b ~[n] \text{ and } b\equiv c~[n]\implies a\equiv c ~[n]∀c∈Z,a≡b [n] and b≡c [n]⟹a≡c [n]

  • ∀m∈N,a≡b [n]  ⟹  am≡bm [n]\forall m \in \mathbb N, a\equiv b~[n] \implies a^m\equiv b^m ~[n]∀m∈N,a≡b [n]⟹am≡bm [n]

  • The proofs are left as an exercise to the reader :p (Hint: go back to the definition)

Seeing as addition and multiplication are well defined, the integers modulonnnform a ring, which we noteZ/nZ\mathbb Z/n\mathbb ZZ/nZ. In sage, you can construct such ring with either of the following

Zn = Zmod(5)
Zn = Integers(5)
Zn = IntegerModRing(5)
# Ring of integers modulo 5
Zn(7)
# 2
Zn(8) == Zn(13)
# True

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

pow(2, 564654533, 7) # Output result as member of Z/7Z
# 4
power_mod(987654321, 987654321, 7) # Output result as simple integer
# 6
Zmod(7)(84564685)^(2^100) # ^ stands for powering in sage. To get XOR, use ^^.
# 5

As a side note, remember that if an equality holds over the integers, then it holds modulo any natural integernnn. 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 integersaaaandbbbsuch thata2=2+4ba^2 = 2 + 4ba2=2+4b

Modular Inverse

Since we can multiply, a question arises: can we divide? The answer is yes, under certain conditions. Dividing by an integercccis the same as multiplying by its inverse; that is we want to find another integerdddsuch thatcd≡1 [n]cd\equiv 1~[n]cd≡1 [n]. Sincecd≡1 [n]  ⟺  ∃k∈Z,cd=1+kncd\equiv 1~[n]\iff\exists k\in\mathbb Z, cd = 1 + kncd≡1 [n]⟺∃k∈Z,cd=1+kn, it is clear from Bézout's Identity that such an inverse exists if and only ifgcd⁡(c,n)=1\gcd(c, n) = 1gcd(c,n)=1. Therefore, the units modulonnnare the integers coprime tonnn, lying in a set we call the unit group modulonnn: (Z/nZ)×\left(\mathbb Z/n\mathbb Z\right)^\times(Z/nZ)×

Zn = Zmod(10)
Zn(7).is_unit()
# True
Zn(8).is_unit()
# False
3 == 1/Zn(7) == Zn(7)^(-1) == pow(7,-1,10) # member of Z/10Z
# True
inverse_mod(7, 10) # simple integer
# 3
Zn(3)/7
# 9
Zn(3)/8
# ZeroDivisionError: inverse of Mod(8, 10) does not exist
Zn.unit_group()
# Multiplicative Abelian group isomorphic to C4 (C4 being the cyclic group of order 4)

Finding the modular inverse of a number is an easy task, thanks to the extended euclidean algorithm (that outputs solutions indddandkkkto the equationcd−kn=1cd-kn=1cd−kn=1from above).

xgcd(7, 10) # find (gcd(a, b), u, v) in au + bv = gcd(a, b)
# (1, 3, -2) <-- (gcd(7, 10), d, -k)

Theorems of Wilson, Euler, and Fermat

Wilson's Theorem

A positive integer 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

Euclidean Algorithm

Introduction

Although we have functions that can compute our 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

Pause and ponder. Make you you understand why that works.

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

This section needs to be expanded a bit.

Bezout's identity

Let . Then there exists such that

The extended euclidean algorithm aims to find given

Contributors

Optional space to say that you've worked on the book

Thank you!

🥳 CryptoBook is the result of the hard work of the CryptoHack community. Thanks to all of our writers, whether it's been line edits or whole section creation. This only exists because of the generosity and passion of a group of cryptographers.

Our Writers

  • ...

  • You?

Join CryptoBook

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

Mathematical Notation

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.

If you're reading a page and something is new to you, come here and add the symbol, someone else who understands it can explain its meaning

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

  • : denotes the set of natural numbers (non-negative integers)

  • : denotes the set of integers mod

  • We refer to unit groups by or . Example:

  • We refer to finite fields with elements by

  • We refer to a general field by

  • We refer to the algebraic closure of this 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

gcd⁡\gcdgcd
a=b⋅q+ra = b \cdot q + ra=b⋅q+r
d=gcd⁡(a,b)d = \gcd(a, b)d=gcd(a,b)
d∣rd | rd∣r
gcd⁡(a,b)=gcd⁡(b,r)\gcd(a, b) = \gcd(b, r)gcd(a,b)=gcd(b,r)
a=q0⋅b+r0b=q1⋅r0+r1r0=q2⋅r1+r2⋮rn−2=rn−1⋅qn−1+rnrn=0 a = q_0 \cdot b + r_0 \\ b = q_1 \cdot r_0 + r_1 \\ r_0 = q_2 \cdot r_1 + r_2 \\ \vdots \\ r_{n-2} = r_ {n-1} \cdot q_{n - 1} + r_n \\ r_n = 0a=q0​⋅b+r0​b=q1​⋅r0​+r1​r0​=q2​⋅r1​+r2​⋮rn−2​=rn−1​⋅qn−1​+rn​rn​=0
rk−2=qk⋅rk−1+rkr_{k-2} = q_k \cdot r_{k-1} + r_krk−2​=qk​⋅rk−1​+rk​
000
gcd⁡(a,b)=gcd(b,r0)=gcd(r0,r1)=⋯=gcd⁡(rn−2,rn−1)=rn−1=d\gcd(a, b) = gcd(b, r_0) = gcd(r_0, r_1) = \dots = \gcd(r_{n-2}, r_{n-1}) = r_{n-1} = dgcd(a,b)=gcd(b,r0​)=gcd(r0​,r1​)=⋯=gcd(rn−2​,rn−1​)=rn−1​=d
d=gcd⁡(a,b)d = \gcd(a, b)d=gcd(a,b)
ddd
r0,r1,...rn−1r_0, r_1, ... r_{n-1}r0​,r1​,...rn−1​
gcd⁡(24,15)\gcd(24, 15)gcd(24,15)
24=1⋅15+915=1⋅9+69=1⋅6+36=2⋅3+0⇒3=gcd⁡(24,15)24 = 1 \cdot 15 + 9 \\ 15 = 1 \cdot 9 + 6 \\ 9 = 1 \cdot 6 + 3 \\ 6 = 2 \cdot 3 + 0 \Rightarrow 3 = \gcd(24, 15) 24=1⋅15+915=1⋅9+69=1⋅6+36=2⋅3+0⇒3=gcd(24,15)
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
gcd⁡\gcdgcd
d=gcd⁡(a,b)d = \gcd(a, b)d=gcd(a,b)
u,vu, vu,v
au+bv=dau + bv = dau+bv=d
d=gcd⁡(a,b), and u,vd = \gcd(a, b), \text{ and }u, vd=gcd(a,b), and u,v
a,ba, ba,b
# 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
C\mathbb{C}C
R\mathbb{R}R
Z\mathbb{Z}Z
Q\mathbb{Q}Q
N\mathbb{N}N
Z/nZ\mathbb{Z}/n\mathbb ZZ/nZ
nnn
"""
We can call each of these sets with Sage using the 
following commands. Comments are the result of the
input.
"""
CC
# Complex Field with 53 bits of precision
RR
# Real Field with 53 bits of precision
ZZ
# Integer Ring
QQ
# Rational Field
NN
# Non negative integer semiring
Zmod(11) # or `Integers(11)` or `IntegerModRing(11)` 
# Ring of integers modulo 11
R×R^\timesR×
R∗R^*R∗
(Z/nZ)×(\mathbb Z/n \mathbb Z)^\times(Z/nZ)×
qqq
Fq\mathbb{F}_qFq​
kkk
kˉ\bar{k}kˉ
"""
Example of defining a field and then its 
algebraic closure
"""
GF(3)
# Finite Field of size 3 , where GF stands for Galois Field 
GF(3).algebraic_closure()
# Algebraic closure of Finite Field of size 3
"""
If you want to find which field an element belongs to you can use the 
`.parent()` function
"""

x = 7
print(x.parent())
# Integer Ring

y = 3.5
print(y.parent())
# Real Field with 53 bits of precision
"""
If you want to "lift" an element from a quotient ring R/I to the ring R
use the `.lift()` function
"""
R = ZZ
RI = Zmod(11)
x =  RI(5)

print(x.parent())
# Ring of integers modulo 11

y = x.lift()
print(y.parent())
# Integer Ring

print(y in R)
# True
∈\in∈
∀\forall∀
∃\exists∃
∃!\exists!∃!
Pr(A)Pr(A)Pr(A)
AAA
Pr[A]Pr[A]Pr[A]
P(A)P(A)P(A)
n>1n > 1n>1
(n−1)!≡−1mod  n(n-1)! \equiv -1 \mod n (n−1)!≡−1modn
n∈Z+n \in \mathbb{Z}^{+}n∈Z+
a∈Za \in \mathbb{Z}a∈Z
gcd(a,n)=1gcd(a, n) = 1gcd(a,n)=1
aϕ(n)≡1mod  na^{\phi(n)} \equiv 1 \mod naϕ(n)≡1modn
ppp
a∈Za \in \mathbb{Z}a∈Z
ap≡amod  pa^p \equiv a \mod pap≡amodp
ap−1≡1mod  pa^{p-1} \equiv 1 \mod pap−1≡1modp
Wilson's Theorem - Brilliant
Euler's Theorem - Brilliant
Fermat's Little Theorem - Brilliant
Discord Channel

Fermat's Little Theorem in Detail

Would you like to be an author?

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.

Power

0

1

2

3

4

5

6

1

0

1

2

3

4

5

6

2

0

1

4

2

2

4

1

3

0

1

1

6

1

6

6

4

0

1

2

4

4

2

1

5

0

1

4

5

2

3

6

6

0

1

1

1

1

1

1

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

Power

0

1

2

3

4

1

0

1

2

3

4

2

0

1

4

4

1

3

0

1

3

2

4

4

0

1

1

1

1

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

p, itworks = 1, True
for _ in range(100):
    p = next_prime(p)
    Fp = GF(p) # Finite Field of size p
    itworks &= all(Fp(x)^(p-1) == 1 for x in range(1,p))

print(itworks)
# True

Claim (Fermat's Little Theorem): Letpppa prime.∀a∈Z,ap≡a [p]\forall a\in\mathbb Z, a^p\equiv a~[p]∀a∈Z,ap≡a [p]

Whena≠0a\neq 0a=0, this is equivalent to what we observed:ap−1≡1 [n]a^{p-1}\equiv 1~[n]ap−1≡1 [n]. 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:∀a∈Z,a⋅ap−2≡ap−1≡1 [p]\forall a\in\mathbb Z, a\cdot a^{p-2}\equiv a^{p-1}\equiv 1~[p]∀a∈Z,a⋅ap−2≡ap−1≡1 [p]. Whenp>2p>2p>2, this means we have found a non-trivial integer that when multiplied toaaayields 1. That is, we have found the inverse ofaaa, wow. Since the inverse is unique moduloppp, 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.

Ideals

Example: Ideals of the integers

Definition - Ideal of Z\mathbb{Z}Z

I⊆Z I \subseteq \mathbb{Z}I⊆Zis an ideal   ⟺  ∀ a,b∈I and,z ∈Z\iff \forall \ a, b \in I \text{ and} , z\ \in \mathbb{Z}⟺∀ a,b∈I and,z ∈Zwe have

a+b∈I and az∈Ia + b \in I \text{ and } az \in Ia+b∈I and az∈I

Example: aZ={az : z∈Z}→2Z,3Z,4Z,…a\mathbb{Z} = \{az \ : \ z \in \mathbb{Z} \} \to 2\mathbb{Z}, 3\mathbb{Z}, 4\mathbb{Z}, \dotsaZ={az : z∈Z}→2Z,3Z,4Z,… - multiples of aaa

Remarks:

  1. ∀a,b∈Z\forall a, b \in \mathbb{Z}∀a,b∈Zwe have b∈aZ  ⟺  a∣bb \in a\mathbb{Z} \iff a | bb∈aZ⟺a∣b

  2. I1+I2={a1+a2 : a1∈I1,a2∈I2}I_1 + I_2 = \{a_1 + a_2 \ : \ a_1 \in I_1 , a_2 \in I_2\}I1​+I2​={a1​+a2​ : a1​∈I1​,a2​∈I2​} is an ideal

Example: Consider 18Z+12Z18\mathbb{Z} + 12\mathbb{Z}18Z+12Z. This ideal contains 6=18⋅1+12⋅(−1)⇒18Z+12Z=6Z6 = 18 \cdot 1 + 12 \cdot (-1) \Rightarrow 18\mathbb{Z} + 12\mathbb{Z} = 6\mathbb{Z}6=18⋅1+12⋅(−1)⇒18Z+12Z=6Z

Greatest common divisor

Let a,b∈Za, b \in \mathbb{Z}a,b∈Z be 2 integers. If d=gcd⁡(a,b)⇒aZ+bZ=dZd = \gcd(a, b) \Rightarrow a\mathbb{Z} + b\mathbb{Z} = d\mathbb{Z}d=gcd(a,b)⇒aZ+bZ=dZ

Sample Page

A rough guideline to a page

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: a+(b+c)=(a+b)+ca + (b + c) = (a + b) + ca+(b+c)=(a+b)+c

  • Commutative: a+b=b+aa + b = b + aa+b=b+a

  • Distributive: a(b+c)=ab+aca(b + c) = ab + aca(b+c)=ab+ac

  • Contains an identity element: a+0=0+a=aa + 0 = 0 + a = aa+0=0+a=a

  • Has an inverse for every element: a+(−a)=(−a)+a=0a + (-a) = (-a) + a = 0a+(−a)=(−a)+a=0

  • Closed: ∀a,b∈Z,a+b∈Z\forall a, b \in \mathbb{Z}, a + b \in \mathbb{Z}∀a,b∈Z,a+b∈Z

Interesting Identity

(1+2+3+…+n)2=13+23+33+…+n3(1 + 2 + 3 + \ldots + n)^2 = 1^3 + 2^3 + 3^3 + \ldots + n^3(1+2+3+…+n)2=13+23+33+…+n3

Sage Example

sage: 1 + (2 + 3) == (1 + 2) + 3
True
sage: 1 + 2 == 2 + 1
True
sage: 5*(7 + 11) == 5*7 + 5*11
True
sage: sum(i for i in range(1000))^2 == sum(i^3 for i in range(1000))
True

Further Resources

  • Links to

  • Other interesting

  • Resources

Continued Fractions

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

a0+b0a1+b1a2+b2⋱a_{0} + \frac{b_{0}}{ a_{1} + \frac{b_{1}}{ a_{2} + \frac{b_{2}}{ \ddots }}}a0​+a1​+a2​+⋱b2​​b1​​b0​​

ai,bia_{i}, b_{i}ai​,bi​are complex numbers. The continued fraction with bi=1 ∀ib_{i} = 1\ \forall ibi​=1 ∀i is called a simple continued fraction and continued fractions with finite number of aia_{i}ai​ are called finite continued fractions.

Consider example rational numbers,

1711=1+611116=1+5665=1+1551=5+0\frac{17}{11} = 1 + \frac{6}{11} \\[10pt] \frac{11}{6} = 1 + \frac{5}{6} \\[10pt] \frac{6}{5} = 1 + \frac{1}{5} \\[10pt] \frac{5}{1} = 5 + 01117​=1+116​611​=1+65​56​=1+51​15​=5+0

the continued fractions could be written as

51=565=1+15116=1+56=1+165=1+11+151711=1+611=1+1116=1+11+11+15\frac{5}{1} =5 \\[10pt] \frac{6}{5} = 1 + \frac{1}{5} \\[10pt] \frac{11}{6} = 1 + \frac{5}{6} = 1 + \frac{1}{\frac{6}{5}} = 1 + \frac{1}{1 + \frac{1}{5}} \\[10pt] \frac{17}{11} = 1 + \frac{6}{11} = 1 + \frac{1}{\frac{11}{6}} = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{5}}}15​=556​=1+51​611​=1+65​=1+56​1​=1+1+51​1​1117​=1+116​=1+611​1​=1+1+1+51​1​1​

Notation

a0+1a1+1a2+1⋱a_{0} + \frac{1}{ a_{1} + \frac{1}{ a_{2} + \frac{1}{ \ddots }}}a0​+a1​+a2​+⋱1​1​1​

A simple continued fraction is represented as a list of coefficients(aia_{i}ai​) i.e

x=[a0; a1, a2, a3, a4, a5, a6, …]x = [a_{0};\ a_{1},\ a_{2},\ a_{3},\ a_{4},\ a_{5},\ a_{6},\ \ldots]x=[a0​; a1​, a2​, a3​, a4​, a5​, a6​, …]

for the above example

1711=[1; 1, 1, 5]  ,116=[1; 1, 5]  ,65=[1;5]  ,51=[5;] \frac{17}{11} = [1;\ 1,\ 1,\ 5]\ \ ,\frac{11}{6} = [1;\ 1,\ 5]\ \ ,\frac{6}{5} = [1; 5]\ \ ,\frac{5}{1} = [5;]1117​=[1; 1, 1, 5]  ,611​=[1; 1, 5]  ,56​=[1;5]  ,15​=[5;]

Computation of simple continued fractions

Given a number xxx, the coefficients(aia_{i}ai​) in its continued fraction representation can be calculated recursively using

x0=xai=⌊xi⌋xi+1=1xi−aix_{0} = x \\[4pt] a_{i} = \lfloor x_{i} \rfloor \\[4pt] x_{i+1} = \frac{1}{x_{i} - a_{i}}x0​=xai​=⌊xi​⌋xi+1​=xi​−ai​1​

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

x0=a0+1a1+1a2,   x1=a1+1a2,   x2=a2xi=ai+1xi+1xi+1=1xi−aix_{0} = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2}}},\ \ \ x_{1} = a_{1} + \frac{1}{a_{2}}, \ \ \ x_{2} = a_{2} \\[10pt] x_{i} = a_{i} + \frac{1}{x_{i+1}} \\[10pt] x_{i+1} = \frac{1}{x_{i} - a_{i}}x0​=a0​+a1​+a2​1​1​,   x1​=a1​+a2​1​,   x2​=a2​xi​=ai​+xi+1​1​xi+1​=xi​−ai​1​

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

def continued_fraction_list(xi):
    ai = floor(xi)
    if xi == ai: # last coefficient
        return [ai]
    return [ai] + continued_fraction_list(1/(x - ai))

Convergents of continued fraction

The kthk^{th}kthconvergent of a continued fractionx=[a0;a1, a2, a3, a4,…]x = [a_{0}; a_{1},\ a_{2},\ a_{3},\ a_{4},\ldots] x=[a0​;a1​, a2​, a3​, a4​,…]is the numerical value or approximation calculated using the firstk−1k - 1k−1coefficients of the continued fraction. The firstkkkconvergents are

a01,   a0+1a1,   a0+1a1+1a2, …, a0+1a1+⋱ak−2+1ak−1\frac{a_{0}}{1},\ \ \ a_{0} + \frac{1}{a_{1}}, \ \ \ a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2}}}, \ \ldots,\ a_{0} + \frac{1}{a_{1} + \frac{\ddots} {a_{k-2} + \frac{1}{a_{k-1}}}}1a0​​,   a0​+a1​1​,   a0​+a1​+a2​1​1​, …, a0​+a1​+ak−2​+ak−1​1​⋱​1​

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

sage: cf = continued_fraction(17/11)
sage: convergents = cf.convergents()
sage: cf
[1; 1, 1, 5]
sage: convergents
[1, 2, 3/2, 17/11]

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

Theorem: if∣x−ab∣<1b2\mid x - \frac{a}{b} \mid < \frac{1}{b^{2}}∣x−ba​∣<b21​, thenab\frac{a}{b}ba​is a convergent ofxxx.

Wiener's attack on the RSA cryptosystem works by proving that under certain conditions, an equation of the form∣x−ab∣\mid x - \frac{a}{b} \mid∣x−ba​∣could be derived wherexxxis entirely made up of public information andab\frac{a}{b}ba​is made up of private information. Under assumed conditions, the inequality∣x−ab∣<1b2\mid x - \frac{a}{b} \mid < \frac{1}{b^{2}}∣x−ba​∣<b21​is statisfied, and the valueab\frac{a}{b}ba​(private information) is calculated from convergents ofxxx(public information), consequently breaking the RSA cryptosystem.

Quadratic Residues

Euler's Theorem in Detail

Todo

Pollard rho

Polynomials With Shared Roots

Algorithmic Number Theory

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

Groups

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

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

For example in AES128 K=M=C={0,1}128\mathcal{K} = \mathcal{M} = \mathcal{C} = \{0, 1\}^{128}K=M=C={0,1}128since the input, output and key spaces are 128 bits. We also have the encryption and decryption operations: Enc:K×M→CDec:K×C→MEnc: \mathcal{K} \times \mathcal{M} \to \mathcal{C} \\ Dec: \mathcal{K} \times \mathcal{C} \to \mathcal{M}Enc:K×M→CDec:K×C→M

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 setGGGpaired with a binary operation ⋅:G×G→G\cdot:G\times G\to G⋅:G×G→Gis a group if the following requirements hold:

  • Closure: For all a,b∈G: a, b \in G: \ a,b∈G:  a⋅b∈Ga\cdot b \in Ga⋅b∈G - Applying the operation keeps the element in the set

  • Associativity: For all a,b,c∈G:a, b, c \in G: a,b,c∈G: (a⋅b)⋅c=a⋅(b⋅c)(a \cdot b) \cdot c=a\cdot (b\cdot c)(a⋅b)⋅c=a⋅(b⋅c)

  • Identity: There exists an elemente∈Ge\in Ge∈Gsuch that a⋅e=e⋅a=aa\cdot e=e\cdot a=aa⋅e=e⋅a=afor all a∈Ga\in Ga∈G

  • Inverse: For all elements a∈Ga\in Ga∈G, there exists some b∈Gb\in Gb∈Gsuch that b⋅a=a⋅b=eb\cdot a=a\cdot b=eb⋅a=a⋅b=e. We usually denotebbbas a−1a^{-1}a−1

For n∈Zn\in\mathbb Zn∈Z, ana^nanmeans a⋅a…⋅a⏟n times\underbrace{a\cdot a\dots{}\cdot a}_{n\text{ times}}n timesa⋅a…⋅a​​when n>0n>0n>0and (a−n)−1\left(a^{-n}\right)^{-1}(a−n)−1when n<0n<0n<0. For n=0n=0n=0, an=ea^n=ean=e.

If ab=baab=baab=ba, then ⋅\cdot⋅is commutative and the group is called abelian. We often denote the group operation by +++instead of ⋅\cdot⋅and we typically use nananainstead of ana^nan.

Remark

  • The identity element of a group GGG is also denoted with 1G1_G1G​ or just 111 if only one groups is present

Examples of groups

Integers modulo nnn (remainders) under modular addition =(Z/nZ,+)= (\mathbb{Z} / n \mathbb{Z}, +)=(Z/nZ,+). Z/nZ={0,1,...,n−1}\mathbb{Z} / n \mathbb{Z} = \{0, 1, ..., n -1\}Z/nZ={0,1,...,n−1} Let's look if the group axioms are satisfied

  1. ✓\checkmark✓ ∀a,b∈Z/nZ let c≡a+b mod n\forall a, b \in \mathbb{Z}/ n\mathbb{Z} \text{ let } c \equiv a + b \bmod n∀a,b∈Z/nZ let c≡a+bmodn. Because of the modulo reduction c<n⇒c∈Z/nZc < n \Rightarrow c \in \mathbb{Z}/ n\mathbb{Z} c<n⇒c∈Z/nZ

  2. ✓\checkmark✓Modular addition is associative

  3. ✓\checkmark ✓0+a≡a+0≡a mod n⇒00 + a \equiv a + 0 \equiv a \bmod n \Rightarrow 00+a≡a+0≡amodn⇒0 is the identity element

  4. ✓\checkmark✓∀a∈Z/nZ\forall a \in \mathbb{Z}/ n\mathbb{Z} ∀a∈Z/nZwe take n−a mod nn - a \bmod nn−amodnto be the inverse of aaa. We check that

    a+n−a≡n≡0 mod na + n - a \equiv n \equiv 0 \bmod na+n−a≡n≡0modn

    n−a+a≡n≡0 mod nn - a + a \equiv n \equiv 0 \bmod nn−a+a≡n≡0modn

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

Z5 = Zmod(5) # Technically it's a ring but we'll use the addition here
print(Z5.list())
# [0, 1, 2, 3, 4]

print(Z5.addition_table(names = 'elements'))
# +  0 1 2 3 4
#  +----------
# 0| 0 1 2 3 4
# 1| 1 2 3 4 0
# 2| 2 3 4 0 1
# 3| 3 4 0 1 2
# 4| 4 0 1 2 3

a, b = Z5(14), Z5(3)
print(a, b)
# 4 3
print(a + b)
# 2
print(a + 0)
# 4
print(a + (5 - a))
# 0

Example of non-groups

(Q,⋅)(\mathbb{Q}, \cdot)(Q,⋅) is not a group because we can find the element 000 that doesn't have an inverse for the identity 111. (Z,⋅)(\mathbb{Z}, \cdot)(Z,⋅)is not a group because we can find elements that don't have an inverse for the identity 111

Exercise

Is (Z/nZ∖{0},⋅)(\mathbb{Z} / n \mathbb{Z} \smallsetminus \{0\}, \cdot)(Z/nZ∖{0},⋅)a group? If yes why? If not, are there values for nnnthat 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. ∀\forall∀ a∈G :(a−1)−1=ga \in G \ : \left(a^{-1} \right) ^{-1} = ga∈G :(a−1)−1=g. The inverse of the inverse of the element is the element itself

  4. ∀a,b∈G:\forall a, b \in G: ∀a,b∈G: (ab)−1=b−1a−1(ab)^{-1} = b^{-1}a^{-1}(ab)−1=b−1a−1

    Proof: (ab)(b−1a−1)=a(bb−1)a−1=aa−1=e.(ab)(b^{−1}a^{−1}) =a(bb^{−1})a^{−1}=aa^{−1}= e.(ab)(b−1a−1)=a(bb−1)a−1=aa−1=e.

n = 11
Zn = Zmod(n)
a, b = Zn(5), Zn(7)
print(n - (a + b))
# 10
print((n - a) + (n - b))
# 10

Orders

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

Group order

The order of a group GGGis the number of the elements in that group. Notation: ∣G∣|G|∣G∣

Element order

The order of an element a∈Ga \in Ga∈G is the smallest integer nnn such that an=1Ga^n = 1_Gan=1G​. If such a number nnn doesn't exist we say the element has order ∞\infty∞. Notation: ∣a∣|a|∣a∣

Z12 = Zmod(12) # Residues modulo 12
print(Z12.order()) # The additive order 
# 12
a, b= Z12(6), Z12(3)
print(a.order(), b.order())
# 2 4
print(a.order() * a)
# 0

print(ZZ.order()) # The integers under addition is a group of infinite order
# +Infinity

We said our messages lay in some group M\mathcal{M}M. The order of this group ∣M∣|\mathcal{M}|∣M∣ is the number of possible messages that we can have. For M={0,1}128\mathcal{M} = \{0,1\}^{128}M={0,1}128we have ∣M∣=2128|\mathcal{M}| = 2^{128}∣M∣=2128 possible messages.

Let m∈Mm \in \mathcal{M}m∈Mbe some message. The order of mmm means how many different messages we can generate by applying the group operation on mmm

Subgroups

Definition

Let (G,⋅)(G, \cdot)(G,⋅) be a group. We say HHHis a subgroup of GGG if HHH is a subset of GGG and (H,⋅)(H, \cdot)(H,⋅)forms a group. Notation: H≤GH \leq GH≤G

Proprieties

  1. The identity of GGG is also in H:H: H:1H=1G1_H = 1_G1H​=1G​

  2. The inverses of the elements in HHHare found in HHH

How to check H≤GH \leq GH≤G? Let's look at a 2 step test

  1. Closed under operation: ∀a,b∈H→ab∈H\forall a, b \in H \to ab \in H∀a,b∈H→ab∈H

  2. Closed under inverses: ∀a∈H→a−1∈H\forall a \in H \to a^{-1} \in H∀a∈H→a−1∈H

Generators

Let GGGbe a group,g∈Gg \in Gg∈Gan element and ∣g∣=n|g| = n∣g∣=n. Consider the following set:

{1,g,g2,...,gn−1}=denoted⟨g⟩.\{1, g, g^2, ..., g^{n-1}\} \overset{\text{denoted}}{=} \langle g\rangle.{1,g,g2,...,gn−1}=denoted⟨g⟩.

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

Why do we care about subgroups? We praise the fact that some problems are hard because the numbers we use are huge and exhaustive space searches are too hard in practice.

Suppose we have a big secret values space GGGand we use an element gggto generate them.

If an elementg∈Gg \in Gg∈Gwith a small order nnn is used then it can generate only nnn possible values and if nnn is small enough an attacker can do a brute force attack.

Example

For now, trust us that if given a prime ppp, a value g∈Z/pZg \in \mathbb{Z} / p \mathbb{Z}g∈Z/pZ and we compute y=gx mod py = g^x \bmod py=gxmodp for a secret xxx, finding xxx is a hard problem. We will tell you why a bit later.

p = 101 # prime
Zp = Zmod(p) 
H_list = Zp.multiplicative_subgroups() # Sage can get the subgroup generators for us
print(H_list)
# ((2,), (4,), (16,), (32,), (14,), (95,), (10,), (100,), ())

g1 = H_list[3][0] # Weak generator
print(g1, g1.multiplicative_order())
# 32 20

g2 = Zp(3) # Strong generator
print(g2, g2.multiplicative_order())
# 3 100


## Consider the following functions
def brute_force(g, p, secret_value):
    """
    Brute forces a secret value, returns number of attempts
    """
    for i in range(p-1):
        t = pow(g, i, p)
        if t == secret_value:
            break
    return i
    
def mean_attempts(g, p, num_keys):
    """
    Tries `num_keys` times to brute force and 
    returns the mean of the number of attempts
    """
    total_attempts = 0
    for _ in range(num_keys):
        k = random.randint(1, p-1)
        sv = pow(g, k, p) # sv = secret value
        total_attempts += brute_force(g, p, sv)
    return 1. * total_attempts / num_keys
    
## Let's try with our generators
print(mean_attempts(g1, p, 100)) # Weak generator
# 9.850
print(mean_attempts(g2, p, 100)) # Strong generator
# 49.200

Examples

// subgroups, quotient groups

// cyclic groups

Rings

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.

  • Distributivity:

// ideals, diff types of domains

Discrete Log Problem

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

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

RRR
+,⋅:R×R→R+,\cdot:R\times R\to R+,⋅:R×R→R
R,+R,+R,+
000
R,⋅R,\cdotR,⋅
111
a(b+c)=ab+ac,(a+b)c=ac+bca(b+c)=ab+ac,(a+b)c=ac+bca(b+c)=ab+ac,(a+b)c=ac+bc
GGG
a,ba,ba,b
an=ba^n=ban=b
nnn
sage: G = DihedralGroup(99)
sage: g = G.random_element()
sage: discrete_log(g^9,g) # note that if the order of g is less than 9 we would get 9 mod g.order()
9
(Z/nZ)∗\left(\mathbb Z/n\mathbb Z\right)^*(Z/nZ)∗
(Z/nZ)∗\left(\mathbb Z/n\mathbb Z\right)^*(Z/nZ)∗
mod n\text{mod }nmod n
xxx
ax=b(modn)a^x=b\pmod nax=b(modn)
sage: R = Integers(99)
sage: a = R(4)
sage: b = a^9
sage: b.log(a)
9
nnn
n=pn=pn=p
p<1050∼2166p < 10^{50} \sim 2 ^{166}p<1050∼2166
n=pkn = p^kn=pk
x = int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))"))
x = gp.znlog(b, gp.Mod(a, n))
p = getPrime(36)
n = p^2
K = Zmod(n)
a = K.multiplicative_generator()
b = a^123456789

time int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))")) 
# CPU times: user 879 µs, sys: 22 µs, total: 901 µs
# Wall time: 904 µs
# 123456789

time b.log(a)
# CPU times: user 458 ms, sys: 17 ms, total: 475 ms
# Wall time: 478 ms
# 123456789

time discrete_log(b,a)
# CPU times: user 512 ms, sys: 24.5 ms, total: 537 ms
# Wall time: 541 ms
# 123456789
p = getPrime(100)
n = p^2
K = Zmod(n)
a = K.multiplicative_generator()
b = a^123456789

time int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))")) 
# CPU times: user 8.08 s, sys: 82.2 ms, total: 8.16 s
# Wall time: 8.22 s
# 123456789
E(k)E(k)E(k)

LLL reduction

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.

Another take on groups

// Visual

// Symmetries

// Permutations

Sieves

Integer Factorization

Overview

Given a composite integer nnn, 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<n1 < p < n1<p<n such that p∣np|np∣nor 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 O(n)O(n)O(n)algorithm! whats all the deal about? By polynomial time, we mean polynomial time in bbbwhen nnnis a b-bit number, so what we looking at is actually a O(2b)O(2^b)O(2b)which is actually exponential (which everyone hates)

Now taking a better look at it, one would realize that a factor of nnncan't be bigger than n\sqrt{n}n​ 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.

Untitled

Polynomials

// symmetric polynomials

// discriminants

// resultants

Applications

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.

LLL reduction

Overview

There are a few issues that one may encounter when attempting to generalize Lagrange's algorithm to higher dimensions. Most importantly, one needs to figure what is the proper way to swap the vectors around and when to terminate, ideally in in polynomial time. A rough sketch of how the algorithm should look like is

There are two things we need to figure out, in what order should we reduce the basis elements by and how should we know when to swap. Ideally, we also want the basis to be ordered in a way such that the smallest basis vectors comes first. Intuitively, it would also be better to reduce a vector by the larger vectors first before reducing by the smaller vectors, a very vague analogy to filling up a jar with big stones first before putting in the sand. This leads us to the following size reduction algorithm:

We can further improve this by optimizing the Gram Schmidt computation as this algorithm does not modify at all. Furthermorechanges in a very predictable fasion and when vectors are swapped, one can write explicit formulas for howchanges as well.

Next, we need to figure a swapping condition. Naively, we want

for all . However, such a condition does not guarantee termination in polynomial time. As short basis vectors should be almost orthogonal, we may also want to incorperate this notion. Concretely, we want to be somewhat small for all pairs of , i.e. we may want something like

However, since , this condition is easily satisfied for a sufficiently long , which is not what we want. The key idea is to merge these two in some way and was first noticed by Lovász - named the Lovász condition:

It turns out that using this condition, the algorithm above terminates in polynomial time! More specifically, it has a time complexity of where we havebasis vectors as a subset of and is a bound for the largest norm of . ensures that the lattice vectors are ordered roughly by size and ensures the algorithm terminates.

Polynomial time proof

This follows the proof provided by the authors of the LLL paper. We first prove that the algorithm terminates by showing it swaps the vectors finitely many times. Letbe the number of basis vectors as a subset of . Let be the volume of the lattice generated by at each step of the algorithm. We have . Now consider the quantity

This quantity only changes whenever some changes, i.e when swaps happen. Let's consider what happens when we swap and . Recall the Gram-Schmidt algorithm:

From this, see that when we swap and , is replaced by . Now using the Lovász condition, we see that we have, hence the value of must decrease by at least , i.e. the new is less than . All other must remain the same as the volume remains fixed when we swap basis vectors around. Hence at each swap, decreases by . This is why we need .Now we are left with showing is bounded from below then we are done.

Let be the length of the shortest (nonzero) vector in the lattice. We can treat as the volume of the lattice generated by. Let be the shortest vector in the lattice in . By using Minkowski's lattice point theorem, we have

(Note that the value of isn't particularly important, one can use a easier value like )

Hence we see that , and hence has a (loose) lower bound , meaning that there are at most swaps. Since at each iteration,either increases bywhen there is no swaps or decreases by at mostwhen there is swaps and ranges fromto, the number of time the loop runs must be at most , hence the algorithm terminates.

This proof also gives us a handle on the time complexity of the operation. Letis the length of the longest input basis vector. Since we have , and the algorithm loops times. The Gram-Schmidt orthogonalization is the most expensive part in the entire process, taking up arithmetic operations. By using classical algorithm for arithmetic operations, each takes time. From this, we deduce that the time complexity of the LLL algorithm is , a somewhat reasonable polynomial time algorithm.

Let be the output of the LLL algorithm, it turns out that we have the bound

which requires . Such bounds for the shortest vector will be elaborated in more detail in the section on reduced basis.

Exercises

1) Implement the LLL in sage and experimentally verify that does indeed decrease byeach time.

2) Show that the time complexity analysis is correct, and indeed each loop takes at most operations.

Introduction

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.

The last example should hint at how we generalize this concept to arbitrary dimensions. In general, lattices consist of discrete points which appear at "regular intervals."

Definitions

A lattice is a subgroup of generated by , i.e.

where are linearly independent vectors. Collectively, form a basis of.

We say a set of vectors are linearly independent if the only solution to the equation is when all are zero.

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, is . A lattice is complete if . Note that we can always choose a subspace of such that the lattice is complete, namely the subspace generated by .

The region

is known as the fundamental mesh.

In the image above, we see the points of a lattice in . 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 (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:

Letbe amatrix whose rows are given by the basis vectors. Then the volume of a fundamental mesh is given by

A subset of is known as centrally symmetric if implies . It is convex if for any , the line joining is contained in , i.e. . Finally we can introduce the most important theorem about lattices, the Minkowski's Lattice Point Theorem:

Let be a complete lattice of dimension and be a centrally symmetric convex set. Suppose

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

Throughout this section, denotes the norm and 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 , hence the inclusion cannot be injective, thus we can find some , . Hence is a nontrivial lattice point.

Exercises

1) Let be the lattice generated by (take the rows as basis vectors).

  • Compute the volume of this lattice

  • Show that generates the same lattice

  • Show that each row in is in the lattice butdoes not generate the lattice. This is one key difference from the case of linear algebra (over fields).

2) Letbe matrices whose row vectors are basis for lattices . Both lattices are the same iff there exists some such that . Find for problem 1. Note that is the group of invertible matrices with integer coefficients, meaning and have integer coefficients.

3) Show that the condition in Minkowski's lattice point theorem is strict, i.e. for any complete latticeof dimension , we can find some centrally symmetric convex setwithbut the only lattice point inis the origin.

4*) Letbe the shortest nonzero vector for some lattice with dimension. Show that

Lagrange's algorithm

Overview

Lagrange's algorithm, often incorrectly called Gaussian reduction, is the 2D analouge to the Euclidean algorithm and is used for lattice reduction. Intuitively, lattice reduction is the idea of finding a new basis that consists of shorter vectors. Before going into Lagrange's algorithm, we first recap the Euclidean algorithm:

The algorithm primarily consists of two steps, a reduction step where the size of is brought down by a multiple of and a swapping step that ensures is always the largest number. We can adapt this idea for lattices:

Here is actually the Gram-Schmidt coefficient and it turns out that this algorithm will always find the shortest possible basis! Using the basis

the Lagrange reduction looks like

and here we see it clearly gives the shortest vectors.

Optimality proof

Let be a lattice. The basis is defined to be the shortest for any other basis , we have and . Note that this generally cannot be generalized to other dimensions, however in dimension 2, this is possible and is given by Lagrange's algorithm. The proof is a somewhat messy sequence of inequalities that eventually lead to the conclusion we want.

Let be the output of the Lagrange reduction for some lattice . To prove that Lagrange reduction gives the shortest basis, we first show that is the shortest vector in .

We know that from the algorithm directly. Let be any element in . We first show that :

Since , this quantity is only when and is a positive integer for all other cases, hence and is a shortest vector of . Note that we can have multiple vectors with the same norm as , for instance . So this is not a unique shortest vector.

Suppose there exists some basis for such that . We show that . Let .

If , then as must form a basis. This means that and by the inequality above, we must have or . The first case tells us that . By squaring the second case, we get

but since is the shortest vector, .

Otherwise, we have and , so

Hence proving Lagrange's algorithm indeed gives us the shortest basis vectors.

Exercises

1) Show that the output of Lagrange's algorithm generate the same lattice as the input.

2) Find a case where . Notice that the vectors here is the equality case for the bound given in Exercise 4 of the introduction, this actually tells us that the optimal lattice circle packing in 2D is given by this precise lattice! It turns out that this is actually the optimal circle packing in 2D but the proof is significantly more involved. (See for the details)

3*) Let , show that

and show that for all steps in the algorithm except the first and last, hence decreases by at least at each loop and the algorithm runs in polynomial time.

HKZ reduced

Definition

Let as the projection to the orthogonal complement of .Then the basis is HKZ-reduced if it is size-reduced and . This definition gives us a relatively simple way to compute a HKZ-reduced basis by iteratively finding the shortest vector in orthogonal projections.

Bounds

Fields

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

  • is a commutative group with identity

  • is a commutative group with identity.

  • Distributivity:

// field extensions, algebraic elements

def LLL(B):
    d = B.nrows()
    i = 1
    while i<d:
        size_reduce(B)
        if swap_condition(B):
            i += 1
        else:
            B[i],B[i-1] = B[i-1],B[i]
            i = max(i-1,1)
    return B
def size_reduce(B):
    d = B.nrows()
    i = 1
    while i<d:
        Bs,M = B.gram_schmidt()
        for j in reversed(range(i)):
            B[i] -= round(M[i,j])*B[j]
            Bs,M = B.gram_schmidt()
    return B
B∗\mathcal B^*B∗
μ\muμ
B∗\mathcal B^*B∗
∥bi∥≤∥bi+1∥\left\lVert b_i\right\rVert\leq\left\lVert b_{i+1}\right\rVert∥bi​∥≤∥bi+1​∥
iii
∣μi,j∣\left|\mu_{i,j}\right|∣μi,j​∣
i,ji,ji,j
∣μi,j∣≤c|\mu_{i,j}|\leq c∣μi,j​∣≤c
μi,j=⟨bi,bj∗⟩⟨bj∗,bj∗⟩\mu_{i,j}=\frac{\langle b_i,b_j^*\rangle}{\langle b_j^*,b_j^*\rangle}μi,j​=⟨bj∗​,bj∗​⟩⟨bi​,bj∗​⟩​
bj∗b_j^*bj∗​
δ∥bi∗∥2≤∥bi+1∗+μi+1,ibi∗∥2δ∈(14,1)\delta\left\lVert b_i^*\right\rVert^2\leq\left\lVert b_{i+1}^*+\mu_{i+1,i}b_i^*\right\rVert^2\quad\delta\in\left(\frac14,1\right)δ∥bi∗​∥2≤​bi+1∗​+μi+1,i​bi∗​​2δ∈(41​,1)
O(d5nlog⁡3B)O\left(d^5n\log^3B\right)O(d5nlog3B)
ddd
Rn\mathbb R^nRn
BBB
bib_ibi​
14<δ\frac14<\delta41​<δ
δ<1\delta<1δ<1
ddd
Rn\mathbb R^nRn
did_idi​
{bj}j=1i\left\{b_j\right\}_{j=1}^i{bj​}j=1i​
di=∏j=1i∥bj∗∥d_i=\prod_{j=1}^i\left\lVert b_j^*\right\rVertdi​=∏j=1i​​bj∗​​
D=∏i=1ddiD=\prod_{i=1}^dd_iD=i=1∏d​di​
bi∗b_i^*bi∗​
bib_ibi​
bi+1b_{i+1}bi+1​
bi∗=bi−∑j=1i−1μi,jbj∗μi,j=⟨bi,bj∗⟩⟨bj∗,bj∗⟩b_i^*=b_i-\sum_{j=1}^{i-1}\mu_{i,j}b_j^*\quad\mu_{i,j}=\frac{\langle b_i,b_j^*\rangle}{\langle b_j^*,b_j^*\rangle}bi∗​=bi​−j=1∑i−1​μi,j​bj∗​μi,j​=⟨bj∗​,bj∗​⟩⟨bi​,bj∗​⟩​
bib_ibi​
bi+1b_{i+1}bi+1​
bi∗b_i^*bi∗​
bi+1∗+μi+1,ibi∗b_{i+1}^*+\mu_{i+1,i}b_i^*bi+1∗​+μi+1,i​bi∗​
∥bi+1∗+μi+1,ibi∗∥2<δ∥bi∗∥2\left\lVert b_{i+1}^*+\mu_{i+1,i}b_i^*\right\rVert^2<\delta\left\lVert b_i^*\right\rVert^2​bi+1∗​+μi+1,i​bi∗​​2<δ∥bi∗​∥2
did_idi​
δ\deltaδ
did_idi​
diδ\frac{d_i}\deltaδdi​​
dj,j≠id_j,j\neq idj​,j=i
DDD
δ\deltaδ
δ<1\delta<1δ<1
did_idi​
λ1(L)\lambda_1(L)λ1​(L)
did_idi​
LiL_iLi​
{bj}j=1i\left\{b_j\right\}_{j=1}^i{bj​}j=1i​
xix_ixi​
LiL_iLi​
λ1(L)≤xi≤2πΓ(i2+1)1i⏟Cidi1idi≥λ1(L)iCii=di,min⁡\begin{align*} \lambda_1(L)\leq x_i&\leq\underbrace{\frac2{\sqrt\pi}\Gamma\left(\frac i2+1\right)^{\frac1i}}_{C_i}d_i^\frac1i\\ d_i&\geq\frac{\lambda_1(L)^i}{C_i^i}=d_{i,\min} \end{align*}λ1​(L)≤xi​di​​≤Ci​π​2​Γ(2i​+1)i1​​​dii1​​≥Cii​λ1​(L)i​=di,min​​
CiC_iCi​
i\sqrt ii​
did_idi​
DDD
Dmin⁡=∏i=1ddi,min⁡D_{\min}=\prod_{i=1}^dd_{i,\min}Dmin​=∏i=1d​di,min​
log⁡Dlog⁡Dmin⁡δ\frac{\log D}{\log D_{\min}\delta}logDmin​δlogD​
kkk
111
111
kkk
222
ddd
2log⁡Dlog⁡Dmin⁡δ+d2\frac{\log D}{\log D_{\min}\delta}+d2logDmin​δlogD​+d
BBB
di≤Bid_i\leq B^idi​≤Bi
D≤Bm2+m2D\leq B^{\frac{m^2+m}2}D≤B2m2+m​
O(d2log⁡B)O\left(d^2\log B\right)O(d2logB)
O(d2n)O\left(d^2n\right)O(d2n)
O(nlog⁡B)O\left(n\log B\right)O(nlogB)
O(d5mlog⁡2B)O\left(d^5m\log^2B\right)O(d5mlog2B)
bib_ibi​
∥b1∥≤(44δ−1)d−14vol(L)1d\left\lVert b_1\right\rVert\leq\left(\frac4{4\delta-1}\right)^{\frac{d-1}4}\text{vol}(L)^\frac1d∥b1​∥≤(4δ−14​)4d−1​vol(L)d1​
δ>14\delta>\frac14δ>41​
DDD
δ\deltaδ
O(d2n)O\left(d^2n\right)O(d2n)
πi\pi_iπi​
{bj}j=1i−1\left\{b_j\right\}_{j=1}^{i-1}{bj​}j=1i−1​
∣∣bi∗∣∣=λ1(πi(L))||b_i^*||=\lambda_1\left(\pi_i(L)\right)∣∣bi∗​∣∣=λ1​(πi​(L))
4i+3≤(∣∣bi∣∣λi(L))2≤i+34\frac4{i+3}\leq\left(\frac{||b_i||}{\lambda_i(L)}\right)^2\leq\frac{i+3}4i+34​≤(λi​(L)∣∣bi​∣∣​)2≤4i+3​
FFF
+,⋅:F×F→F+,\cdot:F\times F\to F+,⋅:F×F→F
R,+R,+R,+
000
R−{0},⋅R-\{0\},\cdotR−{0},⋅
111
a(b+c)=ab+ac,(a+b)c=ac+bca(b+c)=ab+ac,(a+b)c=ac+bca(b+c)=ab+ac,(a+b)c=ac+bc

Minkowski reduced

Definition

The basis{bi}i=1d\left\{b_i\right\}_{i=1}^d{bi​}i=1d​ is Minkowski-reduced if bib_ibi​has minimum length among all vectors in LLL linearly independent from{bj}j=1i−1\left\{b_j\right\}_{j=1}^{i-1}{bj​}j=1i−1​. Equivalently, bib_ibi​has minimum length among all vectors vvvsuch that {b1,…,bi−1,v}\left\{b_1,\dots,b_{i-1},v\right\}{b1​,…,bi−1​,v}can be extended to form a basis ofLLL. Such a notion is strongest among all lattice reduction notions and is generally extremely hard to compute. Another equivalent definition is

∥bi∥≤∥∑j=idcjbj∥gcd⁡(cj)=1\left\lVert b_i\right\rVert\leq\left\lVert\sum_{j=i}^dc_jb_j\right\rVert\quad\gcd\left(c_j\right)=1∥bi​∥≤​j=i∑d​cj​bj​​gcd(cj​)=1

Bounds

λi(L)2≤∥bi∥2≤max⁡(1,(54)i−4)λi(L)2\lambda_i(L)^2\leq\left\lVert b_i\right\rVert^2\leq\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_i(L)^2λi​(L)2≤∥bi​∥2≤max(1,(45​)i−4)λi​(L)2

The proof presented here is based off [Waerden 1956]. We proceed by induction. Letbib_ibi​be a Minkowski-reduced basis for some latticeLLL. The lower bound is immediate and for i=1i=1i=1, the upper bound is immediate as well.

Let v1,v2…viv_1,v_2\dots v_iv1​,v2​…vi​be linearly independent vectors such that∥vj∥=λj(L)\left\lVert v_j\right\rVert=\lambda_j(L)∥vj​∥=λj​(L). Let Li−1L_{i-1}Li−1​be the sublattice generated by b1,b2,…bi−1b_1,b_2,\dots b_{i-1}b1​,b2​,…bi−1​. Evidently somekkkmust exist such thatvkv_kvk​is not in Li−1L_{i-1}Li−1​. Consider the new lattice L′=L∩span(b1,b2,…bi−1,vk)L'=L\cap\text{span}\left(b_1,b_2,\dots b_{i-1},v_k\right)L′=L∩span(b1​,b2​,…bi−1​,vk​). Letvk′v'_kvk′​be the shortest vector inL′−Li−1L'-L_{i-1}L′−Li−1​such thatb1,b2,…,bi−1,vk′b_1,b_2,\dots,b_{i-1},v'_kb1​,b2​,…,bi−1​,vk′​is a basis for L′L'L′and we have

vk=a1b1+a2b2+⋯+ai−1bi−1+nvk′ai,n∈Z∥bi∥≤∥vk′∥v_k=a_1b_1+a_2b_2+\dots+a_{i-1}b_{i-1}+nv'_k\quad a_i,n\in\mathbb Z\\ \left\lVert b_i\right\rVert\leq\left\lVert v'_k\right\rVertvk​=a1​b1​+a2​b2​+⋯+ai−1​bi−1​+nvk′​ai​,n∈Z∥bi​∥≤∥vk′​∥

Ifn=1n=1n=1, then we are done sincevkv_kvk​can be extended to a basis of LLL, so ∥bi∥≤∥vk∥=λk(L)≤λi(L)\left\lVert b_i\right\rVert\leq\left\lVert v_k\right\rVert=\lambda_k(L)\leq\lambda_i(L)∥bi​∥≤∥vk​∥=λk​(L)≤λi​(L). Otherwise, we have n2≥4n^2\geq4n2≥4. Let vk′=p+qv_k'=p+qvk′​=p+qwherepppis the projection ofvk′v'_kvk′​inLi−1L_{i-1}Li−1​. Since by definition we have∥p∥2≤∥p±bi∥2\left\lVert p\right\rVert^2\leq\left\lVert p\pm b_i\right\rVert^2∥p∥2≤∥p±bi​∥2, we must have

∥p∥2≤14∑j=1i−1∥bj∥2\left\lVert p\right\rVert^2\leq\frac14\sum_{j=1}^{i-1}\left\lVert b_j\right\rVert^2∥p∥2≤41​j=1∑i−1​∥bj​∥2

Furthermore, since

λk2=∥vk∥2=∥a1b1+a2b2+…ai−1bi−1+p∥2+n2∥q∥2\lambda_k^2=\left\lVert v_k\right\rVert^2=\left\lVert a_1b_1+a_2b_2+\dots a_{i-1}b_{i-1}+p\right\rVert^2+n^2\left\lVert q\right\rVert^2λk2​=∥vk​∥2=∥a1​b1​+a2​b2​+…ai−1​bi−1​+p∥2+n2∥q∥2

we have ∥q∥2≤14λk2\left\lVert q\right\rVert^2\leq\frac14\lambda_k^2∥q∥2≤41​λk2​, hence we have

∥bi∥≤14∑j=1i−1∥bj∥2+14λk2≤14∑j=1i−1max⁡(1,(54)i−4)λj(L)2+14λk(L)2≤14(1+∑j=1i−1max⁡(1,(54)i−4))λi(L)2{=max⁡(1,(54)i−4)λi(L)2i≥4<λi(L)2i=2,3\begin{align*} \left\lVert b_i\right\rVert&\leq\frac14\sum_{j=1}^{i-1}\left\lVert b_j\right\rVert^2+\frac14\lambda_k^2\\ &\leq\frac14\sum_{j=1}^{i-1}\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_j(L)^2+\frac14\lambda_k(L)^2\\ &\leq\frac14\left(1+\sum_{j=1}^{i-1}\max\left(1,\left(\frac54\right)^{i-4}\right)\right)\lambda_i(L)^2\\ &\begin{cases}=\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_i(L)^2&i\geq4\\<\lambda_i(L)^2&i=2,3\end{cases}\\ \end{align*}∥bi​∥​≤41​j=1∑i−1​∥bj​∥2+41​λk2​≤41​j=1∑i−1​max(1,(45​)i−4)λj​(L)2+41​λk​(L)2≤41​(1+j=1∑i−1​max(1,(45​)i−4))λi​(L)2{=max(1,(45​)i−4)λi​(L)2<λi​(L)2​i≥4i=2,3​​

but since λi(L)2≤∥bi∥2\lambda_i(L)^2\leq \left\lVert b_i\right\rVert^2λi​(L)2≤∥bi​∥2by definition, the case of i=2,3i=2,3i=2,3cannot occur here (hence n=1n=1n=1in these cases).

Exercises

1) Show that both definitions of Minkowski-reduced lattice are equivalent

2) Consider the lattice L=(2000002000002000002011111)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}L=​20001​02001​00201​00021​00001​​. We have showed in a previous exercise that the successive minima are all222but no basisbib_ibi​can satisfy ∥bi∥=λi\left\lVert b_i\right\rVert=\lambda_i∥bi​∥=λi​, show that for any Minkowski reduced basis bib_ibi​, the basis must satisfy ∥bi∥2=max⁡(1,(54)i−4)λi(L)2\left\lVert b_i\right\rVert^2=\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_i(L)^2∥bi​∥2=max(1,(45​)i−4)λi​(L)2

Lattice reduction

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{bi}i=1d\left\{b_i\right\}_{i=1}^d{bi​}i=1d​is size-reduced if ∣μi,j∣≤12\left|\mu_{i,j}\right|\leq\frac12∣μi,j​∣≤21​. Intuitively this captures the idea that a reduced basis being "almost orthogonal".

Let LLLbe a lattice, 1≤i≤dim⁡L=d1\leq i\leq\dim L=d1≤i≤dimL=d, we define the ithi^\text{th}ithsuccessive minimaλi(L)\lambda_i(L)λi​(L) as

λi(L)=min⁡(max⁡1≤j≤i(∥vj∥):vj∈L are linearly independent)\lambda_i(L)=\min\left(\max_{1\leq j\leq i}\left(\left\lVert v_j\right\rVert\right):v_j\in L\text{ are linearly independent}\right)λi​(L)=min(1≤j≤imax​(∥vj​∥):vj​∈L are linearly independent)

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

λ1(L)=min⁡(∥v∥:v∈L)\lambda_1(L)=\min\left(\left\lVert v\right\rVert:v\in L\right)λ1​(L)=min(∥v∥:v∈L)

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

Unfortunately, a basisbib_ibi​for LLLwhere λi(L)=∥bi∥\lambda_i(L)=\left\lVert b_i\right\rVertλi​(L)=∥bi​∥for dimensions 555 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λi(L)\lambda_i(L)λi​(L)that will be helpful is the radius of the smallest ball centered at the origin such that the ball contains at leastiiilinearly independent vectors inLLL.

Exercises

1) Show that both definitions of λi\lambda_iλi​ are equivalent

2) Consider the lattice L=(2000002000002000002011111)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}L=​20001​02001​00201​00021​00001​​. Show that the successive minima are all222but no basisbib_ibi​can satisfy ∥bi∥=λi\left\lVert b_i\right\rVert=\lambda_i∥bi​∥=λi​.

Coppersmith algorithm

This algorithm solves for small roots of polynomials modulo any integer, meaning given some polynomial f(x)∈Z[x]f(x)\in\mathbb Z[x]f(x)∈Z[x]of degree dddand any integer NNN, then if f(x0)=0(modN),∣x0∣<N1df(x_0)=0\pmod{N},|x_0|<N^{\frac1d}f(x0​)=0(modN),∣x0​∣<Nd1​, this algorithm can findx0x_0x0​with time polynomial in log⁡N\log NlogNand ddd. The key idea behind this algorithm is to construct a polynomialg(x)g(x)g(x)such that g(x0)=0g(x_0)=0g(x0​)=0in R\mathbb RR. As roots of polynomials over the reals can be found easily, this gives an easy way to find x0x_0x0​. We shall introduce the Coppersmith algorithm in a few iterations, with each iteration approaching the N1dN^{\frac1d}Nd1​bound.

Polynomials in lattices

We first consider a criteria for a root of a polynomial moduloNNNto exists over the reals as well. Supposef(x)=∑i=0dfixif(x)=\sum_{i=0}^df_ix^if(x)=∑i=0d​fi​xiis a polynomial of degreeddd. Define the ℓ2\ell_2ℓ2​norm∥f(x)∥2\left\lVert f(x)\right\rVert_2∥f(x)∥2​ of a polynomial to be ∑i=0dfi2\sqrt{\sum_{i=0}^df_i^2}∑i=0d​fi2​​. Given ∣x0∣<B,f(x0)=0(modN)|x_0|<B,f(x_0)=0\pmod N∣x0​∣<B,f(x0​)=0(modN), if

∥f(Bx)∥2=∑i=0d(fiBi)2≤Nd+1\left\lVert f(Bx)\right\rVert_2=\sqrt{\sum_{i=0}^d\left(f_iB^i\right)^2}\leq\frac N{\sqrt{d+1}}∥f(Bx)∥2​=i=0∑d​(fi​Bi)2​≤d+1​N​

then f(x0)=0f(x_0)=0f(x0​)=0 in R\mathbb RR. The proof is a relatively straightforward chain of inequalities:

Nd+1≥∑i=0d(fiBi)2≥∑i=0d(fix0i)2≥1d+1∑i=0d∣fix0i∣≥1d+1∣∑i=0dfix0i∣\begin{align*} \frac N{\sqrt{d+1}}&\geq\sqrt{\sum_{i=0}^d\left(f_iB^i\right)^2}\\&\geq\sqrt{\sum_{i=0}^d\left(f_ix_0^i\right)^2}\\ &\geq\frac1{\sqrt{d+1}}\sum_{i=0}^d\left|f_ix_0^i\right|\\ &\geq\frac1{\sqrt{d+1}}\left|\sum_{i=0}^df_ix_0^i\right|\\ \end{align*}d+1​N​​≥i=0∑d​(fi​Bi)2​≥i=0∑d​(fi​x0i​)2​≥d+1​1​i=0∑d​​fi​x0i​​≥d+1​1​​i=0∑d​fi​x0i​​​

and since f(x0)=0(modN)f(x_0)=0\pmod Nf(x0​)=0(modN)implies f(x0)=kNf(x_0)=kNf(x0​)=kNfor some k∈Zk\in\mathbb Zk∈Z, we know that kkkmust be000to satisfy the inequality above.

With this, if we can find some polynomials fif_ifi​such that fi(x0)=0(modN)f_i(x_0)=0\pmod Nfi​(x0​)=0(modN), then if we can find some cic_ici​such that ∥∑icifi(x)∥2≤Nd+1\left\lVert\sum_ic_if_i(x)\right\rVert_2\leq\frac N{\sqrt{d+1}}∥∑i​ci​fi​(x)∥2​≤d+1​N​, then we can find x0x_0x0​easily. This gives a brief idea as to why lattices would be useful in such a problem.

To use lattices, notice that we can encode the polynomial f(x)=∑i=0dfixif(x)=\sum_{i=0}^df_ix^if(x)=∑i=0d​fi​xias the vector with components fif_ifi​. In this way, adding polynomials and multiplying polynomials by numbers still makes sense. Lets suppose that f(x0)=0(modN),x0<Bf(x_0)=0\pmod N,x_0<Bf(x0​)=0(modN),x0​<Band fd=1f_d=1fd​=1(otherwise multiplyfffby fd−1(modN)f_d^{-1}\pmod Nfd−1​(modN). Consider the polynomials gi(x)=Nxig_i(x)=Nx^igi​(x)=Nxiand consider the latticeLLLgenerated by f(Bx)f(Bx)f(Bx)and gi(Bx)g_i(Bx)gi​(Bx), 0≤i≤d−10\leq i\leq d-10≤i≤d−1. As a matrix, the basis vectors are

B=(N00…000NB0…0000NB2…00⋮⋮⋮⋱⋮⋮000…NBd−10f0f1Bf2B2…fd−1Bd−1Bd)\mathcal B=\begin{pmatrix} N&0&0&\dots&0&0\\ 0&NB&0&\dots&0&0\\ 0&0&NB^2&\dots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\dots&NB^{d-1}&0\\ f_0&f_1B&f_2B^2&\dots&f_{d-1}B^{d-1}&B^d\\ \end{pmatrix} B=​N00⋮0f0​​0NB0⋮0f1​B​00NB2⋮0f2​B2​………⋱……​000⋮NBd−1fd−1​Bd−1​000⋮0Bd​​

As every element in this lattice is some polynomial g(Bx)g(Bx)g(Bx), if f(x0)=0(modN)f(x_0)=0\pmod Nf(x0​)=0(modN), theng(x0)=0(modN)g(x_0)=0\pmod Ng(x0​)=0(modN). Furthermore, if ∣x0∣<B|x_0|<B∣x0​∣<Band a short vectorv(Bx)v(Bx)v(Bx)has length less than Nd+1\frac N{\sqrt{d+1}}d+1​N​, then we have v(x0)=0v(x_0)=0v(x0​)=0in R\mathbb RR.

The volume of this lattice is NdBd(d+1)2N^dB^{\frac{d(d+1)}2}NdB2d(d+1)​and the lattice has dimension d+1d+1d+1. By using the LLL algorithm, we can find a vector v(Bx)v(Bx)v(Bx) with length at most

∥v(Bx)∥2=(44δ−1)d4⏟cδ,dvol(L)1d+1=cδ,dNdd+1Bd2\left\lVert v(Bx)\right\rVert_2=\underbrace{\left(\frac4{4\delta-1}\right)^{\frac d4}}_{c_{\delta,d}}\text{vol}(L)^\frac1{d+1}=c_{\delta,d}N^{\frac d{d+1}}B^{\frac d2}∥v(Bx)∥2​=cδ,d​(4δ−14​)4d​​​vol(L)d+11​=cδ,d​Nd+1d​B2d​

As long as cδ,dNdd+1Bd2<Nd+1c_{\delta,d}N^{\frac d{d+1}}B^{\frac d2}<\frac N{\sqrt{d+1}}cδ,d​Nd+1d​B2d​<d+1​N​, then by the above criteria we know that this vector has x0x_0x0​has a root over R\mathbb RR. This tells us that

B<N2d(d+1)(cδ,dd+1)−2dB<N^{\frac2{d(d+1)}}\left(c_{\delta,d}\sqrt{d+1}\right)^{-\frac 2d}B<Nd(d+1)2​(cδ,d​d+1​)−d2​

While this isn't the N1dN^{\frac1d}Nd1​bound that we want, this gives us an idea of what we can do to achieve this bound, i.e. add more vectors such that the length of the shortest vector decreases.

Achieving the N1dN^{\frac1d}Nd1​bound

One important observation to make is that any coefficients in front ofNxN^xNxdoes not matter as we can simply brute force the top bits of our small root in O(1)O(1)O(1)time. Hence we only need to getB=kN1dB=kN^{\frac1d}B=kNd1​for some fixed constantkkk.

In order to achieve this, notice that if f(x0)=0(modN)f(x_0)=0\pmod Nf(x0​)=0(modN), then f(x0)h=0(modNh)f(x_0)^h=0\pmod{N^h}f(x0​)h=0(modNh). This loosens the inequality required for a polynomial to have x0x_0x0​as a small root as our modulus is now larger. With this in mind, consider the polynomials

gi,j(x)=Nh−jf(x)jxi0≤i<d,0≤j<hg_{i,j}(x)=N^{h-j}f(x)^jx^i\quad0\leq i<d,0\leq j<hgi,j​(x)=Nh−jf(x)jxi0≤i<d,0≤j<h

where we will determinehhhlater. Here gi,j(x0)=0(modNh)g_{i,j}(x_0)=0\pmod{N^h}gi,j​(x0​)=0(modNh), hence we shall consider the lattice LLL generated by gi,j(Bx)g_{i,j}(Bx)gi,j​(Bx). As an example, if we have

f(x)=x3+2x2+3x+4h=3f(x)=x^3+2x^2+3x+4\quad h=3f(x)=x3+2x2+3x+4h=3

the basis vectors of our lattice would look like

(N3000000000BN3000000000B2N30000004N23BN22B2N2B3N20000004BN23B2N22B3N2B4N20000004B2N23B3N22B4N2B5N200016N24BN25B2N20B3N10B4N4B5NB6N00016BN24B2N25B3N20B4N10B5N4B6NB7N00016B2N24B3N25B4N20B5N10B6N4B7NB8N)\footnotesize{\left(\begin{array}{rrrrrrrrr} N^{3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & B N^{3} & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & B^{2} N^{3} & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 \, N^{2} & 3 \, B N^{2} & 2 \, B^{2} N^{2} & B^{3} N^{2} & 0 & 0 & 0 & 0 & 0 \\ 0 & 4 \, B N^{2} & 3 \, B^{2} N^{2} & 2 \, B^{3} N^{2} & B^{4} N^{2} & 0 & 0 & 0 & 0 \\ 0 & 0 & 4 \, B^{2} N^{2} & 3 \, B^{3} N^{2} & 2 \, B^{4} N^{2} & B^{5} N^{2} & 0 & 0 & 0 \\ 16 \, N & 24 \, B N & 25 \, B^{2} N & 20 \, B^{3} N & 10 \, B^{4} N & 4 \, B^{5} N & B^{6} N & 0 & 0 \\ 0 & 16 \, B N & 24 \, B^{2} N & 25 \, B^{3} N & 20 \, B^{4} N & 10 \, B^{5} N & 4 \, B^{6} N & B^{7} N & 0 \\ 0 & 0 & 16 \, B^{2} N & 24 \, B^{3} N & 25 \, B^{4} N & 20 \, B^{5} N & 10 \, B^{6} N & 4 \, B^{7} N & B^{8} N \end{array}\right)}​N3004N20016N00​0BN303BN24BN2024BN16BN0​00B2N32B2N23B2N24B2N225B2N24B2N16B2N​000B3N22B3N23B3N220B3N25B3N24B3N​0000B4N22B4N210B4N20B4N25B4N​00000B5N24B5N10B5N20B5N​000000B6N4B6N10B6N​0000000B7N4B7N​00000000B8N​​

We have the following immediate computations of LLL:

dim⁡(L)=dhvol(L)=Ndh(h+1)2B(dh−1)dh2\dim(L)=dh\quad\text{vol}(L)=N^{\frac{dh(h+1)}2}B^{\frac{(dh-1)dh}2}dim(L)=dhvol(L)=N2dh(h+1)​B2(dh−1)dh​

hence when using the LLL algorithm, the shortest LLL basis vectorv(Bx)v(Bx)v(Bx)has length

∥v(Bx)∥2=(44δ−1)dim⁡(L)−14vol(L)1dim⁡(L)=(44δ−1)dh−14Nh+12Bdh−12\begin{align*} \left\lVert v(Bx)\right\rVert_2&=\left(\frac4{4\delta-1}\right)^{\frac{\dim(L)-1}4}\text{vol}(L)^{\frac1{\dim(L)}}\\ &=\left(\frac4{4\delta-1}\right)^{\frac{dh-1}4}N^{\frac{h+1}2}B^{\frac{dh-1}2}\\ \end{align*}∥v(Bx)∥2​​=(4δ−14​)4dim(L)−1​vol(L)dim(L)1​=(4δ−14​)4dh−1​N2h+1​B2dh−1​​

and we need ∥v(Bx)∥2<Nhdh\left\lVert v(Bx)\right\rVert_2<\frac{N^h}{\sqrt{dh}}∥v(Bx)∥2​<dh​Nh​for v(x0)=0v(x_0)=0v(x0​)=0. Hence we have

B<4δ−14(1dh)1dh−1Nh−1dh−1B<\sqrt{\frac{4\delta-1}4}\left(\frac1{dh}\right)^{\frac1{dh-1}}N^{\frac{h-1}{dh-1}}B<44δ−1​​(dh1​)dh−11​Ndh−1h−1​

Since lim⁡h→∞h−1dh−1=1d\lim_{h\to\infty}\frac{h-1}{dh-1}=\frac1dlimh→∞​dh−1h−1​=d1​, this will achieve the N1dN^{\frac1d}Nd1​bound that we want. However as for big hhh, the LLL algorithm would take a very long time, we typically choose a suitably largehhhsuch that the algorithm is still polynomial in log⁡N,d\log N,dlogN,dand brute force the remaining bits.

Exercises

1) We often see h=⌈max⁡(d+dε−1d2ϵ,7d)⌉h=\left\lceil\max\left(\frac{d+d\varepsilon-1}{d^2\epsilon},\frac7d\right)\right\rceilh=⌈max(d2ϵd+dε−1​,d7​)⌉in literature. We shall now show where this mysterious7d\frac7dd7​comes from. The other term will appear in the next exercise. Typically, one sets δ=34\delta=\frac34δ=43​to simplify calculations involving the LLL algorithm as 44δ−1=2\frac4{4\delta-1}=24δ−14​=2. Suppose we want B>12Nh−1dh−1B>\frac12N^{\frac{h-1}{dh-1}}B>21​Ndh−1h−1​, show that this gives us dh≥7dh\geq7dh≥7.

2) We show that we can indeed find small roots less thanN1dN^{\frac1d}Nd1​in polynomial time. In the worse case, the longest basis vector cannot exceed O(Bdh−1Nh)O\left(B^{dh-1}N^h\right)O(Bdh−1Nh). Hence the LLL algorithm will run in at mostO(d6h6(d+h)2log⁡2N)O(d^6h^6(d+h)^2\log^2N)O(d6h6(d+h)2log2N)time.

Let

ε=1d−h−1dh−1h=d+dε−1d2ϵ≈1dε\varepsilon=\frac1d-\frac{h-1}{dh-1}\quad h=\frac{d+d\varepsilon-1}{d^2\epsilon}\approx\frac1{d\varepsilon}ε=d1​−dh−1h−1​h=d2ϵd+dε−1​≈dε1​

and choose ε=1log⁡N\varepsilon=\frac1{\log N}ε=logN1​, then NεN^\varepsilonNεis a constant hence the number of bits needed to be brute forced is a constant. This gives us the approximate run time of O((d+1dlog⁡N)2log⁡8N)O((d+\frac1d\log N)^2\log^8N)O((d+d1​logN)2log8N).

3) We shall show that this is the best bound we can hope for using lattice methods. Suppose there exists some algorithm that finds roots less than O(N1d+ϵ)O\left(N^{\frac1d+\epsilon}\right)O(Nd1​+ϵ)in polynomial time. Then consider the case whenN=p2N=p^2N=p2and f(x)=x2+pxf(x)=x^2+pxf(x)=x2+px. Show that this forces the lattice to have a size too big for the algorithm to run in polynomial time, assuming the algorithm finds all small roots.

LLL reduced

Definition

Let δ∈(14,1)\delta\in\left(\frac14,1\right)δ∈(41​,1). A basis{bi}i=1d\left\{b_i\right\}_{i=1}^d{bi​}i=1d​is δ\deltaδ- LLL-reduced if it is size reduced and satisfy the Lovász condition, i.e.

δ∥bi∗∥2≤∥bi+1∗+μi+1,ibi∗∥2\delta\left\lVert b_i^*\right\rVert^2\leq\left\lVert b_{i+1}^*+\mu_{i+1,i}b_i^*\right\rVert^2δ∥bi∗​∥2≤​bi+1∗​+μi+1,i​bi∗​​2

This notion of reduction is most useful to use for fast algorithms as such a basis can be found in polynomial time (see LLL reduction).

Bounds

∥b1∥≤(44δ−1)d−14vol(L)1d∥bi∥≤(44δ−1)d−12λi(L)∏i=1d∥bi∥≤(44δ−1)d(d−1)4vol(L)\begin{align*} \left\lVert b_1\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d-1}4}\text{vol}(L)^\frac1d\\ \left\lVert b_i\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d-1}2}\lambda_i(L)\\ \prod_{i=1}^d\left\lVert b_i\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d(d-1)}4}\text{vol}(L) \end{align*}∥b1​∥∥bi​∥i=1∏d​∥bi​∥​≤(4δ−14​)4d−1​vol(L)d1​≤(4δ−14​)2d−1​λi​(L)≤(4δ−14​)4d(d−1)​vol(L)​

Gram-Schmidt Orthogonalization

Overview

Gram-Schmidt orthogonalization is an algorithm that takes in a basis {bi}i=1n\left\{b_i\right\}_{i=1}^n{bi​}i=1n​ as an input and returns a basis {bi∗}i=1n\left\{b_i^*\right\}_{i=1}^n{bi∗​}i=1n​where all vectors are orthogonal, i.e. at right angles. This new basis is defined as

bi∗=bi−∑j=1i−1μi,jbj∗μi,j=⟨bi,bj∗⟩⟨bj∗,bj∗⟩b_i^*=b_i-\sum_{j=1}^{i-1}\mu_{i,j}b_j^*\quad\mu_{i,j}=\frac{\langle b_i,b_j^*\rangle}{\langle b_j^*,b_j^*\rangle}bi∗​=bi​−j=1∑i−1​μi,j​bj∗​μi,j​=⟨bj∗​,bj∗​⟩⟨bi​,bj∗​⟩​

where μi,j\mu_{i,j}μi,j​is the Gram-Schmidt coefficients.

One can immediately check that this new basis is orthogonal, meaning

⟨bi∗,bj∗⟩={0i≠j∥bi∗∥2i=j\langle b_i^*,b_j^*\rangle=\begin{cases}0&i\neq j\\\left\lVert b_i^*\right\rVert^2&i=j\end{cases}⟨bi∗​,bj∗​⟩={0∥bi∗​∥2​i=ji=j​

Let B\mathcal BBbe the matrix where the iiith row is given by bib_ibi​andB∗\mathcal B^*B∗be the matrix where the iiith row is given by bi∗b_i^*bi∗​, then the Gram-Schmidt orthogonalization gives us B=μB∗\mathcal B=\mu\mathcal B^*B=μB∗where μi,i=1,μj,i=0\mu_{i,i}=1,\mu_{j,i}=0μi,i​=1,μj,i​=0and μi,j\mu_{i,j}μi,j​is the Gram-Schmidt coefficient. As an example, consider the basis of a subspace of R4\mathbb R^4R4:

b1=(−1−231)b2=(−6−451)b3=(551−3)\begin{matrix} b_1 &= & (&-1&-2&3&1&)\\ b_2 &= & (&-6&-4&5&1&)\\ b_3 &= & (&5&5&1&-3&) \end{matrix}b1​b2​b3​​===​(((​−1−65​−2−45​351​11−3​)))​

Instead of doing the Gram-Schmidt orthogonalization by hand, we can get sage to do it for us:

B = Matrix([
[-1, -2, 3, 1],
[-6, -4, 5, 1],
[5, 5, 1, -3]])

B.gram_schmidt()

This outputs two matrices, B∗\mathcal B^*B∗and μ\muμ:

(
[-1 -2  3  1]  [ 1  0  0]
[-4  0 -1 -1]  [ 2  1  0]
[ 0  3  3 -3], [-1 -1  1]
)

One can quickly verify that B=μB∗\mathcal B=\mu\mathcal B^*B=μB∗ and that the rows of B∗\mathcal B^*B∗are orthogonal to each other.

A useful result is that

det⁡(BBT)=det⁡(B∗B∗T)=∏i∥bi∗∥\det\left(\mathcal B\mathcal B^T\right)=\det\left(\mathcal B^*\mathcal B^{*T}\right)=\prod_i\left\lVert b_i^*\right\rVertdet(BBT)=det(B∗B∗T)=i∏​∥bi∗​∥

Intuitively, this tells us that the more orthogonal a set of basis for a lattice is, the shorter it is as the volume must be constant.

Exercises

1) Show that the basis bi∗b_i^*bi∗​is orthogonal.

2) Verify that the output of sage is indeed correct.

3) Show that μμT=1\mu\mu^T=1μμT=1and B∗B∗T\mathcal B^*\mathcal B^{*T}B∗B∗T is a diagonal matrix whose entries are ∥bi∗∥\left\lVert b_i^*\right\rVert∥bi∗​∥. Conclude that det⁡(BBT)=det⁡(B∗B∗T)=∏i∥bi∗∥\det\left(\mathcal B\mathcal B^T\right)=\det\left(\mathcal B^*\mathcal B^{*T}\right)=\prod_i\left\lVert b_i^*\right\rVertdet(BBT)=det(B∗B∗T)=∏i​∥bi∗​∥.

4*) Given the Iwasawa decomposition B=LDO\mathcal B=LDOB=LDOwhere LLLis a lower diagonal matrix with 111on its diagonal, DDDis a diagonal matrix and OOOan orthogonal matrix, meaning OOT=1OO^T=1OOT=1, show that B∗=DO\mathcal B^*=DOB∗=DOand μ=L\mu=Lμ=L. Furthermore, prove that such a decomposition is unique.

Extensions of Coppersmith algorithm

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 factorbbbofNNNsuch that b<Nβb<N^\betab<Nβand some monic polynomialfffof degreedddsuch that f(x0)=0(modb)f(x_0)=0\pmod bf(x0​)=0(modb)for some x0<Nβ2dx_0<N^{\frac{\beta^2}d}x0​<Ndβ2​. Then we can findx0x_0x0​in time polynomial in log⁡N,d\log N,dlogN,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. ∥f(Bx)∥2≤bd+1≤Nβd+1\left\lVert f(Bx)\right\rVert_2\leq\frac b{\sqrt{d+1}}\leq\frac{N^{\beta}}{\sqrt{d+1}}∥f(Bx)∥2​≤d+1​b​≤d+1​Nβ​is sufficient for a root less thanBBBto 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

gi,j(x)=Nh−jf(x)jxi0≤i<d,0≤j<hgi,h(x)=f(x)hxi0≤i<t\begin{align*} g_{i,j}(x)&=N^{h-j}f(x)^jx^i&0\leq i<d,0\leq j<h\\ g_{i,h}(x)&=f(x)^hx^i&0\leq i<t \end{align*}gi,j​(x)gi,h​(x)​=Nh−jf(x)jxi=f(x)hxi​0≤i<d,0≤j<h0≤i<t​

The latticeLLLgenerated by these polynomials would have

dim⁡(L)=dh+t=nvol(L)=Ndh(h+1)2B(n−1)n2\dim(L)=dh+t=n\quad\text{vol}(L)=N^{\frac{dh(h+1)}{2}}B^{\frac{(n-1)n}2}dim(L)=dh+t=nvol(L)=N2dh(h+1)​B2(n−1)n​

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

B<4δ−14(1n)1n−1N2βhn−1−dh(h+1)n(n−1)B<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}}B<44δ−1​​(n1​)n−11​Nn−12βh​−n(n−1)dh(h+1)​

It turns out that the maxima of 2βhn−1−dh(h+1)n(n−1)\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}n−12βh​−n(n−1)dh(h+1)​is β2d\frac{\beta^2}ddβ2​as n,h→∞n,h\to\inftyn,h→∞. One way to achieve this is by settingn=dβhn=\frac d\beta hn=βd​hand we obtain

B<4δ−14(1n)1n−1N(h−1)β2dh−βB<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{(h-1)\beta^2}{dh-\beta}}B<44δ−1​​(n1​)n−11​Ndh−β(h−1)β2​

and this indeed achieves the O(Nβ2d)O\left(N^{\frac{\beta^2}d}\right)O(Ndβ2​)bound. Similar to the Coppersmith algorithm, one chooses a sufficiently big h,nh,nh,nsuch 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 of2βhn−1−dh(h+1)n(n−1)\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}n−12βh​−n(n−1)dh(h+1)​is indeed β2d\frac{\beta^2}ddβ2​. We can assume that d≥2,h≥1,0<β≤1,n≥2d\geq2,h\geq1,0<\beta\leq1,n\geq2d≥2,h≥1,0<β≤1,n≥2. Since hn−1(2β−dh+1n)\frac h{n-1}\left(2\beta-d\frac{h+1}{n}\right)n−1h​(2β−dnh+1​)and hn−1<h+1n\frac h{n-1}<\frac{h+1}nn−1h​<nh+1​, the maximum occurs when h,n→∞h,n\to\inftyh,n→∞and hn−1,h+1n→x\frac h{n-1},\frac{h+1}n\to xn−1h​,nh+1​→x, hence we have reduced this to maximizing 2βx−dx22\beta x-dx^22βx−dx2which achieves its maximum of β2d\frac{\beta^2}ddβ2​ at x=βdx=\frac\beta dx=dβ​.

Learning with errors (LWE)

Cryptographic lattice problems

RSA

Will be introduced in this page the fundamentals of RSA, mathematical requirement and also some application with python and openSSL.

This page is pretty long, probably could be split up

Edit: I haved deleted the last part, application with RSA, and i made a special part for this. Maybe we can do the same with the second part: Arithmetic for RSA.

I- Introduction:

RSA is a public-key cryptosystem that is widely used in the world today to provide a secure transmission system to millions of communications, is one of the oldest such systems in existence. The acronym RSA comes from the surnames of Ron Rivest, Adi Shamir, and Leonard Adleman, who publicly described the algorithm in 1977. An equivalent system was developed secretly, in 1973 at GCHQ (the British signals intelligence agency), by the English mathematician Clifford Cocks. That system was declassified in 1997.

All public-key systems are based on the concept of trapdoor functions, functions that are simple to compute in one direction but computationally hard to reverse without knowledge of some special information called the trapdoor. In RSA, the trapdoor function is based on the hardness of factoring integers. The function involves the use of a public keyNN Nto encrypt data, which is (supposed to be) encrypted in such a way that the function cannot be reversed without knowledge of the prime factorisation ofNN N, something that should be kept private. Except in certain cases, there exists no efficient algorithm for factoring huge integers.

Further reading: Shor's algorithm

Formalize the introduction and include a discussion of the security based on the hardness of factoring integers.

II- Arithmetic for RSA

Before starting to introducing you RSA, a few arithmetic notions need to be introduce to understand perfectly other steps.

III- Key generation

  • We pick two primes ppp and qqq

  • Using ppp and qqq, we calculate modulus n=p×qn = p\times qn=p×q and its Euler's totient ϕ(n)=(p−1)×(q−1)\phi(n) = (p-1) \times (q-1)ϕ(n)=(p−1)×(q−1)

  • Now, choose the public exponent e\mathbb{e}esuch as gcd(e,ϕ(n))=1\mathbb{gcd(e, \phi(n)) = 1}gcd(e,ϕ(n))=1

  • By using the Extended Euclidean algorithm, we compute the invert d\mathbb{d}d of emod  n\mathbb{e \mod n}emodn :d≡e−1mod  ϕ(n)d \equiv e^{-1} \mod \phi(n)d≡e−1modϕ(n) which is our private exponent.

  • Public key: n,en, en,e

  • Private key: n,dn, dn,d

  • Now, chose a message m\mathbb{m}mthat you convert into integers

  • We can encrypt this plaintext mmm and receive a ciphertext c≡memod  nc \equiv m^e \mod nc≡memodn

  • We can decrypt a ciphertext ccc with m≡cdmod  nm \equiv c^d \mod nm≡cdmodn

IV- Signature

A digital signature is a proof of the authenticity of a message, i.e. a proof that the message has not been tampered with. RSA allows us to sign messages by "encrypting" them using the private key, the result being a signature that anyone can verify by "decrypting" it with the public key and comparing it to the associated message. Any attempt to tamper with the message will result in it no longer matching the signature, and vice-versa. Futhermore, a signature can only be generated using the private key, making it a secure and efficient method of confirming the authenticity of messages.

Say Alice wants to send a message to Bob, but does not want Mallory, who has established herself as a middleman, to make changes to the message or swap it out entirely. Fortunately, Bob knows Alice's public key, and since eee and ddd are inverses such that ed≡1mod  ϕ(n)ed \equiv 1\mod \phi(n)ed≡1modϕ(n), Alice can sign her message mmm by "encrypting" it with the private key such that s≡mdmod  ns \equiv m^d \mod ns≡mdmodn, where sss is the signature verifying that the message came from Alice. Alice can now send mmm and sss to Bob, who is now able to check the authenticity of the message by checking if m≡semod  nm \equiv s^e \mod nm≡semodn. If Mallory tries to change mmm, this congruence no longer holds, and since she does not have the private key, she is also unable to provide a maching sssfor her tampered message.

V- Format

NTRU

Ring-LWE

Low Private Component Attacks

LLL
Rn\mathbb{R}^nRn
bib_ibi​
L=∑i=1dZbi={∑i=1daibi∣ai∈Z}L=\sum_{i=1}^d\mathbb{Z} b_i = \left\{\left. \sum_{i=1}^d a_i b_i \right | a_i \in \mathbb{Z} \right\}L=i=1∑d​Zbi​={i=1∑d​ai​bi​​ai​∈Z}
bib_ibi​
{bi}i=1d\left\{b_i\right\}_{i=1}^d{bi​}i=1d​
LLL
viv_ivi​
∑iaibi=0\sum_{i} a_i b_i = 0∑i​ai​bi​=0
aia_iai​
dim⁡L\dim LdimL
ddd
d=nd=nd=n
Rn\mathbb R^nRn
bib_ibi​
Φ={∑i=1dxibi∣0≤xi<1}\Phi=\left\{\left.\sum_{i=1}^dx_ib_i\right|0\leq x_i<1\right\}Φ={i=1∑d​xi​bi​​0≤xi​<1}
R2\mathbb R^2R2
mmm
B\mathcal BB
d×nd\times nd×n
vol(L)=∣det⁡(BBT)∣\text{vol}(L)=\sqrt{\left|\det\left(\mathcal B\mathcal B^T\right)\right|}vol(L)=∣det(BBT)∣​
XXX
Rn\mathbb R^nRn
x∈Xx\in Xx∈X
−x∈X-x\in X−x∈X
x,y∈Xx,y\in Xx,y∈X
x,yx,yx,y
XXX
{tx+(1−t)y∣0≤t≤1}⊂X\left\{tx+(1-t)y|0\leq t\leq1\right\}\subset X{tx+(1−t)y∣0≤t≤1}⊂X
LLL
nnn
XXX
vol(X)>2nvol(L)\text{vol}(X)>2^n\text{vol}(L)vol(X)>2nvol(L)
XXX
LL L
∥v∥=∑ivi2\left\lVert v\right\rVert=\sqrt{\sum_iv_i^2}∥v∥=∑i​vi2​​
ℓ2\ell_2ℓ2​
⟨a,b⟩=∑iaibi\langle a,b\rangle=\sum_ia_ib_i⟨a,b⟩=∑i​ai​bi​
12X={12x∣x∈X}\frac12X=\left\{\frac12x|x\in X\right\}21​X={21​x∣x∈X}
vol(12X)>vol(L)\text{vol}\left(\frac12 X\right)>\text{vol}(L)vol(21​X)>vol(L)
12X→Rn/L\frac12X\to\mathbb R^n/L21​X→Rn/L
x1=x2+ℓx_1=x_2+\ellx1​=x2​+ℓ
x1,x2∈12X,ℓ∈L,x1≠x2x_1,x_2\in\frac12 X,\ell\in L,x_1\neq x_2x1​,x2​∈21​X,ℓ∈L,x1​=x2​
x1−x2∈Lx_1-x_2\in Lx1​−x2​∈L
LLL
B=(−1981−8−7)\mathcal B=\begin{pmatrix}-1&9&8\\1&-8&-7\end{pmatrix}B=(−11​9−8​8−7​)
B′=(101011)\mathcal B'=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}B′=(10​01​11​)
C=(101022)\mathcal C=\begin{pmatrix}1&0&1\\0&2&2\end{pmatrix}C=(10​02​12​)
C\mathcal CC
B,B′\mathcal B,\mathcal B'B,B′
d×nd\times nd×n
L,L′L,L'L,L′
U∈GLd(Z)U\in\text{GL}_d(\mathbb Z)U∈GLd​(Z)
B′=UB\mathcal B'=U\mathcal BB′=UB
UUU
GLd(Z)\text{GL}_d(\mathbb Z)GLd​(Z)
UUU
U−1U^{-1}U−1
LLL
nnn
XXX
vol(X)=2nvol(L)\text{vol}(X)=2^n\text{vol}(L)vol(X)=2nvol(L)
XXX
vvv
LLL
nnn
∥v∥≤2πΓ(n2+1)1nvol(L)1n\left\lVert v\right\rVert\leq\frac2{\sqrt\pi}\Gamma\left(\frac n2+1\right)^{\frac1n}\text{vol}(L)^\frac1n∥v∥≤π​2​Γ(2n​+1)n1​vol(L)n1​
def euclid(m,n):
    while n!=0:
        q = round(m/n)
        m -= q*n
        if abs(n) > abs(m):
            m, n = n, m
    return abs(m)
mmm
nnn
mmm
def lagrange(b1,b2):
    mu = 1
    while mu != 0:
        mu = round((b1*b2) / (b1*b1))
        b2 -= mu*b1
        if b1*b1 > b2*b2:
            b1, b2 = b2, b1
    return b1, b2
μ\muμ
μ2,1\mu_{2,1}μ2,1​
b1=(−1.8,1.2)b2=(−3.6,2.3)\begin{matrix} b_1&=&(-1.8,1.2)\\ b_2&=&(-3.6,2.3) \end{matrix}b1​b2​​==​(−1.8,1.2)(−3.6,2.3)​
LLL
b1,b2b_1,b_2b1​,b2​
b1′,b2′,∥b1′∥≤∥b2′∥b_1',b_2',\left\lVert b_1'\right\rVert\leq\left\lVert b_2'\right\rVertb1′​,b2′​,∥b1′​∥≤∥b2′​∥
∥b1∥≤∥b1′∥\left\lVert b_1\right\rVert\leq\left\lVert b_1'\right\rVert∥b1​∥≤∥b1′​∥
∥b2∥≤∥b2′∥\left\lVert b_2\right\rVert\leq\left\lVert b_2'\right\rVert∥b2​∥≤∥b2′​∥
b1,b2b_1,b_2b1​,b2​
LLL
∥b1∥\left\lVert b_1\right\rVert∥b1​∥
LLL
∣⟨b1,b2⟩∣∥b1∥2≤12\frac{\left|\langle b_1,b_2\rangle\right|}{\left\lVert b_1\right\rVert^2}\le\frac12∥b1​∥2∣⟨b1​,b2​⟩∣​≤21​
v=mb1+nb2∈Lv=mb_1+nb_2\in Lv=mb1​+nb2​∈L
LLL
∥b1∥≤∥v∥\left\lVert b_1\right\rVert\leq\left\lVert v\right\rVert∥b1​∥≤∥v∥
∥v∥2=∥mb1+nb2∥2=m2∥b1∥2+2mn⟨b1,b2⟩+n2∥b2∥2≥m2∥b1∥2−∣mn∣∥b1∥2+n2∥b1∥2=(m2−∣mn∣+n2)∥b1∥2\begin{align*} \left\lVert v\right\rVert^2&=\left\lVert mb_1+nb_2\right\rVert^2\\ &=m^2\left\lVert b_1\right\rVert^2+2mn\langle b_1,b_2\rangle+n^2\left\lVert b_2\right\rVert^2\\ &\geq m^2\left\lVert b_1\right\rVert^2-|mn|\left\lVert b_1\right\rVert^2+n^2\left\lVert b_1\right\rVert^2\\ &=\left(m^2-|mn|+n^2\right)\left\lVert b_1\right\rVert^2\\ \end{align*}∥v∥2​=∥mb1​+nb2​∥2=m2∥b1​∥2+2mn⟨b1​,b2​⟩+n2∥b2​∥2≥m2∥b1​∥2−∣mn∣∥b1​∥2+n2∥b1​∥2=(m2−∣mn∣+n2)∥b1​∥2​
m2−mn+n2=(m−n2)2+34n2m^2-mn+n^2=\left(m-\frac n2\right)^2+\frac34n^2m2−mn+n2=(m−2n​)2+43​n2
000
m=n=0m=n=0m=n=0
∥v∥≥∥b1∥\left\lVert v\right\rVert\geq\left\lVert b_1\right\rVert∥v∥≥∥b1​∥
∥b1∥\left\lVert b_1\right\rVert∥b1​∥
LLL
b1b_1b1​
−b1-b_1−b1​
b1′,b2′b'_1,b'_2b1′​,b2′​
LLL
∥b1′∥≤∥b2′∥\left\lVert b_1'\right\rVert\leq\left\lVert b_2'\right\rVert∥b1′​∥≤∥b2′​∥
∥b2∥≤∥b2′∥\left\lVert b_2\right\rVert\leq\left\lVert b_2'\right\rVert∥b2​∥≤∥b2′​∥
b2′=mb1+nb2b_2'=mb_1+nb_2b2′​=mb1​+nb2​
n=0n=0n=0
b2′=±b1b_2'=\pm b_1b2′​=±b1​
b1′,b2′b_1',b_2'b1′​,b2′​
∥b1∥=∥b1′∥=∥b2′∥\left\lVert b_1\right\rVert=\left\lVert b_1'\right\rVert=\left\lVert b_2'\right\rVert∥b1​∥=∥b1′​∥=∥b2′​∥
±b1′=b2\pm b_1'=b_2±b1′​=b2​
±b1′=b1+b2\pm b_1'=b_1+b_2±b1′​=b1​+b2​
∥b1′∥=∥b2∥\left\lVert b'_1\right\rVert=\left\lVert b_2\right\rVert∥b1′​∥=∥b2​∥
∥b1′∥2=∥b1+b2∥2∥b1′∥2=∥b1∥2+2⟨b1,b2⟩+∥b2∥20=2⟨b1,b2⟩+∥b2∥2∥b1∥2≤∥b2∥2\begin{align*} \left\lVert b'_1\right\rVert^2&=\left\lVert b_1+b_2\right\rVert^2\\ \left\lVert b'_1\right\rVert^2&=\left\lVert b_1\right\rVert^2+2\langle b_1,b_2\rangle+\left\lVert b_2\right\rVert^2\\ 0&=2\langle b_1,b_2\rangle+\left\lVert b_2\right\rVert^2\\ \left\lVert b_1\right\rVert^2&\leq\left\lVert b_2\right\rVert^2\\ \end{align*}∥b1′​∥2∥b1′​∥20∥b1​∥2​=∥b1​+b2​∥2=∥b1​∥2+2⟨b1​,b2​⟩+∥b2​∥2=2⟨b1​,b2​⟩+∥b2​∥2≤∥b2​∥2​
∥b1∥\left\lVert b_1\right\rVert∥b1​∥
∥b1∥=∥b2∥\left\lVert b_1\right\rVert=\left\lVert b_2\right\rVert∥b1​∥=∥b2​∥
m,n≠0m,n\neq0m,n=0
m2−mn+n2≥1m^2-mn+n^2\geq1m2−mn+n2≥1
∥b2′∥2=m2∥b1∥2+2mn⟨b1,b2⟩+n2∥b2∥2≥m2∥b1∥2−∣mn∣∥b1∥2+n2∥b2∥2=n2(∥b2∥2−∥b1∥2)+(m2−∣mn∣+n2)∥b1∥2≥(n2−1)(∥b2∥2−∥b1∥2)+∥b2∥2≥∥b2∥2\begin{align*} \left\lVert b'_2\right\rVert^2&=m^2\left\lVert b_1\right\rVert^2+2mn\langle b_1,b_2\rangle+n^2\left\lVert b_2\right\rVert^2\\ &\geq m^2\left\lVert b_1\right\rVert^2-|mn|\left\lVert b_1\right\rVert^2+n^2\left\lVert b_2\right\rVert^2\\ &=n^2\left(\left\lVert b_2\right\rVert^2-\left\lVert b_1\right\rVert^2\right)+\left(m^2-|mn|+n^2\right)\left\lVert b_1\right\rVert^2\\ &\geq\left(n^2-1\right)\left(\left\lVert b_2\right\rVert^2-\left\lVert b_1\right\rVert^2\right)+\left\lVert b_2\right\rVert^2\\ &\geq\left\lVert b_2\right\rVert^2 \end{align*}∥b2′​∥2​=m2∥b1​∥2+2mn⟨b1​,b2​⟩+n2∥b2​∥2≥m2∥b1​∥2−∣mn∣∥b1​∥2+n2∥b2​∥2=n2(∥b2​∥2−∥b1​∥2)+(m2−∣mn∣+n2)∥b1​∥2≥(n2−1)(∥b2​∥2−∥b1​∥2)+∥b2​∥2≥∥b2​∥2​
∥b1∥=∥b2∥=∥b1+b2∥\left\lVert b_1\right\rVert=\left\lVert b_2\right\rVert=\left\lVert b_1+b_2\right\rVert∥b1​∥=∥b2​∥=∥b1​+b2​∥
μ2,1=⌊μ2,1⌉+ε=μ+ϵ\mu_{2,1}=\lfloor\mu_{2,1}\rceil+\varepsilon=\mu+\epsilonμ2,1​=⌊μ2,1​⌉+ε=μ+ϵ
∥b2∥2≥((∣μ∣−12)2−ε2)∥b1∥2+∥b2−μb1∥\left\lVert b_2\right\rVert^2\geq\left(\left(|\mu|-\frac12\right)^2-\varepsilon^2\right)\left\lVert b_1\right\rVert^2+\left\lVert b_2-\mu b_1\right\rVert∥b2​∥2≥((∣μ∣−21​)2−ε2)∥b1​∥2+∥b2​−μb1​∥
∣μ∣≥2|\mu|\geq2∣μ∣≥2
∥b1∥∥b2∥\left\lVert b_1\right\rVert\left\lVert b_2\right\rVert∥b1​∥∥b2​∥
3\sqrt33​
https://arxiv.org/abs/1009.4322

Hard lattice problems

This section is not complete. Help is needed with relevance + examples in cryptography, algorithms + hardness, relations between problems.

Also needs review from more experienced people.

Introduction

Now that we are comfortable with lattices we shall study why are they important to cryptography.

Like we said, when we construct cryptosystems we usually are looking for hard problems to base them on. The lattice world provides us with such problems such as the shortest vector problem or the closest vector problem.

What makes lattices even more special is that some cryptographic problems (which we will study in the next chapter) can be reduced to worst-case lattice problems which makes them crazy secure. Moreover, some problems are even secure against quantum computers.

But enough talk, let's get right into it!

Shortest vector problem + GapSVP

Before we go into any problems we must first define the concept of distance in a lattice.

Let:

  • L=L= L= Lattice

  • B=\mathcal B = B= the basis of the lattice

  • n=n = n=the dimension of the lattice

Distance function

Given some distance function (Example: Euclidean norm) the distance from a vector ttt to the lattice LLL is the distance from the vector to the closest point in the in lattice.

μ(t,L)=min⁡v∈L∥t−v∥\mu(t, L) = \underset{v \in \mathcal{L}}{\min}{\|t-v\|}μ(t,L)=v∈Lmin​∥t−v∥

We will denote the length of the shortest vector with ∥v∥=λ1(L)\|v\| = \lambda_1(L)∥v∥=λ1​(L)and the length of the next independent vectors in order with λi(L)⇒λ1(L)≤λ2(L)≤...≤λn(L)\lambda_i(L) \Rightarrow\lambda_1({L}) \leq \lambda_2({L}) \leq ... \leq \lambda_n({L})λi​(L)⇒λ1​(L)≤λ2​(L)≤...≤λn​(L)

Shortest vector problem

Given a lattice LLL and an arbitrary basis B\mathcal{B}B for it our task is to find the shortest vector v∈Lv \in Lv∈L.

Approximate SVP

We relax the SVP problem a bit. Given an arbitrary basis B\mathcal{B}Bfind a shortest nonzero lattice vector v∈Lv \in Lv∈Lsuch that v<γ(n)⋅λ1(L)v < \gamma(n)\cdot \lambda_1(L)v<γ(n)⋅λ1​(L). Here γ(n)>1\gamma(n) > 1γ(n)>1is some approximation factor.

Decision SVP (GapSVP)

Given a lattice LLLwith a basis B\mathcal BB we must distinguish if λ1(L)≤1\lambda_1(L) \leq 1λ1​(L)≤1 or λ>γ(n)\lambda > \gamma(n)λ>γ(n)

Sage example

# We can find the shortest vector using the LLL algorithm
M = matrix([[-1, 2], [-2, 3]])
B = M.LLL()
print(B[0])
# (0, -1)

# Or we can use the Integer Lattice class
L = IntegerLattice(M)
L.shortest_vector()
# (-1, 0)

Closest Vector problem + GapCVP

Closest vector problem

Given a lattice LLL with an arbitrary basis B\mathcal BB and a vector w∈Rnw \in \mathbb{R}^nw∈Rn find the closest lattice vector to www v∈L,∥v−w∥≤μv \in {L}, \|v-w\| \leq \muv∈L,∥v−w∥≤μ

Approximate CVP

Given a lattice LLL with an arbitrary basis B\mathcal BB and a vector w∈Rnw \in \mathbb{R}^nw∈Rn find the closest lattice vector to www v∈L,∥v−w∥<γ(n)⋅μv \in {L}, \|v-w\| < \gamma(n) \cdot \muv∈L,∥v−w∥<γ(n)⋅μ

Decision CVP (GapCVP)

Given a lattice LLLwith a basis B\mathcal BB and a vector www we must decide if

  • There exists v∈Lv \in Lv∈Ls.t ∥v−w∥≤1\| v - w\| \leq 1∥v−w∥≤1

  • ∀v∈L:∥v−w∥>γ(n)\forall v \in L: \|v - w\| > \gamma(n)∀v∈L:∥v−w∥>γ(n)

Sage example

M = matrix([[-1, 2], [-2, 3]])
L = IntegerLattice(M)

w = vector([1.8, 1.5])
L.closest_vector(w)
# (2.00000000000000, 2.00000000000000)

Bounded distance decoding

Given a lattice LLL with an arbitrary basis BBB, a vector w∈Rnw \in \mathbb{R}^nw∈Rn and a real number d∈Rd \in \mathbb{R}d∈R find a lattice vector v∈Lv \in {L}v∈L s.t ∥w−v∥<d⋅λ1(L)\|w-v\| < d \cdot \lambda_1({L})∥w−v∥<d⋅λ1​(L)

Remark

  • If we have d<12d < \dfrac 12d<21​ the solution to the BDD problem is guaranteed to be unique.

Shortest independent vectors (SIVP)

Given a full rank lattice LLL with an arbitrary basis B\mathcal BBfind nnn linearly independent lattice vectors of length at most λn(L)⇒max⁡i∥vi∥≤λn(L)\lambda_n(L) \Rightarrow \max_i\|v_i\| \leq \lambda_n(L)λn​(L)⇒maxi​∥vi​∥≤λn​(L) or max⁡i∣vi∣≤γ(n)λn(L)\max_i|v_i| \leq \gamma(n) \lambda_n(L)maxi​∣vi​∣≤γ(n)λn​(L)for the approximate version.

Hardness of lattice problems

Resources

  • Pictures taken from https://simons.berkeley.edu/sites/default/files/docs/14953/intro.pdf and "Cryptography made simple - Nigel Smart" and edited a bit

  • Or generated by me

Lattices of interest

Needs review.

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⊂RnL \subset \mathbb R^nL⊂Rnbe a lattice. We define the dual of a lattice as the set of all vectors y∈span(L)y \in span(L)y∈span(L) such that y⋅x∈Z y \cdot x \in \mathbb Z \ y⋅x∈Z for all vectors x∈Lx \in Lx∈L:

L∨={y∈span(L):y⋅x∈Z ∀ x∈L}L^\vee = \{y \in span(L) : y \cdot x \in \mathbb{Z} \ \forall \ x \in L\}L∨={y∈span(L):y⋅x∈Z ∀ x∈L}

Note that the vectors in the dual lattice L∨L^\veeL∨ are not necessarily in the initial lattice LLL. They are spanned by the basis vectors of the lattice LLL.

Examples:

  1. (Zn)∨=Zn(\mathbb Z^n) ^ \vee = \mathbb Z^n(Zn)∨=Zn because the dot product of all vectors in Zn\mathbb Z^nZnstays in Zn\mathbb Z^nZn

  2. Scaling: (k⋅L)∨=1k⋅L(k \cdot L)^\vee = \dfrac 1 k \cdot L(k⋅L)∨=k1​⋅L Proof: If y∈(kL)∨⇒y⋅kx=k(x⋅y)∈Z ∀ x∈L⇒y∈1kL∨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^\veey∈(kL)∨⇒y⋅kx=k(x⋅y)∈Z ∀ x∈L⇒y∈k1​L∨ If y∈(1kL)∨⇒yv∈L∨⇒ky⋅x=k(x⋅y)=y⋅kx∈Z ∀ x ∈L⇒y∈(kL)∨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)^\veey∈(k1​L)∨⇒yv∈L∨⇒ky⋅x=k(x⋅y)=y⋅kx∈Z ∀ x ∈L⇒y∈(kL)∨

Plot: 2Z22\mathbb Z ^22Z2 - green, 12Z2\dfrac 1 2 \mathbb Z ^ 221​Z2 - red

Intuition: We can think of the dual lattice L∨L^\veeL∨ as some kind of inverse of the initial lattice LLL

Basis of the dual lattice

We will now focus on the problem of finding the basis B∨B^\veeB∨ of the dual lattice L∨L^\veeL∨given the lattice LLL and its basis BBB.

Reminder: We can think of the lattice LLL as a transformation given by its basis B∈GLn(R)B \in GL_n(\mathbb R)B∈GLn​(R)on Zn\mathbb Z^nZn.

We have the following equivalences:

y∈L∨  ⟺  y⋅x∈Z ∀ x∈L  ⟺  BTy∈Zn  ⟺  y∈(B−1)T⋅Zn\begin{align*} y \in L^\vee & \iff y \cdot x \in \mathbb Z \ \forall\ x \in L \\ & \iff B^Ty \in \mathbb{Z}^n \\ & \iff y \in (B^{-1})^T \cdot \mathbb Z^n \end{align*}y∈L∨​⟺y⋅x∈Z ∀ x∈L⟺BTy∈Zn⟺y∈(B−1)T⋅Zn​

Therefore L∨=(B−1)T⋅ZnL^\vee = (B^{-1})^T \cdot \mathbb Z^nL∨=(B−1)T⋅Znso we have found a base for our dual lattice:

B∨=(B−1)T∈GLn(R)B^\vee = (B^{-1})^T \in GL_n(\mathbb{R})B∨=(B−1)T∈GLn​(R)
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. L1⊆L2  ⟺  L2∨⊆L1∨{L}_1 \subseteq {L}_2 \iff {L}^\vee_2 \subseteq {L}^\vee_1L1​⊆L2​⟺L2∨​⊆L1∨​

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

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

  4. For x∈L,y∈L∨x \in {L}, y \in {L}^\veex∈L,y∈L∨consider the vector dot product and addition - x⋅y∈Zx \cdot y \in \mathbb{Z}x⋅y∈Z - x+yx + yx+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 LLL and its dual L∨L^\veeL∨. Let's see what can we uncover about them.

We recommend to try and think about the problem for a few minutes before reading the conclusions.

What is λ1(2Z2)\lambda_1(2\mathbb Z^2)λ1​(2Z2)? What about λ1((2Z2)∨)\lambda_1((2\mathbb Z^2)^\vee)λ1​((2Z2)∨)? Can you see some patterns?

Reminder: We defined the successive minima of a lattice LLLas such:

λi(L)=min⁡(max⁡1≤j≤i(∥vj∥):vj∈L are linearly independent)\lambda_i(L)=\min\left(\max_{1\leq j\leq i}\left(\left\lVert v_j\right\rVert\right):v_j\in L\text{ are linearly independent}\right)λi​(L)=min(1≤j≤imax​(∥vj​∥):vj​∈L are linearly independent)

Claim 1:

λ1(L)⋅λ1(L∨)≤n\lambda_1(L) \cdot \lambda_1(L^\vee) \leq nλ1​(L)⋅λ1​(L∨)≤n

Proof: By Minkowski's bound we know:

λ1(L)≤n⋅det⁡(L)1/n\lambda_1(L) \leq \sqrt{n} \cdot \det(L)^{1 / n}λ1​(L)≤n​⋅det(L)1/n and λ1(L∨)≤n⋅det(L∨)1/n=ndet⁡(L)1/n\lambda_1(L^\vee) \leq \sqrt{n} \cdot det(L^\vee)^{1 / n} = \dfrac {\sqrt{n}} {\det(L)^{1/n}}λ1​(L∨)≤n​⋅det(L∨)1/n=det(L)1/nn​​. By multiplying them we get the desired result.

From this result we can deduce that the minima of the LLL and L∨L^\veeL∨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:

λ1(L)⋅λn(L∨)≥1\lambda_1(L) \cdot \lambda_n(L^\vee) \geq 1λ1​(L)⋅λn​(L∨)≥1

Proof:

Let x∈Lx∈Lx∈L be such that ∥x∥=λ1(L)\|x\|=λ_1(L)∥x∥=λ1​(L). Then take any set (y1,...,yn)(y_1, . . . , y_n)(y1​,...,yn​) of nnn linearly independent vectors in L∨L^\veeL∨. Not all of them are orthogonal to xxx. Hence, there exists an iii such that yi⋅x≠0y_i \cdot x \neq 0yi​⋅x=0 . By the definition of the dual lattice, we have yi⋅x∈Zy_i \cdot x \in \mathbb Zyi​⋅x∈Z and hence 1≤yi⋅x≤∥yi∥⋅∥x∥≤λ1⋅λn∨1 \leq y_i \cdot x \leq \|y_i\| \cdot \|x\| \leq \lambda_1 \cdot \lambda_n^\vee1≤yi​⋅x≤∥yi​∥⋅∥x∥≤λ1​⋅λn∨​

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 Z\mathbb ZZ) and we limit them to some finite set using the  mod \bmodmod operation (Z→Z/qZ\mathbb Z \to \mathbb Z/ q\mathbb{Z}Z→Z/qZ). 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∈Z, q≥3q \in \mathbb{Z},\ q \geq 3q∈Z, q≥3we call a lattice q-ary if

qZn⊆L⊆Znq\mathbb{Z}^n \subseteq {L} \subseteq \mathbb{Z}^nqZn⊆L⊆Zn

Intuition:

  • qZn⊆Lq\mathbb{Z^n} \subseteq \mathcal{L}qZn⊆L is periodic  mod  q\bmod \ qmod q

  • We use arithmetic  mod  q\bmod \ qmod q

We will now look at 2 more types of lattices that are q-ary. Let A∈(Z/qZ)n×mA \in (\mathbb{Z}/q\mathbb Z)^{n \times m}A∈(Z/qZ)n×m be a matrix with m>nm > nm>n. Consider the following lattices: Lq(A)={y∈Zm:y=ATx mod q∈ for some x∈Zn}⊂ZmL_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}Lq​(A)={y∈Zm:y=ATxmodq∈ for some x∈Zn}⊂Zm Lq⊥(A)={y∈Zm:Ay=0 mod q}⊂ZmL^\perp_q(A) = \{y \in \mathbb Z^m : Ay = 0 \bmod q \} \subset \mathbb{Z^m}Lq⊥​(A)={y∈Zm:Ay=0modq}⊂Zm

Intuition:

  • Think of Lq(A)L_q(A)Lq​(A) as the image of the matrix AAA, the matrix spanned by the rows of AAA

  • Think of Lq⊥(A)L_q^\perp(A)Lq⊥​(A) as the kernel of AAA modulo qqq. The set of solutions Ax=0Ax = 0Ax=0

Remark: If the same matrix AAA is used (AAA is fixed ) then Lq(A)≠Lq⊥(A)L_q(A) \neq L_q^\perp(A)Lq​(A)=Lq⊥​(A)

Claim:

Lq(A)L_q(A)Lq​(A) and Lq⊥(A)L_q^\perp(A)Lq⊥​(A) are the dual of each other (up to scaling): Lq(A)=1qLq⊥(A)L_q(A) = \dfrac 1 q L_q^\perp(A)Lq​(A)=q1​Lq⊥​(A)

Proof:

Firstly we will show Lq⊥(A)⊆q(Lq(A))∨L_q^\perp(A) \subseteq q(L_q(A))^\veeLq⊥​(A)⊆q(Lq​(A))∨

  • Let y∈Lq⊥(A)⇒Ay≡0 mod q  ⟺  Ay=qzy \in L_q^\perp(A) \Rightarrow Ay \equiv 0 \bmod q \iff Ay = qzy∈Lq⊥​(A)⇒Ay≡0modq⟺Ay=qzfor some z∈Zmz \in \mathbb{Z}^mz∈Zm

  • Let y′∈Lq(A)⇒y′≡ATx mod q  ⟺  y′=ATx+qz′y' \in L_q(A)\Rightarrow y' \equiv A^Tx \bmod q \iff y' = A^Tx + qz'y′∈Lq​(A)⇒y′≡ATxmodq⟺y′=ATx+qz′ for some x∈Zn, z′∈Zmx \in \mathbb Z^n, \ z' \in \mathbb Z^mx∈Zn, z′∈Zm

Then we have:y⋅y′=y⋅(ATx+qz′)=y⋅ATx+q(y⋅z′)=Ay⏟qz⋅x+q(y⋅z′)=qz⋅x+q(y⋅z′)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')y⋅y′=y⋅(ATx+qz′)=y⋅ATx+q(y⋅z′)=qzAy​​⋅x+q(y⋅z′)=qz⋅x+q(y⋅z′)

⇒1qy⋅y′∈Z⇒1qy∈Lq(A)∨\Rightarrow \dfrac 1 q y \cdot y' \in \mathbb{Z} \Rightarrow \dfrac 1 q y\in L_q(A)^\vee⇒q1​y⋅y′∈Z⇒q1​y∈Lq​(A)∨

The second part is left as an exercise to the reader :D. Show Lq⊥(A)⊇q(Lq(A))∨L_q^\perp(A) \supseteq q(L_q(A))^\veeLq⊥​(A)⊇q(Lq​(A))∨

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

Short integer solutions (SIS)

Introduction

In this section we will study the short integer solution problem and a hashing algorithm that is based on this algorithm.

Short integer solution problem

Definition

Let SISn,m,q,βSIS_{n, m, q, \beta}SISn,m,q,β​ be a Short Integer Solution problem. We define it as such:

Given mmm uniformly random vectors ai∈(Z/qZ)na_i∈(\mathbb{Z}/q\mathbb Z)^nai​∈(Z/qZ)n, forming the columns of a matrix A∈(Z/qZ)n×mA∈(\mathbb{Z}/q\mathbb Z)^{n×m}A∈(Z/qZ)n×m, find a nonzero integer vector z∈Zmz∈\mathbb{Z}^mz∈Zm of norm ‖z‖≤β‖z‖ ≤β‖z‖≤β (short) such that

fA(z)=Az=∑iai⋅zi=0∈(Z/qZ)nz1a1⃗+z2a2⃗+...+zmam⃗=0f_A(z) = Az = \sum_i a_i \cdot z_i = 0 \in (\mathbb{Z}/q\mathbb Z)^n \\ z_1\vec{a_1} + z_2\vec{a_2} +...+ z_m\vec{a_m} = 0fA​(z)=Az=i∑​ai​⋅zi​=0∈(Z/qZ)nz1​a1​​+z2​a2​​+...+zm​am​​=0

Without the constraint β\betaβ the solution would be as simple as Gaussian elimination. Also we want β<q\beta < qβ<q otherwise z=(q,0,...,0)∈Zmz = (q,0, ..., 0) \in \mathbb{Z}^mz=(q,0,...,0)∈Zm would be a fine solution.

Notice that a solution zzz for AAA can be converted to a solution for the extension [A∣A′][A| A'][A∣A′] by appending 000s to zzz ⇒\Rightarrow⇒

  • big m⇒m \Rightarrowm⇒ easy (the more vectors we are given, the easier the problem becomes)

  • big n⇒n \Rightarrown⇒ hard (the more dimension we work in the harder the problem becomes)

Solution existence is based on parameters set. One should think about them as follows:

  • nnn is the security parameter. The bigger it is the harder the problem becomes

  • mmm is set depending from application to application. Usually m≫nm \gg nm≫n

  • q=poly(n)q = \text{poly}(n)q=poly(n), think of it as q=O(n2)q = \mathcal{O}(n^2)q=O(n2)

  • β=\beta = β=the bound is set depending on application and β≪q\beta \ll qβ≪q

SIS as a SVP problem

// TODO

Ajtai's hashing function

  • Parameters: m,n,q∈Zm, n, q \in \mathbb{Z}m,n,q∈Z, m>nlog⁡2qm > n \log_2 qm>nlog2​q

  • Key: A∈(Z/qZ)n×mA \in (\mathbb{Z}/q\mathbb Z)^{n \times m}A∈(Z/qZ)n×m

  • Input: x∈{0,1}m⇒x \in \{0, 1\}^m \Rightarrowx∈{0,1}m⇒ Short vector

  • Output: fA(x)=Ax mod q\boxed {f_A(x) = Ax \bmod q}fA​(x)=Axmodq​ where fA:{0,1}m→(Z/qZ)nf_A : \{0, 1\}^m \to (\mathbb{Z}/q\mathbb Z)^nfA​:{0,1}m→(Z/qZ)n

Hash function properties:

Compression

We know x∈{0,1}m⇒∣X∣=2nx \in \{0, 1\}^m \Rightarrow |\mathcal{X}| = 2^nx∈{0,1}m⇒∣X∣=2n and Ax∈Y=(Z/qZ)n⇒∣(Z/qZ)n∣=qn=(2log⁡q)nAx \in \mathcal Y = (\mathbb{Z}/q\mathbb Z)^n \Rightarrow |(\mathbb{Z}/q\mathbb Z)^n| = q^n = (2^{\log q})^nAx∈Y=(Z/qZ)n⇒∣(Z/qZ)n∣=qn=(2logq)n. Since we chose m>nlog⁡q⇒∣X∣>∣Y∣m > n \log q \Rightarrow |\mathcal{X}| > |\mathcal{Y}| m>nlogq⇒∣X∣>∣Y∣.

Collision resistance:

halp here

Sage example:

from Crypto.Util.number import long_to_bytes, bytes_to_long

n, m, q = 20, 40, 1009
set_random_seed(1337)
A = random_matrix(Zmod(q),n, m)

print(A.parent())
# Full MatrixSpace of 20 by 40 dense matrices over Ring of integers modulo 1009
print(A.lift().parent())
# Full MatrixSpace of 20 by 40 dense matrices over Integer Ring

msg = b'msg'
x = vector(Zmod(q), [int(i) for i in bin(bytes_to_long(msg))[2:].zfill(m)]) # pad message
print(len(x)
# 40

print(x.parent())
# Vector space of dimension 40 over Ring of integers modulo 1009

print(len(A * x))
# 20

Cryptanalysis

Inverting the function:

Given AAA and yyy find x∈{0,1}mx \in \{0, 1\}^mx∈{0,1}m such that Ax=y mod qAx = y \bmod qAx=ymodq

Formulating as a lattice problem:

Find arbitrary ttt such that At=y mod qAt = y \bmod qAt=ymodq

  • All solutions to Ax=yAx = yAx=y are of the form t+L⊥t + L^{\perp}t+L⊥ where L⊥(A)={x∈Zm:Ax=0∈(Z/qZ)n}{L}^\perp(A) = \{x \in \mathbb{Z}^m : Ax = 0 \in (\mathbb{Z}/q\mathbb Z)^n \}L⊥(A)={x∈Zm:Ax=0∈(Z/qZ)n}

  • So we need to find a short vector in t+L⊥(A)t + {L}^{\perp}(A)t+L⊥(A)

  • Equivalent, find v∈L⊥(A)v \in {L}^{\perp}(A)v∈L⊥(A) closest to ttt (CVP)

Hermite normal form

// TODO

Security Reduction

If somebody can explain the security bounds and reduction better, please do.

Resources

  • https://simons.berkeley.edu/sites/default/files/docs/14967/sis.pdf + https://www.youtube.com/watch?v=qZIjVX61NFc&list=PLgKuh-lKre10rqiTYqJi6P4UlBRMQtPn0&index=4

  • https://crypto.stanford.edu/cs355/18sp/lec9.pdf

  • https://eprint.iacr.org/2015/939.pdf - page 18

Resources and notations

References/Resources

  1. Nguyen, P. Q., & Vallée, B. (Eds.). (2010). The LLL Algorithm. Information Security and Cryptography. doi:10.1007/978-3-642-02295-1

    Massive survey, lots of detail if you're extremely interested)

  2. May, A. (2003). New RSA Vulnerabilities Using Lattice Reduction Methods. Universität Paderborn.

    Excellent exposition to LLL and coppersmith as well as showing some RSA attacks via LLL

  3. Lenstra, A. K., Lenstra, H. W., & Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4), 515–534. doi:10.1007/bf01457454

    The original LLL paper, quite a nice read overall + proof that LLL works

  4. Coppersmith, D. (1996). Finding a Small Root of a Univariate Modular Equation. Lecture Notes in Computer Science, 155–165. doi:10.1007/3-540-68339-9_14

  5. Coppersmith, D. (1996). Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known. Lecture Notes in Computer Science, 178–189. doi:10.1007/3-540-68339-9_16

    Both of these paper introduces the coppersmith algorithm as well as provide some examples

  6. Waerden, B. L. (1956). Die Reduktionstheorie Der Positiven Quadratischen Formen. Acta Mathematica, 96(0), 265–309. doi:10.1007/bf02392364

Notation

  • lattice

    • dimension of lattice

    • volume of lattice

  • a chosen basis for

    • matrix whose th row vectors is

  • Gram-Schmidt orthogonalization of (without normalization)

    • matrix whose th row vectors is

  • Gram-Schmidt coefficients

  • the th successive minima of

Proof of correctness

We now consider necessary for the successful description of an RSA ciphertext. The core of this result is due to which states

for all coprime integers and is .

As a reminder, we say two integers are coprime if they share no non-trivial factors. This is the same statement that .

From the definition of the protocol, we have that

for some . Combining this with Euler's theorem, we see that we recover from the ciphertext

When the requirement does not hold, we can instead look at the equivalences modulo and respectively. Clearly, when we have that and our correctness still holds. Now, consider the case where we have that and Since we have already excluded the case that we can conclude that as is prime. This means that and by the multiplicative properties of the function, we determine that We conclude by invoking the Chinese Remainder theorem with

that The case for follows in a parallel manner.

RSA application

Tutorial for application with RSA. We are going to use openSSL, openSSH and pycryptodome for key generation, key extraction and some implementation with python

Pycryptodome:

Pycryptodome is a python library about cryptography, see the documentation below: There is an example of RSA key generation with pycryptodome:

OpenSSL:

OpenSSL is a robust, commercial-grade, and full-featured toolkit for the Transport Layer Security (TLS) and Secure Sockets Layer (SSL) protocols. It is also a general-purpose cryptography library

OpenSSH:

Recovering the Modulus

When you want to recover N given some (plaintext, ciphertext) pairings

Scenario

Consider the case that that you know a set of (plaintext, ciphertext) pairings - this may be that you are provided them, or that you have access to some functionality that returns ciphertexts for provided plaintexts. If you do not know the modulus, but know the exponent used (note: this may be prone to a brute-force regardless), then given these pairings you can recover the modulus used.

What we know

Let the following be known:

  • plaintext && ciphertext pairings:

  • public exponent e (e.g. e = 65537 = 0x10001)

Process

The idea behind this attack is effectively finding common factors between pairings. Recall that, under general RSA encryption, we have:

and recall what modular arithmetic tells us about the relation between these terms, namely that:

This, rearranged, tells us that

What this means for our known pairings is that, given we know and , we can form the relationship:

Thus we can calculate for the value , though don't know either value individually - we want to somehow derive .

Observe that any two pairings will equate to such a value, both with as a factor. We can take the gcd of these two values, and it is probable that the resulting value will be our value, such that:

However, this is only true for the case that

i.e., both and are coprime. In the case that they are not, i.e. , we have that

In such a case, we don't have sufficient information to completely recover the modulus, and require more plaintext-ciphertext pairs to be successful. In general, the more pairings you have, the more confident you can be the value you calculate is . More specifically:

Thus:

Practical Notes

  • In reality, you're likely to only need two or three (plaintext, ciphertext) pairings (in the context of ctf challenges and exercises), and as such computations can be manual if needed, but shouldn't be too complex

  • As it's likely you'll be dealing with large numbers, overflows and precision errors may arise in code - using libraries like gmpy provide support for integers of (theoretically) infinite size, and some nice accompanying features too (like in-built gcd and efficient modular exponentiation)

  • These two statements are mathematically equivalent, but one is easier to implement in code:

Code Example

Interactive fun

Inspired by:

Lattice + LLL + Fundamental mesh plot

Lattice + CVP

Q-ary plots

LLL
dim⁡(L)\dim(L)dim(L)
vol(L)\text{vol}(L)vol(L)
bib_ibi​
LLL
B\mathcal BB
iii
bib_ibi​
bi∗b_i^*bi∗​
bib_ibi​
B∗\mathcal B^*B∗
iii
bi∗b_i^*bi∗​
μi,j=⟨bi,bj∗⟩⟨bj∗,bj∗⟩\mu_{i,j}=\frac{\langle b_i,b_j^*\rangle}{\langle b_j^*,b_j^*\rangle}μi,j​=⟨bj∗​,bj∗​⟩⟨bi​,bj∗​⟩​
λi(L)\lambda_i(L)λi​(L)
iii
LLL
(Mi,Ci) for i∈[1,∞](M_i,C_i) \text{ for } i \in [1,\infty] (Mi​,Ci​) for i∈[1,∞]
C=Me (mod N)C = M^{e} \text{ } (mod\text{ }N)C=Me (mod N)
a≡b (mod N)a=b+kN for some k∈Za \equiv b\text{ }(mod\text{ } N)\\ a = b + kN \text{ for some } k \in \mathbb{Z} a≡b (mod N)a=b+kN for some k∈Z
a−b≡0 (mod N)a−b=kNa - b \equiv 0\text{ } (mod \text{ } N)\\ a - b = kNa−b≡0 (mod N)a−b=kN
m,cm, cm,c
eee
Ci−Mie≡0 (mod N)Ci−Mie=kiNC_i - M_i^e \equiv 0\text{ } (mod \text{ } N)\\ C_i - M_i^e = k_iNCi​−Mie​≡0 (mod N)Ci​−Mie​=ki​N
kNkNkN
NNN
NNN
NNN
N=gcd(C1−M1e,C2−M2e)N = gcd(C_1 - M_1^e, C_2 - M_2^e)N=gcd(C1​−M1e​,C2​−M2e​)
gcd(k1,k2)=1gcd(k_1, k_2) = 1gcd(k1​,k2​)=1
k1k_1k1​
k2k_2k2​
gcd(k1,k2)≠1gcd(k_1, k_2) \ne 1gcd(k1​,k2​)=1
aN=gcd(C1−M1e,C2−M2e) s.t. 1≠a∈ZaN = gcd(C_1 - M_1^e, C_2 - M_2^e) \text{ s.t. } 1 \ne a \in \mathbb{Z}aN=gcd(C1​−M1e​,C2​−M2e​) s.t. 1=a∈Z
NNN
Pr(a≠1)→0 as k→∞Pr(a \ne1) \rightarrow 0 \text{ as } k\rightarrow \inftyPr(a=1)→0 as k→∞
N=lim⁡k→∞gcd(C1−M1e,C2−M2e,...,Ck−Mke)N = \lim_{k \rightarrow \infty} gcd(C_1 - M_1^e, C_2 - M_2^e, ..., C_k - M_k^e)N=k→∞lim​gcd(C1​−M1e​,C2​−M2e​,...,Ck​−Mke​)
gcd(a,b,c,d,...)=gcd(a,gcd(b,gcd(c,gcd(d,...))))gcd(a, b, c, d, ...) = gcd(a, gcd(b, gcd(c, gcd(d, ...))))gcd(a,b,c,d,...)=gcd(a,gcd(b,gcd(c,gcd(d,...))))
import gmpy2

"""
@param pairings
    list: [(pt1, ct1), (pt2, ct2), ..., (ptk, ctk)]
@param e
    int : encryption exponent
@return
    int : recovered N
"""
def recover_n(pairings, e):
    pt1, ct1 = pairings[0]
    N = ct1 - pow(pt1, e)
    
    # loop through and find common divisors
    for pt,ct in pairings:
        val = gmpy2.mpz(ct - pow(pt, e))
        N = gmpy2.gcd(val, N)
    
    return N
    
cd=med=mc^d = m^{ed} = mcd=med=m
aϕ(n)≡1mod  na^{\phi(n)} \equiv 1 \mod naϕ(n)≡1modn
(a,n)(a,n)(a,n)
ϕ(n)\phi(n)ϕ(n)
gcd⁡(a,n)=1\gcd(a,n)=1gcd(a,n)=1
ed≡1mod  ϕ(n),    ⇒    ed=1+kϕ(n)ed \equiv 1 \mod \phi(n), \;\; \Rightarrow \;\; ed = 1 + k\phi(n)ed≡1modϕ(n),⇒ed=1+kϕ(n)
k∈Zk \in \mathbb{Z}k∈Z
mmm
cd≡(me)dmod  n≡medmod  n≡mkϕ+1mod  n≡mkϕmmod  n≡(mϕ)kmmod  n≡1kmmod  n≡mmod  n\begin{align} c^d &\equiv (m^e)^d &&\mod n \\ &\equiv m^{ed} &&\mod n \\ &\equiv m^{k\phi + 1} &&\mod n \\ &\equiv m^{k\phi} m &&\mod n \\ &\equiv (m^\phi)^km &&\mod n \\ &\equiv 1^km &&\mod n \\ &\equiv m &&\mod n \\ \end{align}cd​≡(me)d≡med≡mkϕ+1≡mkϕm≡(mϕ)km≡1km≡m​​modnmodnmodnmodnmodnmodnmodn​​
gcd⁡(m,n)=1\gcd(m, n) = 1gcd(m,n)=1
ppp
qqq
gcd⁡(m,n)=n,\gcd(m, n) = n,gcd(m,n)=n,
c≡m≡0mod  nc \equiv m \equiv 0 \mod nc≡m≡0modn
m=k⋅p,m = k\cdot p,m=k⋅p,
c≡m≡0mod  pc \equiv m \equiv 0 \mod pc≡m≡0modp
cd≡(me)d(modq).c^d \equiv (m^e)^d \pmod q.cd≡(me)d(modq).
gcd⁡(m,q)=q,\gcd(m, q) = q,gcd(m,q)=q,
gcd⁡(m,q)=1,\gcd(m, q) = 1,gcd(m,q)=1,
qqq
mℓϕ(q)≡1mod  qm^{\ell\phi(q)} \equiv 1 \mod qmℓϕ(q)≡1modq
ϕ\phiϕ
mℓnϕ(n)=mℓϕ(q)≡1mod  q.m^{\ell_n\phi(n)} = m^{\ell\phi(q)} \equiv 1 \mod q.mℓn​ϕ(n)=mℓϕ(q)≡1modq.
m≡0mod  pm≡1ℓmmod  q\begin{align*} m &\equiv 0 &&\mod p \\ m &\equiv 1^\ell m &&\mod q\\ \end{align*}mm​≡0≡1ℓm​​modpmodq​
me⋅d≡mmod  n.m^{e\cdot d} \equiv m \mod n.me⋅d≡mmodn.
m=k⋅qm = k\cdot qm=k⋅q
Euler's theorem
Euler's totient function
from Crypto.Util.number import getPrime, bytes_to_long


def generate_keys():
    e = 0x10001    #public exponent e, we generally use this one by default
    while True:
        p = getPrime(512)
        q = getPrime(512)
        phi = (p - 1) * (q - 1)    #Euler's totient 
        d = pow(e, -1, phi)    #Private exponent d
        if d != -1:
            break

    n = p * q
    public_key = (n, e)
    private_key = (n, d)
    return public_key, private_key


def encrypt(plaintext: int, public_key) -> int:
    n, e = public_key
    return pow(plaintext, e, n)    #plaintext ** e mod n


def decrypt(ciphertext: int, private_key) -> int:
    n, d = private_key
    return pow(ciphertext, d, n)   #ciphertext ** d mod n


message = bytes_to_long(b"super_secret_message")
public_key, private_key = generate_keys()
ciphertext = encrypt(message, public_key)
plaintext = decrypt(ciphertext, private_key)
https://www.pycryptodome.org/en/latest/

Diffie-Hellman

Overview

We need to make some changes: separate the explanation from the code, add a subpart about the MITM and maybe to develop more the instructions

Let's say Alice and Bob want to exchange a secret over an insecure channel. In other words, anyone can read the messages they send, but the goal is to ensure that only Alice and Bob can calculate the secret key.

Diffie-Hellman key exchange provides a solution to this seemingly impossible task. Since code may be easier to understand than a detailed explanation, I'll provide it first:

import Crypto.Util.number as cun
import Crypto.Random.random as crr


class DiffieHellman:
    def __init__(self, p: int):
        self.p = p
        self.g = 5
        self.private_key = crr.randrange(2, p-1)

    def public_key(self) -> int:
        return pow(self.g, self.private_key, self.p)

    def shared_key(self, other_public_key: int) -> int:
        return pow(other_public_key, self.private_key, self.p)


p = cun.getPrime(512)
alice = DiffieHellman(p)
bob = DiffieHellman(p)

shared_key = bob.shared_key(alice.public_key())
assert shared_key == alice.shared_key(bob.public_key())

Here's a brief explanation of the code:

  • We choose a prime ppp and a generator g∈Fpg \in \mathbb{F}_pg∈Fp​

  • Alice picks a private key a∈Zp−1a \in \mathbb{Z}_{p-1}a∈Zp−1​

  • Bob picks a private key b∈Zp−1b \in \mathbb{Z}_{p-1}b∈Zp−1​

  • Alice's public key is gamod  pg^a \mod pgamodp

  • Bob's public key is gbmod  pg^b \mod pgbmodp

  • Their shared key is gab≡(ga)b≡(gb)a(modp)g^{ab} \equiv (g^a)^b \equiv (g^b)^a \pmod pgab≡(ga)b≡(gb)a(modp)

So anybody observing the messages sent between Alice and Bob would see p,g,ga,gbp, g, g^a, g^bp,g,ga,gb, but they wouldn't be able to calculate the shared key gabg^{ab}gab.

This is because given ggg and gag^aga, it should be infeasible to calculate aaa. If this sounds familiar, that's because it's the Discrete Log Problem.

The original paper can be found here. It uses the group of integers modulo a prime to perform the key exchange. In practice however, any group with a hard discrete log problem can be used.

Elliptic Curve Cryptography

Common Modulus Attack

What to do when the same message is encrypted twice with the same modulus but a different public key?

Imagine we have Alice and Bob. Alice sends the SAME message to Bob more than once using the same public key. The internet being the internet, a problem may happen; a bit is flipped, and the public key changed while the modulus stayed the same.

What we know

Let be the following:

  • m the message in plaintext

  • e1 the public key of the first ciphertext

  • c1 the first ciphertext

  • e2 the public key of the second ciphertext

  • c2 the second ciphertext

  • n the modulus that is common to both ciphertexts

All of these but m are essentially given to us.

Conditions of the attack

Because we are going to need to calculate inverses for this attack, we must first make sure that these inverses exist in the first place:

gcd(e1,e2)=1gcd(c2,n)=1gcd(e_1, e_2) = 1 \newline gcd(c_2, n) = 1 gcd(e1​,e2​)=1gcd(c2​,n)=1

The math behind the attack

We know that RSA goes as follows:

c=me mod nc = m^e\ mod\ nc=me mod n

From the conditions above we also know that e1e1 e1 and e2e2e2 are co-prime. Thus using Bezout's Theorem we can get:

xe1+ye2=gcd(e1,e2)=1xe_1 +ye_2 = gcd(e_1, e_2) = 1xe1​+ye2​=gcd(e1​,e2​)=1

Using this, we can derive the original message mm m :

NB: all the calculations are done mod nn n

C1x∗C2y=(me1)x∗(me2)y=me1x+e2y=m1=mC_1^x * C_2^y = (m^{e_1})^x*(m^{e_2})^y \newline = m^{e_1x+e_2y} \newline = m^1 = m C1x​∗C2y​=(me1​)x∗(me2​)y=me1​x+e2​y=m1=m

In general, Bezout's Theorem gives a pair of positive and negative numbers. We just need to adapt this equation a little to make it work for us. In this case, let's assume yyy is the negative number:

Let y=−aC2y=C2−a=(C2−1)a=(C2−1)−yLet\ y = -a \newline C_2^y = C_2^{-a} \newline = (C_2^{-1})^a \newline = (C_2^{-1})^{-y}Let y=−aC2y​=C2−a​=(C2−1​)a=(C2−1​)−y

Now to truly recover the plaintext, we are actually doing:

C1x×(C2−1)−y mod nC_1^x \times (C_2^{-1})^{-y}\ mod\ n C1x​×(C2−1​)−y mod n

The One Time Pad

Author: chuck_bartowski

Introduction

The One Time Pad (OTP) is a well known example of encryption schemes that provide "perfect secrecy". Informally, this means that observing a ciphertext does no give any information to the eavesdropper. A proof of this fact will be provided later. Crucially we will assume that the sender and the receiver have both access to a common source of random bits.

XOR as a One-Time Pad

XOR(addition modulo 2) can be used as an encryption scheme as follows: The message space is M⊆{0,1}n\mathcal M \subseteq \{0, 1\}^nM⊆{0,1}n(i.e.: length n bit strings), the key space is K={0,1}\mathcal K = \{0, 1\}K={0,1} and the ciphertext space is also {0,1}\{0,1\}{0,1}

  • Encryption: Enc(m,k)=m⊕k\text{Enc}(m,k) = m \oplus kEnc(m,k)=m⊕k

  • Decryption:Dec(c,k)=c⊕k\text{Dec}(c,k) = c \oplus kDec(c,k)=c⊕k

The correctness of the schemes is easily verifiable. If the encryption produces c=m⊕kc = m \oplus kc=m⊕k, then the decryption produces m′=c⊕k=m⊕k⊕k=mm' = c \oplus k = m \oplus k \oplus k = mm′=c⊕k=m⊕k⊕k=m.

In the Python snippet below with use to os module to generate random bits.

import os

def xor(a,b):
    res = bytes([x^y for (x,y) in zip(a,b)])
    return res
    
message = b"YELLOW SUBMARINE"
key = os.urandom(len(message))
ciphertext = xor(message, key)
recovered = xor(ciphertext, key)
print(f"Message: {message}\nKey: {key}\nCiphertext: {ciphertext}\nrecovered: {recovered}")
# A possible ouput might be as below
# Message: b'YELLOW SUBMARINE'
# Key: b'\x8e<3\xc9\x8d\xbaD\x16Zb\x1b\xbb\xb3\x0c@<'
# Ciphertext: b'\xd7y\x7f\x85\xc2\xeddE\x0f V\xfa\xe1E\x0ey'
# recovered: b'YELLOW SUBMARINE'

As seen above the receiver with access to the same key can recover the message.

Generalized One-Time Pad

Although XOR is commonly used for the OTP, OTP can be made out of more general objects. If fact We can define an OTP if the message and the keys are objects from a set with a group like structure. (see GroupTheorySection #TODO)

MITM

Explanation of the MITM (Man In The Middle) with the Diffie-Hellmann key exchange

Sets and Functions

@interact
def draw_lattice(v1x = input_box(label = "v1 x =", default = 1),
                 v1y = input_box(label = "v1 y =", default = 0),
                 v2x = input_box(label = "v2 x =", default = 0),
                 v2y = input_box(label = "v2 y =", default = 1),
                 box = 5, search = 10,
                 plot_LLL = True,
                 plot_C = True,
                 plot_F = True):

    v1 = vector((v1x, v1y))
    v2 = vector((v2x, v2y))
    vecs = []
    # Generate vectors
    for i in range(-search,search):
        for j in range(-search,search):
            vecs.append(i*v1 + j*v2)
    # Plot stuff
    G = Graphics()
    for p1 in vecs:
        x1, y1 = p1
        if x1 > -box and x1 < box and y1 > -box and y1 < box:
            G += point(p1, color = 'green', size = 30)
            G += line([p1, p1 + v2], linestyle = '--', alpha = .20)
            G += line([p1, p1 + v1], linestyle = '--', alpha = .20)
    G+= arrow((0, 0), v1, color = 'red', arrowsize = 2)
    G+= arrow((0, 0), v2, color = 'red', arrowsize = 2)
    G+= text('v1', v1 + .2 * v1, color = 'red')
    G+= text('v2', v2 + .2 * v2, color = 'red')
    
    # LLL
    if plot_LLL:
        v1_, v2_ = matrix([v1, v2]).LLL()
        G+= arrow((0, 0), v1_, color = 'purple', arrowsize = 2)
        G+= arrow((0, 0), v2_, color = 'purple', arrowsize = 2)
        if plot_C:
            G += circle(center = (0, 0), radius = norm(v1_) if norm(v1_) > norm(v2_) else norm(v2_), alpha = .5, color = 'purple')
    # Fundamental mesh
    if plot_F:
        F = polygon([[0, 0], v1, v1 + v2, v2], color='red', alpha = .1)
        G += F
    G.show(axes = False, figsize = (7, 7))

@interact
def draw_cvp(v1x = input_box(label = "v1 x =", default = 1),
             v1y = input_box(label = "v1 y =", default = 0),
             v2x = input_box(label = "v2 x =", default = 0),
             v2y = input_box(label = "v2 y =", default = 1),
             wx = input_box(label = "w x =", default = 1.8),
             wy = input_box(label = "w y =", default = 1.7),
             box = 5, search = 10):

    v1 = vector((v1x, v1y))
    v2 = vector((v2x, v2y))
    print(v1, v2)
    vecs = []
    # Generate vectors
    for i in range(-search,search):
        for j in range(-search,search):
            vecs.append(i*v1 + j*v2)
    # Plot stuff
    G = Graphics()
    for p1 in vecs:
        x1, y1 = p1
        if x1 > -box and x1 < box and y1 > -box and y1 < box:
            G += point(p1, color = 'green', size = 30)
            G += line([p1, p1 + v2], linestyle = '--', alpha = .20)
            G += line([p1, p1 + v1], linestyle = '--', alpha = .20)
    G+= arrow((0, 0), v1, color = 'red', arrowsize = 2)
    G+= arrow((0, 0), v2, color = 'red', arrowsize = 2)
    G+= text('v1', v1 + .2 * v1, color = 'red')
    G+= text('v2', v2 + .2 * v2, color = 'red')         
    
    # Cvp
    L = IntegerLattice(matrix([v1, v2]))
    w = vector((wx, wy))
    t = L.closest_vector(w)
    G += point(w, color = 'purple', size = 30)
    G+= text('w', w + .2 * v1, color = 'purple')         

    G += point(t, color = 'red', size = 30)
    G+= text('t', t + .2 * v1, color = 'red')         
    G+= circle(center = w, radius=norm(t - w), color = 'purple', alpha = .5)
    G.show(axes = False, figsize = (7, 7))
@interact
def draw_dual(v1x = input_box(label = "v1 x =", default = 1),
                 v1y = input_box(label = "v1 y =", default = 0),
                 v2x = input_box(label = "v2 x =", default = 0),
                 v2y = input_box(label = "v2 y =", default = 1),
                 box = 3, search = 6,
                 plot_lattice_points = True,
                 plot_lattice_lines = True,
                 plot_dual_points = True,
                 plot_dual_lines = True):

    v1 = vector((v1x, v1y))
    v2 = vector((v2x, v2y))
    vecs = []
    v1_, v2_ = matrix([v1,v2]).inverse().T
    vecs_ = []
    # Generate vectors
    for i in range(-search,search):
        for j in range(-search,search):
            vecs.append(i*v1 + j*v2)
    for i in range(-search,search):
        for j in range(-search,search):
            vecs_.append(i*v1_ + j*v2_)
    # Plot stuff
    G = Graphics()
    for p1 in vecs:
        x1, y1 = p1
        if x1 > -box and x1 < box and y1 > -box and y1 < box:
            if plot_lattice_points:
                G += point(p1, color = 'green', size = 70)
            if plot_lattice_lines:
                G += line([p1, p1 + v2], linestyle = '--', alpha = .20, color = 'green')
                G += line([p1, p1 + v1], linestyle = '--', alpha = .20, color = 'green')
    if plot_lattice_lines:
        G+= arrow((0, 0), v1, color = 'green', arrowsize = 2)
        G+= arrow((0, 0), v2, color = 'green', arrowsize = 2)
        G+= text('v1', v1 + .2 * v1, color = 'green')
        G+= text('v2', v2 + .2 * v2, color = 'green')
    
    # Dual
    for p1 in vecs_:
        x1, y1 = p1
        if x1 > -box and x1 < box and y1 > -box and y1 < box:
            if plot_dual_points:
                G += point(p1, color = 'red', size = 25)
            if plot_dual_lines:
                G += line([p1, p1 + v2_], linestyle = '--', alpha = .20, color = 'red')
                G += line([p1, p1 + v1_], linestyle = '--', alpha = .20, color = 'red')
    if plot_dual_lines:
        G+= arrow((0, 0), v1_, color = 'red', arrowsize = 2)
        G+= arrow((0, 0), v2_, color = 'red', arrowsize = 2)
        G+= text('v1\'', v1_ + .2 * v1, color = 'red')
        G+= text('v2\'', v2_ + .2 * v2, color = 'red')
    
    G.show(axes = False, figsize = (7, 7))
# I'm not sure this does what is supposed to do
# but the plots are nice

from sage.modules.free_module_integer import IntegerLattice
@interact
def draw_qary(v1x = input_box(label = "v1 x =", default = 1),
                 v1y = input_box(label = "v1 y =", default = 0),
                 v2x = input_box(label = "v2 x =", default = 0),
                 v2y = input_box(label = "v2 y =", default = 1),
                 q = input_box(label = "q =", default = 5),
                 box = 7, search = 6,
                 plot_lattice_points = True,
                 plot_lattice_lines = True,
                 plot_qary_points = True,
                 plot_qary_lines = True):

    v1 = vector((v1x, v1y))
    v2 = vector((v2x, v2y))
    L = IntegerLattice(matrix([v1, v2]))
    vecs = []
    v1_ = v1.change_ring(Zmod(q))
    v2_ = v2.change_ring(Zmod(q))
    vecs_ = []
    # Generate vectors
    for i in range(-search,search):
        for j in range(-search,search):
            v = i*v1 + j*v2
            vecs.append(v)
            v = v.change_ring(Zmod(q)).change_ring(ZZ)
            if v not in vecs_:
                vecs_.append(v)
                
    # Lattice
    G = Graphics()
    for p1 in vecs:
        x1, y1 = p1
        if x1 > -box and x1 < box and y1 > -box and y1 < box:
            if plot_lattice_points:
                G += point(p1, color = 'green', size = 70)
            if plot_lattice_lines:
                G += line([p1, p1 + v2], linestyle = '--', alpha = .20, color = 'green')
                G += line([p1, p1 + v1], linestyle = '--', alpha = .20, color = 'green')
    if plot_lattice_lines:
        G+= arrow((0, 0), v1, color = 'green', arrowsize = 2)
        G+= arrow((0, 0), v2, color = 'green', arrowsize = 2)
        G+= text('v1', v1 + .2 * v1, color = 'green')
        G+= text('v2', v2 + .2 * v2, color = 'green')
    
    # qary
    for p1 in vecs_:
        p1 = p1
        x1, y1 = p1
        if x1 > -box and x1 < box and y1 > -box and y1 < box:
            if plot_qary_points:
                G += point(p1, color = 'red', size = 25)
            if plot_qary_lines:
                G += line([p1, p1 + v2_], linestyle = '--', alpha = .20, color = 'red')
                G += line([p1, p1 + v1_], linestyle = '--', alpha = .20, color = 'red')
    if plot_qary_lines:
        G+= arrow((0, 0), v1_, color = 'purple', arrowsize = 2)
        G+= arrow((0, 0), v2_, color = 'purple', arrowsize = 2)
        G+= text('v1\'', v1_.change_ring(ZZ) + .2 * v1, color = 'purple')
        G+= text('v2\'', v2_.change_ring(ZZ) + .2 * v2, color = 'purple')
    
    G.show(axes = False, figsize = (10, 10))
https://crypto.katestange.net/lattice-tools/

Boneh-Durfee Attack

What is Boneh-Durfee Attack

Boneh-Durfee attack is an extension of Wiener's attack. That is, it also attacks on low private component dddwith a further relaxed condition. If dddsatisfies:

d<N0.292d < N^{0.292} d<N0.292

Then we can use Boneh-Durfee attack to retrive ddd

this, using a graphical directed point of view, can be seen as:

{E,n}→d<N0.292P{d}\{E, n\} \xrightarrow[d < N^{0.292}]{P} \{d\} {E,n}Pd<N0.292​{d}

Consider d<Nid < N^{i}d<Nifor first, see that

1=ed+kϕ(N)21=ed + \frac{k \phi(N)}{2}\\ 1=ed+2kϕ(N)​

As stated above, the RSA's totient function can be espressed as:

ϕ(N)=(p−1)(q−1)=N−q−p+1 \phi(N) = (p-1)(q-1) = N-q-p+1ϕ(N)=(p−1)(q−1)=N−q−p+1

continuing with the equation, we see that

1=ed+k(N+12−p+q2)1 = ed + k(\frac{N+1}{2}-\frac{p+q}{2} )1=ed+k(2N+1​−2p+q​)

and if we decide to consider x=N+12x = \frac{N+1}{2} x=2N+1​and y=p+q2y = \frac{p+q}{2} y=2p+q​, we will have:

1=ed+k(x+y)1 = ed + k(x+y)1=ed+k(x+y)

At this point, finding dddis equivalent to find the 2 small solutions xxxand yyyto the congruence

f(x,y)≡k(x+y)≡1 (mod e)k(x+y)≡1( mod e)f(x,y) \equiv k(x+y) \equiv 1 \space (mod \space e) \\ k(x + y) \equiv 1 (\space mod \space e)f(x,y)≡k(x+y)≡1 (mod e)k(x+y)≡1( mod e)

now let s=−p+q2s = -\frac{p+q}{2}s=−2p+q​and A=N+12A = \frac{N+1}{2}A=2N+1​this will preserve the scomposed ϕ(N)\phi(N) ϕ(N)subtraction

k(A+s)≡1( mod e)k(A+s) \equiv 1 (\space mod \space e)k(A+s)≡1( mod e)

consider e=Nαe=N^{\alpha}e=Nα(with any α\alphaα), we deduct that α\alphaαmust be really closed to 111because eeeis in the same order of the length of NNN(so e=N∼1−e=N^{\sim 1^{-}}e=N∼1−), we will get

∣s∣<2N=p+q2<2N=2e12α∼e∣k∣<2edϕ(N)≤3edN<3e1+α+1α<ei| s | < 2\sqrt{N} = \\ \frac{p+q}{2} < 2\sqrt{N} =2e^{\frac{1}{2\alpha}} \sim \sqrt{e} \\ |k| < \frac{2ed}{\phi{(N)}} \leq\frac{3ed}{N}< 3e^{1+\frac{\alpha+1}{\alpha}} < e^{i}∣s∣<2N​=2p+q​<2N​=2e2α1​∼e​∣k∣<ϕ(N)2ed​≤N3ed​<3e1+αα+1​<ei

Sage Implementation

Wiener's Attack

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

Wiener's theorem

Wiener's attack is based on the following theorem:

Let n=pqn = pqn=pq, with q<p<2qq < p < 2qq<p<2q. Let d<13n4d < \frac{1}{3}\sqrt[4]{n}d<31​4n​. Given nnn and eee with ed≡1mod  ϕ(n)ed \equiv 1 \mod \phi(n)ed≡1modϕ(n), the attacker can efficiently recover ddd.

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 ed≡1mod  ϕ(n)ed \equiv 1 \mod \phi(n)ed≡1modϕ(n) can be written as the equality ed=kϕ(n)+1ed = k\phi(n)+1ed=kϕ(n)+1 for some value kkk, we may additionally note that ϕ(n)=(p−1)(q−1)=pq−p−q+1\phi(n) = (p-1)(q-1) = pq - p - q + 1ϕ(n)=(p−1)(q−1)=pq−p−q+1, since both ppp and qqq are much shorter than pq=npq = npq=n, we can say that ϕ(n)≈n\phi(n) \approx nϕ(n)≈n.

Dividing the former equation by dϕ(n)d\phi(n)dϕ(n) gives us eϕ(n)=k+1d\frac{e}{\phi(n)} = \frac{k+1}{d}ϕ(n)e​=dk+1​, and using the latter approximation, we can write this as en≈kd\frac{e}{n} \approx \frac{k}{d}ne​≈dk​. 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 nnn by knowing nnn and ϕ(n)\phi(n)ϕ(n). Consider the quadratic polynomial (x−q)(x−p)(x-q)(x-p)(x−q)(x−p), this polynomial will have the roots ppp and qqq. Expanding it gives us x2−(p+q)x+pqx^2 - (p + q)x + pqx2−(p+q)x+pq, and substituting for the variables we know we can write this as x2−(n−ϕ(n)+1)x+nx^2 - (n - \phi(n) + 1)x + nx2−(n−ϕ(n)+1)x+n. Applying the quadratic formula gives us ppp and qqq: p∧q=−b±b2−4ac2ap \wedge q = \frac{-b \pm \sqrt{b^2-4ac}}{2a}p∧q=2a−b±b2−4ac​​, where a=1a = 1a=1, b=n−ϕ(n)+1b = n - \phi(n) + 1b=n−ϕ(n)+1, and c=nc = nc=n.

Wiener's attack works by expanding en\frac{e}{n}ne​ to a continued fraction and iterating through the terms to check various approximations of kd\frac{k}{d}dk​. In order to make this checking process more efficient, we can make a few observations (this part is optional):

  • Since ϕ(n)\phi(n)ϕ(n) is even, and eee and ddd are both by definition coprime to ϕ(n)\phi(n)ϕ(n), we know that ddd is odd.

  • Given the above equations and the values of eee, nnn, ddd, and kkk, we can solve for ϕ(n)\phi(n)ϕ(n) with the equation ϕ(n)=ed−1k\phi(n) = \frac{ed-1}{k}ϕ(n)=ked−1​, thus we know that ed−1ed-1ed−1 has to be divisible by kkk.

  • If our ϕ(n)\phi(n)ϕ(n) is correct, the polynomial x2−(n−ϕ(n)+1)x+nx^2 - (n - \phi(n) + 1)x + nx2−(n−ϕ(n)+1)x+n will have roots ppp and qqq, which we can verify by checking if pq=npq = npq=n.

The Attack

Suppose we have the public key (n,e)(n, e)(n,e), this attack will determine ddd

  1. Convert the fraction en\frac{e}{n}ne​ into a continued fraction [a0;a1,a2,…,ak−2,ak−1,ak][a_0;a_1,a_2, \ldots , a_{k-2},a_{k-1}, a_k][a0​;a1​,a2​,…,ak−2​,ak−1​,ak​]

  2. Iterate over each convergent in the continued fraction: a01,a0+1a1,a0+1a1+1a2, …,a0+1a1+⋱ak−2+1ak−1,\frac{a_{0}}{1},a_{0} + \frac{1}{a_{1}},a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2}}}, \ \ldots, a_{0} + \frac{1}{a_{1} + \frac{\ddots} {a_{k-2} + \frac{1}{a_{k-1}}}},1a0​​,a0​+a1​1​,a0​+a1​+a2​1​1​, …,a0​+a1​+ak−2​+ak−1​1​⋱​1​,

  3. Check if the convergent is kd\frac{k}{d}dk​ by doing the following:

    • Set the numerator to be kkk and denominator to be ddd

    • Check if ddd is odd, if not, move on to the next convergent

    • Check if ed≡1mod  ked \equiv 1 \mod ked≡1modk, if not, move on to the next convergent

    • Set ϕ(n)=ed−1k\phi(n) = \frac{ed-1}{k}ϕ(n)=ked−1​ and find the roots of the polynomial x2−(n−ϕ(n)+1)x+nx^2 - (n - \phi(n) + 1)x + nx2−(n−ϕ(n)+1)x+n

    • If the roots of the polynomial are integers, then we've found ddd. (If not, move on to the next convergent)

  4. If all convergents have been tried, and none of them work, then the given RSA parameters are not vulnerable to Wiener's attack.

Here's a sage implementation to play around with:

from Crypto.Util.number import long_to_bytes

def wiener(e, n):
    # Convert e/n into a continued fraction
    cf = continued_fraction(e/n)
    convergents = cf.convergents()
    for kd in convergents:
        k = kd.numerator()
        d = kd.denominator()
        # Check if k and d meet the requirements
        if k == 0 or d%2 == 0 or e*d % k != 1:
            continue
        phi = (e*d - 1)/k
        # Create the polynomial
        x = PolynomialRing(RationalField(), 'x').gen()
        f = x^2 - (n-phi+1)*x + n
        roots = f.roots()
        # Check if polynomial as two roots
        if len(roots) != 2:
            continue
        # Check if roots of the polynomial are p and q
        p,q = int(roots[0][0]), int(roots[1][0])
        if p*q == n:
            return d
    return None
# Test to see if our attack works
if __name__ == '__main__':
    n = 6727075990400738687345725133831068548505159909089226909308151105405617384093373931141833301653602476784414065504536979164089581789354173719785815972324079
    e = 4805054278857670490961232238450763248932257077920876363791536503861155274352289134505009741863918247921515546177391127175463544741368225721957798416107743
    c = 5928120944877154092488159606792758283490469364444892167942345801713373962617628757053412232636219967675256510422984948872954949616521392542703915478027634
    d = wiener(e,n)
    assert not d is None, "Wiener's attack failed :("
    print(long_to_bytes(int(pow(c,d,n))).decode())

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

#!/usr/bin/env python3
import owiener
from Crypto.Util.number import long_to_bytes

#--------Data--------#

N = <N>
e = <e>
c = <c>

#--------Wiener's attack--------#

d = owiener.attack(e, N)

if d:
    m = pow(c, d, N)
    flag = long_to_bytes(m).decode()
    print(flag)
else:
    print("Wiener's Attack failed.")

AES

Advanced Encryption Standard

Introduction

The Advanced Encryption Standard most known as AES is one of the most used ciphers nowadays. Created by Vinent Rijmen and Joan Daemen under the name Rijndael, it won the NIST competition that resulted in its standardization in 2001 to replace older algorithms such as DES (and its variant 3DES). In fact, it is six times faster than 3DES.

AES encrypts a block of 16 bytes only at a time, though ciphertexts tend to be much longer. To accomodate this, cipherexts are cut in blocks of 16 bytes using an operating mode [see future section on mode]. We only focus on the encryption of a single block.

The array of 16 bytes(p0,…,p15)(p_0,\ldots,p_{15})(p0​,…,p15​)are arranged from up to bottom, column by column in4×44 \times 44×4matrix. During the encryption, the state of this matrix changes and results in a 16-bytes ciphertext(c0,…,c15)(c_0,\ldots,c_{15})(c0​,…,c15​)whose output can be read following the same ordering:

AES encryption.

A key is involved and three sizes are possible: 128, 192, or 256 bits. Depending of the size, there are a few differences which will be explained later. For now, it is sufficient to know that round keys are derived from this master key.

Our interest is to look at what goes inside the transformation between the plaintext and the ciphertext. Basically, there are four operations on the state matrix, each important for the security of AES:

  • AK: add round key;

  • SR: shift row;

  • SB: substitution box;

  • MC: MixColumn.

All these operations are executed a several number of times in what are called rounds to mix the plaintext enough. A look on the flow of an encryption is given in the figure below.

Rounds of AES.

Two particular cases can be noticed:

  • the first round is preceded by an additional AK;

  • last round is missing MC.

The number of rounds NR is different depending on the master key length:

Key length

Number of rounds

128

10

192

12

256

14

Encryption

Author: Chuck_bartwoski

Introduction

A typical application of cryptography is secure communication. Informally a secure communication channel is one that provides both confidentiality and Integrity of the messages. In this section we investigate confidentiality, therefore we may assume that integrity is already guaranteed by some other means. (see section on integrity...#TODO)

We assume that two parties that want to communicate share a secret key . Prior to sending a message, the sender encrypts the message with the secret key, this produces a ciphertext that is then sent. The receiver uses the same key to decrypt the message and recover the message.

Intuitively: A secure encryption scheme will prevent an eavesdropper to learn the content of the message since the ciphertext is unintelligible. The security requirement will be formalized later.

Formal definition

We introduce some notation first: We will use to denote the set of al possible message, is the set of all possible keys and is the set of ciphertexts.

A symmetric encryption scheme is a tuple of efficiently computable functions .:

  • Selects a key at random from the key space.

  • . Encrypts the message with the key into a ciphertext . Sometimes written as

  • . Decrypts the ciphertexts with the key into the message or returns an error (). . Sometimes written as

For to be useful we need that . This is also called correctness.

After all what's the point of confidentially sending a nice Christmas card to your grand children if they wont be able to read its content

TODO: security notions and examples

Round Transformations

This page gives a description of the four operations that compose a round of AES. Each has been designed to satisfy criterias, one of them is that all must be invertible.

Add Round Key

This is the only operation that involves a key. It is obvious that omitting it would mean no encryption.

Round keys are derived from the master key (see the Key Schedule section) and are all composed of 16 bytes. We simply xor byte by byte the state by the bytes of the round key in the according position.

Its inverse is itself: if we xor again, we get back the original value of the state.

Mix Columns

A major goal of MC is the diffusion property: each byte has an impact on the whole column, so a modification propagates to other positions.

This operation mixes each column of the state independently from each other: each byte of the column is replaced by a (slightly different) combination of the four bytes of the column.

Let the quadruplet of elements of a column, the operation MC is done by multiplying with a matrix .

The calculations are performed in the finite field. If you are not familiar enough with the notions, you can skip to the next part and retain that this operation is also invertible using another matrix.

This matrix is circulant: each row is the same as the one above but is shifted by one column. So we can construct it in one line of SageMath (recall that the bytes 02 and 03 correspond respectively to and in the field):

Inverse of Mix Column

It is needed to reverse MC for the decryption process. Fortunately, there exists a matrix such that , the identity matrix.

We remark that the coefficient of the matrix are less friendly for the inverse operation as it involves polynomial of higher degree. This means that the decryption is a bit slower.

Shift Rows

The goal of shifting rows is reinforce the diffusion property: the bytes of a column are shifted so they are all positioned on different columns. Combined with MC, then a one byte modification will have an effect to the whole state after several rounds: this is the .

This operation shifts the rows of the state in the following manner:

The rows are shifted from top to bottom respectively by an offset of 0, 1, 2 or 3 columns to the left. Bytes that overflow on the left are put back to the right of the row.

The inverse is almost the same: the rows are shifted to the right instead by the same offsets and exceeding bytes are put back to the left.

Small exercise: to what extent would be the impact on the security of AES if no shifting were present?

Substitution Box

Last, but not least, the SB design criterias is to bring the confusion property to make correlation between a plaintext and a ciphertext as small as possible.

The precedent operations shuffle the plaintext in such a way that any modification of a byte has an impact to the whole state after several rounds. Though, this is not enough as those operations are linear: it means that the ciphertext could be expressed as linear equations from the plaintext and the master key. From a known couple plaintext/ciphertext it would be easy to solve the system and find the key.

The substitution box is the operation that breaks the linearity: each byte of the state is replaced by another following the table below.

If 3b is the input, its output is on row 30 and column 0b and is the byte e2.

Let sbox the name of this table, then for any bytes b1 and b2, we have

which is the desired property.

Though, this is not enough and the design of the sbox is made to include a sufficient algebraic complexity. The construction of the sbox table is done in two steps:

  1. An elementis replaced by ( has no inverse and is mapped to );

  2. An affine transformation on the coefficients of :

The table we gave above has been construted with SageMath and applying the two steps:

The inverse of the table is simple to produce: we only need to reverse the match between an input and its output.

Exercise: write the inverse of the substitution box in SageMath using the inverse of the affine transformation.

Isogenies

Motivation

Prerequisites: in this section we assume the reader is somewhat familiar with elliptic curves and begin by considering morphisms (maps) between elliptic curves.

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 between elliptic curves defined over a field is a surjective morphism of curves which includes a group homomorphism

References

Rijndael Finite Field

A first time reader might skip this section and go directly to the description of the round transformations, then come back later (it is mostly useful to understand the construction of the operation MC and SB).

Each byte in AES is viewed as an element of a binary finite field of 256 elements, where it can always be represented as a polynomial of degree at most 7 with coefficients in. The construction of the finite field is made as the quotient ring, whereis an irreducible polynomial of degree 8 inso the ring becomes a field.

In AES, the choice foris

We can check with SageMath that it is irreducible:

Matching Bytes as Finite Field Elements

A byte is composed of 8 bits and is matched to a polynomial as

For instance, take the byte 3a whose binary decomposition is and becomes the polynomial

Polynomial Reduction

Polynomials of degree 8 or more can always be reduced, using the fact that in the finite field, we have , so we have the relation

Why not ? In fact, that's also true, but the coefficient are in so the additive inverse of is itself.

In SageMath, this reduction can be produced in one of the following methods.

Method 1: Remainder of an Euclidean division by

Method 2: Image in the quotient ring

Method 3: Using the Finite Field class of SageMath directly.

On this page we use this last method. Also, this helper converts an element of the finite field to the hexadecimal representation of a byte, and could be useful in the examples:

Addition

The addition of two polynomials is done by adding the coefficients corresponding of each monomial:

And as the addition of the coefficients is in, it corresponds to the bitwise xor operation on the byte.

Multiplication

Multiplication of two polynomials is more complex (one example would be the , more efficient than the naive algorithm). For an implementation of AES, it is possible to only use the multiplication by , whose byte representation is 02.

Letan element and we consider the multiplication by:

All coefficients are shifted to a monomial one degree higher. Then, there are two cases:

  • Ifis, then we have a polynomial of degree at most 7 and we are done;

  • Ifis, we can replacebyduring the reduction phase:

This can be used to implement a very efficient multiplication bywith the byte representation:

  1. A bitwise shiftleft operation: (b << 1) & 0xff;

  2. Followed by a conditional addition with 1b if the top bit of is .

Here an example in SageMath (we use the finite field construction of method 3):

Introduction / overview

Authors: Zademn Reviewed by:

Introduction

Another desired propriety of our cryptographic protocols is data / message integrity. This propriety assures that during a data transfer the data has not been modified.

Suppose Alice has a new favourite game and wants to send it to Bob. How can Bob be sure that the file he receives is the same as the one Alice intended to send? One would say to run the game and see. But what if the game is a malware? What if there are changes that are undetectable to the human eye?

Hashes are efficient algorithms to check if two files are the same based on the data they contain. The slightest change (a single bit) would change the hash completely.

On the internet, when you download, files you often see a number near the download button called the hash of that file. If you download that file, recalculate the hash locally and obtain the same hash you can be sure that the data you downloaded is the intended one.

Another use for hashes is storing passwords. We don't want to store plaintext passwords because in case of a breach the attacker will know our password. If we hash them he will have to reverse the hash (or find a collision) to use our password. Luckily the hashes are very hard to reverse and collision resistant by definition and construction.

Note that hashes need a secure channel for communication. Alice must have a secure way to send her hash to Bob. If Eve intercepts Alice's message and hash she can impersonate Alice by changing the file, computing the hash and sending them to Bob. Hashes do not provide authenticity.

Definitions and Formalism

Definition - Hash

A hash is an efficient deterministic function that takes an arbitrary length input and produces a fixed length output (digest, hash). Let be a function where

  • = message space

  • = digest space

Desired proprieties

  • Deterministic

  • Fast to compute

  • Small changes change the hash completely

  • Preimage, second preimage and collision resistance (Explained below)

How to use a hash:

  • Suppose you want to check if Alice and Bob have the same version of some file (File integrity)

    • They compute

    • They check if

Proprieties

  • Preimage Image Resistance

  • Second Preimage resistance

  • Resistant to collisions

1. Preimage Resistance

The hash function must be a one way function. Given find s.t

Intuition

It should be unfeasible to reverse a hash function ( time where is the number of output bits)

This propriety prevents an attacker to find the original message from a hash

2. Second Preimage Resistance

Given it should be hard to find with

Attack game

An adversary is given a message and outputs a message .

wins the game if he finds

His advantage is where is a probability

  • In practice a hash function with bits output should need queries before one can find a second preimage

  • This propriety prevents an attacker to substitute a message with another and get the same hash

3. Hash Collisions

Intuition

A hash collision happens when we have two different messages that have the same hash

Why do we care about hash collisions?

  • Since hashes are used to fastly verify a message integrity if two messages have the same hash then we can replace one with another => We can play with data

  • Now, we want to hash big files and big messages so => It would appear that hash collisions are possible

  • Natural collisions are normal to happen and we consider them improbable if is big enough ( )

  • Yet, we don't want hash collisions to be computable

    • We don't want an attacker to be able to craft collisions or find collisions given a message

Let's throw some definitions

Attack game

An adversary outputs two messages

wins the game if he finds

His advantage is

Security

A hash function is collision resistant if for all efficient and explicit adversaries the advantage is negligible

Intuition

We know hash collisions exist (therefore an efficient adversary must exist) and that is easy to prove therefore we request an explicit algorithm that finds these collisions

This propriety makes it difficult for an attacker to find 2 input values with the same hash

Difference from 2nd preimage

  • There is a fundamental difference in how hard it is to break collision resistance and second-preimage resistance.

    • Breaking collision-resistance is like inviting more people into the room until the room contains 2 people with the same birthday.

    • Breaking second-preimage resistance is like inviting more people into the room until the room contains another person with your birthday.

  • One of these fundamentally takes longer than the other

Implications

Lemma 1

Assuming a function is preimage resistant for every element of the range of is a weaker assumption than assuming it is either collision resistant or second preimage resistant.

Note

  • Provisional implication

Lemma 2

Assuming a function is second preimage resistant is a weaker assumption than assuming it is collision resistant.

Resources

  • - Wikipedia entry

  • - Computerphile

  • - Good read for more details

Bibliography

  • Figure 1 - Wikipedia

Introduction to Isogeny Cryptography

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 isogeny graphs are 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

  • Mathematics of Isogeny Based Cryptography by Luca De Feo

    • -

  • The Arithmetic of Elliptic Curves by Joseph H. Silverman

ϕ:E1→E2\phi : E_1 \to E_2ϕ:E1​→E2​
kkk
E1(kˉ)→E1(kˉ)E_1(\bar{k}) \to E_1(\bar{k})E1​(kˉ)→E1​(kˉ)
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
F2\mathbf{F}_2F2​
F2[x]/f(x)\mathbf{F}_2[x]/f(x)F2​[x]/f(x)
fff
F2[x]\mathbf F_2[x]F2​[x]
fff
f(x)=x8+x4+x3+x+1.f(x) = x^8 + x^4 + x^3 + x + 1.f(x)=x8+x4+x3+x+1.
F2 = GF(2)
K.<x> = F2[]
f = x^8 + x^4 + x^3 + x + 1
f.is_irreducible()
# True
bbb
(b7,…,b0)2(b_7, \ldots, b_0)_2(b7​,…,b0​)2​
b7x7+b7x6+⋯+b1x+b0.b_7x^7 + b_7 x^6 + \cdots + b_1 x + b_0.b7​x7+b7​x6+⋯+b1​x+b0​.
(0,0,1,1,1,0,1,0)2(0, 0, 1, 1, 1, 0, 1, 0)_2(0,0,1,1,1,0,1,0)2​
0⋅x7+0⋅x6+1⋅x5+1⋅x4+1⋅x3+0⋅x2+1⋅x+0=x5+x4+x3+x.0\cdot x^7 + 0\cdot x^6 + 1\cdot x^5 + 1\cdot x^4 + 1\cdot x^3 + 0\cdot x^2 + 1\cdot x + 0 = x^5 + x^4 + x^3 + x.0⋅x7+0⋅x6+1⋅x5+1⋅x4+1⋅x3+0⋅x2+1⋅x+0=x5+x4+x3+x.
f(x)=0f(x) = 0f(x)=0
x8=x4+x3+x+1x^8 = x^4 + x^3 + x + 1x8=x4+x3+x+1
x8=−x4−x3−x−1x^8 = - x^4 - x^3 - x - 1x8=−x4−x3−x−1
F2\mathbf F_2F2​
−1-1−1
111
fff
(x^8 + x^6 + x^4 + 1) % f
# x^6 + x^3 + x
F2[x]/f(x)\mathbf{F}_2[x]/f(x)F2​[x]/f(x)
R = K.quotient(f)
R(x^8 + x^6 + x^4 + 1)
# xbar^6 + xbar^3 + xbar
F.<x> = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1)
x^8 + x^6 + x^4 + 1
# x^6 + x^3 + x
def F_to_hex(a):
    return ZZ(a.integer_representation()).hex()

b = x^4 + x^3 + x + 1
F_to_hex(b)
# '1b'
∑i=07aixi+∑i=07bixi=∑i=07(ai+bi)xi.\sum_{i=0}^7 a_ix^i + \sum_{i=0}^7 b_ix^i = \sum_{i=0}^7(a_i + b_i)x^i.i=0∑7​ai​xi+i=0∑7​bi​xi=i=0∑7​(ai​+bi​)xi.
F2\mathbf{F}_2F2​
xxx
b7x7+⋯+b1x+b0b_7x^7 + \cdots + b_1x + b_0b7​x7+⋯+b1​x+b0​
xxx
x×(b7x7+⋯+b1x+b0)=b7x8+b6x7+⋯b1x2+b0x.x\times (b_7x^7 + \cdots + b_1x + b_0) = b_7x^8 + b_6x^7 + \cdots b_1 x^2 + b_0x.x×(b7​x7+⋯+b1​x+b0​)=b7​x8+b6​x7+⋯b1​x2+b0​x.
b7b_7b7​
000
b7b_7b7​
111
x8x^8x8
x4+x3+x+1x^4 + x^3 + x + 1x4+x3+x+1
x×(x7+b6x6+⋯+b1x+b0)=x8+b6x7+⋯b1x2+b0x=(x4+x3+x+1)+b6x7+⋯+b1x2+b0x\begin{align*} x\times (x^7 + b_6x^6 + \cdots + b_1x + b_0) & = x^8 + b_6x^7 + \cdots b_1 x^2 + b_0x \\ & = (x^4 + x^3 + x + 1) + b_6x^7 + \cdots + b_1x^2 + b_0x \end{align*}x×(x7+b6​x6+⋯+b1​x+b0​)​=x8+b6​x7+⋯b1​x2+b0​x=(x4+x3+x+1)+b6​x7+⋯+b1​x2+b0​x​
xxx
bbb
111
b = x^7 + x^5 + x^4 + x^2 + 1
F_to_hex(b)
# 'b5'
(2*0xb5 & 0xff) ^^ 0x1b).hex() == F_to_hex(x*b)    # the xor in Sage is "^^"
# True
Karatsuba algorithm
ℓ\ellℓ
(ℓ+1)(\ell + 1)(ℓ+1)
https://eprint.iacr.org/2019/1321.pdf
https://arxiv.org/pdf/1711.04062.pdf
https://www.springer.com/gp/book/9780387094939

Isogeny and Ramanujan Graphs

I (Jack) know nothing about this. At all. But it will need to be talked about.

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

Probability Theory

The Birthday paradox / attack

Authors: Zademn, ireland Reviewed by:

Prerequisites

  • Probability theory (for the main idea)

  • Hashes (an application)

Motivation

  • Breaking a hash function (insert story)

The birthday paradox

*insert story / introduction about why it's called a paradox + use*

Birthday version

Question 1

What is the probability that 1 person has the same birthday as you?

Solution

  • Let AAA be the event that someone has the same birthday as you and Aˉ\bar{A}Aˉ be the complementary event

    • The events are mutually exclusive => Pr(A)=1−Pr(Aˉ)Pr(A) = 1 - Pr(\bar{A})Pr(A)=1−Pr(Aˉ)

  • Let EiE_iEi​ be the events that person iii does not have your birthday

Then

  • Pr(A)=1−Pr(Aˉ)=1−∏i=1nPr(Ei)=1−(364365)nPr(A) = 1 - Pr(\bar{A}) = 1 - \prod_{i=1}^n Pr(E_i) = 1 - \left( \dfrac {364} {365}\right)^nPr(A)=1−Pr(Aˉ)=1−∏i=1n​Pr(Ei​)=1−(365364​)n

Reminder: Pr(A,B)=Pr(A)⋅Pr(B)Pr(A, B) = Pr(A) \cdot Pr(B)Pr(A,B)=Pr(A)⋅Pr(B)if A,BA, BA,Bare independent events

Question 2

What is the probability that 2 out of nnn people in a room share the same birthday?

  • Suppose the birthdays are distributed independently and uniformly

Solution

  • Let AAA be the event that 2 people have the same birthday, let Aˉ\bar{A}Aˉ be the complementary event (no 2 people have the same birthday)

  • Event 1 = Person 1 is born => Pr(E1)=365365Pr(E_1) = \dfrac {365} {365}Pr(E1​)=365365​

  • Event 2 = Person 2 is born on a different day than Person 1 => Pr(E2)=364365Pr(E_2) = \dfrac {364} {365}Pr(E2​)=365364​

    ⋮\vdots⋮

  • Event n = Person n is born on a different day than Person 1,...,n−1⇒1,...,n-1 \Rightarrow1,...,n−1⇒ ⇒Pr(En)=365−(n−1)365\Rightarrow Pr(E_n) = \dfrac {365-(n-1)} {365}⇒Pr(En​)=365365−(n−1)​

Pr(Aˉ)=Pr(E1)⋅Pr(E2)⋅⋯⋅Pr(En)=365365⋅364365⋅⋯⋅365−(n−1)365=(1365)n⋅365!(365−n)!=∏i=1n−1(1−i365)Pr(\bar{A}) = Pr(E1) \cdot Pr(E_2) \cdot \dots \cdot Pr(E_n) = \dfrac {365} {365} \cdot \dfrac {364} {365} \cdot \dots \cdot \dfrac {365-(n-1)} {365} = \left( \dfrac {1} {365} \right) ^{n} \cdot \dfrac {365!} {(365-n)!} = \prod_{i=1}^{n-1} \left(1 - \dfrac i {365}\right)Pr(Aˉ)=Pr(E1)⋅Pr(E2​)⋅⋯⋅Pr(En​)=365365​⋅365364​⋅⋯⋅365365−(n−1)​=(3651​)n⋅(365−n)!365!​=∏i=1n−1​(1−365i​)

General case

Question 1

  • Instead of 365365365 days we have d⇒1−(d−1d)nd \Rightarrow \boxed{1 - \left( \dfrac {d-1} {d}\right)^n}d⇒1−(dd−1​)n​

Question 2

  • Instead of 365365365 days we have d⇒1−∏i=1n−1(1−id)d \Rightarrow \boxed{1 - \prod_{i=1}^{n-1} \left(1 - \dfrac i {d}\right)}d⇒1−i=1∏n−1​(1−di​)​

Code examples

def my_birthday(n, d):
    return 1 - pow((d-1)/d , n)

def same_birthday(n, d):
    p = 1
    for i in range(1, n): #1 -> n-1
        p*=(1-i/d)
    return 1 - p

print(same_birthday(23, 365), same_birthday(32, 365), same_birthday(100, 365))
# (0.5072972343239854, 0.7533475278503207, 0.9999996927510721)

An useful approximation

From the Taylor approximation we know ex=1+x+x22!+⋯=>ex≈1+xe^x = 1 + x + \dfrac {x^2} {2!} + \dots => e_x\approx 1 + xex=1+x+2!x2​+⋯=>ex​≈1+x for x≪1x \ll 1x≪1 Apply for each event: ⇒x=−ad⇒e−a/d≈1−ad⇒Pr(A)=1−∏i=1n−1e−i/d=1−e−n(n−1)/2d≈1−e−n2/2d\Rightarrow x = -\dfrac a d \Rightarrow e^{ -a /d} \approx 1- \dfrac a d \Rightarrow Pr(A) = 1 - \prod_{i=1}^{n-1}e^{-i/d} = 1-e^{-n(n-1) /{2d}} \approx 1-\boxed{e^{-{n^2} / {2d}}}⇒x=−da​⇒e−a/d≈1−da​⇒Pr(A)=1−∏i=1n−1​e−i/d=1−e−n(n−1)/2d≈1−e−n2/2d​

If we want to solve for nnn knowing Pr(A)Pr(A)Pr(A) we take the ln⁡\lnln => n≈2dln⁡(11−Pr(A))\boxed{n \approx \sqrt{2d \ln \left(\dfrac 1 {1-Pr(A)}\right)}}n≈2dln(1−Pr(A)1​)​​

def approx_same_birthday(n, d):
    return 1 - pow(e, -pow(n, 2) / (2*d)).n()
    
print(approx_same_birthday(23, 365)) 
print(approx_same_birthday(32, 365))
print(approx_same_birthday(100, 365))

# 0.515509538061517
# 0.754077719532824
# 0.999998876014983

Finding a collision

  • Let H:M⟶TH:\mathcal{M} \longrightarrow \mathcal{T}H:M⟶T be a hash function with ∣M∣>>∣T∣|\mathcal{M}| >> |T|∣M∣>>∣T∣

  • Let's denote N=∣T∣N = |\mathcal{T}|N=∣T∣

Algorithm

1. Choose s≈Ns \approx \sqrt{N}s≈N​ random distinct messages in M\mathcal{M}M

2. Compute ti=H(mi)t_i = H(m_i)ti​=H(mi​) for 1≤i≤N1\leq i \leq \sqrt{N}1≤i≤N​

3. Look for (ti=tj)→(t_i = t_j) \to(ti​=tj​)→ If not found go to step 1

Example:

Consider the following hash function:

import hashlib
import random
from Crypto.Util.number import long_to_bytes, bytes_to_long

def small_hash(m, hash_bits):
    '''
    Arguments
        m: bytes -- input
        hash_bits: int -- number of bits of the hash
    Returns:
        {bytes} - hash of the message of dimension `hash_bits`
        '''
    assert hash_bits > 0, "no negative number of bits"
    
    mask = (1 << hash_bits) - 1 # Mask of bits
    t = hashlib.sha256(m).digest() # the hash in bytes
    t = bytes_to_long(t)
    t = t & mask # get the last 12 bits
    return long_to_bytes(t)

We make the following function to find the hashes:


def small_hash_colision(M_bits, T_bits):
    '''
    Arguments
        M_bits: int -- dimension of the message space
        T_bits: int -- dimension of the hash space
    Returns:
        {(bytes, bytes, bytes)} -- message1, message2, hash
        or
        {(b'', b'', b'')} -- if no collision found
    '''
    N = 1<<T_bits 
    print('Hash size: ', N)
    # This is `s`
    num_samples = 1 * isqrt(N)
    num_samples += num_samples//5 + 1 # num_samples = 1.2 * isqrt(N) + 1
    print(f'Making a list of {num_samples} hashes')
    print(f'Probability of finding a collision is {same_birthday(num_samples, N)}')
    
    m_list = []
    t_list = []
    
    # Make a list of hashes
    for i in range(num_samples):
        m = random.getrandbits(M_bits) # Get random message
        #m = random.randint(0, M_bits-1) 
        m = long_to_bytes(m)
        
        t = small_hash(m, T_bits) # Hash it
        if m not in m_list:
            m_list.append(m)
            t_list.append(t)
            
    # Check for collisionn
    for i in range(len(t_list)):
        for j in range(i+1, len(t_list)):
            if t_list[i] == t_list[j]:
                print('Collision found!')
                return m_list[i], m_list[j], t_list[i]
    else:
        print('Collision not found :(')
        return b"", b"", b""

We use it as follows:

M_bits = 30
T_bits = 20

m1, m2, t = small_hash_colision(M_bits, T_bits)
print(m1, m2, t)
print(small_hash(m1, T_bits) == small_hash(m2, T_bits))

# Hash size:  1048576
# Making a list of 1229 hashes
# Probability of finding a collision is 0.513213460854798
# Collision found!
# b'!\xafB\xc5' b'4F\xb6w' b'\x01y\xf7'
# True

Eliminating Storage Requirements with Pollard's Rho

While the above algorithm works to find a hash collision in time O(N)O(\sqrt N )O(N​), it also requires storing O(N)O(\sqrt N )O(N​)hash values. As such, it represents a classic time-space tradeoff over the naive approach, which involves randomly selecting pairs of inputs until they hash to the same value. While the naive approach does not require any additional storage, it does have runtime O(N)O(N )O(N).

However, there is a better approach combining the best of both worlds: constant storage requirements and O(N)O(\sqrt N)O(N​)runtime. This approach is based on Pollard's Rho algorithm, which is better-known for its application to solving discrete logarithms. The core insight behind the algorithm is that by the Birthday Paradox, we expect to encounter a hash collision after trying O(N)O(\sqrt N)O(N​)random inputs. However, it is possible to detect whether a collision has occurred without needing to store all of the inputs and hashes if the inputs are chosen in a clever way.

This is done by choosing the next input based on the hash of the previous input, according to the following sequence:

x0=g(seed)x1=g(H(x0))x2=g(H(x1))…xn+1=g(H(xn))x_0 = g(seed) \\ x_1 = g(H(x_0)) \\ x_2 = g(H(x_1)) \\ \dots \\ x_{n+1} = g(H(x_n)) \\x0​=g(seed)x1​=g(H(x0​))x2​=g(H(x1​))…xn+1​=g(H(xn​))

Where H:M⟶TH:\mathcal{M} \longrightarrow \mathcal{T}H:M⟶T is our hash function and g:T⟶Mg: \mathcal{T} \longrightarrow \mathcal{M} g:T⟶M is a "sufficiently random" function which takes a hash value and produces a new. We define the composition of the functions to bef=H∘g:T⟶Tf = H \circ g : \mathcal{T} \longrightarrow \mathcal{T} f=H∘g:T⟶T.

# TODO:
# have the two hash functions used in this chapter be the same

from Crypto.Hash import SHA256
from Crypto.Util.number import bytes_to_long, long_to_bytes

from tqdm.autonotebook import tqdm

# bits in hash output
n = 30

# H
def my_hash(x):
    x = bytes(x, 'ascii')
    h = SHA256.new()
    h.update(x)
    y = h.digest()
    y = bytes_to_long(y)
    y = y % (1<<n)
    y = int(y)
    return y

# g
def get_message(r):
    x = "Crypto{" + str(r) + "}"
    return x

# f
def f(r):
    return my_hash(get_message(r))

By the Birthday Paradox, we expect that the sequence will have a collision (where xi=xjx_i = x_jxi​=xj​ for two distinct values i,ji,ji,j) after O(N)O(\sqrt N)O(N​)values. But once this occurs, then the sequence will begin to cycle, because xi+1=g(H(xi))=g(H(xj))=xj+1x_{i+1} = g(H(x_i)) = g(H(x_j)) = x_{j+1}xi+1​=g(H(xi​))=g(H(xj​))=xj+1​.

Therefore, we can detect that a collision has occurred by using standard cycle-detection algorithms, such as Floyd's tortoise and hare!

And finally, we can locate the first place in the sequence where the collision occurred, which will let us determine what the colliding inputs to the hash function are. This is done by determining how many iterations apart the colliding inputs are, and then stepping together one iteration at a time until the collision occurs.

For Floyd's tortoise and hare, this is done by noting that when we found our collision after nnn iterations, we were comparing H(xn)=H(x2n)H(x_{n}) = H(x_{2 n})H(xn​)=H(x2n​). And because the sequence is cyclic, if the first colliding input is xix_ixi​, then it collides withH(xi)=H(xi+n)H(x_{i}) = H(x_{i+n})H(xi​)=H(xi+n​). So we define the new sequence yi=xn+iy_i = x_{n+i}yi​=xn+i​, and step through the xix_ixi​ and yiy_iyi​ sequences together until we find our collision!

This is implemented in the following code snippet.

"""
initialization

This routine will find a hash collision in sqrt time with constant space.
"""

seed = 0

x0 = get_message(seed)
x = x0
y = f(x)

"""
detect collision
using Floyd / tortoise and hare cycle finding algorithm

expected number of iterations is ~ sqrt(pi/2) * 2^(n/2),
we run for up to 4 * 2^(n/2) iterations
"""
for i in tqdm(range(4 << (n//2))):
        
    if f(x) == f(y):
        break
        
    x = f(x)
    
    y = f(y)
    y = f(y)
    

"""
locate collision
"""
x = x0
y = f(y)


for j in tqdm(range(i)):
    if f(x) == f(y):
        break
    
    x = f(x)
    
    y = f(y)
    

m1 = get_message(x)
m2 = get_message(y)

assert my_hash(m1) == f(x)
assert my_hash(m2) == f(y)

print("[+] seeds for messages: {}, {}".format(x, y))
print("[+] messages: {}, {}".format(m1, m2))
print("[+] collided hashes of messages: {}, {}".format(my_hash(m1), my_hash(m2)))


# 31%    40391/131072 [00:03<00:08, 10666.20it/s]
# 30%    12032/40391 [00:00<00:02, 13112.15it/s]
# 
# [+] seeds for messages: 404842900, 254017312
# [+] messages: Crypto{404842900}, Crypto{254017312}
# [+] collided hashes of messages: 1022927209, 1022927209

Finally, there is a third algorithm for finding hash collisions in O(N)O(\sqrt N)O(N​)time, namely the van Oorschot-Wiener algorithm based on Distinguished Points. While it does have additional storage requirements over Pollard's Rho, the main advantage of this algorithm is that it parallelizes extremely well, achieving O(Nm)O(\frac{\sqrt N}{m})O(mN​​)runtime when run on mmm processors.

Resources

  • https://en.wikipedia.org/wiki/Birthday_problem - wiki entry

  • https://en.wikipedia.org/wiki/Birthday_attack - wiki entry

  • https://www.youtube.com/watch?v=ofTb57aZHZs - vsauce2 video

  • van Oorschot-Wiener Parallel Collision Search with Cryptanalytic Applications

  • http://www.cs.umd.edu/~jkatz/imc/hash-erratum.pdf

  • https://crypto.stackexchange.com/questions/3295/how-does-a-birthday-attack-on-a-hashing-algorithm-work?rq=1

kkk
M\mathcal MM
K\mathcal KK
C\mathcal CC
E\mathcal EE
(KGen, Enc, Dec)(\text{KGen, Enc, Dec})(KGen, Enc, Dec)
\text{KGen}: \diamond \xrightarrow $ \mathcal K
Enc:M×K↦C\text{Enc}: \mathcal M \times \mathcal K \mapsto \mathcal CEnc:M×K↦C
mmm
kkk
c=Enc(m,k)c = \text{Enc}(m, k)c=Enc(m,k)
c=Enck(m)c = \text{Enc}_k(m)c=Enck​(m)
Dec:C×K↦M×{⊥}\text{Dec}: \mathcal C \times \mathcal K \mapsto \mathcal M \times \{ \bot\}Dec:C×K↦M×{⊥}
ccc
kkk
mmm
⊥\bot⊥
m=Dec(c,k)m = \text{Dec}(c, k)m=Dec(c,k)
m=Deck(c)m = \text{Dec}_k(c)m=Deck​(c)
E\mathcal EE
Dec(Enc(m,k),k)=m;∀m,k\text{Dec}(\text{Enc}(m,k), k) = m; \forall m,kDec(Enc(m,k),k)=m;∀m,k
(a0,a1,a2,a3)(a_0, a_1, a_2, a_3)(a0​,a1​,a2​,a3​)
MMM
xxx
x+1x+1x+1
# we construct the matrix
# (we use the finite field F constructed in the previous page)
M = Matrix.circulant([x, x + 1, 1, 1])
M
# [    x x + 1     1     1]
# [    1     x x + 1     1]
# [    1     1     x x + 1]
# [x + 1     1     1     x]

# We multiply a column
col1 = vector([F.random_element() for i in range(4)])
col1
# (x^6 + x + 1, x^7 + x^4 + x^2, x^6 + x^4 + x^3 + x^2, x^7 + x^6 + x^4 + x^3 + x^2)
col2 = M*col1
col2
# (x^7 + x^5 + 1, x^6 + x^3, x^4, x^7 + x^5 + x^3 + x^2 + x)
NNN
M×N=N×M=IdM\times N = N \times M = \textrm{Id}M×N=N×M=Id
N = M^-1
N
# [x^3 + x^2 + x   x^3 + x + 1 x^3 + x^2 + 1       x^3 + 1]
# [      x^3 + 1 x^3 + x^2 + x   x^3 + x + 1 x^3 + x^2 + 1]
# [x^3 + x^2 + 1       x^3 + 1 x^3 + x^2 + x   x^3 + x + 1]
# [  x^3 + x + 1 x^3 + x^2 + 1       x^3 + 1 x^3 + x^2 + x]

# hexadecimal representation
for row in N:
    print([F_to_hex(a) for a in row])
# ['e', 'b', 'd', '9']
# ['9', 'e', 'b', 'd']
# ['d', '9', 'e', 'b']
# ['b', 'd', '9', 'e']

col3 = N*col2
col3 == col1
# True

00

01

02

03

04

05

06

07

08

09

0a

0b

0c

0d

0e

0f

00

63

7c

77

7b

f2

6b

6f

c5

30

01

67

2b

fe

d7

ab

76

10

ca

82

c9

7d

fa

59

47

f0

ad

d4

a2

af

9c

a4

72

c0

20

b7

fd

93

26

36

3f

f7

cc

34

a5

e5

f1

71

d8

31

15

30

04

c7

23

c3

18

96

05

9a

07

12

80

e2

eb

27

b2

75

40

09

83

2c

1a

1b

6e

5a

a0

52

3b

d6

b3

29

e3

2f

84

50

53

d1

00

ed

20

fc

b1

5b

6a

cb

be

39

4a

4c

58

cf

60

d0

ef

aa

fb

43

4d

33

85

45

f9

02

7f

50

3c

9f

a8

70

51

a3

40

8f

92

9d

38

f5

bc

b6

da

21

10

ff

f3

d2

80

cd

0c

13

ec

5f

97

44

17

c4

a7

7e

3d

64

5d

19

73

90

60

81

4f

dc

22

2a

90

88

46

ee

b8

14

de

5e

0b

db

a0

e0

32

3a

0a

49

06

24

5c

c2

d3

ac

62

91

95

e4

79

b0

e7

c8

37

6d

8d

d5

4e

a9

6c

56

f4

ea

65

7a

ae

08

c0

ba

78

25

2e

1c

a6

b4

c6

e8

dd

74

1f

4b

bd

8b

8a

d0

70

3e

b5

66

48

03

f6

0e

61

35

57

b9

86

c1

1d

9e

e0

e1

f8

98

11

69

d9

8e

94

9b

1e

87

e9

ce

55

28

df

f0

8c

a1

89

0d

bf

e6

42

68

41

99

2d

0f

b0

54

bb

16

sbox(b1⊕b2)≠sbox(b1)⊕sbox(b2)\texttt{sbox}(\texttt{b1} \oplus \texttt{b2}) \neq \texttt{sbox}(\texttt{b1}) \oplus \texttt{sbox}(\texttt{b2})sbox(b1⊕b2)=sbox(b1)⊕sbox(b2)
aaa
b=a−1b = a^{-1}b=a−1
000
000
aaa
[1000111111000111111000111111000111111000011111000011111000011111]⋅[b0b1b2b3b4b5b6b7]+[11000110]\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{bmatrix}​11111000​01111100​00111110​00011111​10001111​11000111​11100011​11110001​​⋅​b0​b1​b2​b3​b4​b5​b6​b7​​​+​11000110​​
def construct_sbox():
    mat = Matrix.circulant(vector(GF(2), [1,0,0,0,1,1,1,1]))
    sbox = []
    for a in range(256):
        # convert a byte value to field element
        b = sum(((a >> i) & 1)*x^i for i in range(8))
        # first step: map to inverse
        if b != 0:
        b = b^-1
        # second step:
        # affine transformation using a vector space over GF(2)
        b = mat*vector(b) + vector(GF(2), [1, 1, 0, 0, 0, 1, 1, 0])
        # convert the vector as an integer in [0, 255]
        sbox.append(sum(ZZ(b[i]) << i for i in range(8)))
    return sbox

sbox = construct_sbox()
for i in range(16):
    print([f'{a:02x}' for a in sbox[16*i : 16*(i + 1)]])
# ['63', '7c', '77', '7b', 'f2', '6b', '6f', 'c5', '30', '01', '67', '2b', 'fe', 'd7', 'ab', '76']
# ['ca', '82', 'c9', '7d', 'fa', '59', '47', 'f0', 'ad', 'd4', 'a2', 'af', '9c', 'a4', '72', 'c0']
# ['b7', 'fd', '93', '26', '36', '3f', 'f7', 'cc', '34', 'a5', 'e5', 'f1', '71', 'd8', '31', '15']
# ['04', 'c7', '23', 'c3', '18', '96', '05', '9a', '07', '12', '80', 'e2', 'eb', '27', 'b2', '75']
# ['09', '83', '2c', '1a', '1b', '6e', '5a', 'a0', '52', '3b', 'd6', 'b3', '29', 'e3', '2f', '84']
# ['53', 'd1', '00', 'ed', '20', 'fc', 'b1', '5b', '6a', 'cb', 'be', '39', '4a', '4c', '58', 'cf']
# ['d0', 'ef', 'aa', 'fb', '43', '4d', '33', '85', '45', 'f9', '02', '7f', '50', '3c', '9f', 'a8']
# ['51', 'a3', '40', '8f', '92', '9d', '38', 'f5', 'bc', 'b6', 'da', '21', '10', 'ff', 'f3', 'd2']
# ['cd', '0c', '13', 'ec', '5f', '97', '44', '17', 'c4', 'a7', '7e', '3d', '64', '5d', '19', '73']
# ['60', '81', '4f', 'dc', '22', '2a', '90', '88', '46', 'ee', 'b8', '14', 'de', '5e', '0b', 'db']
# ['e0', '32', '3a', '0a', '49', '06', '24', '5c', 'c2', 'd3', 'ac', '62', '91', '95', 'e4', '79']
# ['e7', 'c8', '37', '6d', '8d', 'd5', '4e', 'a9', '6c', '56', 'f4', 'ea', '65', '7a', 'ae', '08']
# ['ba', '78', '25', '2e', '1c', 'a6', 'b4', 'c6', 'e8', 'dd', '74', '1f', '4b', 'bd', '8b', '8a']
# ['70', '3e', 'b5', '66', '48', '03', 'f6', '0e', '61', '35', '57', 'b9', '86', 'c1', '1d', '9e']
# ['e1', 'f8', '98', '11', '69', 'd9', '8e', '94', '9b', '1e', '87', 'e9', 'ce', '55', '28', 'df']
# ['8c', 'a1', '89', '0d', 'bf', 'e6', '42', '68', '41', '99', '2d', '0f', 'b0', '54', 'bb', '16']
Avalanche effect
AK: each byte is xored with a byte of the round key in the same position.
MC: each column is multiplied by a matrix.
SR: each is shifted by a different offset to the left.
H:M⟶TH:\mathcal{M} \longrightarrow \mathcal{T}H:M⟶T
M\mathcal{M}M
T\mathcal{T}T
H(a),H(b)H(a), H(b)H(a),H(b)
H(a)=H(b)H(a) = H(b)H(a)=H(b)
from hashlib import sha256
m1 = b"Some file"
m2 = b"Some file"
sha256(m1).digest() == sha256(m2).digest() # -> True
t∈Tt \in \mathcal{T}t∈T
m∈Mm \in \mathcal{M}m∈M
H(m)=tH(m) = tH(m)=t
O(2l)\mathcal{O}(2^l)O(2l)
lll
mmm
m′≠mm' \neq mm′=m
H(m′)=H(m)H(m') = H(m)H(m′)=H(m)
A\mathcal{A}A
mmm
m′≠mm' \neq mm′=m
A\mathcal{A}A
H(m)=H(m′)H(m) = H(m')H(m)=H(m′)
Pr[A finds a second preimage]Pr[\mathcal{A} \text{ finds a second preimage}]Pr[A finds a second preimage]
Pr(⋅)Pr(\cdot)Pr(⋅)
lll
2l2^l2l
∣M∣>>∣T∣|\mathcal{M}| >> |\mathcal{T}|∣M∣>>∣T∣
T\mathcal{T}T
SHA256⇒T=\text{SHA256} \Rightarrow T =SHA256⇒T=
{0,1}256\{0,1\}^{256}{0,1}256
A\mathcal{A}A
m0≠m1m_0 \neq m_1m0​=m1​
A\mathcal{A}A
H(m0)=H(m1)H(m_0) = H(m_1)H(m0​)=H(m1​)
Pr[Adversary finds a collision]Pr[\text{Adversary finds a collision}]Pr[Adversary finds a collision]
HHH
HHH
HHH
https://crypto.stackexchange.com/questions/10602/why-does-second-pre-image-resistance-imply-pre-image-resistance?rq=1
https://crypto.stackexchange.com/questions/9684/pre-image-resistant-but-not-2nd-pre-image-resistant
https://en.wikipedia.org/wiki/Cryptographic_hash_function
https://www.youtube.com/watch?v=b4b8ktEV4Bg
https://www.tutorialspoint.com/cryptography/cryptography_hash_functions.htm
https://www.cs.ucdavis.edu/~rogaway/papers/relates.pdf
Figure 1.
Figure 2. Security game - second preimage resistance
Figure 3. Security game - Collision resistance
RSA-and-LLL-attacks/boneh_durfee.sage at master · mimoo/RSA-and-LLL-attacksGitHub
Boneh-Durfee attack Sage implementation
owiener
GitHub - orisano/owiener: A Python3 implementation of the Wiener attack on RSAGitHub
Logo
Logo