## Mathematics

This category covers more advanced cryptographic math. It's not necessary to solve these before moving to the Block Cipher and RSA sections. However, the first challenges will expand your modular toolbox, while the later ones are reported to be among the most satisfying puzzles to solve on CryptoHack. #### Modular Math

Toggle
25 pts · 8056 Solves

We've looked at multiplication and division in modular arithmetic, but what does it mean to take the square root modulo an integer?

For the following discussion, let's work modulo `p = 29`. We can take the integer `a = 11` and calculate `a2 = 5 mod 29`.

As `a = 11, a2 = 5`, we say the square root of `5` is `11`.

This feels good, but now let's think about the square root of `18`. From the above, we know we need to find some integer `a` such that `a2 = 18`

Your first idea might be to start with `a = 1` and loop to `a = p-1`. In this discussion `p` isn't too large and we can quickly look.

Have a go, try coding this and see what you find. If you've coded it right, you'll find that for all `a ∈ Fp*` you never find an `a` such that `a2 = 18`.

What we are seeing, is that for the elements of `F*p`, not every element has a square root. In fact, what we find is that for roughly one half of the elements of `Fp*`, there is no square root.

We say that an integer `x` is a Quadratic Residue if there exists an `a` such that `a2 = x mod p`. If there is no such solution, then the integer is a Quadratic Non-Residue.

In other words, `x` is a quadratic residue when it is possible to take the square root of `x` modulo an integer `p`.

In the below list there are two non-quadratic residues and one quadratic residue.

Find the quadratic residue and then calculate its square root. Of the two possible roots, submit the smaller one as the flag.

If `a2 = x` then (-a)2 = x. So if `x` is a quadratic residue in some finite field, then there are always two solutions for `a`.

p = 29
ints = [14, 6, 11]

You must be logged in to submit your flag.

• Legendre Symbol
35 pts · 5972 Solves

In Quadratic Residues we learnt what it means to take the square root modulo an integer. We also saw that taking a root isn't always possible.

In the previous case when `p = 29`, even the simplest method of calculating the square root was fast enough, but as `p` gets larger, this method becomes wildly unreasonable.

Lucky for us, we have a way to check whether an integer is a quadratic residue with a single calculation thanks to Legendre. In the following, we will assume we are working modulo a prime `p`.

Before looking at Legendre's symbol, let's take a brief detour to see an interesting property of quadratic (non-)residues.

Want an easy way to remember this? Replace "Quadratic Residue" with `+1` and "Quadratic Non-residue" with `-1`, all three results are the same!

So what's the trick? The Legendre Symbol gives an efficient way to determine whether an integer is a quadratic residue modulo an odd prime `p`.

Legendre's Symbol: `(a / p) ≡ a(p-1)/2 mod p` obeys:

(a / p) = 1 if a is a quadratic residue and a ≢ 0 mod p
(a / p) = -1 if a is a quadratic non-residue mod p
(a / p) = 0 if a ≡ 0 mod p

Which means given any integer `a`, calculating `pow(a,(p-1)//2,p)` is enough to determine if `a` is a quadratic residue.

Now for the flag. Given the following 1024 bit prime and 10 integers, find the quadratic residue and then calculate its square root; the square root is your flag. Of the two possible roots, submit the larger one as your answer.

So Legendre's symbol tells us which integer is a quadratic residue, but how do we find the square root?! The prime supplied obeys `p = 3 mod 4`, which allows us easily compute the square root. The answer is online, but you can figure it out yourself if you think about Fermat's little theorem.

Challenge files:
- output.txt

You must be logged in to submit your flag.

• Modular Square Root
35 pts · 4866 Solves

In Legendre Symbol we introduced a fast way to determine whether a number is a square root modulo a prime. We can go further: there are algorithms for efficiently calculating such roots. The best one in practice is called Tonelli-Shanks, which gets its funny name from the fact that it was first described by an Italian in the 19th century and rediscovered independently by Daniel Shanks in the 1970s.

All primes that aren't 2 are of the form `p ≡ 1 mod 4` or `p ≡ 3 mod 4`, since all odd numbers obey these congruences. As the previous challenge hinted, in the `p ≡ 3 mod 4` case, a really simple formula for computing square roots can be derived directly from Fermat's little theorem. That leaves us still with the `p ≡ 1 mod 4` case, so a more general algorithm is required.

In a congruence of the form `r2 ≡ a mod p`, Tonelli-Shanks calculates `r`.

Tonelli-Shanks doesn't work for composite (non-prime) moduli. Finding square roots modulo composites is computationally equivalent to integer factorization - that is, it's a hard problem.

The main use-case for this algorithm is finding elliptic curve co-ordinates. Its operation is somewhat complex so we're not going to discuss the details, however, implementations are easy to find and Sage has one built-in.

Find the square root of `a` modulo the 2048-bit prime `p`. Give the smaller of the two roots as your answer.

Challenge files:
- output.txt

You must be logged in to submit your flag.

• Chinese Remainder Theorem
40 pts · 5266 Solves

The Chinese Remainder Theorem gives a unique solution to a set of linear congruences if their moduli are coprime.

This means, that given a set of arbitrary integers `ai`, and pairwise coprime integers `ni`, such that the following linear congruences hold:

Note "pairwise coprime integers" means that if we have a set of integers `{n1, n2, ..., ni}`, all pairs of integers selected from the set are coprime: `gcd(ni, nj) = 1`.

x ≡ a1 mod n1
x ≡ a2 mod n2
...
x ≡ an mod nn

There is a unique solution `x ≡ a mod N` where `N = n1 * n2 * ... * nn`.

In cryptography, we commonly use the Chinese Remainder Theorem to help us reduce a problem of very large integers into a set of several, easier problems.

Given the following set of linear congruences:

x ≡ 2 mod 5
x ≡ 3 mod 11
x ≡ 5 mod 17

Find the integer `a` such that `x ≡ a mod 935`

Starting with the congruence with the largest modulus, use that for `x ≡ a mod p` we can write `x = a + k*p` for arbitrary integer `k`.

You must be logged in to submit your flag.

#### Lattices

Toggle
• Vectors
10 pts ·

Before defining a lattice or talking about how lattices appear in cryptography, let's review some of the basics of linear algebra. The following challenges should be considered as revision, if this is totally new to you, you might need to do a bit of background reading. As usual, we recommend "An Introduction to Mathematical Cryptography" by Hoffstein, Pipher, Silverman, as well as this excellent introduction to lattices and their applications.

A vector space `V` over a field `F` is a set defined with two binary operators. For a vector `v ∈ V`, and a scalar `a ∈ F`, vector addition takes two vectors and produces another vector: `v + w = z, for v,w,z ∈ V` and scalar multiplication takes a vector and a scalar and produces a vector: `a*v = w, for v,w ∈ V, a ∈ F`.

You will probably have first seen vectors in the context of a two dimensional vector space defined over the reals. We'll use this here too as an example!

Let's consider a two dimensional vector space over the reals. A vector `v ∈ V` can be considered as a pair of numbers: `v = (a,b) for a,b ∈ R`. Vector addition works as `v + w = (a,b) + (c,d) = (a+c, b+d)`, and scalar multiplication by `c*v = c*(a,b) = (c*a, c*b)`.

One can also define the inner product (also called the dot product), which takes two vectors and returns a scalar. Formally we think of this as `v ∙ w = a for v,w ∈ V, a ∈ F`. In our two-dimensional example, the inner product works as `v ∙ w = (a,b) ∙ (c,d) = a*c + b*d`.

Time for the flag! Given a three dimensional vector space defined over the reals, where `v = (2,6,3)`, `w = (1,0,0)` and `u = (7,7,2)`, calculate `3*(2*v - w) ∙ 2*u`.

You must be logged in to submit your flag.

• Size and Basis
15 pts · 3123 Solves

We say a set of vectors `v1, v2, ..., vk ∈ V` are linearly independent if the only solution to the equation:

a1*v1 + a2*v2 + ... + ak*vk = 0

is for `a1 = a2 = ... = ak = 0`.

To visualise this, think of a vector pointing out of a point. Given a set of linearly independent vectors, the only way to return back to the original point is by moving along the original vector. No combination of any of the other vectors will get you there.

A basis is a set of linearly independent vectors `v1, v2, ..., vn ∈ V` such that any vector `w ∈ V` can be written as:

w = a1*v1 + a2*v2 + ... + ak*vn

The number of elements in the basis is also the dimension of the vector space.

We define the size of a vector, denoted `||v||`, using the inner product of the vector with itself: `||v||2 = v ∙ v`.

A basis is orthogonal if for a vector basis `v1, v2, ..., vn ∈ V`, the inner product between any two different vectors is zero: `vi ∙ vj = 0, i ≠ j`.

A basis is orthonormal if it is orthogonal and `||vi|| = 1, for all i`.

That's a lot of stuff, but we'll be needing it. Time for the flag. Given the vector `v = (4, 6, 2, 5)`, calculate its size.

You must be logged in to submit your flag.

• Gram Schmidt
30 pts · 2225 Solves

In the last challenge we saw that there is a special kind of basis called an orthogonal basis. Given a basis `v1, v2, ..., vn ∈ V` for a vector space, the Gram-Schmidt algorithm calculates an orthogonal basis `u1, u2, ..., un ∈ V`.

In "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, the Gram-Schmidt algorithm is given as:

Algorithm for Gram-Schmidt

u1 = v1
Loop i = 2,3...,n
Compute μij = vi ∙ uj / ||uj||2, 1 ≤ j < i.
Set ui = vi - μij * uj (Sum over j for 1 ≤ j < i)
End Loop

To test your code, let's grab the flag. Given the following basis vectors:

v1 = (4,1,3,-1), v2 = (2,1,-3,4), v3 = (1,0,-2,7), v4 = (6, 2, 9, -5),

use the Gram-Schmidt algorithm to calculate an orthogonal basis. The flag is the float value of the second component of `u4` to 5 significant figures.

Note that this algorithm doesn't create an orthonormal basis! It's a small change to implement this. Think about what you would have to change. If you're using someone else's algorithm and the flag is incorrect, this might be the issue. If everything seems good and you're still not having your answer accepted, check your rounding when you take 5.s.f. for the solution.

You must be logged in to submit your flag.

• What's a Lattice?
40 pts · 2372 Solves

We're now ready to start talking about lattices. Given a set of linearly independent vectors `v1, v2, ..., vn ∈ Rm`, the lattice `L` generated by `v1, v2, ..., vn` is the set of linearly independent vectors `v1, v2, ..., vn` with integer coefficients.

L = {a1*v1 + a2*v2 + ... + ak*vk : a1, a2, ..., an ∈ Z}.

The basis for the lattice `L` is any set of independent vectors that generates `L`. The choice of basis is far from unique. In the image below, we show a two dimensional lattice with two different basis vectors given by `u1, u2` and `v1, v2`. Using a basis, we can reach any point within the lattice with integer multiples of the basis vectors. The basis vectors also define the fundamental domain:

F(v1,...,vn) = {t1 v1 + t2 v2 + ... + tn vn : 0 ≤ ti < 1}.

As a two dimensional example, the fundamental domain is the parallelogram with sides `u1` and `u2`.

We can calculate the volume of the fundamental domain from the basis vectors. As an example, let us take a two dimensional lattice with basis vectors `v = (2,5), u = (3,1)`. Create a matrix `A` with rows corresponding to the basis vectors: `A = [[2,5],[3,1]]`. The volume of the fundamental domain is the magnitude of the determinant of A: `Vol(F) = |det(A)| = |2*1 - 5*3| = |-13| = 13`.

For the flag, calculate the volume of the fundamental domain with the basis vectors `v1 = (6, 2, -3), v2 = (5, 1, 4), v3 = (2, 7, 1)`.

You must be logged in to submit your flag.

• Gaussian Reduction
50 pts · 2033 Solves

If you look closely enough, lattices start appearing everywhere in cryptography. Sometimes they appear through manipulation of a cryptosystem, breaking parameters which were not generated securely enough. The most famous example of this is Coppersmith's attack against RSA cryptography.

Lattices can also be used to build cryptographic protocols, whose security is based on two fundamental "hard" problems:

The Shortest Vector Problem (SVP): find the shortest non-zero vector in a lattice `L`. In other words, find the non-zero vector within `v ∈ L` such that `||v||` is minimised.

The Closest Vector Problem (CVP): Given a vector `w ∈ Rm` that is not in `L`, find the vector `v ∈ L` that is the closest to `w`, i.e. find the vector `v ∈ L` such that `||v - w||` is minimised.

The SVP is hard for a generic lattice, but for simple enough cases there are efficient algorithms to compute either a solution or an approximation for the SVP. When the dimension of the lattice is four or less, we can compute this exactly in polynomial time; for higher dimensions, we have to settle for an approximation.

Gauss developed his algorithm to find an optimal basis for a two-dimensional lattice given an arbitrary basis. Moreover, the output `v1` of the algorithm is a shortest nonzero vector in `L`, and so solves the SVP.

For higher dimensions, there's a basis lattice reduction algorithm called the LLL algorithm, named after Lenstra, Lenstra and Lovász. If you play CTFs regularly, you'll already know about it. The LLL algorithm runs in polynomial time. For now though, lets stay in two dimensions.

Gauss's algorithm roughly works by subtracting multiples of one basis vector from the other until it's no longer possible to make them any smaller. As this works in two-dimensions, it's nice to visualise. Here's a description of the algorithm from "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman:

Algorithm for Gaussian Lattice Reduction

Loop
(a) If ||v2|| < ||v1||, swap v1, v2
(b) Compute m = ⌊ v1∙v2 / v1∙v1 ⌉
(c) If m = 0, return v1, v2
(d) v2 = v2 - m*v1
Continue Loop

Note the similarity to Euclid's GCD algorithm with the "swap" and "reduction" steps, and that we have round the float, as on a lattice we may only use integer coefficients for our basis vectors.

For the flag, take the two vectors `v = (846835985, 9834798552), u = (87502093, 123094980)` and by applying Gauss's algorithm, find the optimal basis. The flag is the inner product of the new basis vectors.

You must be logged in to submit your flag.

• Find the Lattice
100 pts · 1193 Solves

As we've seen, lattices contain hard problems which can form trapdoor functions for cryptosystems. We also find that in cryptanalysis, lattices can break cryptographic protocols which seem at first to be unrelated to lattices.

This challenge uses modular arithmetic to encrypt the flag, but hidden within the protocol is a two-dimensional lattice. We highly recommend spending time with this challenge and finding how you can break it with a lattice. This is a famous example with plenty of resources available, but knowing how to spot the lattice within a system is often the key to breaking it.

As a hint, you will be able to break this challenge using the Gaussian reduction from the previous challenge.

Challenge files:
- source.py
- output.txt

You must be logged in to submit your flag.

• Backpack Cryptography
120 pts · 787 Solves

I love this cryptosystem so much, I carry it everywhere in my backpack. To lighten the load, I make sure I don't pack anything with high densities.

Challenge files:
- source.py
- output.txt

Challenge contributed by VincBreaker

You must be logged in to submit your flag.

#### Brainteasers Part 1

Toggle
• Successive Powers
60 pts · 2135 Solves

The following integers: `588, 665, 216, 113, 642, 4, 836, 114, 851, 492, 819, 237` are successive large powers of an integer `x`, modulo a three digit prime `p`.

Find `p` and `x` to obtain the flag.

You can do this with a pen and paper. We've included this challenge as an excuse for you to get used to algebra and modular mathematics.

You must be logged in to submit your flag.

80 pts · 3253 Solves

Adrien's been looking at ways to encrypt his messages with the help of symbols and minus signs. Can you find a way to recover the flag?

Challenge files:
- source.py
- output.txt

You must be logged in to submit your flag.

• Modular Binomials
80 pts · 2571 Solves

Rearrange the following equations to get the primes `p,q`

N = p*q
c1 = (2*p + 3*q)**e1 mod N
c2 = (5*p + 7*q)**e2 mod N

Challenge files:
- data.txt

You must be logged in to submit your flag.

• Broken RSA
100 pts · 1263 Solves

I tried to send you an important message with RSA, however I messed up my RSA implementation really badly. Can you still recover the flag?

If you think you're doing the right thing but getting garbage, be sure to check all possible solutions.

Challenge files:
- broken_rsa.txt

You must be logged in to submit your flag.

• No Way Back Home
100 pts · 557 Solves

Quantum Computers are going to break some of the standard cryptosystems like RSA, ECC and others. We're in some trouble, so why don't we make our own Quantum-Safe Key Exchange Protocol?

Challenge files:
- nowayback.py
- out.txt

Challenge contributed by DCryp7

You must be logged in to submit your flag.

#### Brainteasers Part 2

Toggle
• Ellipse Curve Cryptography
125 pts · 531 Solves

I overheard my professor talking about ellipse curve cryptography. I tried googling it, but didn't find anything so I implemented it myself.

Challenge files:
- source.py
- output.txt

You must be logged in to submit your flag.

125 pts · 398 Solves

Cracking discrete logarithms is hard. Change my mind. I'll even let you to use your own parameters, as long as the modulus is of the given order.

Connect at `nc socket.cryptohack.org 13403`

Challenge files:
- 13403.py

Challenge contributed by Mystiz

You must be logged in to submit your flag.

• Unencryptable
125 pts · 794 Solves

I swear I knew what I was doing, but I encrypted some data on my hard drive and nothing happened? RSA is so confusing. Luckily my flag is safe, but it seems I have a lot more learning to do.

Challenge files:
- source.py
- output.txt

Challenge contributed by unblvr

You must be logged in to submit your flag.

• Cofactor Cofantasy
150 pts · 458 Solves

Do you have the power to break out of my cofactor cofantasy?

Calculating the solution should take less than 15 minutes.

Connect at `nc socket.cryptohack.org 13398`

Challenge files:
- 13398.py

Challenge contributed by Robin_Jadoul and Thunderlord

You must be logged in to submit your flag.

• Real Eisenstein
150 pts · 490 Solves

I've hidden my secret among the primes. Reducing the number back down to the flag shouldn't be possible!

Challenge files:
- real_eisenstein.py

Challenge contributed by ariana

You must be logged in to submit your flag.

#### Primes

Toggle
• Prime and Prejudice
200 pts · 554 Solves

You may look through my window and see my flag, but to maintain my modesty, only the first character is available.

Connect at `nc socket.cryptohack.org 13385`

Challenge files:
- 13385.py

You must be logged in to submit your flag.

### Level Up You are now level Current level