Mathematics - Modular Math

Quadratic Residues

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

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 ints = [14, 6, 11]"

We can simply loop through all value for a from 0 to p-1 and see if a solution exists

#!/usr/bin/env python3
p = 29
ints = [14, 6, 11]

for a in range(p):
    t = pow(a, 2, p)
    if t in ints:
        print(str(t) + " is quadratic Residue with a = " + str(a))

Legendre Symbol

"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

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

When p = 3 mod 4 then a^((p+1)/4) mod p is a square root of a

So, first we find the quadratic residue and then the square root.

#!/usr/bin/env python3

p = 1015240... #From the text file
ints = [2508184120...0985105257601565] #From the text file

for a in ints:
    if pow(a,(p-1)//2,p) == 1:
        print(pow(a,(p+1)//4, p))

Modular Square Root

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

The following implementation does the trick.

The function legendre_symbol(a, p) computes the Legendre symbol of a modulo p, using Euler's criterion. The function tonelli_shanks(n, p) finds a quadratic residue of n modulo p, assuming that p is prime. If n is not a quadratic residue modulo p, the function returns None.

Chinese Remainder Theorem

"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"

This script will output x given a list of a's and n's.

n = [5, 11, 17]

a = [2, 3, 5]

The script will output a number smaller than 935, which means that x is a solution for a

def chinese_remainder(n, a):
    # Compute the product of the moduli
    prod = 1
    for ni in n:
        prod *= ni

    # Compute the sum of the terms
    x = 0
    for ni, ai in zip(n, a):
        pi = prod // ni  # compute the product of the moduli except ni
        xi = pow(pi, -1, ni)  # compute the modular inverse of pi
        x += ai * xi * pi  # add the product to the sum

    # Return the solution modulo the product of the moduli
    return x % prod

# Test the function
n = [5, 11, 17]
a = [2, 3, 5]
print(chinese_remainder(n, a))

Also, I've created a solution that explains the steps a bit more clearly.

#!/usr/bin/env python3
import math

# Define the system of congruences
m = [5, 11, 17]
a = [2, 3, 5]

# Print the system of congruences
print("We can use the Chinese Remainder Theorem to find a unique solution X such that:")
for i in range(len(m)):
    print(f"x = {a[i]} mod {m[i]}")
print()

# Find M
M = math.prod(m)
print("First we find M, which is the product of all the moduli:")
print(f"M = {M}")
print()

# Calculate Mi
Mi = [M // mi for mi in m]
print("Next we calculate a list of Mi = M/mi for i in 1..r:")
for i in range(len(m)):
    print(f"M_{i+1} = {M} / {m[i]} = {Mi[i]}")
print()

# Calculate yi
y = [pow(Mi[i], -1, m[i]) for i in range(len(m))]
print("Then we calculate a list of yi = Mi^-1 mod mi for i in 1..r:")
for i in range(len(m)):
    print(f"y_{i+1} = {Mi[i]}^-1 mod {m[i]} = {y[i]}")
print()

# Calculate x
x = sum([a[i]*Mi[i]*y[i] for i in range(len(m))]) % M
print("Finally we can compute our x = sum of ai*Mi*yi mod M for i in 1..r:")
print(f"x = {x}")
print()

# Print the final equation
print("Thus we get the final equation as such:")
print(f"x = {x} mod {M} = {x} mod {math.prod(m)}")