Mathematics

This category covers more advanced cryptographic math. It's not necessary to solve these before moving to the Symmetric Ciphers 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
  • Quadratic Residues
    25 pts · 13173 Solves · 56 Solutions
    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 $a^{2} = 5 \mod 29$.

    As $a = 11, a^{2} = 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 $a^{2} = 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 check all options.

    Have a go, try coding this and see what you find. If you've coded it right, you'll find that for all $a \in \Fp^{*}$ you never find an $a$ such that $a^{2} = 18$.

    What we are seeing, is that for the elements of $\Fp^{*}$, 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 $a^{2} \equiv 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 $a^{2} = 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 \quad ints = [14, 6, 11]$

    You must be logged in to submit your flag.


  • Legendre Symbol
    35 pts · 10073 Solves · 42 Solutions
    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.

    Quadratic Residue * Quadratic Residue = Quadratic Residue
    Quadratic Residue * Quadratic Non-residue = Quadratic Non-residue
    Quadratic Non-residue * Quadratic Non-residue = Quadratic Residue


    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) \equiv a^{(p-1)/2} \mod p$ obeys:

    $(a / p) = 1$ if $a$ is a quadratic residue and $a \not\equiv 0 \mod p$
    $(a / p) = -1$ if $a$ is a quadratic non-residue $\mod p$
    $(a / p) = 0$ if $a \equiv 0 \mod p$


    Which means given any integer $a$, calculating $a^{(p-1)/2} \mod 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 · 8261 Solves · 33 Solutions
    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 \equiv 1 \mod 4$ or $p \equiv 3 \mod 4$, since all odd numbers obey these congruences. As the previous challenge hinted, in the $p \equiv 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 \equiv 1 \mod 4$ case, so a more general algorithm is required.

    In a congruence of the form $r^2 \equiv 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 coordinates. 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 · 8608 Solves · 49 Solutions
    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 $a^{i}$, and pairwise coprime integers $n^{i}$, such that the following linear congruences hold:

    Note "pairwise coprime integers" means that if we have a set of integers $\{n^{1}, n^{2}, ..., n^{i}\}$, all pairs of integers selected from the set are coprime: $\gcd(n^{i}, n^{j}) = 1$.

    $x \equiv a^{1} \mod n^{1}$
    $x \equiv a^{2} \mod n^{2}$
    $\ldots$
    $x \equiv a^{n} \mod n^{n}$


    There is a unique solution $x \equiv a \mod N$ where $N = n^{1} \cdot n^{2} \cdot ... \cdot n^{n}$.

    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 \equiv 2 \mod 5$
    $x \equiv 3 \mod 11$
    $x \equiv 5 \mod 17$


    Find the integer $a$ such that $x \equiv a \mod 935$

    Starting with the congruence with the largest modulus, use that for $x \equiv a \mod p$ we can write $x = a + k \cdot p$ for arbitrary integer $k$.

    You must be logged in to submit your flag.



Brainteasers Part 1

Toggle
  • Successive Powers
    60 pts · 3150 Solves · 23 Solutions
    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.


  • Adrien's Signs
    80 pts · 5938 Solves · 39 Solutions
    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 · 4877 Solves · 21 Solutions
    Rearrange the following equations to get the primes p,q

    $N = p \cdot q$
    $c_1 = (2 \cdot p + 3 \cdot q)^{e_1} \mod N$
    $c_2 = (5 \cdot p + 7 \cdot q)^{e_2} \mod N$


    Challenge files:
      - data.txt

    You must be logged in to submit your flag.


  • Broken RSA
    100 pts · 1960 Solves · 18 Solutions
    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 · 1035 Solves · 9 Solutions
    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 · 835 Solves · 12 Solutions
    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.


  • Roll your Own
    125 pts · 696 Solves · 5 Solutions
    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 socket.cryptohack.org 13403

    Challenge files:
      - 13403.py


    Challenge contributed by Mystiz

    You must be logged in to submit your flag.


  • Unencryptable
    125 pts · 1160 Solves · 8 Solutions
    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 · 707 Solves · 10 Solutions
    Do you have the power to break out of my cofactor cofantasy?

    Calculating the solution should take less than 15 minutes.

    Connect at 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 · 709 Solves · 7 Solutions
    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 · 791 Solves · 9 Solutions
    You may look through my window and see my flag, but to maintain my modesty, only the first character is available.

    Connect at socket.cryptohack.org 13385

    Challenge files:
      - 13385.py

    You must be logged in to submit your flag.


Level Up

level up icon

You are now level Current level