Unit 3: Assymetric-key Encipherment

I. Orientation

Asymmetric-key cryptography, developed publicly in the 1970s, uses mathematically related but different keys: a public key that may be distributed openly and a private key retained by its owner. Its security depends on computationally difficult mathematical problems rather than secrecy of the algorithm.

A. Defining Principles

The asymmetric model enables confidentiality, authentication, digital signatures, and secure key establishment over an insecure network.

• Key pair: Each participant generates a public key (K_U) and a corresponding private key (K_R).
• One-way relationship: Computing the public key from the private parameters is efficient, but recovering the private key from the public key should be computationally infeasible.
• Confidentiality convention: A sender encrypts using the recipient's public key; only the recipient should be able to decrypt using the private key.
• Signature convention: The owner signs with the private key, while others verify with the public key.
• Security assumption: RSA relies mainly on integer factorization, ElGamal and Diffie-Hellman on discrete logarithms, and Rabin on modular square-root extraction.
• Operational limitation: Public-key operations are relatively expensive, so practical systems use them to establish a symmetric session key rather than encrypting an entire data stream.

II. Mathematical Foundations

A. Mathematics of Asymmetric cryptography

The mathematics of asymmetric cryptography supplies operations that are easy to compute in one direction but difficult to reverse without secret information.

• Modular arithmetic: For integers (a), (b), and positive modulus (n), (a \equiv b \pmod n) means that (n) divides (a-b).
• Modular inverse: (a^{-1}\pmod n) is an integer (x) satisfying (ax\equiv1\pmod n); it exists exactly when (\gcd(a,n)=1).
• Euler's totient: (\phi(n)) counts integers in ({1,\ldots,n}) coprime to (n). For distinct primes (p,q):
  
  TEXT

  n = pq
  phi(n) = (p - 1)(q - 1)

• Euler's theorem: If (\gcd(a,n)=1), then (a^{\phi(n)}\equiv1\pmod n). This supports RSA's correctness.
• Fermat's little theorem: For prime (p) and (p\nmid a), (a^{p-1}\equiv1\pmod p).
• Discrete logarithm: Given (g), (p), and (y\equiv g^x\pmod p), finding (x) is hard for suitable parameters, although computing (y) from (x) is efficient.
• Fast exponentiation: Square-and-multiply computes (a^e\bmod n) in (O(\log e)) modular multiplications.

B. Significance and Limitations

• Parameter dependence: Hardness requires adequately sized moduli, carefully generated primes, and appropriate groups.
• Quantum threat: Shor's algorithm could solve factorization and discrete logarithms efficiently on a sufficiently powerful quantum computer.
• Implementation risk: Timing, power, cache, and fault observations can reveal private values even when the underlying mathematics remains secure.

III. Prime Selection

A. Prime and Primality Testing

Prime generation produces the large prime parameters required by RSA, Rabin, ElGamal, and many Diffie-Hellman groups.

1. Trial division: Divide (n) by primes up to (\sqrt n). It is exact but impractical for cryptographic-size numbers.
2. Probabilistic testing: Miller-Rabin tests whether an odd candidate behaves like a prime for several bases and efficiently rejects composites.

• Miller-Rabin decomposition: Express (n-1=2^sd), where (d) is odd, and test powers of a selected base (a):
  
  TEXT

  x = a^d mod n
  accept this round if x = 1 or x = n - 1
  otherwise repeatedly set x = x^2 mod n, at most s - 1 times
  accept this round if x becomes n - 1; otherwise declare composite

• Error control: For an odd composite, one random Miller-Rabin round has false-prime probability at most (1/4); (k) independent rounds reduce it to at most (4^{-k}).
• Prime generation: Generate a random odd number of the required bit length, reject small-prime divisibility, and apply repeated primality tests.

B. Practical Requirements

• Unpredictability: Candidates must come from a cryptographically secure random number generator.
• Structure checks: Protocols may require safe primes (p=2q+1), where both (p) and (q) are prime.
• Validation: Accepting composite or maliciously structured parameters can invalidate the assumed hard problem.

IV. Integer Decomposition

A. Factorization

Factorization expresses a composite integer as a product of primes and forms the central hardness assumption behind RSA and Rabin.

• Cryptographic problem: Given (n=pq), recover the secret primes (p) and (q). No classical polynomial-time algorithm is known for suitably chosen large primes.
• Trial division: Tests candidate factors directly and is useful only for removing small factors.
• Pollard's rho: Uses pseudorandom modular sequences to find relatively small factors through greatest-common-divisor calculations.
• Quadratic sieve: Efficient for moderately large general integers by finding values whose squares are congruent modulo (n).
• Number field sieve: The best-known classical general-purpose method for factoring very large integers.
• Key-size implication: Larger RSA moduli increase resistance because factorization cost rises rapidly; modern deployments normally require at least a 2048-bit RSA modulus.
• Weak-prime risk: If (p) and (q) are too close, Fermat factorization may recover them from:
  
  TEXT

  n = a^2 - b^2 = (a - b)(a + b)

B. Security Implications

• Shared factors: If two moduli share a prime, (\gcd(n_1,n_2)) immediately reveals it.
• Prime secrecy: Once (p) and (q) are known, an attacker computes (\phi(n)) and derives the RSA private exponent.
• Balance: RSA primes should be random, distinct, sufficiently large, and comparable in bit length.

V. Modular Reconstruction

A. Chinese Remainder Theorem

The Chinese Remainder Theorem reconstructs a unique residue modulo a product of pairwise coprime moduli.

• Formal statement: If (\gcd(n_i,n_j)=1) for (i\ne j), the system (x\equiv a_i\pmod{n_i}) has one solution modulo (N=\prod_i n_i).
• Construction: Define (N_i=N/n_i) and (M_i=N_i^{-1}\pmod{n_i}). Then:
  
  TEXT

  x = sum(a_i N_i M_i) mod N

• Worked example: For (x\equiv2\pmod3) and (x\equiv3\pmod5), (N=15), (N_1=5), (M_1=2), (N_2=3), and (M_2=2):
  
  TEXT

  x = (2 x 5 x 2 + 3 x 3 x 2) mod 15 = 8

• Cryptographic use: RSA decryption can compute separately modulo (p) and (q), then combine the results, making private-key operations substantially faster.
• Fault risk: A faulty CRT-RSA signature may expose a prime factor, so implementations verify results or apply fault-resistant countermeasures.

VI. Cryptosystem Comparison

A. Difference of Symmetric and Assymetric Cryptosystems

Symmetric systems use one shared secret, whereas asymmetric systems divide cryptographic capability between public and private keys.

1. Symmetric cryptography:
   • Key model: The same secret key, or easily related keys, performs encryption and decryption.
   • Performance: Algorithms such as AES efficiently protect high-volume data.
   • Distribution problem: Both parties must obtain the shared key securely before communication.
2. Asymmetric cryptography:
   • Key model: A public key is distributed, while the mathematically related private key remains secret.
   • Performance: Modular exponentiation makes it slower than symmetric encryption.
   • Capabilities: It supports public-key encryption, signatures, authentication, and key agreement.

• Hybrid operation: TLS commonly uses asymmetric authentication and key establishment, then symmetric authenticated encryption for application data.
• Trust requirement: A certificate or trusted key-distribution mechanism must bind a public key to its claimed owner.
• Relative key sizes: Security levels are not compared directly by bit count; a 256-bit elliptic-curve key and a 3072-bit RSA key can target roughly comparable classical security.

VII. RSA

A. RSA Cryptosystem

RSA uses modular exponentiation and the difficulty of factoring a product of two large primes.

• Key generation:
  
  TEXT

  Choose distinct primes p and q
  n = pq
  phi(n) = (p - 1)(q - 1)
  Choose e such that gcd(e, phi(n)) = 1
  Compute d = e^(-1) mod phi(n)
  Public key = (n, e); private key = d

• Encryption: For encoded message (m), where (0\le m<n), compute (c=m^e\bmod n).
• Decryption: Recover (m=c^d\bmod n), since (ed\equiv1\pmod{\phi(n)}).
• Correct encoding: Textbook RSA is deterministic and insecure. Encryption requires randomized OAEP padding; signatures require schemes such as RSA-PSS.
• Security boundary: RSA security is associated with factorization, but no general proof establishes that breaking every RSA instance is exactly equivalent to factoring.
• Implementation protection: Private operations require constant-time arithmetic, blinding, and resistance to padding-oracle attacks.

VIII. ElGamal

A. ElGamal Cryptosystem

ElGamal encrypts through a fresh ephemeral exponent and derives security from the discrete-logarithm family of assumptions.

• Key generation: Select cyclic group generator (g), modulus (p), and private (x); publish (y=g^x\bmod p).
• Encryption: For message representative (m), choose a new random (k):
  
  TEXT

  c1 = g^k mod p
  c2 = m y^k mod p
  ciphertext = (c1, c2)

• Decryption: Compute shared value (s=c_1^x\bmod p), then recover (m=c_2s^{-1}\bmod p).
• Randomization: Different values of (k) produce different ciphertexts for the same message.
• Critical requirement: Reusing or predicting (k) can reveal relationships between plaintexts and destroy security.
• Limitation: Ciphertexts contain two group elements and are malleable; secure applications require authenticated hybrid constructions rather than textbook ElGamal.

IX. Rabin

A. Rabin Cryptosystem

Rabin encrypts a message by squaring it modulo a composite and has security directly related to integer factorization.

• Key generation: Choose primes (p\equiv q\equiv3\pmod4), compute (n=pq), publish (n), and retain (p,q).
• Encryption:
  
  TEXT

  c = m^2 mod n

• Decryption: Use (p) and (q) to find square roots modulo each prime, then combine them through the Chinese Remainder Theorem.
• Four-root ambiguity: A quadratic residue modulo (n=pq) generally has four square roots, so redundancy or structured padding is needed to identify the intended message.
• Security result: Extracting arbitrary modular square roots modulo a composite of unknown factorization is computationally equivalent to factoring that modulus.
• Practical weakness: Unprotected Rabin encryption is deterministic and vulnerable to chosen-ciphertext attacks; secure encoding is essential.

X. Diffie-Hellman

A. Diffie-Hellman cryptosystem

Diffie-Hellman, introduced publicly in 1976, is principally a key-agreement mechanism rather than a direct message-encryption algorithm.

• Public parameters: Participants agree on a large prime (p) and a generator (g) of a suitable subgroup.
• Alice's value: Alice chooses private (a) and sends (A=g^a\bmod p).
• Bob's value: Bob chooses private (b) and sends (B=g^b\bmod p).
• Shared secret:
  
  TEXT

  Alice computes K = B^a mod p
  Bob computes K = A^b mod p
  Both obtain K = g^(ab) mod p

• Key derivation: The group element (K) is passed through a key-derivation function before use as a symmetric key.
• Forward secrecy: Ephemeral Diffie-Hellman uses fresh (a) and (b) per session, limiting damage if a long-term authentication key is later compromised.
• Authentication limitation: Basic Diffie-Hellman is vulnerable to a man-in-the-middle attack because exchanged values have no authenticated identity.
• Parameter validation: Implementations must validate group elements and use secure groups to prevent small-subgroup and invalid-parameter attacks.