Cryptography Mathematics Basics

Modern encryption doesn't rely on secrecy; it relies on math. The security of your online banking, private messages, and digital identity hinges on mathematical problems that are straightforward in one direction but computationally infeasible to reverse without a secret key. Understanding these foundational concepts—prime numbers, modular arithmetic, and discrete logarithms—reveals why our digital world can be both open and secure.

Modular Arithmetic: The Clockwork Foundation

All modern cryptography operates within finite sets, and modular arithmetic provides the essential framework. Think of it as "clock math." On a 12-hour clock, 14 o'clock is 2 o'clock. We write this as $14\equiv 2(\mathrm{mod}12)$, meaning 14 and 2 have the same remainder when divided by 12. The number 12 is called the modulus.

In cryptography, we work with huge moduli (like a 2048-bit number). This system creates a finite, wrap-around world essential for calculations. A crucial property is that operations like addition, subtraction, and multiplication work intuitively within this system: $$(a+b)\mathrm{mod}n=(a\mathrm{mod}n+b\mathrm{mod}n)\mathrm{mod}n$$ This predictability allows for complex equations. However, division is not straightforward; it requires finding a modular inverse. For a number $a$, its inverse modulo $n$ is a number $b$ such that $a\cdot b\equiv 1(\mathrm{mod}n)$. This inverse only exists if $a$ and $n$ are coprime (they share no common factors other than 1). Finding this inverse efficiently, using the Extended Euclidean Algorithm, is a cornerstone of cryptographic key generation.

The Prime Factorization Problem and RSA

The security of one of the most widely used algorithms, RSA (Rivest–Shamir–Adleman), rests on the integer factorization problem. It is easy to multiply two large prime numbers together. For example, given primes $p=61$ and $q=53$, their product $n=3233$ is trivial to compute. However, given only the product $3233$, finding the original prime factors $61$ and $53$ is extremely difficult for sufficiently large primes.

RSA exploits this one-way nature. In simplified terms:

1. Key Generation: Two large primes ($p$ and $q$) are multiplied to create a public modulus $n=p\times q$. A public exponent $e$ is chosen, and a private exponent $d$ is calculated using the prime factors.
2. Encryption: A message (converted to a number $m$) is encrypted as ciphertext $c$ using the public key: $c\equiv m^e(\mathrm{mod}n)$.
3. Decryption: The rightful owner uses the private key to recover the message: $m\equiv c^d(\mathrm{mod}n)$.

An attacker who sees $n$ and $e$ cannot compute $d$ without knowing $p$ and $q$. Factoring a 2048-bit $n$ is considered impossible for classical computers within any practical timeframe, which is what makes RSA secure. This is a classic trapdoor function: easy to compute in one direction (encryption), hard to reverse without the trapdoor (the private key derived from the prime factors).

The Discrete Logarithm Problem and Key Exchange

While RSA is used for encryption and digital signatures, secure communication often starts with a key exchange protocol. The most famous, the Diffie-Hellman key exchange, relies on the hardness of the discrete logarithm problem (DLP).

Imagine working in modular arithmetic with a prime modulus $p$ and a special number $g$ called a generator. The core operation is modular exponentiation. It is relatively easy to compute $g^x\mathrm{mod}p$ for a secret exponent $x$. However, given the result $g^x\mathrm{mod}p$, finding the exponent $x$ is the discrete logarithm problem, which is exceptionally hard for large $p$.

Diffie-Hellman uses this for two parties, Alice and Bob, to create a shared secret over a public channel:

1. Alice and Bob agree publicly on a large prime $p$ and a generator $g$.
2. Alice picks a secret number $a$ and sends Bob $A=g^a\mathrm{mod}p$.
3. Bob picks a secret number $b$ and sends Alice $B=g^b\mathrm{mod}p$.
4. Alice computes the shared secret $s=B^a\mathrm{mod}p=(g^b{)}^a\mathrm{mod}p$.
5. Bob computes the shared secret $s=A^b\mathrm{mod}p=(g^a{)}^b\mathrm{mod}p$.

Both arrive at the same secret $s=g^{ab}\mathrm{mod}p$. An eavesdropper sees $p,g,A,$ and $B$, but cannot feasibly compute $g^{ab}$ without solving the discrete logarithm for either $a$ or $b$. This shared secret can then be used as a key for symmetric encryption. This protocol is the foundation for the security of HTTPS, VPNs, and SSH connections.

Common Pitfalls

1. Believing Larger Keys Are Always Better: While increasing key size (e.g., from 1024-bit to 2048-bit RSA) increases security, it also slows down computation. The goal is to choose a key size that provides security against foreseeable computational advances for the required lifespan of the data, balancing performance. A 4096-bit key is overkill for a message that needs to be secure for only 5 minutes.

2. Misunderstanding the One-Way Function's Assumptions: The security of factoring and discrete logarithm problems assumes the absence of a major mathematical breakthrough or quantum computers. Shor's algorithm, a quantum algorithm, can solve both problems efficiently, which is why the field is actively developing post-quantum cryptography based on different mathematical problems.

3. Using Small or Non-Random Primes: The strength of RSA depends entirely on the primes $p$ and $q$ being large, random, and truly secret. Using small primes, predictable primes, or reusing primes across systems creates catastrophic vulnerabilities. Key generation must use a cryptographically secure random number generator.

4. Confusing the Properties of Modular Arithmetic: Forgetting that modular reduction must happen at each step in a calculation or misunderstanding that $(a\mathrm{mod}n)\cdot (b\mathrm{mod}n)$ is not always equal to $(a\cdot b)\mathrm{mod}n$ unless you reduce modulo $n$ at the end, can lead to incorrect implementations and security flaws.

Summary

• Modern cryptography is built on "hard" mathematical problems that are easy to compute in one direction but practically impossible to reverse without secret information, known as trapdoor functions.
• Modular arithmetic creates the finite, cyclical number systems in which all these calculations occur, with modular inversion being a key operation for generating keys.
• The RSA encryption algorithm relies on the integer factorization problem—the difficulty of factoring a large composite number into its prime components.
• The Diffie-Hellman key exchange protocol enables secure key establishment over public channels by relying on the discrete logarithm problem in modular arithmetic.
• The security of these systems is not absolute but depends on key size, randomness, and the current state of computational mathematics, with ongoing research required to counter future threats like quantum computing.