Cryptography Quiz: Key Management and Diffie-Hellman

Asymmetric Encryption Overview

• Asymmetric encryption uses two keys: a public key and a private key.
• The public key is used to encrypt data; only the corresponding private key can decrypt it.
• This contrasts with symmetric encryption where the same key is used for both encryption and decryption.

Asymmetric Encryption Problems

• Attackers can potentially access the encryption scheme and ciphertext, along with the public key.
• This allows for impersonation of other users.
• Asymmetric encryption is computationally more intensive than symmetric encryption.

Asymmetric Encryption Applications

• Encryption and decryption
• Digital signatures: Encrypting a message with a private key to verify authenticity.
• Symmetric key exchange: Securely sharing a secret key using asymmetric encryption.

Asymmetric Encryption: Requirements

• Generating public/private key pairs is computationally easy.
• Encrypting messages using the public key is computationally easy.
• Decrypting messages using the private key is computationally easy.
• Finding a corresponding private key from a public key is computationally infeasible.
• Recovering a message from its encrypted form using only the public key is computationally infeasible.

Asymmetric Encryption: Public Key Cryptanalysis

• Key size needs to be large enough to thwart brute-force attacks on the algorithm used to generate the keys.
• Key size should be practical to use.
• Another attack is finding the private key from the public key; this remains mathematically infeasible today for many algorithms.

Rivest Shamir Adleman (RSA) Algorithm

• RSA key generation involves choosing two large prime numbers (p and q), calculating n = p * q, and other calculations.
• The public key is <e, n>, while the private key is <d, n>.
• Encryption: c = m^e mod n
• Decryption: m = c^d mod n
• Security relies on the difficulty of factoring large numbers.

RSA Example

• An example illustrates RSA encryption and decryption using specific numbers.

RSA Processing of Multiple Blocks

• Data is divided into multiple blocks for encryption and decryption.
• Each block is processed independently using the RSA algorithm.

RSA Security Attacks

• Brute-force attacks attempt to try all possible keys.
• Mathematical attacks target the algorithm's underlying assumptions about factorization difficulty.
• Timing attacks exploit decryption time variations based on data characteristics. Techniques like constant time implementations are used as a countermeasure.
• Hardware fault-based attacks try to induce faults in hardware to learn private key information.
• Chosen ciphertext attacks exploit properties of the RSA algorithm by selecting ciphertext and obtaining corresponding plaintexts to try and derive the private key.

RSA Factorization

• Factoring large numbers is crucial for RSA's security. The 2020 factorization of RSA-250 highlights continuing efforts to test security assumptions with progressively larger keys.

Key Management: Session Key Exchange

• Public keys are associated with certificates (proofs of ownership or authenticity) for authenticity.
• A Key Distribution Center (KDC) facilitates key distribution to multiple parties using negotiated shared keys.
• Diffie-Hellman Key Exchange enables two parties to securely establish a shared secret key.

Diffie Hellman Key Exchange

• A and B exchange parameters like a prime p and generator g (potentially also prime).
• Each party generates a secret number (e.g., x and y) calculates a public value (e.g., n, m) and transmits it to the other.
• Both parties use the received public values to calculate a shared secret key.
• The key exchange's security rests on the complexity of computing discrete logarithms.

Diffie Hellman Key Exchange Example

• An example illustrates how Diffie Hellman works numerically, with the steps being shown and described.

"Man in the Middle" Attack

• This attack involves an interceptor impersonating both parties in a key exchange.
• This attack breaks the security of the key exchange, gaining access to shared secrets.

Elliptic Curves Arithmetic

• Elliptic curve cryptography (ECC) uses elliptic curves, which have specific mathematical properties.
• These curves are described by equations, and computations are restricted to values in finite fields.

Elliptic Curves over Zp

• Elliptic curve cryptography uses variables and coefficients restricted to values in finite fields (like integers modulo p).
• Some parameters for these curves can be prime numbers. Some are binary curves over GF(2m) (which are binary), and these are faster for hardware processing.

Points on the Elliptic Curve

• Points on the elliptic curve have specific properties and addition rules under this structure.
• For any three points in the curve, the sum of those points is the zero point.

Elliptic Curves Addition Rules

• Elliptic curves have specific ways to add points.
• To add two points P and Q with different x coordinates, draw a line through them and find the point of intersection; this intersection creates a new point known as the negative of the point.

Elliptic Curves Example

• A demonstration of adding points on an elliptic curve (with real or finite field values).

Elliptic Curves Cryptography

• Elliptic curve cryptography (ECC) builds cryptographic systems using the mathematical properties of elliptic curves.
• It is assumed to be difficult to find corresponding keys or values and for many implementations, to find a solution to the discrete logarithm problem in elliptic curves.

Example ECC

• An example of elliptic curve cryptography computations is provided.

Analog to Diffie Hellman Key Exchange

• The basic idea is analogous to Diffie-Hellman but specific to elliptic curves.

Comparable Key Sizes

• A table contrasts key sizes required for different types of cryptography (like symmetric, asymmetric algorithms, and digital signatures).

Conclusion

• The presented information is intended to summarize topics related to asymmetric encryption and elliptic curve cryptography.