Crypto 4: Lattices
by Arnav Vora
We will cover a more advanced topic in cryptography: lattices. These are essential in many cryptographic attacks. Lattices can be used to describe linear systems of integers, and are very powerful when solving for inequalities/small solutions of linear integer equations. When using lattice-based attacks, we often rely on lattice reduction, which transforms a lattice basis into a nearly orthonormal one, allowing one to find small integer solutions to systems. We will see some applications of lattice attacks in LCGs (linear congruential generators) and other instances where small integer solutions are needed.
Slides
Slides that I presented for PBR last year, relevant for today's lesson!
Challenges
The following challenges have been found in various CTF competitions, and are good examples of lattice-based attacks
- LACTF 2024:
crypto/any-percent-ssg - LACTF 2025:
crypto/shuffle-revenge - glacierCTF 2024:
crypto/signmeup
Resources
The following resources are great to practice/learn about the concepts covered today:
- Matthew Bolan: Minecraft seedcracking: A nice video series that described how lattices can be used to crack Minecraft's LCG and find seeds that satisfy some constraints.
- Lattice tutorial: A good tutorial for using lattices in cryptography.
- Another lattice tutorial: Another good tutorial for lattices in cryptography, applied to common CTF challenges.
- SageMath: An open-source mathematics system that integrates with Python and is incredibly useful in many cryptography challenges.