Applied Cryptography Lecture 7

Applied Cryptography - Lecture #7

• Topic: Public Key Cryptography I
• Symmetric Cryptosystems Shortcomings
  • A key problem is key distribution and key management
  • Alice and Bob need a secret key for secure communication
  • Key exchange requires a secure channel or courier.
  • With n users, n(n-1)/2 secret key exchanges are necessary, all needing secure storage.
  • Digital signatures from symmetric-key encryption require large keys or a trusted third party (TTP).
• Asymmetric Cryptography
  • Bob publishes a public encryption key, known by everyone
  • Bob has a matching secret key for decryption
  • Bob's key has public (k_pub) and private (k_pr) parts
  • Asymmetric systems are also called public-key cryptosystems
• Asymmetric Cryptography - Basic Concepts
  • Public-key encryption schemes are substantially slower than symmetric-key algorithms like DES.
  • Public-key encryption is used for key transport, bulk data encryption, data integrity and authentication, and encrypting small data items (e.g., credit card numbers, PINs).
• Asymmetric Cryptography - Protocol
  • Sender uses recipient's public key to encrypt
  • Recipient uses their private key to decrypt
  • Different keys are used for encryption and decryption

One-Way Function

• Public-key algorithms rely on one-way functions.
• Function f(x) where y = f(x) is computationally easy and x = f^-1(y) is computationally infeasible.
• Computation of y = f(x) needs to be fast, but the inverse computation has to be computationally intensive.

Public-Key Algorithm Families

• Integer-Factorization Schemes: Difficult to factor large integers (e.g., RSA)
• Discrete Logarithm Schemes: Based on the discrete logarithm problem in finite fields (e.g., Diffie-Hellman, Elgamal, DSA).
• Elliptic Curve (EC) Schemes: Generalization of the discrete logarithm algorithm (e.g., ECDH, ECDSA).

Key Lengths and Security Levels

• Public-key algorithm families rely on number theoretic functions needing long operands and keys
• Longer operands/keys lead to greater security.
• Security level (n-bit): the best attack requires 2ⁿ steps.
• RSA-like and discrete-logarithm schemes typically require very long operands and keys.
• EC schemes have significantly smaller key lengths while maintaining sufficient strength when compared to symmetric ciphers.
• 128-bit security level usually required for long-term security.

RSA Cryptosystem

• RSA (1977), invented by Rivest, Shamir, and Adleman, is the most widely used public-key cryptosystem.
• Applications include:
  • Encryption of small pieces of data, especially for key transport
  • Digital signatures for digital certificates on the Internet.

Euclidean Algorithm

• Used for calculating the greatest common divisor (gcd) of two positive integers (r₀ and r₁).
• gcd(r₀, r₁) is the largest positive integer dividing both r₀ and r₁.

Euler's Phi Function

• φ(m) is the number of integers in Z_m that are relatively prime to m
• Useful for public-key schemes (especially RSA). This is often used in modular arithmetic when dealing with RSA.

RSA Key Generation

• Each entity creates an RSA public and private key.
  • Generate two large prime numbers p and q
  • Compute n = pq and φ(n) = (p-1)(q-1)
  • Select a random integer e (1 < e < φ(n)) such that gcd(e,φ(n)) = 1.
  • Find the unique integer d (1 < d < φ(n)) such that ed = 1 (mod φ(n)).
• Public key (n, e)
• Private key d

RSA Encryption and Decryption

• Encryption: y = x^e mod n (x is plaintext, y is ciphertext, e and n are from the public key)

• Decryption: x = y^d mod n (y is ciphertext, x is plaintext, d is the private key)

• In practice, x, y, n, and d are very large numbers (often 1024-bit or more)

• For Bob to send Alice an encrypted message, Alice must know Bob's public key. Bob decrypts with his private key

• e is the encryption exponent, d is the decryption exponent.

RSA Encryption in Practice

• Techniques to speed up RSA operations include fast modular multiplication and fast modular exponentiation, but, RSA encryption/decryption is nevertheless substantially slower than symmetric algorithms.

Avoiding RSA Vulnerabilities

• Use a strong prime number generator to make prime numbers unpredictable and difficult to guess.
• Use a minimum length of 2048 bits for the RSA key.
• Securely manage and rotate RSA keys properly, using different keys for different applications if appropriate.

Exercise

• Encrypt two messages (x₁ and x₂) using RSA with given parameters (p, q, e, d, x₁, x₂). Use the supplied values.

Explore the principles of Public Key Cryptography in this quiz. Understand the shortcomings of symmetric cryptosystems and the basics of asymmetric cryptography. Test your knowledge on key distribution, digital signatures, and public-key systems.