🔐Cryptography Unit 2 – Mathematical Foundations

Key Concepts and Terminology

• Cryptography involves the study of techniques for secure communication in the presence of adversaries
• Plaintext refers to the original message or data before encryption
• Ciphertext is the result of encrypting plaintext using an encryption algorithm and key
• Encryption transforms plaintext into ciphertext using a cryptographic algorithm and key
• Decryption reverses the encryption process, converting ciphertext back into plaintext using the appropriate key
• Cryptographic keys are secret values used in conjunction with an algorithm to encrypt and decrypt data
• Symmetric-key cryptography uses the same key for both encryption and decryption (AES, DES)
• Public-key cryptography, also known as asymmetric cryptography, uses a pair of keys: a public key for encryption and a private key for decryption (RSA, ECC)
  • The public key can be freely distributed, while the private key must be kept secret by the owner

Number Theory Fundamentals

• Number theory studies the properties of integers and their relationships
• Divisibility determines if one integer can be divided evenly by another without leaving a remainder
  • For example, 12 is divisible by 3 because 12 ÷ 3 = 4 with no remainder
• Greatest common divisor (GCD) of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder
  • Euclidean algorithm efficiently computes the GCD of two numbers
• Least common multiple (LCM) of two or more integers is the smallest positive integer that is divisible by each of the integers
• 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 factors
• Congruence relation ($a \equiv b \pmod{m}$) holds if $a$ and $b$ leave the same remainder when divided by $m$
• Multiplicative inverse of an integer $a$ modulo $m$ exists if $gcd(a, m) = 1$, and satisfies the equation $ax \equiv 1 \pmod{m}$

Modular Arithmetic

• Modular arithmetic performs calculations within a fixed range of integers, wrapping around when reaching the modulus
• The modulus, typically denoted as $m$ or $n$, determines the range of integers in modular arithmetic
• Modular addition ($a + b \pmod{m}$) adds two integers $a$ and $b$ and returns the remainder when divided by the modulus $m$
• Modular subtraction ($a - b \pmod{m}$) subtracts integer $b$ from $a$ and returns the remainder when divided by the modulus $m$
  • If the result is negative, add the modulus to obtain a positive remainder
• Modular multiplication ($a \times b \pmod{m}$) multiplies two integers $a$ and $b$ and returns the remainder when divided by the modulus $m$
• Modular exponentiation ($a^b \pmod{m}$) computes the remainder when $a$ raised to the power $b$ is divided by the modulus $m$
  • Efficient algorithms like repeated squaring are used to compute modular exponentiation
• Modular arithmetic properties include closure, associativity, commutativity, and the existence of identity elements for addition and multiplication

Prime Numbers and Factorization

• Prime numbers are integers greater than 1 that have exactly two positive divisors: 1 and itself
• Composite numbers are integers greater than 1 that have more than two positive divisors
• Primality testing determines whether a given number is prime or composite
  • Deterministic tests (AKS primality test) and probabilistic tests (Miller-Rabin test) are used
• Prime factorization expresses a composite number as a product of prime numbers
  • Trial division and more advanced algorithms (Pollard's Rho, Quadratic Sieve) are used for factorization
• Sieve of Eratosthenes is an efficient method for finding all prime numbers up to a given limit
• Fermat's Little Theorem states that if $p$ is prime and $a$ is not divisible by $p$, then $a^{p-1} \equiv 1 \pmod{p}$
• Euler's Totient function $\phi(n)$ counts the number of positive integers up to $n$ that are relatively prime to $n$
  • For a prime number $p$, $\phi(p) = p - 1$

Algebraic Structures

• Groups are algebraic structures consisting of a set and a binary operation satisfying closure, associativity, identity, and inverse properties
  • Examples include integers under addition $(\mathbb{Z}, +)$ and non-zero real numbers under multiplication $(\mathbb{R} \setminus \{0\}, \times)$
• Rings are algebraic structures with two binary operations (addition and multiplication) satisfying certain axioms
  • Examples include integers $(\mathbb{Z})$ and polynomials with real coefficients $(\mathbb{R}[x])$
• Fields are rings where every non-zero element has a multiplicative inverse
  • Examples include real numbers $(\mathbb{R})$ and complex numbers $(\mathbb{C})$
• Finite fields, also known as Galois fields $GF(p^n)$, are fields with a finite number of elements
  • Widely used in cryptography for designing secure algorithms (AES, ECC)
• Cyclic groups are groups where every element can be generated by a single element called the generator
  • Cryptographic algorithms often rely on the hardness of discrete logarithm problem in cyclic groups
• Elliptic curves are algebraic curves defined by equations of the form $y^2 = x^3 + ax + b$ over a field
  • Elliptic curve cryptography (ECC) uses the algebraic structure of elliptic curves for designing secure public-key cryptosystems

Probability and Statistics in Cryptography

• Probability theory studies the likelihood of events occurring and provides a foundation for analyzing cryptographic algorithms
• Random variables are variables whose values are determined by the outcome of a random experiment
  • Discrete random variables take on a countable number of distinct values (coin flips, dice rolls)
  • Continuous random variables can take on any value within a specified range or interval (time, temperature)
• Probability distributions describe the likelihood of different outcomes for a random variable
  • Examples include uniform distribution, binomial distribution, and normal distribution
• Expected value of a random variable is the average value obtained over a large number of independent trials
• Standard deviation measures the dispersion of a random variable around its expected value
• Cryptographically secure pseudorandom number generators (CSPRNGs) produce sequences of numbers that appear random and are suitable for cryptographic purposes
  • Examples include Blum Blum Shub (BBS) and Fortuna
• Statistical tests (NIST SP 800-22) are used to evaluate the randomness of pseudorandom number generators
• Cryptanalysis techniques often rely on statistical analysis to detect patterns and weaknesses in cryptographic algorithms

Computational Complexity

• Computational complexity theory studies the resources (time, space) required to solve problems using algorithms
• Big O notation describes the upper bound of an algorithm's running time or space complexity
  • Examples: $O(1)$ constant time, $O(n)$ linear time, $O(n^2)$ quadratic time, $O(2^n)$ exponential time
• Polynomial-time algorithms have running times bounded by a polynomial function of the input size
  • Considered feasible for practical purposes
• Exponential-time algorithms have running times bounded by an exponential function of the input size
  • Considered infeasible for large input sizes
• P (Polynomial) is the class of decision problems that can be solved by a deterministic Turing machine in polynomial time
• NP (Nondeterministic Polynomial) is the class of decision problems that can be verified by a deterministic Turing machine in polynomial time
  • NP-complete problems are the hardest problems in NP, and solving one efficiently would imply solving all NP problems efficiently
• Cryptographic algorithms rely on the presumed hardness of certain computational problems (integer factorization, discrete logarithm) for their security

Applications in Cryptographic Algorithms

• Symmetric-key algorithms (AES, DES) use the same key for encryption and decryption
  • AES (Advanced Encryption Standard) is a widely used symmetric-key block cipher with key sizes of 128, 192, or 256 bits
• Public-key algorithms (RSA, ECC) use a pair of keys: a public key for encryption and a private key for decryption
  • RSA (Rivest-Shamir-Adleman) is a widely used public-key cryptosystem based on the hardness of integer factorization
• Digital signatures provide authentication, integrity, and non-repudiation for digital messages
  • Examples include RSA signatures and ECDSA (Elliptic Curve Digital Signature Algorithm)
• Key exchange protocols (Diffie-Hellman) allow two parties to establish a shared secret key over an insecure channel
• Hash functions (SHA-256, MD5) generate fixed-size digests of input messages
  • Cryptographic hash functions are designed to be one-way and collision-resistant
• Message authentication codes (MACs) provide data integrity and authentication using a shared secret key
  • Examples include HMAC (Hash-based MAC) and CMAC (Cipher-based MAC)
• Cryptographic protocols (SSL/TLS, IPsec) use a combination of cryptographic primitives to provide secure communication over networks