Discrete Mathematics Unit 5 ReviewNumber Theory and Cryptography

Fundamentals of Number Theory

• Number theory studies the properties and relationships of integers, including prime numbers, divisibility, and modular arithmetic
• Integers are whole numbers that can be positive, negative, or zero (e.g., -3, 0, 5)
• Division algorithm states that for any two integers $a$ and $b$ with $b \neq 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = bq + r$, where $0 \leq r < |b|$
• Greatest common divisor (GCD) of two integers $a$ and $b$ is the largest positive integer that divides both $a$ and $b$ without leaving a remainder
  • Euclidean algorithm efficiently computes the GCD by repeatedly dividing the larger number by the smaller number and replacing the larger number with the smaller number and the smaller number with the remainder until the remainder is zero
• Least common multiple (LCM) of two integers $a$ and $b$ is the smallest positive integer that is divisible by both $a$ and $b$
• Fundamental theorem of arithmetic states that every positive integer greater than 1 can be uniquely represented as a product of prime numbers, up to the order of the factors
• Diophantine equations are polynomial equations with integer coefficients for which integer solutions are sought (e.g., $3x + 5y = 7$)

Prime Numbers and Factorization

• Prime numbers are integers greater than 1 that have exactly two positive divisors: 1 and itself (e.g., 2, 3, 5, 7, 11)
• Composite numbers are integers greater than 1 that are not prime, meaning they have more than two positive divisors (e.g., 4, 6, 8, 9, 10)
• Fundamental theorem of arithmetic guarantees the existence and uniqueness of the prime factorization for every positive integer greater than 1
• Prime factorization expresses a composite number as a product of prime numbers (e.g., $60 = 2^2 \times 3 \times 5$)
• Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit by iteratively marking the multiples of each prime number and eliminating them from the list of potential primes
• Primality testing algorithms determine whether a given number is prime or composite
  • Deterministic algorithms, such as the AKS primality test, provide a definitive answer but may be slower for large numbers
  • Probabilistic algorithms, such as the Miller-Rabin primality test, are faster but may have a small probability of error
• Prime number theorem describes the asymptotic distribution of prime numbers, stating that the number of primes less than or equal to $n$ is approximately $\frac{n}{\ln(n)}$ for large $n$

Modular Arithmetic

• Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value called the modulus
• Congruence relation: two integers $a$ and $b$ are congruent modulo $m$ if their difference $a - b$ is divisible by $m$, denoted as $a \equiv b \pmod{m}$ (e.g., $7 \equiv 2 \pmod{5}$ because $7 - 2 = 5$ is divisible by 5)
• Modular addition, subtraction, and multiplication are performed by computing the result as usual and then taking the remainder when divided by the modulus
  • Example: $(5 + 3) \bmod 7 = 1$ because $8 \equiv 1 \pmod{7}$
• Modular exponentiation is the process of raising a number to a power and then taking the remainder when divided by the modulus (e.g., $3^4 \bmod 5 = 1$ because $81 \equiv 1 \pmod{5}$)
  • Efficient algorithms, such as repeated squaring, are used to compute modular exponentiation for large exponents
• Modular multiplicative inverse of an integer $a$ modulo $m$ is an integer $b$ such that $ab \equiv 1 \pmod{m}$
  • Modular multiplicative inverses exist only when $a$ and $m$ are coprime (i.e., their GCD is 1)
  • Extended Euclidean algorithm can be used to find modular multiplicative inverses efficiently
• Chinese remainder theorem states that if the moduli are pairwise coprime, then a system of linear congruences has a unique solution modulo the product of the moduli

Cryptography Basics

• Cryptography is the study of techniques for secure communication in the presence of adversaries
• Plaintext is the original message or data that is to be encrypted
• Ciphertext is the result of encrypting the plaintext using an encryption algorithm and a key
• Encryption is the process of converting plaintext into ciphertext using a cryptographic algorithm and a key
• Decryption is the process of converting ciphertext back into plaintext using a cryptographic algorithm and a key
• Symmetric-key cryptography uses the same key for both encryption and decryption
  • Examples of symmetric-key algorithms include AES (Advanced Encryption Standard) and DES (Data Encryption Standard)
• Asymmetric-key cryptography, also known as public-key cryptography, uses a pair of keys: a public key for encryption and a private key for decryption
• Hash functions are one-way functions that map data of arbitrary size to a fixed-size output called a hash value or digest
  • Cryptographic hash functions, such as SHA-256 and MD5, are designed to be collision-resistant and preimage-resistant
• Digital signatures provide authentication, integrity, and non-repudiation by using asymmetric-key cryptography to sign a message or hash value with the sender's private key, allowing anyone to verify the signature using the sender's public key

Public Key Cryptosystems

• Public-key cryptography, also known as asymmetric-key cryptography, uses two different keys: a public key for encryption and a private key for decryption
• Public keys can be freely distributed and used by anyone to encrypt messages or verify digital signatures
• Private keys must be kept secret by the owner and are used to decrypt messages or create digital signatures
• Diffie-Hellman key exchange is a protocol that allows two parties to establish a shared secret key over an insecure channel without any prior knowledge of each other
  • The shared secret key can then be used for symmetric-key encryption to enable secure communication
• ElGamal cryptosystem is a public-key encryption scheme based on the discrete logarithm problem
  • It consists of key generation, encryption, and decryption algorithms, and provides semantic security under chosen-plaintext attacks
• Elliptic curve cryptography (ECC) is a type of public-key cryptography based on the algebraic structure of elliptic curves over finite fields
  • ECC offers similar security to other public-key cryptosystems with smaller key sizes, making it more efficient for resource-constrained devices
• Post-quantum cryptography refers to cryptographic algorithms that are believed to be secure against attacks by quantum computers
  • Examples include lattice-based cryptography, code-based cryptography, and multivariate cryptography

RSA Encryption

• RSA (Rivest-Shamir-Adleman) is a widely-used public-key cryptosystem named after its inventors
• Key generation in RSA involves selecting two large prime numbers $p$ and $q$, computing their product $n = pq$, and selecting an encryption exponent $e$ coprime to $(p-1)(q-1)$
  • The public key is $(n, e)$, and the private key is $(n, d)$, where $d$ is the modular multiplicative inverse of $e$ modulo $(p-1)(q-1)$
• Encryption in RSA is performed by raising the plaintext message $m$ to the power of $e$ modulo $n$, i.e., $c \equiv m^e \pmod{n}$
• Decryption in RSA is performed by raising the ciphertext $c$ to the power of $d$ modulo $n$, i.e., $m \equiv c^d \pmod{n}$
• Security of RSA relies on the difficulty of factoring large integers, as recovering the private key requires factoring the modulus $n$ into its prime factors $p$ and $q$
• Padding schemes, such as OAEP (Optimal Asymmetric Encryption Padding), are used to randomize the plaintext before encryption to prevent certain types of attacks
• Digital signatures in RSA are created by encrypting the hash value of a message with the sender's private key, allowing anyone to verify the signature using the sender's public key

Applications in Computer Science

• Secure communication protocols, such as HTTPS and SSH, use public-key cryptography to establish secure channels for exchanging symmetric keys and encrypting data
• Digital certificates are electronic documents that bind a public key to an identity, allowing for secure authentication and communication
  • Certificate authorities (CAs) are trusted third parties that issue and sign digital certificates
• Cryptocurrencies, such as Bitcoin and Ethereum, use public-key cryptography and digital signatures to secure transactions and prevent double-spending
• Secure multi-party computation allows multiple parties to jointly compute a function over their inputs while keeping those inputs private
  • Examples include secure voting systems, auctions, and data aggregation
• Homomorphic encryption enables computation on encrypted data without decrypting it first, allowing for privacy-preserving computation in untrusted environments
• Zero-knowledge proofs allow one party (the prover) to convince another party (the verifier) that a statement is true without revealing any additional information beyond the truth of the statement
  • Examples include Schnorr identification protocol and zk-SNARKs (zero-knowledge Succinct Non-interactive Arguments of Knowledge)
• Secure hardware, such as Trusted Platform Modules (TPMs) and Hardware Security Modules (HSMs), use cryptographic primitives to provide secure key storage, encryption, and attestation capabilities

Advanced Topics and Open Problems

• Lattice-based cryptography is a type of post-quantum cryptography that relies on the hardness of lattice problems, such as the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP)
  • Examples of lattice-based cryptosystems include NTRU, LWE (Learning with Errors), and Ring-LWE
• Fully homomorphic encryption (FHE) allows for arbitrary computation on encrypted data without decrypting it, enabling secure computation in untrusted environments
  • Current FHE schemes, such as the Gentry-Sahai-Waters scheme, are still computationally expensive and require further optimization for practical use
• Multiparty computation (MPC) protocols allow multiple parties to jointly compute a function over their private inputs without revealing those inputs to each other
  • Examples of MPC protocols include the GMW protocol, the BGW protocol, and the CCD protocol
• Indistinguishability obfuscation (iO) is a cryptographic primitive that aims to make two equivalent programs indistinguishable from each other, even if one program is an obfuscated version of the other
  • Constructing secure and efficient iO schemes is an active area of research with potential applications in software protection and secure computation
• Quantum cryptography, such as quantum key distribution (QKD), uses principles of quantum mechanics to enable secure communication and detect eavesdropping attempts
  • Practical challenges in implementing quantum cryptography include the need for specialized hardware and the limited distance of quantum channels
• Leakage-resilient cryptography aims to design cryptographic primitives and protocols that remain secure even if some information about the secret key is leaked to an adversary
  • Examples of leakage-resilient primitives include leakage-resilient encryption, signature schemes, and pseudorandom functions
• Cryptographic complexity theory studies the computational complexity of cryptographic primitives and the relationships between different cryptographic assumptions
  • Examples of complexity-theoretic notions in cryptography include one-way functions, trapdoor functions, and pseudorandom generators