Asymmetric-key Cryptography

Part 1: Principles of Public-Key Cryptography

This lesson introduces the revolutionary idea of separating the encryption and decryption keys.

The Key Distribution Problem

• In symmetric-key cryptography, the same secret key is used for both encryption and decryption.
• The problem is how can two parties securely exchange this secret key in the first place?
  • If they can meet in person, they could exchange the key physically. However, this isn’t always practical (especially when separated over large distances)
  • If they send it over an insecure channel like the internet, an eavesdropper might be able to intercept it, and they might be able to decrypt all of their communications
• This problem is called the key distribution problem, and it is a major limitation in symmetric-key cryptography.

Public-Key Cryptography

• It uses two different keys:
  • Public Key: This key can be shared with anyone. It is used for encryption
  • Private Key: This key is kept secret by its owner. They can only have it. It is used for decryption.
• The process for encryption is as follows:
  • Suppose that two parties, Alice and Bob, wants to communicate:
  1. Key Generation: Each of them generates a key pair: a public key and a private key based on their chosen cryptosystem.
  2. Key Exchange: Alice shares her public key with Bob, and to anyone she wants to communicate with securely. Bob does the same, sharing his public key to Alice.
  3. Encryption: If Bob wants to send a message to Alice, he uses Alice’s public key to encrypt the message.
  4. Decryption: Alice can then only decrypt the message with her private key.

Mathematical Foundations

Public key cryptography relies on the difficulty of certain mathematical problems.
These problems can be easy to do in one direction, but computationally infeasible to reverse.

• Integer Factorization
  • Multiplying two large prime numbers is easy, but finding the two prime factors of a large number is hard.
  • This is the core concept of RSA cryptosystem.
• Discrete Logarithm Problem
  • Given a base , an exponent , and a modulus , computing is easy.
  • However, computing for the exponent in reverse is hard.
  • This is the core concept of the Diffie-Hellman and DSA cryptosystems.
• Elliptic Curve Discrete Logarithm Problem
  • This problem is related to the Discrete Logarithm Problem, but adapted to the algebraic structure of elliptic curves over finite fields.
  • The basis of the ECC cryptosystem.
  • While they have the same level of security as RSA or Diffie-Hellman, it is more efficient as it operates in much smaller key sizes, suitable for mobile devices or smart cards.

Part 2: The RSA Algorithm

The RSA, or the Rivest-Shamir-Adleman Algorithm, is one of the oldest and most widely used public-key cryptosystems. The security of this algorithm relies on the difficulty of integer factorization.

Key Generation Process

1. Choose Two Large Primes. The client chooses two distinct, random, very large prime numbers and . The larger the primes, the stronger the security. Typical sizes are 1024-bits, 2048-bits, and 4196-bits.
2. Compute the Modulus: The client then computes the product . The security of RSA depends on the difficulty of factoring back to and .
3. Compute Euler’s Totient: The client the computes Euler’s totient function of using the formula .
4. Choose the Public Exponent: The client chooses an integer such that:
   • is between and
   • and are both prime numbers
5. Compute the Private Exponent: The client computes the private exponent by solving:
6. Get the Key Pairs: The client’s public key is , and their private key is or

Encryption Process

When the other party encrypts a message to the client:

1. They obtain the client’s public key:
2. The message is represented as an integer ()
   • If the message is larger, it is broken into blocks.
3. The ciphertext is computed using .

Decryption Process

The client receives the ciphertext .

1. Use the private key: .
2. Compute the plaintext using the formula

Part 3: The Diffie-Hellman Key Exchange

• The Diffie-Hellman (DH) is a key agreement protocol.
  • It was made by Whitfield Diffie and Martin Hellman in a paper published in 1976.
• It allows two parties to agree on a shared secret key over an insecure channel, without ever directly transmitting the secret key itself.
• It is not an encryption algorithm. It is used to establish a shared secret key, which can be used with a symmetric key encryption algorithm to encrypt and decrypt.

Process Overview

Suppose that two parties, Alice and Bob, tries to communicate

1. Public Parameter Agreement: Alice and Bob agrees on two values, a large prime number , and a primitive root modulo (also called a generator), , which can be publicly known.
2. Private Key Generation: Alice and Bob chooses a random integer and . These are kept secret and it serves as their private key.
3. Public Key Generation: Alice and Bob computes their public keys, and respectively using the formula: .
4. Key Exchange: Both Alice and Bob exchanges public keys.
5. Shared Secret Calculation: The trick is that if Alice computes , it is inherently the same as when Bob computes ; this is the shared secret key which can then be used for symmetric-key cryptography.

Vulnerability to Man-in-the-Middle Attacks

• The Diffie-Hellman protocol in its basic form is vulnerable to a man-in-the-middle attack.

• How it May Work

  • The attacker intercepts the communication between Alice and Bob.
  • When Alice sends her public key , the attacker sends their own public key .
  • When Bob sends his own public key , the attacker sends their own other public key .
  • Alice and Bob now think that they’re establishing a shared secret between Alice and Bob when they’re actually establishing separate shared secrets with the attacker.
  • The attacker can now decrypt any messages between Alice and Bob, modify them, and re-encrypt them, all without anyone knowing.

Part 4: Elliptic Curve Cryptography

• Elliptic Curve Cryptography is based on the algebraic structure of elliptic curves over finite fields.
• While it provides the same level of security over RSA and Diffie-Hellman, it operates in much smaller key sizes, which makes it much more efficient, especially for environments with limited computing power.

What is an Elliptic Curve?

• These are curves defined by equations in the form:

• These equations have special geometric and algebraic properties.
• We use curves over a particular finite field (like numbers between 0 and : a large prime number minus 1).
• The coordinates of the points on an elliptic curve are elements of the finite field.
• One operation within points in an elliptic curve is point addition.
  • However, unlike regular addition, they are defined geometrically.
• Some of the properties of point addition are as follows:
  • Scalar Multiplication:
    
    • Inverse: For each point in the elliptic curve over the finite field , there is a special point whose sum is , the point in infinity.
      
    • Identity: Adding the point at infinity to any point is the point itself.
      

Key Generation Process

• Public Parameters: Alice chooses an elliptic curve and a base point .
• Private Key Generation: Alice chooses a random, secret integer .
• Public Key Generation: Alice then computes . This is her public key.

Cryptographic Processes

• ECDH (Elliptic Curve Diffie-Hellman): Uses elliptic curve point addition instead of modular exponentiation.
• ECDSA (Elliptic Curve Digital Signature Algorithm): Combines elliptic curves and digital signatures.
• ECIES (Elliptic Curve Integrated Encryption Scheme): A hybrid encryption scheme that uses ECC for key exchange and a symmetric cipher for message encryption.

Key Sizes

Security Level (bits)	RSA Key Size (bits)	ECC Key Size (bits)
80	1024	160
112	2048	224
128	3072	256
192	7680	384
256	15360	512

Common Uses of ECC

• TLS/SSL Certificates: Used for securing websites. Has the same level of complexity as RSA but much efficient due to smaller key sizes.
• Cryptocurrencies: Uses ECDSA for digital signatures for transaction authorization.
• SSH: Used in SSH key exchange and authentication.
• Mobile Devices and Embedded Systems: Ideal for resource-constrained devices.
• Smart Cards: For secure identification and authentication.

Part 5: Key Management and Public Key Infrastructure

• Key Problems
  • How do we know that a particular public key really belongs to the person or entity it claims to belong to?
  • How do you prevent the attacker from substituting their own public key and impersonating someone else?

What is Public Key Infrastructure?

• Public Key Infrastructure
  • It is a system of digital certificates, certificate authorities (CAs), and other supporting infrastructure that provides a way to trust public keys.
  • It’s the framework that binds public keys to identities and enables secure communication and digital signatures.

Certificate Authorities (CA)

• These are trusted organizations that issue and verify digital certificates.
• The process is as follows:
  • Identity Verification: When an entity applies to a digital certificate, they submit a CSR (Certificate Signing Request) to a CA. It verifies the entity’s identity using various methods depending on the type of certificate and the level of assurance required.
  • Certificate Issuance: The CA then issues a digital certificate, signing it with their private key.
  • Trust: Your browser comes pre-installed with a list of trusted root CA certificates. These list ensures that your browser trusts these certificates that have been signed by these CAs.

Digital Certificates

• It is analogous to digital ID card for a public key.
• It binds a public key to a particular entity.
• The most common digital certificate standard is X.509.
• The contents of a digital certificate are:
  • Subject: The identity of the entity the certificate is being issued to.
  • Public Key: The actual public key of the subject.
  • Issuer: The identity of the entity that issued the certificate.
  • Validity Period: The date/time which the certificate is valid.
  • Serial Number: The unique identifier for the certificate.
  • Signature Algorithm: The algorithm used to sign the certificate.
  • Digital Signature: The digital signature of the CA. This verifies the integrity of the certificate.
  • Extensions (Optional): Other information for the certificates , such as key usage restrictions, etc.

Chain of Trust

• Some certificates may not be directly signed by a root CA, but there is a chain of certificates leading back to a trusted root CA.
• If the certificate can be traced back to a top-level CA, then it can be trusted.
• Root CA: These are the top-level CAs, whose certificate is self-signed (its private key signs its own public key). Certificates from these CAs come preinstalled in some browsers and operating systems.
• Intermediate CAs: CAs whose certificates are signed by a root CA, or by an another intermediate CA.
• End-Entity Certificate: The certificate issued to the actual entity.

Certificate Revocation

• If a private key may be compromised, or a certificate is issued incorrectly, it needs to be revoked before its expiry date.
• Some methods are:
  • Certificate Revocation Lists (CRL): A list of serial numbers of revoked certificates.
  • Online Certification Status Protocol (OCSP): A protocol that allows a browser to check the revocation of a specific certificate through a real-time query to the CA.

Web of Trust

• In this model, trust is decentralized.
• Users generate their own key pairs, which are used to sign each other’s public keys.
• If you trust a user, it means that you might also trust the keys they signed, which creates a web of interconnected trust relationships.