home

Public Key (Asymmetric) Encryption

Intro - What is Assymetric Encryption?

Why? If we use symmetric encryption, in sending emails, we need a shared key with each person we want to communicate with (think - why?). So, we won’t be able to send an email to anyone we don’t yet know.

Generating and exchanging new symmetric keys will get tedious as more people want to encrypt messages to you

  • In Assym encryption, anyone can send encrypted messages to us using just our public key.

  • Only, we can decrypt those messages using our private key.

Functional behaviour

  1. Generate a public key and a private key using a key-gen algorithm.
  2. Anyone with public key can encrypt the messages
  3. Only the owner (with the private) key can decrypt.
  4. Risk : the public key may not belong to who they’re claiming to be. Problem for later. If Alice is sending me an email – how do we know if a public key I am using belongs to Alice?

The input (security parameter) usually translates as "how big do you want your keys to be?" (the bigger, the more secure)

Performance

  1. Asyym is very low performant for emails, its slow, the operations it does are computationalally expensive.
  2. Symm key encryption uses AND, OR, XOR ops which are fast. In practice, this is 100-1000x faster than asymm encryption

How do we use Asymm Encryptionm

  1. Key Exhcanges
  2. Hybrid Exchanges

Key Exchanges

Asymm can be used to perform key exchanges. Mostly via key encapsulation alt text

Key encapsulation: Bob generates random key, then encrypts that key for Alice using public key of Alice. Only Alice can decrypt that cipher. She will therefore get the random key generated by Bob. After this alice/bob will share a key and will communicate via symmetric key encryption. Remember, asymm encryption is very slow. So, using asymm just for key exhcange reduces the need to use it so much.

This is done usually via RSA algorithm; although RSA is used less as compares to Elliptic Curve Diffie-Hellman algo (ECDH). ECDH has smaller parameter size, and RSA has been found to have some vulnerabilities.

alt text

^ The ‘encrypted symmetric key’ encrypted via Alice’s public key –> is the encapsulation of the key. The ‘encapsulated key’ gets sent to Alice, and only she can unexcapsulate it.

Hybrid Encryption

  • Every invocation of aymm encryption can encrypt plaintexts upto a certain length ceiling.
  • This largest possible size is limited by the ‘security parameter’ (what is this param?)
  • Current recc 512 ASCII chars (4096 bits)

What can we do?

  • Break message into blocks and encrypt them.. but the problem is that asymm encryp is slow.
  • Most applns use hyrbid encryption which implicitly uses key encapsulation and authenticated encryption.. making it faster and safer!

Defn:

  • Hybird encryption is a combination of symm + asymm crypto primitives:
    1. Non-symm: key-exchange
    2. Symm: use authenticated encryption

It similar to key-encapsulation in key-exchange, but we are also encapsulating data as well.

In Summary “We generate a symmetric key; (asymm) use Alice’s public key to encrypt this key, so only Alice can decrypt it; once alice decrypts it: we then use symmetric key encryption (using the just shared key) to communicate with alice”

Funtionally it looks like asymm encryption: alt text

alt text

Example: Elliptic Curve Integrated Encryption Scheme (ECIES)

alt text

ECIES IS a hybrid encrypotion system.

Asymmetric Encryption: RSA

Take numbers from number 1 to p- 1 ; p is a prime; under multiplication modulo p alt text

  • One of the numbers represents the message we want to send

alt text

alt text

issues and fixes

  • [first issue] if the numbers that can be encrypted for a case are small; then a attacker can brute forrce and fidn all the (plaintext - ciphertext) pairs

then ‘PKCS v1.5’ was introduced that fixes the issue by padding the message with random bytes

  • 1998 another issue to break PKCS v1.5’ the “million messages attack” – the mitigations were found, but too hard to implement. (Bleichenbacker’s attack/adapttive chosen ciphertext) – tampers with the ciphertext.

  • ‘RSA-OAEP’ fixed the issues to prevent Bleichenbacker. PKCS V2.0 it comes with a method to generate key. RSA-OAEP has a secure padding scheme.

  • OAEP vuln were found – but only if the implementation is impoper. Theoretically its ok. Better to have simpler messages

how it works

  1. first we pad the message
  2. paded message is XORs with a random number (masking)
  3. a tag is added
  4. these MGFs: are hasing functions / extendable output functions

More info alt text

RSA-KEM

  • Key encapsulating mech
  • Ciphertext: a random number is used to produce a symm key (via hashing). this symm key is used to encrypt via authenticated encryotion.
  • RSA KEM is rarely used. Most used are PKCS v1.5 or v2.0 standards.

Hybrid encryption with ECIES (elliptic curve)

  • Most widely used.
  • ANSI
  • NO KEY ENCAPSULATION. Key exhcange is used
  • DH version exists, not widely used. What is the advantage of using ECIES for hybrid encryption?

  • It uses ECDH for key exchange, which has smaller parameter sizes

  • step 1: bob create ephemeral key pair (pub, private)

  • with ephenmeral private key–> we do a key exchange using alice public key
  • hence we get a shared symm key

  • this symm key is used for (to generate cipher) authenticated encryption with alice.

  • alice combines the public key she receieved (step 1) with her private key to re-generate the symmetric key

  • now she can decrypt the ciphertext and can read with integrity + authenticity

  • AES-GSM, ChaCha,

RSA