Mathematics
Quadratic Residues and Their Cryptographic Applications
Quick fact
In the Diffie-Hellman key exchange, both parties can publicly share a number that is a quadratic residue, yet only they can compute a shared secret, because finding square roots modulo a large prime is computationally hard.
Why this is interesting
You know how every positive number has a square root? What if we only allowed remainders after division by a prime? Suddenly, some numbers have square roots and others don't—and this simple difference becomes a secret code for modern cryptography.
Read the full explanation
Understanding Quadratic Residues and Their Cryptographic Applications
Think of numbers on a clock that has a prime number of hours, say 7. We only care about remainders when dividing by 7: 0, 1, 2, 3, 4, 5, 6. Now, take some number x, square it, and then take its remainder. For example, 2² = 4, so 4 is a quadratic residue modulo 7. 3² = 9, which leaves remainder 2, so 2 is also a residue. Notice that some numbers, like 3, never appear as a square—no matter which x we pick. Those are called quadratic non-residues. This division of numbers into two groups—residues and non-residues—is not just a neat pattern; it's the secret ingredient in several cryptographic methods. The key is that while it's easy to compute a square, it's hard to reverse it when the modulus is huge, making it perfect for hiding information.
A deeper explanation
The mathematical foundation is the Legendre symbol and Euler's criterion. For a prime p and a number a not divisible by p, a is a quadratic residue if there exists an integer x such that x² ≡ a (mod p). Euler's criterion states that a^( (p-1)/2 ) ≡ 1 (mod p) if a is a residue, and ≡ -1 (mod p) if it is a non-residue. This gives a fast way to test for quadratic residuosity. Cryptographically, the security of systems like Diffie-Hellman relies on the discrete logarithm problem, but quadratic residuosity itself underpins the Goldwasser-Micali scheme. In Goldwasser-Micali, a bit is encoded by whether a randomly chosen element is a residue or not. The public key includes a non-residue with Jacobi symbol 1, making it computationally hard for an adversary to distinguish residues from non-residues without knowing the factorization of the modulus. Thus, the simple algebraic property of being a square modulo a prime becomes a one-way function, enabling secure encryption and key exchange.