Public-Key Encryption

Public-Key Encryption

• Public-Key Encryption is also known as Asymmetric Encryption.

Public-Key Encryption Structure

• Public-Key Encryption was publicly proposed by Diffie and Hellman in 1976.
• It relies on mathematical functions.
• It uses two separate keys: a public key and a private key.
• The public key is made available for anyone to use.
• A protocol for distribution is required.

Key Concepts

• Plaintext: The readable message or data fed into the encryption algorithm as input.
• Encryption Algorithm: Performs transformations on the plaintext.
• Public and Private Key: A pair of keys, where one is for encryption and the other for decryption.
• Ciphertext: The scrambled message produced as output.
• Decryption Key: Produces the original plaintext.
• A user encrypts data using their own private key.
• Anyone with the corresponding public key can decrypt the message.

Applications for Public-Key Cryptosystems

• Applications include RSA, Diffie-Hellman, DSS, and Elliptic Curve algorithms.
• RSA is used for digital signatures, symmetric key distribution, and encryption of secret keys.
• Diffie-Hellman is used for symmetric key distribution but not for digital signatures or encryption of secret keys.
• DSS is used for digital signatures only.
• Elliptic Curve is used for digital signatures, symmetric key distribution, and encryption of secret keys.

Requirements for Public-Key Cryptosystems

• It should be computationally easy to create key pairs.
• Either key can be used for each role.
• It should be computationally easy for the sender to encrypt messages knowing the public key.
• It should be computationally easy for the receiver to decrypt ciphertext knowing the private key.
• It should be computationally infeasible for an opponent to determine the private key from the public key.
• It should be computationally infeasible for an opponent to recover the original message.

Asymmetric Encryption Algorithms

• RSA (Rivest, Shamir, Adleman): Developed in 1977, it's widely accepted and implemented for public-key encryption, using a block cipher with integers between 0 and n-1.
• Diffie-Hellman Key Exchange: Enables two users to securely agree on a shared secret for subsequent symmetric encryption.
• Digital Signature Standard (DSS): Provides only a digital signature function using SHA-1.
• Elliptic Curve Cryptography (ECC): Offers security like RSA but with smaller keys.

Principles of Public-Key Cryptography

• Pairs of keys are used: public and private.
• Relies on hard mathematical problems that have no efficient solution.
• It is much slower/less efficient than symmetric (secret-key) protocols like AES.
• No secure channel is required to exchange the keys.
• Private keys are used to sign the message for authentication, and public keys are used to verify.
• Public keys are used to encrypt the message.
• Often used in hybrid cryptosystems, employing a public-key protocol for AES key exchange, then AES for the data encryption/decryption.

Ciphertext Indistinguishability

• An adversary cannot distinguish two ciphertexts encrypting two different messages and can only guess with a probability of 1/2.
• A secure ciphertext should not be distinguished from a freshly generated random sample using the same mathematical representation as ciphertext.
• Proofs of ciphertext indistinguishability for cryptographic schemes are derived using security games.
• INDistinguishability under Chosen Plaintext Attack (IND-CPA): The attacker can obtain encryptions for arbitrary plaintexts, which is feasible in public-key encryption.
• INDistinguishability under Chosen Ciphertext Attack (IND-CCA): The attacker can obtain decryptions of chosen ciphertexts.
• IND-CCA has two variants: IND-CCA1 (non-adaptive; weaker) and IND-CCA2 (adaptive; stronger).
• Relationship between these types of indistinguishability: IND-CPA ≤ IND-CCA1 ≤ IND-CCA2.

RSA Public-Key Encryption

• RSA was created by Rivest, Shamir, and Adleman of MIT in 1977.
• It is the best known and widely used public-key algorithm.
• It utilizes exponentiation of integers modulo a prime.
• The encryption formula is C = Me mod n.
• The decryption formula is M = Cd mod n = (Me)d mod n = M.
• Both sender and receiver know the values of n and e.
• Only the receiver knows the value of d.
• The public key encryption algorithm uses a public key PU = {e, n} and a private key PR = {d, n}.

RSA Algorithm

• Key Generation:
  • Select two prime numbers p and q, where p ≠ q.
  • Calculate n = p * q.
  • Calculate φ(n) = (p - 1) * (q - 1).
  • Select an integer e such that gcd(φ(n), e) = 1 and 1 < e < φ(n).
  • Calculate d such that de mod φ(n) = 1.
  • Public key: KU = {e, n}.
  • Private key: KR = {d, n}.
• Encryption:
  • Plaintext: M < n.
  • Ciphertext: C = Me (mod n).
• Decryption:
  • Ciphertext: C.
  • Plaintext: M = Cd (mod n).

Security of RSA

• Security can be compromised through brute force, mathematical attacks, timing attacks, and chosen ciphertext attacks.
• Brute Force: Involves trying all possible private keys.
• Mathematical Attacks: Several approaches attempt to factor the product of two primes.
• Timing Attacks: Depend on the running time of the decryption algorithm.
• Chosen Ciphertext Attacks: Exploit properties of the RSA algorithm.

Diffie-Hellman Key Exchange

• First published public-key algorithm.
• It was created by Diffie and Hellman in 1976.
• Practical for secure exchange of a secret key for subsequent message encryption.
• Security depends on the difficulty of computing discrete logarithms.
• Global Public Elements: prime number q, and α is a primitive root of q.

User A Key Generation

• Select a Key X that is less than q.
• Calculates Key Y which equal α to the power of X mod q.
• Both users exchange their public values.
• Each user raises the others value to their private value.

Diffie-Hellman Example

• Prime number q = 353 and primitive root α = 3 are publicly known.
• A computes YA = 3^97 mod 353 = 40.
• B computes YB = 3^233 mod 353 = 248.
• For A: K = (248)^97 mod 353 = 160.
• For B: K = (40)^233 mod 353 = 160.
• An attacker would have to solve 3^x mod 353 = 40, which is hard.

Security Vulnerability

• The Man-in-the-Middle Attack is a key challenge.
• A third party, Darth, intercepts and manipulates the key exchange. Steps include Darth generating their own key pair, intercepting Alice's transmission, and forwarding altered keys, compromising subsequent communications.

Digital Signatures

• Used for authenticating both the source and data integrity.
• Created by encrypting a hash code with a private key.
• It doesn't provide confidentiality as messages are safe from alteration but not eavesdropping.

Digital Signature Model

The digital signature are created using the senders private key to generate a digital signature that can be transmitted along with the message to allow the recipient Alice to verify and validate the signature.

Cryptographic Goals

• Confidentiality: Achieved through symmetric-key ciphers (block and stream) and public-key ciphers.
• Data Integrity: Ensured using arbitrary length hash functions, message authentication codes (MACs), and digital signatures.
• Authentication: Relies on entity authentication and message authentication codes (MACs).
• Non-Repudiation: Achieved through digital signatures.

Non-Repudiation

• If m is a signed message and s is a valid signature for m, the recipient can be sure the sender actually sent this message.
• Alice denies her signature if she finds m'≠m : s is a valid signature for m'

Use of MAC

• Used to provide data integrity and message authentication.
• Achieved through secret keys and algorithms.
• Both sender and receiver must share the same secret key.

Use of Digital Signatures

• Provides data integrity, message authentication, and non-repudiation.
• Signer's private key is used to create and transmit the signature that is transmitted along with the document.
• Signers public key is used to verify the integrity and authenticity of the message.

Difference between MAC and Digital Signature

• Validating a MAC to a third party requires revealing the key.
• Any party is able to create or verify the MAC if they have access to the signers secret key.
• MACs do not provide non-repudiation, as the secret key is shared between sender and recipient
• Computing a MAC is generally faster than computing a digital signature.

Public-Key for Certified Authority

• A browser sends a request to connect to the server and ask for a secure page.
• The web server sends its public key with its signing certificate back to the client.
• The browser checks whether the certificate was issued by a CA it trusts.
• The client compares the information in the certificate with the information received from the website and verifies all the details.
• The browser generates a random symmetric encryption key and encrypts to the server's public key.
• The information is sent to the server along with encrypted URL and other encrypted HTTP data.
• The web server decrypts the incoming packet using its private key.
• The web server then uses the symmetric key to decript the URL.
• Then the requested document from the client along with other data is encrypted with the symmetric key and sent back to browser.
• Finally, the browser decrypts the packet using the symmetric key and secure handshaking is established.

Certificate Authority

• Company A must make a certificate request to a certification authority to get a certificate for the key pair.
• The public key of A's key pair is included as part of the certificate request.
• The CA then uses company A's identity information to determine whether the request meets the CA's criteria for issuing a certificate.
• CA signs company A's public key with its private key to verify authenticity.
• Company A's public key signed with a valid CA's private key is called company A's certificate.
• A W3Techs survey from May 2015 reported on the market share of issuers.
• The top issuers include Comodo at 41.0% and Symantec at 30.2%.