Cryptography Fundamentals

Cryptography is the mathematical engine of digital trust, enabling everything from secure online banking to private messaging. It transforms sensitive data into unintelligible form for transmission and storage, ensuring confidentiality, verifying identities, and guaranteeing data integrity. To master it, you must understand three core pillars: symmetric encryption, public-key cryptography, and hash functions, all built upon profound number-theoretic foundations.

Goals and Foundational Principles

Modern cryptography aims to provide specific security services. Confidentiality ensures data is secret from unauthorized parties, while integrity guarantees it has not been altered. Authentication verifies the identity of a communicating party, and non-repudiation prevents a sender from later denying they sent a message. These goals are achieved not through obscurity but through publicly scrutinized algorithms whose security rests on well-defined computational hardness assumptions. These are mathematical problems, like factoring large integers, believed to be intractable for classical computers within a practical timeframe, even when the attacker knows the encryption algorithm itself.

Symmetric Encryption: Sharing a Secret Key

Symmetric encryption uses a single, shared secret key for both encryption and decryption. Imagine a physical safe where the same key locks and unlocks it. The sender encrypts plaintext $P$ with key $K$ to produce ciphertext $C=E(K,P)$. The legitimate recipient decrypts with the same key to recover $P=D(K,C)$. Algorithms like AES (Advanced Encryption Standard) are highly efficient and secure, making them ideal for encrypting large volumes of data. The critical challenge is key distribution: how do two parties securely establish the same secret key over an insecure channel? This "key exchange problem" was the breakthrough that led to public-key cryptography.

Number-Theoretic Foundations

The security of asymmetric cryptography hinges on concepts from number theory. A fundamental idea is modular arithmetic, working with remainders. For an integer $n$, we say $a\equiv b(\mathrm{mod}n)$ if $n$ divides $(a-b)$. Crucially, some operations are easy in one direction but conjectured to be hard in reverse, forming one-way functions. For example, multiplying two large primes $p$ and $q$ to get $n=pq$ is computationally easy. However, given only $n$, finding its prime factors $p$ and $q$ is believed to be extremely difficult; this is the integer factorization problem. Another key problem is the discrete logarithm problem: given $g$, $h$, and a prime modulus $p$, finding $x$ such that $h\equiv g^x(\mathrm{mod}p)$ is hard, even though computing $g^x\mathrm{mod}p$ is easy.

Public-Key Cryptography: Asymmetric Keys

Public-key cryptography solves the key distribution problem by using a linked key pair: a public key for encryption or verification, and a private key for decryption or signing. The public key can be freely distributed; the private key is kept secret. Knowledge of the public key should not feasibly reveal the private key, which relies on computational hardness assumptions.

The RSA Algorithm

RSA, named for Rivest, Shamir, and Adleman, is based on the difficulty of integer factorization. Key generation involves:

1. Choose two large, distinct primes $p$ and $q$.
2. Compute $n=pq$ and $\varphi (n)=(p-1)(q-1)$.
3. Choose public exponent $e$ such that $1<e<\varphi (n)$ and $\gcd (e,\varphi (n))=1$.
4. Compute private exponent $d$ as the modular multiplicative inverse of $e$ modulo $\varphi (n)$, satisfying $e\cdot d\equiv 1(\mathrm{mod}\varphi (n))$.

The public key is $(n,e)$; the private key is $(n,d)$. To encrypt a message $M$ (represented as an integer less than $n$), compute ciphertext $C\equiv M^e(\mathrm{mod}n)$. Decryption recovers the message: $M\equiv C^d(\mathrm{mod}n)$. The security relies on the infeasibility of deriving $d$ from $(n,e)$ without knowing $\varphi (n)$, which requires factoring $n$.

Diffie-Hellman Key Exchange

Diffie-Hellman key exchange allows two parties to establish a shared secret over a public channel, based on the hardness of the discrete logarithm problem. It does not encrypt data directly but creates a symmetric key for later use.

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

Both arrive at the same secret $s\equiv g^{ab}(\mathrm{mod}p)$. An eavesdropper sees $p$, $g$, $A$, and $B$, but cannot feasibly compute $s=g^{ab}$ without solving the discrete logarithm problem to find $a$ or $b$.

Elliptic Curve Cryptography (ECC)

Elliptic curve cryptography provides similar functionality to RSA or Diffie-Hellman but uses the algebraic structure of elliptic curves over finite fields. The security relies on the elliptic curve discrete logarithm problem (ECDLP): given points $P$ and $Q=kP$ on a curve, finding the scalar $k$ is computationally infeasible. ECC offers equivalent security to older systems with much smaller key sizes (e.g., a 256-bit ECC key provides security comparable to a 3072-bit RSA key), leading to greater efficiency in bandwidth and computation, crucial for mobile devices and IoT.

Hash Functions and Digital Signatures

Hash functions are one-way, deterministic algorithms that map arbitrary-sized input data to a fixed-size output called a digest or hash (e.g., 256 bits). A cryptographically secure hash function must be preimage-resistant (given a hash $h$, it's hard to find any input $m$ with $hash(m)=h$), collision-resistant (hard to find two distinct inputs $m_1$ and $m_2$ with the same hash), and exhibit a strong avalanche effect.

These properties enable digital signatures, which provide authentication, integrity, and non-repudiation. A signature scheme, like ECDSA or RSA-PSS, uses a public-key primitive. To sign a message, the signer first computes its hash $h=H(m)$. They then apply a signing function using their private key to $h$, producing the signature $\sigma$. Anyone can verify the signature by recomputing $h=H(m)$ and applying a verification function using the signer's public key to the pair $(h,\sigma )$. A valid verification proves the message was signed by the holder of the private key and was not altered.

Common Pitfalls

Misunderstanding "Security Through Obscurity": Relying on a secret, proprietary algorithm instead of a publicly vetted one is a fatal flaw. True security comes from algorithms that remain secure even when everything except the key is known.

Insecure Key Generation and Management: Using weak random number generators to create keys (e.g., for RSA primes) can catastrophically compromise a system. Similarly, poor key storage, such as hardcoding keys in software, renders strong cryptography useless.

Misusing Cryptographic Primitives: Using a hash function like MD5 for passwords without a salt, or using ECB mode for block encryption, introduces critical vulnerabilities. Each primitive has specific properties and is designed for a particular use case.

Ignoring Side-Channel Attacks: An implementation can be mathematically sound but leak information through power consumption, timing, or sound. For example, a naive implementation of RSA that takes different times to process a 0 bit versus a 1 bit can reveal the private key.

Summary

• Modern cryptography is built on three pillars: symmetric encryption for efficiency, public-key cryptography for key management and digital signatures, and hash functions for data integrity.
• Security relies on computational hardness assumptions from number theory, primarily the integer factorization problem (RSA) and the discrete logarithm problem (Diffie-Hellman, ECC).
• Elliptic curve cryptography offers strong security with smaller key sizes, improving efficiency for modern applications.
• Digital signatures combine hash functions and public-key algorithms to provide authentication, integrity, and non-repudiation for digital messages.
• Correct implementation and key management are as critical as the choice of strong mathematical primitives; theoretical security can be undone by practical mistakes.