Asymmetric Cryptography Summary

Ciphers Taxonomy:
- Symmetric (one key)
- Asymmetric (two keys)
  - Stream
  - Block
Asymmetric Ciphers: Encryption and decryption keys are different.
- Keys are related, but deriving one from the other is computationally infeasible.
- Each participant needs a key pair (private and public).
- Also known as public key cryptography.
- Security depends on:
  - Algorithm strength
  - Key size
  - Confidentiality of the private key.

Key distribution is simpler than symmetric ciphers.
Each participant:
- Creates an asymmetric key pair.
- Publishes the public key.
- Keeps the private key secret.
If there are $n$ participants, $n$ key pairs are needed.
Ways to obtain public keys:
- Directly from the owner.
- Website.
- Public keyserver.

To send a confidential message to Bob, Alice:
1. Needs Bob's public key.
2. Encrypts the message using Bob's public key.
3. Sends the ciphertext to Bob.
Bob recovers the message using his private key.
Anyone knowing Bob's public key can encrypt messages for him; only Bob can decrypt them.
Analogy: Bob's public key is like an unlocked padlock he gives out; his private key is the key to that padlock.
Process:
1. Bob creates a public/private key pair.
2. Alice gets Bob's public key.
3. Alice encrypts her message using Bob's public key.
4. Alice sends the ciphertext to Bob.
5. Bob decrypts the ciphertext using his private key.
Notation:
- Encryption: $C = E(P, KR_{pub})$
- Decryption: $P = D(C, KR_{priv})$
- $KR_{pub}$ (Recipient's public key) used for encryption
- $KR_{priv}$ (Recipient's private key) used for decryption

Reporting vulnerabilities or communicating with news reporters where confidentiality is needed but a shared secret key for symmetric encryption is unavailable.
Organizations provide a public key for asymmetric encryption.

Relies on the difficulty of discrete logarithms.
Designed for encryption, not key agreement, unlike Diffie-Hellman.
Ciphertext is twice the length of the plaintext.
Ciphertext is randomized.
- multiple encryptions produce different ciphertexts.
System parameters $p$ and $g$ (same as Diffie-Hellman).
Alice:
1. Picks random integer $a$ as private key
2. Publishes public key: $K<em>{A</em>{Pub}} = g^a mod p$
Bob (to encrypt message $m$ ):
1. Encodes $m$ as a number
2. Picks random integer $r$ and computes: $g^r mod p$ , $(K<em>{A</em>{Pub}})^r = g^{ar} mod p$ , and $m \times g^{ar} mod p$
3. Sends ciphertext $(g^r mod p, m \times g^{ar} mod p)$
Alice (to recover message):
1. Computes shared secret: $(g^r)^a = g^{ar} mod p$
2. Recovers $m = (m \times g^{ar} mod p) / (g^{ar} mod p)$

Based on the difficulty of factoring large integers using modular arithmetic.
Used for encryption (confidentiality) and digital signatures (integrity, authentication).
Breaking RSA is as hard as factoring the modulus.
Key Generation:
- Choose two large primes $p$ and $q$ .
- Calculate $n = pq$ .
- Choose public exponent $e$ (where e > 1 and $(p-1)(q-1)$ have no common factors).
- Calculate private exponent $d$ using secret knowledge of $p$ and $q$ .
- Public key is $(n, e)$ . Private key is $d$ .
Encryption:
1. Encode plaintext as integers: $1 \leq m \leq n$
2. Encrypt: $c = m^e mod n$
Decryption: $m = c^d mod n$
Key sizes: 1024, 2048, 4096 bits.

Uses algebraic group defined on points on an elliptic curve.
Based on Elliptic Curve Discrete Logarithm Problem.
Smaller key size and ciphertext size compared to RSA for the same security level.
AES Key Size (Symmetric key) | RSA Key Size | Elliptic curve Key Size
- <80 | 1024 | 160-223
- 128 | 3072 | 256-383
- 192 | 7680 | 384-511
- 256 | 15360 | 512+

Asymmetric ciphers simplify key distribution.
Combination:
1. Asymmetric cipher encrypts a short message.
  - A randomly chosen shared secret key for a symmetric cipher.
2. Symmetric cipher encrypts the bulk data with that key.