# Table of Contents - [CryptoBook | CryptoBook](#cryptobook-cryptobook) - [Division and Greatest common divisor | CryptoBook](#division-and-greatest-common-divisor-cryptobook) - [Contributors | CryptoBook](#contributors-cryptobook) - [Sample Page | CryptoBook](#sample-page-cryptobook) - [Theorems of Wilson, Euler, and Fermat | CryptoBook](#theorems-of-wilson-euler-and-fermat-cryptobook) - [Style Guide | CryptoBook](#style-guide-cryptobook) - [Fermat's Little Theorem in Detail | CryptoBook](#fermat-s-little-theorem-in-detail-cryptobook) - [Mathematical Notation | CryptoBook](#mathematical-notation-cryptobook) - [Modular Arithmetic | CryptoBook](#modular-arithmetic-cryptobook) - [Euclidean Algorithm | CryptoBook](#euclidean-algorithm-cryptobook) - [Book Plan | CryptoBook](#book-plan-cryptobook) - [Pollard rho | CryptoBook](#pollard-rho-cryptobook) - [Quadratic Residues | CryptoBook](#quadratic-residues-cryptobook) - [Polynomials | CryptoBook](#polynomials-cryptobook) - [Polynomials With Shared Roots | CryptoBook](#polynomials-with-shared-roots-cryptobook) - [Sieves | CryptoBook](#sieves-cryptobook) - [Integer Factorization | CryptoBook](#integer-factorization-cryptobook) - [Euler's Theorem in Detail | CryptoBook](#euler-s-theorem-in-detail-cryptobook) - [Rings | CryptoBook](#rings-cryptobook) - [Fields | CryptoBook](#fields-cryptobook) - [Applications | CryptoBook](#applications-cryptobook) - [Another take on groups | CryptoBook](#another-take-on-groups-cryptobook) - [NTRU | CryptoBook](#ntru-cryptobook) - [Ideals | CryptoBook](#ideals-cryptobook) - [HKZ reduced | CryptoBook](#hkz-reduced-cryptobook) - [Low Private Component Attacks | CryptoBook](#low-private-component-attacks-cryptobook) - [Ring-LWE | CryptoBook](#ring-lwe-cryptobook) - [Discrete Log Problem | CryptoBook](#discrete-log-problem-cryptobook) - [Untitled | CryptoBook](#untitled-cryptobook) - [MITM | CryptoBook](#mitm-cryptobook) - [Cryptographic lattice problems | CryptoBook](#cryptographic-lattice-problems-cryptobook) - [Learning with errors (LWE) | CryptoBook](#learning-with-errors-lwe-cryptobook) - [LLL reduction | CryptoBook](#lll-reduction-cryptobook) - [Resources and notations | CryptoBook](#resources-and-notations-cryptobook) - [Lattice reduction | CryptoBook](#lattice-reduction-cryptobook) - [RSA application | CryptoBook](#rsa-application-cryptobook) - [Gram-Schmidt Orthogonalization | CryptoBook](#gram-schmidt-orthogonalization-cryptobook) - [LLL reduced | CryptoBook](#lll-reduced-cryptobook) - [Elliptic Curve Cryptography | CryptoBook](#elliptic-curve-cryptography-cryptobook) - [RSA | CryptoBook](#rsa-cryptobook) - [Common Modulus Attack | CryptoBook](#common-modulus-attack-cryptobook) - [Proof of correctness | CryptoBook](#proof-of-correctness-cryptobook) - [Continued Fractions | CryptoBook](#continued-fractions-cryptobook) - [Boneh-Durfee Attack | CryptoBook](#boneh-durfee-attack-cryptobook) - [Probability Theory | CryptoBook](#probability-theory-cryptobook) - [Diffie-Hellman | CryptoBook](#diffie-hellman-cryptobook) - [Encryption | CryptoBook](#encryption-cryptobook) - [Interactive fun | CryptoBook](#interactive-fun-cryptobook) - [Isogenies | CryptoBook](#isogenies-cryptobook) - [Isogeny and Ramanujan Graphs | CryptoBook](#isogeny-and-ramanujan-graphs-cryptobook) - [Hard lattice problems | CryptoBook](#hard-lattice-problems-cryptobook) - [Extensions of Coppersmith algorithm | CryptoBook](#extensions-of-coppersmith-algorithm-cryptobook) - [Sets and Functions | CryptoBook](#sets-and-functions-cryptobook) - [The One Time Pad | CryptoBook](#the-one-time-pad-cryptobook) - [AES | CryptoBook](#aes-cryptobook) - [Recovering the Modulus | CryptoBook](#recovering-the-modulus-cryptobook) - [Groups | CryptoBook](#groups-cryptobook) - [Introduction to Isogeny Cryptography | CryptoBook](#introduction-to-isogeny-cryptography-cryptobook) - [Lagrange's algorithm | CryptoBook](#lagrange-s-algorithm-cryptobook) - [Short integer solutions (SIS) | CryptoBook](#short-integer-solutions-sis-cryptobook) - [Minkowski reduced | CryptoBook](#minkowski-reduced-cryptobook) - [LLL reduction | CryptoBook](#lll-reduction-cryptobook) - [Introduction | CryptoBook](#introduction-cryptobook) - [Wiener's Attack | CryptoBook](#wiener-s-attack-cryptobook) - [Rijndael Finite Field | CryptoBook](#rijndael-finite-field-cryptobook) - [Introduction / overview | CryptoBook](#introduction-overview-cryptobook) - [Lattices of interest | CryptoBook](#lattices-of-interest-cryptobook) - [Round Transformations | CryptoBook](#round-transformations-cryptobook) - [The Birthday paradox / attack | CryptoBook](#the-birthday-paradox-attack-cryptobook) - [Coppersmith algorithm | CryptoBook](#coppersmith-algorithm-cryptobook) --- # CryptoBook | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/#about-this-project) About this project ---------------------------------------------------------------------------------------- CryptoBook is a community project, developed by members of [CryptoHack](https://cryptohack.org/) 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](https://www.sagemath.org/) 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](https://discord.gg/eJaJ3xC) [NextBook Plan](https://cryptohack.gitbook.io/cryptobook/todo) Last updated 4 years ago Was this helpful? --- # Division and Greatest common divisor | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd#introduction) 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 f**undamentals** 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!_ [](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd#division) 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 > 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 Copy 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 Copy 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. [](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd#greatest-common-divisor) 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:** Copy # 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 #### [](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd#things-to-think-about) 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? [PreviousMathematical Notation](https://cryptohack.gitbook.io/cryptobook/fundamentals/notation) [NextEuclidean Algorithm](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd/euclidean-algorithm) Last updated 4 years ago Was this helpful? --- # Contributors | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/contributors#thank-you) 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. [](https://cryptohack.gitbook.io/cryptobook/contributors#our-writers) Our Writers -------------------------------------------------------------------------------------- * ... * You? [](https://cryptohack.gitbook.io/cryptobook/contributors#join-cryptobook) Join CryptoBook ---------------------------------------------------------------------------------------------- If you would like to join the team, come over to our [Discord Channel](https://discord.gg/eJaJ3xC) and talk with us about your ideas [PreviousSample Page](https://cryptohack.gitbook.io/cryptobook/style-guide/sample-page) [NextMathematical Notation](https://cryptohack.gitbook.io/cryptobook/fundamentals/notation) Last updated 4 years ago Was this helpful? --- # Sample Page | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/style-guide/sample-page#introduction) 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. [](https://cryptohack.gitbook.io/cryptobook/style-guide/sample-page#laws-of-addition) 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 ### [](https://cryptohack.gitbook.io/cryptobook/style-guide/sample-page#interesting-identity) 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 ### [](https://cryptohack.gitbook.io/cryptobook/style-guide/sample-page#sage-example) Sage Example Copy 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 [](https://cryptohack.gitbook.io/cryptobook/style-guide/sample-page#further-resources) Further Resources ------------------------------------------------------------------------------------------------------------- * Links to * Other interesting * Resources ### [](https://cryptohack.gitbook.io/cryptobook/style-guide/sample-page#undefined) [PreviousStyle Guide](https://cryptohack.gitbook.io/cryptobook/style-guide) [NextContributors](https://cryptohack.gitbook.io/cryptobook/contributors) Last updated 4 years ago Was this helpful? --- # Theorems of Wilson, Euler, and Fermat | CryptoBook ### [](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat#wilsons-theorem) Wilson's Theorem A positive integer n\>1n > 1n\>1is a prime **if and only if**: (n−1)!≡−1mod  n(n-1)! \\equiv -1 \\mod n (n−1)!≡−1modn ### [](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat#eulers-theorem) Euler's Theorem Let n∈Z+n \\in \\mathbb{Z}^{+}n∈Z+ and a∈Za \\in \\mathbb{Z}a∈Z s.t. gcd(a,n)\=1gcd(a, n) = 1gcd(a,n)\=1, then: aϕ(n)≡1mod  na^{\\phi(n)} \\equiv 1 \\mod naϕ(n)≡1modn ### [](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat#fermats-little-theorem) Fermat's Little Theorem Let pppbe a prime and a∈Za \\in \\mathbb{Z}a∈Z, then: ap≡amod  pa^p \\equiv a \\mod pap≡amodp or equivalently: ap−1≡1mod  pa^{p-1} \\equiv 1 \\mod pap−1≡1modp ### [](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat#reference) Reference 1. [Wilson's Theorem - Brilliant](https://brilliant.org/wiki/wilsons-theorem/) 2. [Euler's Theorem - Brilliant](https://brilliant.org/wiki/eulers-theorem/) 3. [Fermat's Little Theorem - Brilliant](https://brilliant.org/wiki/fermats-little-theorem/) [PreviousModular Arithmetic](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic) [NextFermat's Little Theorem in Detail](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat/fermat-euler-theorem) Last updated 4 years ago Was this helpful? --- # Style Guide | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/style-guide#working-together) 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 [](https://cryptohack.gitbook.io/cryptobook/style-guide#general-tips) 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](https://cryptohack.gitbook.io/cryptobook/todo) 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 [](https://cryptohack.gitbook.io/cryptobook/style-guide#page-structure) 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](https://cryptohack.gitbook.io/cryptobook/todo) . * 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](https://cryptohack.gitbook.io/cryptobook/style-guide/sample-page) [](https://cryptohack.gitbook.io/cryptobook/style-guide#formatting) Formatting ----------------------------------------------------------------------------------- ### [](https://cryptohack.gitbook.io/cryptobook/style-guide#mathematics-notation) 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? ### [](https://cryptohack.gitbook.io/cryptobook/style-guide#code-blocks) 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 Copy # Example a = 3 b = 6 print(a+b) # 9 ### [](https://cryptohack.gitbook.io/cryptobook/style-guide#algorithms) Algorithms * Algorithms should be presented as?? Copy // todo [PreviousBook Plan](https://cryptohack.gitbook.io/cryptobook/todo) [NextSample Page](https://cryptohack.gitbook.io/cryptobook/style-guide/sample-page) Last updated 4 years ago Was this helpful? --- # Fermat's Little Theorem in Detail | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat/fermat-euler-theorem#introduction) 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. [](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat/fermat-euler-theorem#fermats-little-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! Copy 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. [PreviousTheorems of Wilson, Euler, and Fermat](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat) [NextEuler's Theorem in Detail](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat/eulers-theorem-in-detail) Last updated 4 years ago Was this helpful? --- # Mathematical Notation | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/fundamentals/notation#introduction) 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 [](https://cryptohack.gitbook.io/cryptobook/fundamentals/notation#mathematical-objects) Mathematical Objects ----------------------------------------------------------------------------------------------------------------- ### [](https://cryptohack.gitbook.io/cryptobook/fundamentals/notation#special-sets) Special Sets * C\\mathbb{C}C: denotes the set of complex numbers * R\\mathbb{R}R: denotes the set of real numbers * Z\\mathbb{Z}Z: denotes the set of integers * Q\\mathbb{Q}Q: denotes the set of rational numbers * N\\mathbb{N}N: denotes the set of natural numbers (non-negative integers) * Z/nZ\\mathbb{Z}/n\\mathbb ZZ/nZ: denotes the set of integers mod nnn Copy """ 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 * We refer to unit groups by R×R^\\timesR× or R∗R^\*R∗. Example: (Z/nZ)×(\\mathbb Z/n \\mathbb Z)^\\times(Z/nZ)× * We refer to finite fields with qqq elements by Fq\\mathbb{F}\_qFq​ * We refer to a general field by kkk * We refer to the algebraic closure of this field by kˉ\\bar{k}kˉ Copy """ 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 Copy """ 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 Copy """ 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 ### [](https://cryptohack.gitbook.io/cryptobook/fundamentals/notation#relation-operators) Relation operators * ∈\\in∈means is an element of (belongs to) ### [](https://cryptohack.gitbook.io/cryptobook/fundamentals/notation#logical-notation) Logical Notation * ∀\\forall∀means for all * ∃\\exists∃means there exists. ∃!\\exists!∃! means uniquely exists ### [](https://cryptohack.gitbook.io/cryptobook/fundamentals/notation#operators) Operators * Pr(A)Pr(A)Pr(A) means the probability of an event AAAto happen. Sometimes denoted as Pr\[A\]Pr\[A\]Pr\[A\]or as P(A)P(A)P(A) [PreviousContributors](https://cryptohack.gitbook.io/cryptobook/contributors) [NextDivision and Greatest common divisor](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd) Last updated 4 years ago Was this helpful? --- # Modular Arithmetic | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic#introduction) 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. [](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic#congruences) 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 Copy 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](https://en.wikipedia.org/wiki/Exponentiation_by_squaring) algorithm, so we needn't worry about it taking too much time when working with high powers Copy 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 [](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic#modular-inverse) 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](https://en.wikipedia.org/wiki/B%C3%A9zout%27s_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)× Copy 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](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) (that outputs solutions indddandkkkto the equationcd−kn\=1cd-kn=1cd−kn\=1from above). Copy xgcd(7, 10) # find (gcd(a, b), u, v) in au + bv = gcd(a, b) # (1, 3, -2) <-- (gcd(7, 10), d, -k) [PreviousEuclidean Algorithm](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd/euclidean-algorithm) [NextTheorems of Wilson, Euler, and Fermat](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat) Last updated 4 years ago Was this helpful? --- # Euclidean Algorithm | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd/euclidean-algorithm#introduction) Introduction ----------------------------------------------------------------------------------------------------------------------------- Although we have functions that can compute our gcd⁡\\gcdgcdeasily 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. [](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd/euclidean-algorithm#euclidean-algorithm) Euclidean Algorithm ------------------------------------------------------------------------------------------------------------------------------------------- **Important Remark** > If a\=b⋅q+ra = b \\cdot q + ra\=b⋅q+rand d\=gcd⁡(a,b)d = \\gcd(a, b)d\=gcd(a,b) then d∣rd | rd∣r. Therefore gcd⁡(a,b)\=gcd⁡(b,r)\\gcd(a, b) = \\gcd(b, r)gcd(a,b)\=gcd(b,r) ### [](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd/euclidean-algorithm#algorithm) Algorithm We write the following: 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 Or iteratively rk−2\=qk⋅rk−1+rkr\_{k-2} = q\_k \\cdot r\_{k-1} + r\_krk−2​\=qk​⋅rk−1​+rk​ until we find a 000. Then we stop Now here's the trick: 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 If d\=gcd⁡(a,b)d = \\gcd(a, b)d\=gcd(a,b) then ddd divides r0,r1,...rn−1r\_0, r\_1, ... r\_{n-1}r0​,r1​,...rn−1​ Pause and ponder. Make you you understand why that works. **Example:** Calculate 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) **Code** Copy def my_gcd(a, b): # If a < b swap them if a < b: a, b = b, a # If we encounter 0 return a if b == 0: return a else: r = a % b return my_gcd(b, r) print(my_gcd(24, 15)) # 3 **Exercises**: 1. Pick 2 numbers and calculate their gcd⁡\\gcdgcdby hand. 2. Implement the algorithm in Python / Sage and play with it. **Do not copy paste the code** [](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd/euclidean-algorithm#extended-euclidean-algorithm) Extended Euclidean Algorithm ------------------------------------------------------------------------------------------------------------------------------------------------------------- This section needs to be expanded a bit. **Bezout's identity** > Let d\=gcd⁡(a,b)d = \\gcd(a, b)d\=gcd(a,b). Then there exists u,vu, vu,v such that au+bv\=dau + bv = dau+bv\=d The extended euclidean algorithm aims to find d\=gcd⁡(a,b), and u,vd = \\gcd(a, b), \\text{ and }u, vd\=gcd(a,b), and u,vgiven a,ba, ba,b Copy # 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 [PreviousDivision and Greatest common divisor](https://cryptohack.gitbook.io/cryptobook/fundamentals/division-and-gcd) [NextModular Arithmetic](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic) Last updated 4 years ago Was this helpful? --- # Book Plan | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/todo#philosophy) 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!! [](https://cryptohack.gitbook.io/cryptobook/todo#proposed-topics) Proposed topics -------------------------------------------------------------------------------------- This list is **not complete** so please add to it as you see fit. ### [](https://cryptohack.gitbook.io/cryptobook/todo#mathematical-background) Mathematical Background #### [](https://cryptohack.gitbook.io/cryptobook/todo#fundamentals) 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 #### [](https://cryptohack.gitbook.io/cryptobook/todo#number-theory) Number Theory Mainly thinking things like * Prime decomposition and distribution * Primality testing * Euler's theorem * Factoring * Legendre / Jacobi symbol #### [](https://cryptohack.gitbook.io/cryptobook/todo#abstract-algebra) 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 #### [](https://cryptohack.gitbook.io/cryptobook/todo#basilar-cryptanalysis-forms) Basilar Cryptanalysis forms * Introduction to Cryptanalysis * A linear Approach to Cryptanalysis * Matsui's Best biases algorithm * A Differential Approach to Cryptanalysis #### [](https://cryptohack.gitbook.io/cryptobook/todo#elliptic-curves) Elliptic Curves * Weierstrass * Montgomery * Edwards * Counting points (Schoof's algorithm) * Complex multiplication * [Good reference, thanks Joachim](https://crypto.stanford.edu/pbc/thesis.pdf) **Generating Elliptic Curves** * [Generating Anomalous curves](http://www.monnerat.info/publications/anomalous.pdf) * Generating curves of prime order * Generating supersingular curves [Wikipedia](https://en.wikipedia.org/wiki/Supersingular_elliptic_curve#Examples) * [Generating non-supersinular curves of low embedding degree](https://eprint.iacr.org/2004/058.pdf) * Generating curves of arbitary order (hard) * [Thesis on the topic](https://www.math.leidenuniv.nl/scripties/Broker.pdf) * Sage implementation [ChiCube's script](https://gist.github.com/ChiCubed/0977601c9ce88eda03b9d2576231192e) #### [](https://cryptohack.gitbook.io/cryptobook/todo#hyperelliptic-curves) Hyperelliptic curves * Generalization of elliptic curves * Recovering a group structure using the Jacobian * Example: genus one curves, jacobian is isomorphic to the set of points * Mumford representation of divisors * Computing the order of the Jacobian * [For characteristic 2^n: Example 56](https://www.math.uwaterloo.ca/~ajmeneze/publications/hyperelliptic.pdf) * Hyper Metroid example ### [](https://cryptohack.gitbook.io/cryptobook/todo#security-background) 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 ### [](https://cryptohack.gitbook.io/cryptobook/todo#asymmetric-cryptography) Asymmetric Cryptography #### [](https://cryptohack.gitbook.io/cryptobook/todo#rsa) 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](https://eprint.iacr.org/2002/073.pdf) * [Bellcore Attack (Low Voltage Attack)](https://eprint.iacr.org/2012/553.pdf) #### [](https://cryptohack.gitbook.io/cryptobook/todo#paillier-cryptosystem) Paillier Cryptosystem * Textbook protocol #### [](https://cryptohack.gitbook.io/cryptobook/todo#elgamal-encryption-system) ElGamal Encryption System * Textbook protocol * ElGamal Digital Signature Scheme #### [](https://cryptohack.gitbook.io/cryptobook/todo#diffie-hellman) Diffie-Hellman * Textbook protocol * Strong primes, and why #### [](https://cryptohack.gitbook.io/cryptobook/todo#elliptic-curve-cryptography) Elliptic Curve Cryptography * ECDSA * EdDSA ### [](https://cryptohack.gitbook.io/cryptobook/todo#symmetric-cryptography) Symmetric Cryptography #### [](https://cryptohack.gitbook.io/cryptobook/todo#one-time-pad) One Time Pad * XOR and its properties * XOR as One Time Pad * Generalized One Time Pad **Block Ciphers** * AES **Stream Ciphers** * Affine * RC4 ### [](https://cryptohack.gitbook.io/cryptobook/todo#hashes) **Hashes** * Introduction * Trapdoor Functions * MD family * SHA family * BLAKE Hash family * // TODO: Insert Attacks ### [](https://cryptohack.gitbook.io/cryptobook/todo#isogeny-based-cryptography) Isogeny Based Cryptography * Isogenies * Isogeny graphs * Torsion poins * SIDH * SIKE * BIKE ### [](https://cryptohack.gitbook.io/cryptobook/todo#cryptographic-protocols) Cryptographic Protocols #### [](https://cryptohack.gitbook.io/cryptobook/todo#zero-knowledge-proofs) Zero-knowledge proofs * Schnorr proof of knowledge for dlog * Core definitions * Proof of equality of dlog * Proof of knowledge of a group homomorphism preimage #### [](https://cryptohack.gitbook.io/cryptobook/todo#formal-verification-of-security-protocols) 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 #### [](https://cryptohack.gitbook.io/cryptobook/todo#usefull-resources-books-articles-..-based-on-my-material) 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) [PreviousCryptoBook](https://cryptohack.gitbook.io/cryptobook) [NextStyle Guide](https://cryptohack.gitbook.io/cryptobook/style-guide) Last updated 4 years ago Was this helpful? --- # Pollard rho | CryptoBook [PreviousInteger Factorization](https://cryptohack.gitbook.io/cryptobook/integer-factorization) [NextSieves](https://cryptohack.gitbook.io/cryptobook/integer-factorization/sieves) Last updated 4 years ago Was this helpful? --- # Quadratic Residues | CryptoBook [PreviousEuler's Theorem in Detail](https://cryptohack.gitbook.io/cryptobook/fundamentals/modular-arithmetic/theorems-of-wilson-euler-and-fermat/eulers-theorem-in-detail) [NextContinued Fractions](https://cryptohack.gitbook.io/cryptobook/fundamentals/continued-fractions) Last updated 4 years ago Was this helpful? --- # Polynomials | CryptoBook // symmetric polynomials // discriminants // resultants [PreviousFields](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/fields) [NextUntitled](https://cryptohack.gitbook.io/cryptobook/elliptic-curves/untitled) Last updated 4 years ago Was this helpful? --- # Polynomials With Shared Roots | CryptoBook * 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! [PreviousIdeals](https://cryptohack.gitbook.io/cryptobook/ideals) [NextInteger Factorization](https://cryptohack.gitbook.io/cryptobook/integer-factorization) Last updated 4 years ago Was this helpful? --- # Sieves | CryptoBook [PreviousPollard rho](https://cryptohack.gitbook.io/cryptobook/integer-factorization/pollard-rho) [NextGroups](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups) Last updated 4 years ago Was this helpful? --- # Integer Factorization | CryptoBook ### [](https://cryptohack.gitbook.io/cryptobook/integer-factorization#overview) 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 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 [PreviousContinued Fractions](https://cryptohack.gitbook.io/cryptobook/fundamentals/continued-fractions) [NextPolynomials With Shared Roots](https://cryptohack.gitbook.io/cryptobook/polynomials-with-shared-roots) Last updated 4 years ago Was this helpful? --- # HKZ reduced | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/hkz-reduced#definition) Definition -------------------------------------------------------------------------------------------------------------------- Let πi\\pi\_iπi​as the projection to the orthogonal complement of {bj}j\=1i−1\\left\\{b\_j\\right\\}\_{j=1}^{i-1}{bj​}j\=1i−1​.Then the basis is **HKZ-reduced** if it is size-reduced and ∣∣bi∗∣∣\=λ1(πi(L))||b\_i^\*||=\\lambda\_1\\left(\\pi\_i(L)\\right)∣∣bi∗​∣∣\=λ1​(πi​(L)). This definition gives us a relatively simple way to compute a HKZ-reduced basis by iteratively finding the shortest vector in orthogonal projections. [](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/hkz-reduced#bounds) Bounds ------------------------------------------------------------------------------------------------------------ 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​ [PreviousMinkowski reduced](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/minkowski-reduced) [NextLLL reduced](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/lll-reduced) Last updated 4 years ago Was this helpful? --- # Low Private Component Attacks | CryptoBook [Wiener's Attack](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack) [Boneh-Durfee Attack](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/boneh-durfee-attack) [PreviousRSA application](https://cryptohack.gitbook.io/cryptobook/untitled/rsa-application) [NextWiener's Attack](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack) Last updated 4 years ago Was this helpful? --- # Ring-LWE | CryptoBook [PreviousLearning with errors (LWE)](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/learning-with-errors-lwe) [NextNTRU](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/ntru) Last updated 4 years ago Was this helpful? --- # Discrete Log Problem | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups/untitled#discrete-log-problem) Discrete log problem ---------------------------------------------------------------------------------------------------------------------------- Given any groupGGGand elementsa,ba,ba,bsuch that an\=ba^n=ban\=b, the problem of solving fornnnis known as the disctete log problem (DLP). In sage, this can be done for general groups by calling `discrete_log` Copy 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 [](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups/untitled#discrete-log-over) Discrete log over (Z/nZ)∗\\left(\\mathbb Z/n\\mathbb Z\\right)^\*(Z/nZ)∗ ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Typically, one considers the discrete log problem in (Z/nZ)∗\\left(\\mathbb Z/n\\mathbb Z\\right)^\*(Z/nZ)∗, i.e. the multiplicative group of integersmod n\\text{mod }nmod n. Explicitly, the problem asks forxxxgiven ax\=b(modn)a^x=b\\pmod nax\=b(modn). This can be done by calling `b.log(a)` in sage: Copy sage: R = Integers(99) sage: a = R(4) sage: b = a^9 sage: b.log(a) 9 This section is devoted to helping the reader understand which functions are called when for this specific instance of DLP. Whennnnis 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 n\=pn=pn\=pis a prime, Pari `znlog` will be used, which uses a linear sieve index calculus method, suitable for p<1050∼2166p < 10^{50} \\sim 2 ^{166}p<1050∼2166. When n\=pkn = p^kn\=pk, 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) Copy x = int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))")) x = gp.znlog(b, gp.Mod(a, n)) #### [](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups/untitled#example) Example Given a small prime, we can compare the Pari method with the Sage defaults Copy 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 We can also solve this problem with even larger primes in a very short time Copy 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 [](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups/untitled#discrete-log-over-1) Discrete log over E(k)E(k)E(k) ------------------------------------------------------------------------------------------------------------------------------------- // elliptic curve discrete log functions [PreviousAnother take on groups](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups/another-take-on-groups) [NextRings](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/rings) Last updated 4 years ago Was this helpful? --- # Untitled | CryptoBook [PreviousPolynomials](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/polynomials) [NextIntroduction](https://cryptohack.gitbook.io/cryptobook/lattices/definitions) Last updated 4 years ago Was this helpful? --- # MITM | CryptoBook [PreviousDiffie-Hellman](https://cryptohack.gitbook.io/cryptobook/diffie-hellman) [NextElliptic Curve Cryptography](https://cryptohack.gitbook.io/cryptobook/elliptic-curve-cryptography) Last updated 4 years ago Was this helpful? --- # Cryptographic lattice problems | CryptoBook [Short integer solutions (SIS)](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/short-integer-solutions-sis) [Learning with errors (LWE)](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/learning-with-errors-lwe) [Ring-LWE](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/ring-lwe) [NTRU](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/ntru) [PreviousLattices of interest](https://cryptohack.gitbook.io/cryptobook/lattices/lattices-of-interest) [NextShort integer solutions (SIS)](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/short-integer-solutions-sis) Last updated 4 years ago Was this helpful? --- # Learning with errors (LWE) | CryptoBook [PreviousShort integer solutions (SIS)](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/short-integer-solutions-sis) [NextRing-LWE](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/ring-lwe) Last updated 4 years ago Was this helpful? --- # LLL reduction | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction#introduction) 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. [PreviousIntroduction](https://cryptohack.gitbook.io/cryptobook/lattices/definitions) [NextGram-Schmidt Orthogonalization](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gram-schmidt-orthogonalization) Last updated 4 years ago Was this helpful? --- # Resources and notations | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/lattices/resources-and-notations#references-resources) 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 [](https://cryptohack.gitbook.io/cryptobook/lattices/resources-and-notations#notation) Notation ---------------------------------------------------------------------------------------------------- * LLL lattice * dim⁡(L)\\dim(L)dim(L)dimension of lattice * vol(L)\\text{vol}(L)vol(L)volume of lattice * bib\_ibi​ a chosen basis for LLL * B\\mathcal BB matrix whose iiith row vectors is bib\_ibi​ * bi∗b\_i^\*bi∗​ Gram-Schmidt orthogonalization of bib\_ibi​(without normalization) * B∗\\mathcal B^\*B∗matrix whose iiith row vectors is 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∗​⟩​ Gram-Schmidt coefficients * λi(L)\\lambda\_i(L)λi​(L) the iiith successive minima of LLL [PreviousInteractive fun](https://cryptohack.gitbook.io/cryptobook/lattices/interactive-fun) [NextRSA](https://cryptohack.gitbook.io/cryptobook/untitled) Last updated 4 years ago Was this helpful? --- # Lattice reduction | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem#overview) 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. [](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem#definitions) 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}ith**successive 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](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gaussian-reduction) ) 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. [](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem#exercises) 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​. [PreviousLLL reduction](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/lll-reduced-basis) [NextMinkowski reduced](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/minkowski-reduced) Last updated 4 years ago Was this helpful? --- # RSA application | CryptoBook #### [](https://cryptohack.gitbook.io/cryptobook/untitled/rsa-application#pycryptodome) Pycryptodome: Pycryptodome is a python library about cryptography, see the documentation below: [https://www.pycryptodome.org/en/latest/](https://www.pycryptodome.org/en/latest/) There is an example of RSA key generation with pycryptodome: Copy 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://cryptohack.gitbook.io/cryptobook/untitled/rsa-application#openssl) 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 #### [](https://cryptohack.gitbook.io/cryptobook/untitled/rsa-application#openssh) OpenSSH: [PreviousProof of correctness](https://cryptohack.gitbook.io/cryptobook/untitled/proof-of-correctness) [NextLow Private Component Attacks](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks) Last updated 4 years ago Was this helpful? --- # Gram-Schmidt Orthogonalization | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gram-schmidt-orthogonalization#overview) 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: Copy 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μ: Copy ( [-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. [](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gram-schmidt-orthogonalization#exercises) 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. [PreviousLLL reduction](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction) [NextLagrange's algorithm](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gaussian-reduction) Last updated 4 years ago Was this helpful? --- # LLL reduced | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/lll-reduced#definition) 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](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/lll-reduced-basis) ). [](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/lll-reduced#bounds) 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)​ [PreviousHKZ reduced](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/hkz-reduced) [NextApplications](https://cryptohack.gitbook.io/cryptobook/lattices/applications) Last updated 4 years ago Was this helpful? --- # Elliptic Curve Cryptography | CryptoBook [PreviousMITM](https://cryptohack.gitbook.io/cryptobook/diffie-hellman/mitm) [NextEncryption](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/encryption) Last updated 4 years ago Was this helpful? --- # RSA | CryptoBook 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. ### [](https://cryptohack.gitbook.io/cryptobook/untitled#i-introduction) I- Introduction: RSA is a [public-key cryptosystem](https://en.wikipedia.org/wiki/Public-key_cryptography) 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](https://en.wikipedia.org/wiki/Acronym) **RSA** comes from the surnames of [Ron Rivest](https://en.wikipedia.org/wiki/Ron_Rivest) , [Adi Shamir](https://en.wikipedia.org/wiki/Adi_Shamir) , and [Leonard Adleman](https://en.wikipedia.org/wiki/Leonard_Adleman) , who publicly described the algorithm in 1977. An equivalent system was developed secretly, in 1973 at [GCHQ](https://en.wikipedia.org/wiki/Government_Communications_Headquarters) (the British [signals intelligence](https://en.wikipedia.org/wiki/Signals_intelligence) agency), by the English mathematician [Clifford Cocks](https://en.wikipedia.org/wiki/Clifford_Cocks) . That system was [declassified](https://en.wikipedia.org/wiki/Classified_information) in 1997. All public-key systems are based on the concept of [_trapdoor functions_](https://en.wikipedia.org/wiki/Trapdoor_function#:~:text=A%20trapdoor%20function%20is%20a,are%20widely%20used%20in%20cryptography.) , 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](https://en.wikipedia.org/wiki/Integer_factorization) . 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](https://en.wikipedia.org/wiki/Shor%27s_algorithm) Formalize the introduction and include a discussion of the security based on the hardness of factoring integers. ### [](https://cryptohack.gitbook.io/cryptobook/untitled#ii-arithmetic-for-rsa) II- Arithmetic for RSA Before starting to introducing you RSA, a few arithmetic notions need to be introduce to understand perfectly other steps. ### [](https://cryptohack.gitbook.io/cryptobook/untitled#iii-key-generation) 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 ### [](https://cryptohack.gitbook.io/cryptobook/untitled#iv-signature) 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. ### [](https://cryptohack.gitbook.io/cryptobook/untitled#v-format) V- Format [PreviousResources and notations](https://cryptohack.gitbook.io/cryptobook/lattices/resources-and-notations) [NextProof of correctness](https://cryptohack.gitbook.io/cryptobook/untitled/proof-of-correctness) Last updated 4 years ago Was this helpful? --- # Common Modulus Attack | CryptoBook 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. [](https://cryptohack.gitbook.io/cryptobook/untitled/common-modulus-attack#what-we-know) 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. [](https://cryptohack.gitbook.io/cryptobook/untitled/common-modulus-attack#conditions-of-the-attack) 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 [](https://cryptohack.gitbook.io/cryptobook/untitled/common-modulus-attack#the-math-behind-the-attack) 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 [PreviousBoneh-Durfee Attack](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/boneh-durfee-attack) [NextRecovering the Modulus](https://cryptohack.gitbook.io/cryptobook/untitled/recovering-the-modulus) Last updated 4 years ago Was this helpful? --- # Proof of correctness | CryptoBook We now consider cd\=med\=mc^d = m^{ed} = mcd\=med\=mnecessary for the successful description of an RSA ciphertext. The core of this result is due to [Euler's theorem](https://en.wikipedia.org/wiki/Euler%27s_theorem) which states aϕ(n)≡1mod  na^{\\phi(n)} \\equiv 1 \\mod naϕ(n)≡1modn for all coprime integers (a,n)(a,n)(a,n) and ϕ(n)\\phi(n)ϕ(n) is [Euler's totient function](https://en.wikipedia.org/wiki/Euler%27s_totient_function) . As a reminder, we say two integers are coprime if they share no non-trivial factors. This is the same statement that gcd⁡(a,n)\=1\\gcd(a,n)=1gcd(a,n)\=1. From the definition of the protocol, we have that 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) for some k∈Zk \\in \\mathbb{Z}k∈Z. Combining this with Euler's theorem, we see that we recover mmmfrom the ciphertext 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​​ When the requirement gcd⁡(m,n)\=1\\gcd(m, n) = 1gcd(m,n)\=1does not hold, we can instead look at the equivalences modulo pppand qqqrespectively. Clearly, when gcd⁡(m,n)\=n,\\gcd(m, n) = n,gcd(m,n)\=n,we have that c≡m≡0mod  nc \\equiv m \\equiv 0 \\mod nc≡m≡0modnand our correctness still holds. Now, consider the case m\=k⋅p,m = k\\cdot p,m\=k⋅p,where we have that c≡m≡0mod  pc \\equiv m \\equiv 0 \\mod pc≡m≡0modpand cd≡(me)d(modq).c^d \\equiv (m^e)^d \\pmod q.cd≡(me)d(modq).Since we have already excluded the case that gcd⁡(m,q)\=q,\\gcd(m, q) = q,gcd(m,q)\=q,we can conclude that gcd⁡(m,q)\=1,\\gcd(m, q) = 1,gcd(m,q)\=1,as qqqis prime. This means that mℓϕ(q)≡1mod  qm^{\\ell\\phi(q)} \\equiv 1 \\mod qmℓϕ(q)≡1modqand by the multiplicative properties of the ϕ\\phiϕfunction, we determine that 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.We conclude by invoking the Chinese Remainder theorem with 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​ that me⋅d≡mmod  n.m^{e\\cdot d} \\equiv m \\mod n.me⋅d≡mmodn.The case for m\=k⋅qm = k\\cdot qm\=k⋅qfollows in a parallel manner. [PreviousRSA](https://cryptohack.gitbook.io/cryptobook/untitled) [NextRSA application](https://cryptohack.gitbook.io/cryptobook/untitled/rsa-application) Last updated 4 years ago Was this helpful? --- # Continued Fractions | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/fundamentals/continued-fractions#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​ [](https://cryptohack.gitbook.io/cryptobook/fundamentals/continued-fractions#notation) 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;\] [](https://cryptohack.gitbook.io/cryptobook/fundamentals/continued-fractions#computation-of-simple-continued-fractions) 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`. Copy def continued_fraction_list(xi): ai = floor(xi) if xi == ai: # last coefficient return [ai] return [ai] + continued_fraction_list(1/(x - ai)) [](https://cryptohack.gitbook.io/cryptobook/fundamentals/continued-fractions#convergents-of-continued-fraction) 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 Copy 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​∣ 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](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups/untitled) . The original paper can be found [here](https://ee.stanford.edu/~hellman/publications/24.pdf) . 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. [PreviousRecovering the Modulus](https://cryptohack.gitbook.io/cryptobook/untitled/recovering-the-modulus) [NextMITM](https://cryptohack.gitbook.io/cryptobook/diffie-hellman/mitm) Last updated 4 years ago Was this helpful? --- # Encryption | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/encryption#introduction) 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 kkk. 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. [](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/encryption#formal-definition) Formal definition ----------------------------------------------------------------------------------------------------------------------- We introduce some notation first: We will use M\\mathcal MM to denote the set of al possible message, K\\mathcal KK is the set of all possible keys and C\\mathcal CC is the set of ciphertexts. A symmetric encryption scheme E\\mathcal EEis a tuple of efficiently computable functions (KGen, Enc, Dec)(\\text{KGen, Enc, Dec})(KGen, Enc, Dec).: * Selects a key at random from the key space. * Enc:M×K↦C\\text{Enc}: \\mathcal M \\times \\mathcal K \\mapsto \\mathcal CEnc:M×K↦C. Encrypts the message mmm with the key kkk into a ciphertext c\=Enc(m,k)c = \\text{Enc}(m, k)c\=Enc(m,k). Sometimes written as 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×{⊥}. Decrypts the ciphertexts ccc with the key kkk into the message mmm or returns an error (⊥\\bot⊥). m\=Dec(c,k)m = \\text{Dec}(c, k)m\=Dec(c,k). Sometimes written as m\=Deck(c)m = \\text{Dec}\_k(c)m\=Deck​(c) ForE\\mathcal EE to be useful we need that 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. 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** [PreviousElliptic Curve Cryptography](https://cryptohack.gitbook.io/cryptobook/elliptic-curve-cryptography) [NextThe One Time Pad](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/the-one-time-pad) Last updated 4 years ago Was this helpful? --- # Interactive fun | CryptoBook Inspired by: [https://crypto.katestange.net/lattice-tools/](https://crypto.katestange.net/lattice-tools/) **Lattice + LLL + Fundamental mesh plot** Copy @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)) ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_LNgyX24sOJlTW5zG1%252F-M_LYRpwOzf-fLi5b68U%252Fimage.png%3Falt%3Dmedia%26token%3D95f0c8cc-f01d-41d0-b75e-bfa75e80fb9b&width=768&dpr=4&quality=100&sign=796e9616&sv=2) #### [](https://cryptohack.gitbook.io/cryptobook/lattices/interactive-fun#lattice--cvp) **Lattice + CVP** Copy @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)) ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_LNgyX24sOJlTW5zG1%252F-M_LTcfAQaAotEfZa8w-%252Fimage.png%3Falt%3Dmedia%26token%3D18d60326-66f4-4fd1-be26-0c9f7075e99c&width=768&dpr=4&quality=100&sign=12f2d5ef&sv=2) Copy @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)) **Q-ary plots** Copy # 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)) [PreviousNTRU](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/ntru) [NextResources and notations](https://cryptohack.gitbook.io/cryptobook/lattices/resources-and-notations) Last updated 4 years ago Was this helpful? --- # Isogenies | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/isogeny-based-cryptography/untitled#motivation) 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). [](https://cryptohack.gitbook.io/cryptobook/isogeny-based-cryptography/untitled#isogenies-of-elliptic-curves) Isogenies of Elliptic Curves ----------------------------------------------------------------------------------------------------------------------------------------------- **Definition**: We say an **isogeny** ϕ:E1→E2\\phi : E\_1 \\to E\_2ϕ:E1​→E2​ between elliptic curves defined over a field kkkis a surjective morphism of curves which includes a group homomorphism E1(kˉ)→E1(kˉ)E\_1(\\bar{k}) \\to E\_1(\\bar{k})E1​(kˉ)→E1​(kˉ) [](https://cryptohack.gitbook.io/cryptobook/isogeny-based-cryptography/untitled#references) References ----------------------------------------------------------------------------------------------------------- * [https://arxiv.org/pdf/1711.04062.pdf](https://arxiv.org/pdf/1711.04062.pdf) * [https://math.mit.edu/classes/18.783/2019/LectureNotes5.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](https://doc.sagemath.org/html/en/reference/arithmetic_curves/sage/schemes/elliptic_curves/ell_curve_isogeny.html) [PreviousIntroduction to Isogeny Cryptography](https://cryptohack.gitbook.io/cryptobook/isogeny-based-cryptography/introduction-to-isogeny-cryptography) [NextIsogeny and Ramanujan Graphs](https://cryptohack.gitbook.io/cryptobook/isogeny-based-cryptography/isogeny-and-ramanujan-graphs) Last updated 4 years ago Was this helpful? --- # Isogeny and Ramanujan Graphs | CryptoBook **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](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. [PreviousIsogenies](https://cryptohack.gitbook.io/cryptobook/isogeny-based-cryptography/untitled) [NextSets and Functions](https://cryptohack.gitbook.io/cryptobook/appendices/sets-and-functions) Last updated 4 years ago Was this helpful? --- # Hard lattice problems | CryptoBook 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. [](https://cryptohack.gitbook.io/cryptobook/lattices/hard-lattice-problems#introduction) 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 s**hortest vector problem** or the c**losest 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! [](https://cryptohack.gitbook.io/cryptobook/lattices/hard-lattice-problems#shortest-vector-problem--gapsvp) 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∥ ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_G-TFN1no4S3ObmyHo%252F-M_Gj5lgZJDty2Zzb_z0%252Fimage.png%3Falt%3Dmedia%26token%3Dae64fce2-bc91-4409-8c16-9f11578b9586&width=768&dpr=4&quality=100&sign=6ef0ed96&sv=2) 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) ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_G-TFN1no4S3ObmyHo%252F-M_GjFcgh-BUvnCektQM%252Fimage.png%3Falt%3Dmedia%26token%3Dc79813cf-5694-41b8-aef6-298e5ca7c16a&width=768&dpr=4&quality=100&sign=c248c46&sv=2) #### [](https://cryptohack.gitbook.io/cryptobook/lattices/hard-lattice-problems#shortest-vector-problem) 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. ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_G-TFN1no4S3ObmyHo%252F-M_Gh1fr0WxHiv2Pztb9%252Fimage.png%3Falt%3Dmedia%26token%3D563ec5d7-5b3e-4c5e-a315-03671f48deb4&width=768&dpr=4&quality=100&sign=fbfc89f1&sv=2) #### [](https://cryptohack.gitbook.io/cryptobook/lattices/hard-lattice-problems#decision-svp-gapsvp) 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) #### [](https://cryptohack.gitbook.io/cryptobook/lattices/hard-lattice-problems#sage-example) Sage example Copy # 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) [](https://cryptohack.gitbook.io/cryptobook/lattices/hard-lattice-problems#closest-vector-problem--gapcvp) 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∥≤μ ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_G-TFN1no4S3ObmyHo%252F-M_HFedCjh99aYzSK_Xu%252Fimage.png%3Falt%3Dmedia%26token%3Dd16de51c-b866-4afb-b8af-4089efb22942&width=768&dpr=4&quality=100&sign=fef01200&sv=2) ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_LmOjlAdCfD46sZgwq%252F-M_LnKU-pZNnPu1TlwwS%252Fimage.png%3Falt%3Dmedia%26token%3Da7839a34-de2d-42d0-922a-798b416b8fbb&width=768&dpr=4&quality=100&sign=50babc52&sv=2) **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)⋅μ ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_G-TFN1no4S3ObmyHo%252F-M_HFb9yodzG6YE58qns%252Fimage.png%3Falt%3Dmedia%26token%3D13ed9bb5-4bd1-43b0-9ca7-d74c4c49d1cf&width=768&dpr=4&quality=100&sign=b852e8f6&sv=2) #### [](https://cryptohack.gitbook.io/cryptobook/lattices/hard-lattice-problems#decision-cvp-gapcvp) 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) #### [](https://cryptohack.gitbook.io/cryptobook/lattices/hard-lattice-problems#sage-example-1) Sage example Copy M = matrix([[-1, 2], [-2, 3]]) L = IntegerLattice(M) w = vector([1.8, 1.5]) L.closest_vector(w) # (2.00000000000000, 2.00000000000000) [](https://cryptohack.gitbook.io/cryptobook/lattices/hard-lattice-problems#bounded-distance-decoding) 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∥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 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∣ Copy 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 [](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups#subgroups) 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 ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_A5kWObEYFLML4-zks%252F-M_ADEsQa5d631gpS3My%252Fsubgroup1.svg%3Falt%3Dmedia%26token%3D037432df-2202-4210-8942-4ee8f8bd898c&width=768&dpr=4&quality=100&sign=67bf43a3&sv=2) **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 ### [](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups#generators) 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. Copy 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 [](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups#examples) Examples ------------------------------------------------------------------------------------------- // subgroups, quotient groups // cyclic groups [PreviousSieves](https://cryptohack.gitbook.io/cryptobook/integer-factorization/sieves) [NextAnother take on groups](https://cryptohack.gitbook.io/cryptobook/abstract-algebra/groups/another-take-on-groups) Last updated 4 years ago Was this helpful? --- # Introduction to Isogeny Cryptography | CryptoBook Making this section as a motivation to make sure this is part of the book. Something to work towards. [](https://cryptohack.gitbook.io/cryptobook/isogeny-based-cryptography/introduction-to-isogeny-cryptography#page-plan) Page Plan ------------------------------------------------------------------------------------------------------------------------------------- * Describe that there is a drive towards post-quantum algorithms * The incredible fact that paths within isogeny graphs commute (with the help of torsion points) * Supersingular ℓ\\ellℓ isogeny graphs are (ℓ+1)(\\ell + 1)(ℓ+1)regular Ramanujan graphs * Using paths through these graphs has spawned a whole bunch of protocols * SIKE / BIKE / ... * Hashes * ... * First we will look at the fundementals that allow these protocols to be expected as good candidates for post-quantum * Then we look at these protocols in more detail. Hopefully with SageMath implementations for each [](https://cryptohack.gitbook.io/cryptobook/isogeny-based-cryptography/introduction-to-isogeny-cryptography#references-i-plan-to-use) References I plan to use ------------------------------------------------------------------------------------------------------------------------------------------------------------------- * Introduction by Craig Costello * [https://eprint.iacr.org/2019/1321.pdf](https://eprint.iacr.org/2019/1321.pdf) * Mathematics of Isogeny Based Cryptography by Luca De Feo * [https://arxiv.org/pdf/1711.04062.pdf](https://arxiv.org/pdf/1711.04062.pdf) \- * The Arithmetic of Elliptic Curves by Joseph H. Silverman * [https://www.springer.com/gp/book/9780387094939](https://www.springer.com/gp/book/9780387094939) [PreviousThe Birthday paradox / attack](https://cryptohack.gitbook.io/cryptobook/hashes/the-birthday-paradox-attack) [NextIsogenies](https://cryptohack.gitbook.io/cryptobook/isogeny-based-cryptography/untitled) Last updated 4 years ago Was this helpful? --- # Lagrange's algorithm | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gaussian-reduction#overview) 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: Copy 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) The algorithm primarily consists of two steps, a reduction step where the size of mmmis brought down by a multiple of nnnand a swapping step that ensures mmmis always the largest number. We can adapt this idea for lattices: Copy 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 Here μ\\muμis actually the Gram-Schmidt coefficient μ2,1\\mu\_{2,1}μ2,1​and it turns out that this algorithm will always find the shortest possible basis! Using the basis 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)​ the Lagrange reduction looks like ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-MZOA-QwYo1UuEedHLGr%252F-MZOTWLcnoqcYd4fdEjd%252Flagrange1.svg%3Falt%3Dmedia%26token%3Df4f2c1f5-ccca-43f8-9e62-0ae2d5dd995b&width=768&dpr=4&quality=100&sign=796116bf&sv=2) ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-MZOA-QwYo1UuEedHLGr%252F-MZOT_KG709ulbgWmm21%252Flagrange2.svg%3Falt%3Dmedia%26token%3D12bc2be6-4f0a-4ea6-b9b6-690fe9e6b7c2&width=768&dpr=4&quality=100&sign=cef6ad51&sv=2) ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-MZOA-QwYo1UuEedHLGr%252F-MZOTbq3Ap6rtH4dAauI%252Flagrange3.svg%3Falt%3Dmedia%26token%3Ddcc87e8b-be64-46f9-8398-9dc1a3c218d9&width=768&dpr=4&quality=100&sign=511e9899&sv=2) and here we see it clearly gives the shortest vectors. [](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gaussian-reduction#optimality-proof) Optimality proof ----------------------------------------------------------------------------------------------------------------------------- Let LLLbe a lattice. The basis b1,b2b\_1,b\_2b1​,b2​is defined to be the shortest for any other basis b1′,b2′,∥b1′∥≤∥b2′∥b\_1',b\_2',\\left\\lVert b\_1'\\right\\rVert\\leq\\left\\lVert b\_2'\\right\\rVertb1′​,b2′​,∥b1′​∥≤∥b2′​∥, we have ∥b1∥≤∥b1′∥\\left\\lVert b\_1\\right\\rVert\\leq\\left\\lVert b\_1'\\right\\rVert∥b1​∥≤∥b1′​∥and ∥b2∥≤∥b2′∥\\left\\lVert b\_2\\right\\rVert\\leq\\left\\lVert b\_2'\\right\\rVert∥b2​∥≤∥b2′​∥. 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 b1,b2b\_1,b\_2b1​,b2​be the output of the Lagrange reduction for some lattice LLL. To prove that Lagrange reduction gives the shortest basis, we first show that ∥b1∥\\left\\lVert b\_1\\right\\rVert∥b1​∥is the shortest vector in LLL. We know that ∣⟨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​from the algorithm directly. Let v\=mb1+nb2∈Lv=mb\_1+nb\_2\\in Lv\=mb1​+nb2​∈Lbe any element in LLL. We first show that ∥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​ Since 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, this quantity is only 000when m\=n\=0m=n=0m\=n\=0and is a positive integer for all other cases, hence ∥v∥≥∥b1∥\\left\\lVert v\\right\\rVert\\geq\\left\\lVert b\_1\\right\\rVert∥v∥≥∥b1​∥and ∥b1∥\\left\\lVert b\_1\\right\\rVert∥b1​∥is a shortest vector of LLL. Note that we can have multiple vectors with the same norm as b1b\_1b1​, for instance −b1\-b\_1−b1​. So this is not a unique shortest vector. Suppose there exists some basis b1′,b2′b'\_1,b'\_2b1′​,b2′​for LLLsuch that ∥b1′∥≤∥b2′∥\\left\\lVert b\_1'\\right\\rVert\\leq\\left\\lVert b\_2'\\right\\rVert∥b1′​∥≤∥b2′​∥. We show that ∥b2∥≤∥b2′∥\\left\\lVert b\_2\\right\\rVert\\leq\\left\\lVert b\_2'\\right\\rVert∥b2​∥≤∥b2′​∥. Let b2′\=mb1+nb2b\_2'=mb\_1+nb\_2b2′​\=mb1​+nb2​. If n\=0n=0n\=0, then b2′\=±b1b\_2'=\\pm b\_1b2′​\=±b1​as b1′,b2′b\_1',b\_2'b1′​,b2′​must form a basis. This means that ∥b1∥\=∥b1′∥\=∥b2′∥\\left\\lVert b\_1\\right\\rVert=\\left\\lVert b\_1'\\right\\rVert=\\left\\lVert b\_2'\\right\\rVert∥b1​∥\=∥b1′​∥\=∥b2′​∥ and by the inequality above, we must have ±b1′\=b2\\pm b\_1'=b\_2±b1′​\=b2​or ±b1′\=b1+b2\\pm b\_1'=b\_1+b\_2±b1′​\=b1​+b2​. The first case tells us that ∥b1′∥\=∥b2∥\\left\\lVert b'\_1\\right\\rVert=\\left\\lVert b\_2\\right\\rVert∥b1′​∥\=∥b2​∥. By squaring the second case, we get ∥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​ but since ∥b1∥\\left\\lVert b\_1\\right\\rVert∥b1​∥is the shortest vector, ∥b1∥\=∥b2∥\\left\\lVert b\_1\\right\\rVert=\\left\\lVert b\_2\\right\\rVert∥b1​∥\=∥b2​∥. Otherwise, we have m,n≠0m,n\\neq0m,n\=0 and m2−mn+n2≥1m^2-mn+n^2\\geq1m2−mn+n2≥1, so ∥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​ Hence proving Lagrange's algorithm indeed gives us the shortest basis vectors. [](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gaussian-reduction#exercises) Exercises --------------------------------------------------------------------------------------------------------------- 1) Show that the output of Lagrange's algorithm generate the same lattice as the input. 2) Find a case where ∥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​∥. 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 [https://arxiv.org/abs/1009.4322](https://arxiv.org/abs/1009.4322) for the details) 3\*) Let μ2,1\=⌊μ2,1⌉+ε\=μ+ϵ\\mu\_{2,1}=\\lfloor\\mu\_{2,1}\\rceil+\\varepsilon=\\mu+\\epsilonμ2,1​\=⌊μ2,1​⌉+ε\=μ+ϵ, show that ∥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​∥ and show that ∣μ∣≥2|\\mu|\\geq2∣μ∣≥2for all steps in the algorithm except the first and last, hence ∥b1∥∥b2∥\\left\\lVert b\_1\\right\\rVert\\left\\lVert b\_2\\right\\rVert∥b1​∥∥b2​∥decreases by at least 3\\sqrt33​ at each loop and the algorithm runs in polynomial time. [PreviousGram-Schmidt Orthogonalization](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gram-schmidt-orthogonalization) [NextLLL reduction](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/lll-reduced-basis) Last updated 4 years ago Was this helpful? --- # Short integer solutions (SIS) | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/short-integer-solutions-sis#introduction) Introduction ----------------------------------------------------------------------------------------------------------------------------------------------- In this section we will study the short integer solution problem and a hashing algorithm that is based on this algorithm. [](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/short-integer-solutions-sis#short-integer-solution-problem) 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 β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 ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_G-TFN1no4S3ObmyHo%252F-M_Hua3xCZFECt_ktYcv%252Fajtai2.svg%3Falt%3Dmedia%26token%3Dec31a6fe-c62c-4401-a594-64f9de55a746&width=768&dpr=4&quality=100&sign=642e7d31&sv=2) ### [](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/short-integer-solutions-sis#hash-function-properties) 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**: Copy 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 ### [](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/short-integer-solutions-sis#cryptanalysis) 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) ### [](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/short-integer-solutions-sis#hermite-normal-form) Hermite normal form // TODO [](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/short-integer-solutions-sis#security-reduction) Security Reduction ----------------------------------------------------------------------------------------------------------------------------------------------------------- If somebody can explain the security bounds and reduction better, please do. [](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/short-integer-solutions-sis#resources) Resources ----------------------------------------------------------------------------------------------------------------------------------------- * [https://simons.berkeley.edu/sites/default/files/docs/14967/sis.pdf](https://simons.berkeley.edu/sites/default/files/docs/14967/sis.pdf) + [https://www.youtube.com/watch?v=qZIjVX61NFc&list=PLgKuh-lKre10rqiTYqJi6P4UlBRMQtPn0&index=4](https://www.youtube.com/watch?v=qZIjVX61NFc&list=PLgKuh-lKre10rqiTYqJi6P4UlBRMQtPn0&index=4) * [https://crypto.stanford.edu/cs355/18sp/lec9.pdf](https://crypto.stanford.edu/cs355/18sp/lec9.pdf) * [https://eprint.iacr.org/2015/939.pdf](https://eprint.iacr.org/2015/939.pdf) - page 18 [PreviousCryptographic lattice problems](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems) [NextLearning with errors (LWE)](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems/learning-with-errors-lwe) Last updated 4 years ago Was this helpful? --- # Minkowski reduced | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/minkowski-reduced#definition) 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 [](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/minkowski-reduced#bounds) 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). [](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/minkowski-reduced#exercises) 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 [PreviousLattice reduction](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem) [NextHKZ reduced](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem/hkz-reduced) Last updated 4 years ago Was this helpful? --- # LLL reduction | CryptoBook [](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/lll-reduced-basis#overview) 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 Copy def LLL(B): d = B.nrows() i = 1 while i14\\delta>\\frac14δ\>41​. Such bounds for the shortest vector will be elaborated in more detail in the section on reduced basis. [](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/lll-reduced-basis#exercises) Exercises -------------------------------------------------------------------------------------------------------------- 1) Implement the LLL in sage and experimentally verify that DDDdoes indeed decrease byδ\\deltaδeach time. 2) Show that the time complexity analysis is correct, and indeed each loop takes at most O(d2n)O\\left(d^2n\\right)O(d2n)operations. [PreviousLagrange's algorithm](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction/gaussian-reduction) [NextLattice reduction](https://cryptohack.gitbook.io/cryptobook/lattices/shortest-vector-problem) Last updated 4 years ago Was this helpful? --- # Introduction | CryptoBook 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." [](https://cryptohack.gitbook.io/cryptobook/lattices/definitions#definitions) Definitions ---------------------------------------------------------------------------------------------- A **lattice** LLL is a subgroup of Rn\\mathbb{R}^nRngenerated by bib\_ibi​, i.e. 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} where bib\_ibi​ are linearly independent vectors. Collectively, {bi}i\=1d\\left\\{b\_i\\right\\}\_{i=1}^d{bi​}i\=1d​ form a **basis** ofLLL. We say a set of vectors viv\_ivi​are **linearly independent** if the only solution to the equation ∑iaibi\=0\\sum\_{i} a\_i b\_i = 0∑i​ai​bi​\=0 is when all aia\_iai​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, denoteddim⁡L\\dim LdimL, is ddd. A lattice is **complete** if d\=nd=nd\=n. Note that we can always choose a subspace of Rn\\mathbb R^nRnsuch that the lattice is complete, namely the subspace generated by bib\_ibi​. The region Φ\={∑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} is known as the **fundamental mesh**. ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-MZDhVtU0LpddXtPo3r8%252F-MZDqMAbFAp_9a50Tg6H%252Flattice.svg%3Falt%3Dmedia%26token%3D2475ade7-4d1b-4ab1-b788-7451168a75c5&width=768&dpr=4&quality=100&sign=c47155c&sv=2) In the image above, we see the points of a lattice in R2\\mathbb R^2R2. 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 (mmmdimensional) 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: LetB\\mathcal BBbe ad×nd\\times nd×nmatrix whose rows are given by the basis vectors. Then the volume of a fundamental mesh is given by vol(L)\=∣det⁡(BBT)∣\\text{vol}(L)=\\sqrt{\\left|\\det\\left(\\mathcal B\\mathcal B^T\\right)\\right|}vol(L)\=∣det(BBT)∣​ A subset XXXof Rn\\mathbb R^nRnis known as **centrally symmetric** if x∈Xx\\in Xx∈Ximplies −x∈X\-x\\in X−x∈X. It is convex if for any x,y∈Xx,y\\in Xx,y∈X, the line joining x,yx,yx,y is contained in XXX, i.e. {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. Finally we can introduce the most important theorem about lattices, the **Minkowski's Lattice Point Theorem**: Let LLLbe a complete lattice of dimensionnnn and XXXbe a centrally symmetric convex set. Suppose vol(X)\>2nvol(L)\\text{vol}(X)>2^n\\text{vol}(L)vol(X)\>2nvol(L) Then XXXcontains at least one nonzero point of LL L. This result is primarily used to prove the existence of lattice vectors. Throughout this section, ∥v∥\=∑ivi2\\left\\lVert v\\right\\rVert=\\sqrt{\\sum\_iv\_i^2}∥v∥\=∑i​vi2​​ denotes the ℓ2\\ell\_2ℓ2​norm and ⟨a,b⟩\=∑iaibi\\langle a,b\\rangle=\\sum\_ia\_ib\_i⟨a,b⟩\=∑i​ai​bi​ denotes the inner product. [](https://cryptohack.gitbook.io/cryptobook/lattices/definitions#proof-sketch-of-minkowskis-theorem) Proof sketch of Minkowski's theorem --------------------------------------------------------------------------------------------------------------------------------------------- This proof is by some sort of a pigeonhole argument on volumes. Consider the set 12X\={12x∣x∈X}\\frac12X=\\left\\{\\frac12x|x\\in X\\right\\}21​X\={21​x∣x∈X} We have vol(12X)\>vol(L)\\text{vol}\\left(\\frac12 X\\right)>\\text{vol}(L)vol(21​X)\>vol(L), hence the inclusion 12X→Rn/L\\frac12X\\to\\mathbb R^n/L21​X→Rn/Lcannot be injective, thus we can find some 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​. Hence x1−x2∈Lx\_1-x\_2\\in Lx1​−x2​∈Lis a nontrivial lattice point. [](https://cryptohack.gitbook.io/cryptobook/lattices/definitions#exercises) Exercises ------------------------------------------------------------------------------------------ 1) Let LLLbe the lattice generated by B\=(−1981−8−7)\\mathcal B=\\begin{pmatrix}-1&9&8\\\\1&-8&-7\\end{pmatrix}B\=(−11​9−8​8−7​)(take the rows as basis vectors). * Compute the volume of this lattice * Show that B′\=(101011)\\mathcal B'=\\begin{pmatrix}1&0&1\\\\0&1&1\\end{pmatrix}B′\=(10​01​11​)generates the same lattice * Show that each row in C\=(101022)\\mathcal C=\\begin{pmatrix}1&0&1\\\\0&2&2\\end{pmatrix}C\=(10​02​12​)is in the lattice butC\\mathcal CCdoes not generate the lattice. This is one key difference from the case of linear algebra (over fields). 2) LetB,B′\\mathcal B,\\mathcal B'B,B′be d×nd\\times nd×nmatrices whose row vectors are basis for lattices L,L′L,L'L,L′. Both lattices are the same iff there exists some U∈GLd(Z)U\\in\\text{GL}\_d(\\mathbb Z)U∈GLd​(Z) such that B′\=UB\\mathcal B'=U\\mathcal BB′\=UB. Find UUUfor problem 1. Note that GLd(Z)\\text{GL}\_d(\\mathbb Z)GLd​(Z)is the group of invertible matrices with integer coefficients, meaning UUUand U−1U^{-1}U−1have integer coefficients. 3) Show that the condition in Minkowski's lattice point theorem is strict, i.e. for any complete latticeLLLof dimension nnn, we can find some centrally symmetric convex setXXXwithvol(X)\=2nvol(L)\\text{vol}(X)=2^n\\text{vol}(L)vol(X)\=2nvol(L)but the only lattice point inXXXis the origin. 4\*) Letvvvbe the shortest nonzero vector for some lattice LLLwith dimensionnnn. Show that ∥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​ [PreviousUntitled](https://cryptohack.gitbook.io/cryptobook/elliptic-curves/untitled) [NextLLL reduction](https://cryptohack.gitbook.io/cryptobook/lattices/lll-reduction) Last updated 3 years ago Was this helpful? --- # Wiener's Attack | CryptoBook 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) ### [](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack#wieners-theorem) Wiener's theorem Wiener's attack is based on the following theorem: Let n\=pqn = pqn\=pq, with q e = 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.") [PreviousLow Private Component Attacks](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks) [NextBoneh-Durfee Attack](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/boneh-durfee-attack) Last updated 4 years ago Was this helpful? --- # Rijndael Finite Field | CryptoBook 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 inF2\\mathbf{F}\_2F2​. The construction of the finite field is made as the quotient ringF2\[x\]/f(x)\\mathbf{F}\_2\[x\]/f(x)F2​\[x\]/f(x), wherefffis an irreducible polynomial of degree 8 inF2\[x\]\\mathbf F\_2\[x\]F2​\[x\]so the ring becomes a field. In AES, the choice forfffis f(x)\=x8+x4+x3+x+1.f(x) = x^8 + x^4 + x^3 + x + 1.f(x)\=x8+x4+x3+x+1. We can check with SageMath that it is irreducible: Copy F2 = GF(2) K. = F2[] f = x^8 + x^4 + x^3 + x + 1 f.is_irreducible() # True [](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/rijndael-finite-field#matching-bytes-as-finite-field-elements) Matching Bytes as Finite Field Elements ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- A byte bbb is composed of 8 bits (b7,…,b0)2(b\_7, \\ldots, b\_0)\_2(b7​,…,b0​)2​ and is matched to a polynomial as b7x7+b7x6+⋯+b1x+b0.b\_7x^7 + b\_7 x^6 + \\cdots + b\_1 x + b\_0.b7​x7+b7​x6+⋯+b1​x+b0​. For instance, take the byte `3a` whose binary decomposition is (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​ and becomes the polynomial 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. [](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/rijndael-finite-field#polynomial-reduction) Polynomial Reduction -------------------------------------------------------------------------------------------------------------------------------------------- Polynomials of degree 8 or more can always be reduced, using the fact that in the finite field, we have f(x)\=0f(x) = 0f(x)\=0 , so we have the relation x8\=x4+x3+x+1x^8 = x^4 + x^3 + x + 1x8\=x4+x3+x+1 > Why not x8\=−x4−x3−x−1x^8 = - x^4 - x^3 - x - 1x8\=−x4−x3−x−1? In fact, that's also true, but the coefficient are in F2\\mathbf F\_2F2​ so the additive inverse−1\-1−1 of 111 is itself. In SageMath, this reduction can be produced in one of the following methods. Method 1: Remainder of an Euclidean division by fff Copy (x^8 + x^6 + x^4 + 1) % f # x^6 + x^3 + x **Method 2**: Image in the quotient ring F2\[x\]/f(x)\\mathbf{F}\_2\[x\]/f(x)F2​\[x\]/f(x) Copy R = K.quotient(f) R(x^8 + x^6 + x^4 + 1) # xbar^6 + xbar^3 + xbar **Method 3**: Using the Finite Field class of SageMath directly. Copy F. = GF(2^8, modulus=x^8 + x^4 + x^3 + x + 1) x^8 + x^6 + x^4 + 1 # x^6 + x^3 + x 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: Copy def F_to_hex(a): return ZZ(a.integer_representation()).hex() b = x^4 + x^3 + x + 1 F_to_hex(b) # '1b' [](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/rijndael-finite-field#addition) Addition -------------------------------------------------------------------------------------------------------------------- The addition of two polynomials is done by adding the coefficients corresponding of each monomial: ∑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. And as the addition of the coefficients is inF2\\mathbf{F}\_2F2​, it corresponds to the bitwise `xor` operation on the byte. [](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/rijndael-finite-field#multiplication) Multiplication -------------------------------------------------------------------------------------------------------------------------------- Multiplication of two polynomials is more complex (one example would be the [Karatsuba algorithm](https://en.wikipedia.org/wiki/Karatsuba_algorithm) , more efficient than the naive algorithm). For an implementation of AES, it is possible to only use the multiplication by xxx, whose byte representation is `02`. Letb7x7+⋯+b1x+b0b\_7x^7 + \\cdots + b\_1x + b\_0b7​x7+⋯+b1​x+b0​an element and we consider the multiplication byxxx: 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. All coefficients are shifted to a monomial one degree higher. Then, there are two cases: * Ifb7b\_7b7​is000, then we have a polynomial of degree at most 7 and we are done; * Ifb7b\_7b7​is111, we can replacex8x^8x8byx4+x3+x+1x^4 + x^3 + x + 1x4+x3+x+1during the reduction phase: 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​ This can be used to implement a very efficient multiplication byxxxwith the byte representation: 1. A bitwise shiftleft operation: `(b << 1) & 0xff`; 2. Followed by a conditional addition with `1b` if the top bit of bbb is 111. Here an example in SageMath (we use the finite field construction of method 3): Copy 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 [PreviousAES](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes) [NextRound Transformations](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/round-transformations) Last updated 4 years ago Was this helpful? --- # Introduction / overview | CryptoBook Authors: Zademn Reviewed by: [](https://cryptohack.gitbook.io/cryptobook/hashes/introduction-overview#introduction) 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.** [](https://cryptohack.gitbook.io/cryptobook/hashes/introduction-overview#definitions-and-formalism) 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 H:M⟶TH:\\mathcal{M} \\longrightarrow \\mathcal{T}H:M⟶T be a function where > > * M\\mathcal{M}M = message space > > * T\\mathcal{T}T = 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 H(a),H(b)H(a), H(b)H(a),H(b) * They check if H(a)\=H(b)H(a) = H(b)H(a)\=H(b) ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-MZJ0WriZG6_u6hddfb0%252F-MZJ0qMgg6BYrKjvl494%252Fimage.png%3Falt%3Dmedia%26token%3D2998c41c-0ac6-4df5-9b0f-8aabd44e4231&width=768&dpr=4&quality=100&sign=f60c03be&sv=2) Figure 1. Copy from hashlib import sha256 m1 = b"Some file" m2 = b"Some file" sha256(m1).digest() == sha256(m2).digest() # -> True [](https://cryptohack.gitbook.io/cryptobook/hashes/introduction-overview#proprieties) Proprieties ------------------------------------------------------------------------------------------------------ * Preimage Image Resistance * Second Preimage resistance * Resistant to collisions ### [](https://cryptohack.gitbook.io/cryptobook/hashes/introduction-overview#id-1.-preimage-resistance) 1\. Preimage Resistance > The hash function must be a one way function. Given t∈Tt \\in \\mathcal{T}t∈T find m∈Mm \\in \\mathcal{M}m∈M s.t H(m)\=tH(m) = tH(m)\=t _Intuition_ It should be unfeasible to reverse a hash function (O(2l)\\mathcal{O}(2^l)O(2l) time where lll is the number of output bits) This propriety prevents an attacker to find the original message from a hash ### [](https://cryptohack.gitbook.io/cryptobook/hashes/introduction-overview#id-2.-second-preimage-resistance) 2\. Second Preimage Resistance > Given mmm it should be hard to find m′≠mm' \\neq mm′\=m with H(m′)\=H(m)H(m') = H(m)H(m′)\=H(m) **Attack game** > An adversary A\\mathcal{A}A is given a message mmm and outputs a message m′≠mm' \\neq mm′\=m. > > A\\mathcal{A}A wins the game if he finds H(m)\=H(m′)H(m) = H(m')H(m)\=H(m′) > > His advantage is Pr\[A finds a second preimage\]Pr\[\\mathcal{A} \\text{ finds a second preimage}\]Pr\[A finds a second preimage\] where Pr(⋅)Pr(\\cdot)Pr(⋅)is a probability ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-MZvYxDb_uWfei2mIpxL%252F-MZvZ6UYQh9jxahgQ8Px%252Fdiagram-20210505-2.svg%3Falt%3Dmedia%26token%3Db79953f5-8639-4651-a8f0-4393068c041c&width=768&dpr=4&quality=100&sign=a019ec0a&sv=2) Figure 2. Security game - second preimage resistance * In practice a hash function with lll bits output should need 2l2^l2l queries before one can find a second preimage * This propriety prevents an attacker to substitute a message with another and get the same hash ### [](https://cryptohack.gitbook.io/cryptobook/hashes/introduction-overview#id-3.-hash-collisions) 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 ∣M∣\>\>∣T∣|\\mathcal{M}| >> |\\mathcal{T}|∣M∣\>>∣T∣ => It would appear that hash collisions are possible * Natural collisions are normal to happen and we consider them improbable if T\\mathcal{T}T is big enough (SHA256⇒T\=\\text{SHA256} \\Rightarrow T =SHA256⇒T\= {0,1}256\\{0,1\\}^{256}{0,1}256) * 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 #### [](https://cryptohack.gitbook.io/cryptobook/hashes/introduction-overview#lets-throw-some-definitions) Let's throw some definitions **Attack game** > An adversary A\\mathcal{A}A outputs two messages m0≠m1m\_0 \\neq m\_1m0​\=m1​ > > A\\mathcal{A}A wins the game if he finds H(m0)\=H(m1)H(m\_0) = H(m\_1)H(m0​)\=H(m1​) > > His advantage is Pr\[Adversary finds a collision\]Pr\[\\text{Adversary finds a collision}\]Pr\[Adversary finds a collision\] ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-MZvZ_YYzZrrge8-M9--%252F-MZv_B2Jdchf_oKNb0mw%252Fdiagram-20210505-3.svg%3Falt%3Dmedia%26token%3D2f111a17-043c-4baf-b72d-4e6b2eadaf77&width=768&dpr=4&quality=100&sign=a0537076&sv=2) Figure 3. Security game - Collision resistance **Security** > A hash function HHH 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 #### [](https://cryptohack.gitbook.io/cryptobook/hashes/introduction-overview#difference-from-2nd-preimage) 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 HHH is preimage resistant for every element of the range of HHH is a **weaker** assumption than assuming it is either collision resistant or second preimage resistant. **Note** * Provisional implication * [https://crypto.stackexchange.com/questions/10602/why-does-second-pre-image-resistance-imply-pre-image-resistance?rq=1](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://crypto.stackexchange.com/questions/9684/pre-image-resistant-but-not-2nd-pre-image-resistant) **Lemma 2** > Assuming a function is second preimage resistant is a **weaker** assumption than assuming it is collision resistant. [](https://cryptohack.gitbook.io/cryptobook/hashes/introduction-overview#resources) Resources -------------------------------------------------------------------------------------------------- * [https://en.wikipedia.org/wiki/Cryptographic\_hash\_function](https://en.wikipedia.org/wiki/Cryptographic_hash_function) - Wikipedia entry * [https://www.youtube.com/watch?v=b4b8ktEV4Bg](https://www.youtube.com/watch?v=b4b8ktEV4Bg) - Computerphile * [https://www.tutorialspoint.com/cryptography/cryptography\_hash\_functions.htm](https://www.tutorialspoint.com/cryptography/cryptography_hash_functions.htm) * [https://www.cs.ucdavis.edu/~rogaway/papers/relates.pdf](https://www.cs.ucdavis.edu/~rogaway/papers/relates.pdf) - Good read for more details #### [](https://cryptohack.gitbook.io/cryptobook/hashes/introduction-overview#bibliography) Bibliography * Figure 1 - Wikipedia [PreviousRound Transformations](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/round-transformations) [NextThe Birthday paradox / attack](https://cryptohack.gitbook.io/cryptobook/hashes/the-birthday-paradox-attack) Last updated 4 years ago Was this helpful? --- # Lattices of interest | CryptoBook Needs review. [](https://cryptohack.gitbook.io/cryptobook/lattices/lattices-of-interest#introduction) 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. [](https://cryptohack.gitbook.io/cryptobook/lattices/lattices-of-interest#dual-lattice) 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 ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_PIfLDRgtPd2NAVAxQ%252F-M_PInGWuRpyrsTNnSFA%252Fimage.png%3Falt%3Dmedia%26token%3D5f6f319a-dc23-4efb-b575-7a1df5a2b27d&width=768&dpr=4&quality=100&sign=11b38a72&sv=2) _Intuition:_ We can think of the dual lattice L∨L^\\veeL∨ as some kind of **inverse** of the initial lattice LLL ### [](https://cryptohack.gitbook.io/cryptobook/lattices/lattices-of-interest#basis-of-the-dual-lattice) 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) Copy 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](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 ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_PIfLDRgtPd2NAVAxQ%252F-M_PMl6tx-4fkDhL_nfn%252Fdual22.svg%3Falt%3Dmedia%26token%3D92dae8d6-a077-42e0-812e-31cda0e81b87&width=768&dpr=4&quality=100&sign=298f75a7&sv=2) ### [](https://cryptohack.gitbook.io/cryptobook/lattices/lattices-of-interest#properties) 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 ### [](https://cryptohack.gitbook.io/cryptobook/lattices/lattices-of-interest#successive-minima) 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). Copy 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∨​ Copy 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 [](https://cryptohack.gitbook.io/cryptobook/lattices/lattices-of-interest#geometry--partitioning) Geometry + Partitioning ------------------------------------------------------------------------------------------------------------------------------ // TODO [](https://cryptohack.gitbook.io/cryptobook/lattices/lattices-of-interest#q-ary-lattices) 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 ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_Q-LKCCYumiQ5DX_hh%252F-M_Q9ZnrxDKfiCrhWDJe%252Fqary3.svg%3Falt%3Dmedia%26token%3D61a929fd-699a-4ddc-9961-f8b0cc238398&width=768&dpr=4&quality=100&sign=56d8766b&sv=2) ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-M_Pw7rAsX4_QPcyWnK1%252F-M_Pz8SCb6IqxU8JLkI_%252Fqary2.svg%3Falt%3Dmedia%26token%3D4321d350-113a-459c-bcbe-b5e6716dda81&width=768&dpr=4&quality=100&sign=9d9d7d89&sv=2) 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))∨ [](https://cryptohack.gitbook.io/cryptobook/lattices/lattices-of-interest#resources) Resources --------------------------------------------------------------------------------------------------- * [https://cims.nyu.edu/~regev/teaching/lattices\_fall\_2004/ln/DualLattice.pdf](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://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://simons.berkeley.edu/sites/default/files/docs/14953/intro.pdf) * [https://cseweb.ucsd.edu/~daniele/papers/FOSAD11.pdf](https://cseweb.ucsd.edu/~daniele/papers/FOSAD11.pdf) [PreviousHard lattice problems](https://cryptohack.gitbook.io/cryptobook/lattices/hard-lattice-problems) [NextCryptographic lattice problems](https://cryptohack.gitbook.io/cryptobook/lattices/cryptographic-lattice-problems) Last updated 4 years ago Was this helpful? --- # Round Transformations | CryptoBook 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. [](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/round-transformations#add-round-key) 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. ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-MZgzy0xwju6mu-dDTFp%252F-MZh2xCD1CflMWnTzjSW%252Ffigures-figure3.svg%3Falt%3Dmedia%26token%3De51fa77b-7d65-42d1-ba18-5241c1307c01&width=768&dpr=4&quality=100&sign=b2796974&sv=2) AK: each byte is xored with a byte of the round key in the same position. Its inverse is itself: if we xor again, we get back the original value of the state. [](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/round-transformations#mix-columns) 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 (a0,a1,a2,a3)(a\_0, a\_1, a\_2, a\_3)(a0​,a1​,a2​,a3​) the quadruplet of elements of a column, the operation `MC` is done by multiplying with a matrix MMM. ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-MZgzy0xwju6mu-dDTFp%252F-MZh5IfQMpTRidUI98so%252Ffigures-figure4.svg%3Falt%3Dmedia%26token%3D75ab5016-b7ae-448a-964c-85ef397ac266&width=768&dpr=4&quality=100&sign=b029b47f&sv=2) MC: each column is multiplied by 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 xxxand x+1x+1x+1 in the field): Copy # 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) ### [](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/round-transformations#inverse-of-mix-column) Inverse of Mix Column It is needed to reverse `MC` for the decryption process. Fortunately, there exists a matrix NNN such that M×N\=N×M\=IdM\\times N = N \\times M = \\textrm{Id}M×N\=N×M\=Id, the identity matrix. Copy 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 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. [](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/round-transformations#shift-rows) 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 [Avalanche effect](https://en.wikipedia.org/wiki/Avalanche_effect) . This operation shifts the rows of the state in the following manner: ![](https://cryptohack.gitbook.io/cryptobook/~gitbook/image?url=https%3A%2F%2F3048596314-files.gitbook.io%2F%7E%2Ffiles%2Fv0%2Fb%2Fgitbook-legacy-files%2Fo%2Fassets%252F-MZDWnXlfe2CXv0vGqAA%252F-MZY_a_fsv5JyPfB7mni%252F-MZYcGjXZy1EVikn-ZH8%252Ffigures-figure1.svg%3Falt%3Dmedia%26token%3Db947efb4-aa9a-4413-912b-06676b1412f9&width=768&dpr=4&quality=100&sign=e937312b&sv=2) SR: each is shifted by a different offset to the left. 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? [](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/round-transformations#substitution-box) 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. 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 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 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) 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 elementaaais replaced by b\=a−1b = a^{-1}b\=a−1 (000 has no inverse and is mapped to 000); 2. An affine transformation on the coefficients of 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​​ The table we gave above has been construted with SageMath and applying the two steps: Copy 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'] 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. [PreviousRijndael Finite Field](https://cryptohack.gitbook.io/cryptobook/symmetric-cryptography/aes/rijndael-finite-field) [NextIntroduction / overview](https://cryptohack.gitbook.io/cryptobook/hashes/introduction-overview) Last updated 4 years ago Was this helpful? --- # The Birthday paradox / attack | CryptoBook Authors: Zademn, ireland Reviewed by: **Prerequisites** * Probability theory (for the main idea) * Hashes (an application) **Motivation** * Breaking a hash function (insert story) [](https://cryptohack.gitbook.io/cryptobook/hashes/the-birthday-paradox-attack#the-birthday-paradox) The birthday paradox ------------------------------------------------------------------------------------------------------------------------------ \*insert story / introduction about why it's called a paradox + use\* ### [](https://cryptohack.gitbook.io/cryptobook/hashes/the-birthday-paradox-attack#birthday-version) 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​) ### [](https://cryptohack.gitbook.io/cryptobook/hashes/the-birthday-paradox-attack#general-case) **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** Copy 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) #### [](https://cryptohack.gitbook.io/cryptobook/hashes/the-birthday-paradox-attack#an-useful-approximation) 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​)​​ Copy 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 ### [](https://cryptohack.gitbook.io/cryptobook/hashes/the-birthday-paradox-attack#finding-a-collision) 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: Copy 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: Copy 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<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. [PreviousApplications](https://cryptohack.gitbook.io/cryptobook/lattices/applications) [NextExtensions of Coppersmith algorithm](https://cryptohack.gitbook.io/cryptobook/lattices/applications/extensions-of-coppersmith-algorithm) Last updated 4 years ago Was this helpful? ---