CMSC 426 Lecture 6

1. Q: What is asymmetric encryption?
A: Asymmetric encryption (or public key cryptography) uses two distinct keys—one public and one private. The sender encrypts a message with the recipient’s public key, and the recipient decrypts it with their private key.

2. Q: What is RSA and who invented it?
A: RSA is a widely used asymmetric encryption algorithm named after its inventors Rivest, Shamir, and Adleman. It uses a public key for encryption and a private key for decryption.

3. Q: What are the basic steps in the RSA key generation algorithm?
A:

1. Pick two secret prime numbers, p and q.

2. Compute n = p × q and ϕ(n) = (p–1) × (q–1).

3. Choose a public exponent e (common value: 65537).

4. Compute the private exponent d such that d × e ≡ 1 (mod ϕ(n)).

4. Q: What constitutes RSA public and private keys?
A: The RSA public key is the pair (n, e) and the private key is (n, d). The primes p, q, and ϕ(n) are kept secret and used only during key generation.

5. Q: How are messages encrypted and decrypted in RSA?
A: Encryption is performed as c = m^e mod n (with m as plaintext), and decryption is m = c^d mod n.

6. Q: Can you provide a brief RSA key generation example?
A: For example, if p = 43 and q = 59, then n = 2537 and ϕ(n) = 2436. Choosing e = 67, we find d = 1927 so the public key is (2537, 67) and the private key is (2537, 1927).

7. Q: How does RSA encryption/decryption work in practice?
A: Using the example above, to encrypt m = 42: compute c = 42^67 mod 2537 = 1332. To decrypt, compute m = 1332^1927 mod 2537, which returns 42.

8. Q: Why is RSA considered secure?
A: RSA’s security depends on the difficulty of factoring the large number n into its prime factors (p and q). The larger the primes, the harder it is for an attacker to compute d.

9. Q: What are cryptanalytic attacks on RSA?
A: Attacks target the RSA algorithm by attempting to factor n, derive d from public parameters, or exploit weaknesses in unpadded RSA, especially when small exponents or repeated plaintexts are used.

10. Q: How can factoring a small RSA key compromise security?
A: If n is small, an attacker can factor it into p and q, compute ϕ(n), and then determine the private exponent d, breaking the encryption.

11. Q: How does RSA key size affect security?
A: Larger RSA key sizes (typically 2048 or 4096 bits) make factoring n computationally infeasible. Small keys can be factored more easily, compromising security.

12. Q: What vulnerabilities exist with unpadded RSA?
A: Without padding, RSA is deterministic—encrypting the same message always produces the same ciphertext—and is vulnerable to brute-force and chosen-plaintext attacks.

13. Q: What is the issue with unpadded RSA when m and e are small?
A: If m^e < n, the modulus operation has no effect, allowing an attacker to compute the e‑th root of c to recover m directly.

14. Q: Why is unpadded RSA considered deterministic?
A: Because encrypting the same plaintext always yields the same ciphertext, which makes it vulnerable to chosen-plaintext attacks and pattern analysis.

15. Q: What risk does encrypting repeated plaintext with RSA pose?
A: If the same message m is encrypted with different public keys (sharing the same e), an attacker can use the Chinese Remainder Theorem to recover m.

16. Q: What is Elliptic Curve Cryptography (ECC)?
A: ECC is an asymmetric cryptographic method based on the algebraic structure of elliptic curves over finite fields, offering equivalent security with smaller key sizes.

17. Q: What equation defines an elliptic curve and what are its key properties?
A: An elliptic curve is defined by y² = x³ + ax + b. It is symmetric about the x-axis and any line intersects it at no more than three points.

18. Q: How is point multiplication performed on an elliptic curve?
A: Point multiplication involves repeatedly adding a point P to itself (using tangent lines and reflections) to compute multiples like 2P, 3P, etc.

19. Q: How are ECC public and private keys generated?
A: The private key is an integer k, and the public key is computed as Q = kP, where P is a publicly known generator point on the curve.

20. Q: What makes the Elliptic-Curve Discrete Logarithm Problem hard?
A: Given P and Q, finding k such that Q = kP is computationally infeasible, as no efficient algorithm exists to reverse ECC point multiplication.

21. Q: What are some applications of ECC?
A: ECC is used in Elliptic Curve Diffie-Hellman (ECDH) key exchange, Elliptic Curve Integrated Encryption Scheme (ECIES), Elliptic Curve Digital Signature Algorithm (ECDSA), and is employed in cryptocurrencies like Bitcoin.

22. Q: When should symmetric and asymmetric cryptography be used respectively?
A: Use symmetric cryptography for encrypting large volumes of data (speed), and asymmetric cryptography for secure key exchange and digital signatures (security and non-repudiation).

23. Q: Why is symmetric encryption favored for speed?
A: Symmetric encryption algorithms (like AES) are generally faster and more efficient in hardware, making them ideal for encrypting bulk data.

24. Q: What role does asymmetric encryption play in key exchange?
A: Asymmetric encryption securely exchanges symmetric keys between parties, which are then used for fast, efficient data encryption.

25. Q: What are digital signatures and why are they important?
A: Digital signatures use private key encryption to “sign” a message, ensuring authenticity and non-repudiation—only the signer could have generated the signature.

26. Q: How do RSA digital signatures work?
A: The signer computes a signature s = m^d mod n using their private key. Anyone can verify it by computing m = s^e mod n with the signer’s public key.

27. Q: What is a Message Authentication Code (MAC)?
A: A MAC is a short piece of information attached to a message that verifies its integrity and authenticity using a shared secret key.

28. Q: How can message integrity be verified with hashes?
A: The sender appends a hash (or HMAC) of the message to it. The receiver re-computes the hash; if it matches the attached hash, the message is assumed unaltered.

29. Q: What are common methods for generating MACs?
A: MACs can be generated using cryptographic hash functions (as in HMAC) or block cipher-based methods, with the security relying on a shared secret key.

30. Q: What is an HMAC and why is it used?
A: HMAC (Hash-based Message Authentication Code) uses a cryptographic hash function with a secret key to produce a secure tag for verifying both message integrity and authenticity.

31. Q: What is the expression for an HMAC?
A: HMAC(k, m) = H((k⁺ ⊕ opad) ∥ H((k⁺ ⊕ ipad) ∥ m)), where k⁺ is the key adjusted to the block size, ⊕ denotes XOR, opad and ipad are constant pads, and ∥ denotes concatenation.

32. Q: How is an HMAC used in practice?
A: The sender computes HMAC(k, m) and appends it to the message. The receiver recalculates the HMAC with the shared key and compares it to the received tag to verify integrity and authenticity.

33. Q: How do digital signatures combine hashing and encryption?
A: The sender first hashes the message and then encrypts the hash with their private key, producing a digital signature. The receiver decrypts the signature with the public key and compares the hash to verify authenticity.

34. Q: What is the basic review of digital signatures?
A: Digital signatures provide authentication and non-repudiation by having the sender “sign” a message with their private key, allowing anyone with the public key to verify its origin.

35. Q: How does combining encryption with digital signatures enhance security?
A: It ensures confidentiality (via encryption), integrity (through hashing), authentication (via the signature), and non-repudiation (since only the signer could have created the signature).

36. Q: What is Public Key Infrastructure (PKI)?
A: PKI is a framework of hardware, software, policies, and procedures that manages digital certificates, public keys, and their revocation, enabling secure electronic transactions.

37. Q: What are X.509 certificates?
A: X.509 certificates are digital certificates that bind a public key to an entity (such as a website or individual) and include identifying information, validity dates, and a digital signature from a Certificate Authority (CA).

38. Q: What role do Certificate Authorities (CAs) play in PKI?
A: CAs are trusted organizations that issue and manage digital certificates, forming a chain of trust that browsers and systems rely on to verify identities.

39. Q: What information is contained in an X.509 certificate?
A: It typically includes the subject’s identity, public key, issuer information, validity period, and the digital signature of the issuing CA, along with revocation information.

40. Q: What are self-signed certificates and when are they used?
A: Self-signed certificates are issued and signed by the same entity rather than a CA. They are common in test environments, internal networks, or when establishing a root CA.

41. Q: What is an X.509 Certificate Signing Request (CSR)?
A: A CSR is a request sent to a CA to issue a digital certificate. It contains the entity’s public key and identifying information, and is signed by the entity’s private key.

42. Q: What is the chain of trust in PKI?
A: The chain of trust is the hierarchical structure in which a trusted root CA signs intermediate certificates, which in turn sign end-entity certificates. This chain allows users to verify that a certificate is trustworthy.

43. Q: What does an SSL certificate demo typically illustrate?
A: An SSL certificate demo shows how a website’s digital certificate is used to establish an encrypted connection (HTTPS), verifying the site’s identity and securing data in transit.

44. Q: How do asymmetric and symmetric cryptography complement each other?
A: Asymmetric cryptography is used for secure key exchange and digital signatures, while symmetric cryptography is used for fast data encryption. Typically, asymmetric methods exchange a symmetric key, which is then used to encrypt bulk data.