Cryptography Fundamentals: Encryption, Authentication, PKI

Cryptography Fundamentals

Alice wants to send a message m to Bob.
Eve is an adversary who may try to eavesdrop or modify the message.
The goal of cryptography is to ensure that Eve cannot read or alter the message without authorization.

Encryption is used to prevent Eve from reading the message.
Key Concepts:
- Secret Key (Ke): A shared key between Alice and Bob. The longer the key, the higher the security.
- Plaintext (m): The original message.
- Ciphertext (c): The encrypted message, which is the result of applying the encryption function.
- Encryption Function (E(Ke, m)): Transforms the plaintext into ciphertext using the secret key.
- Decryption Function (D(Ke, c)): Reverses the encryption to recover the plaintext using the secret key.
Kerckhoffs’ Principle: Kerckhoffs’ Principle states that the security of a cryptographic system should depend only on the secrecy of the key, not on the secrecy of the algorithm. This is important because it allows cryptographic algorithms to be publicly analyzed for weaknesses, ensuring they are robust and secure. It also makes systems easier to implement and maintain, as the algorithm can be openly shared without compromising security.

Authentication ensures that Eve cannot modify the message without detection.
Key Concepts:
- Authentication Key (Ka): A shared key used for authentication.
- Message Authentication Code (MAC): A short piece of information used to authenticate a message.
- MAC Function (h(Ka, m)): A Message Authentication Code (MAC) is a short piece of information (a “tag”) used to verify the integrity and authenticity of a message. It ensures that the message has not been altered during transmission and that it comes from a legitimate sender.
- Verification: Bob checks if the received MAC matches the computed MAC using the same key.
Replay Attacks: Eve can copy valid messages and replay them. To prevent this, a numbering scheme is used to sequence messages. Bob discards messages with previously accepted sequence numbers.

Public Key Encryption (also known as Asymmetric Encryption) uses a pair of keys: a public key and a private key.
Key Concepts:
- Public Key (Pbob): Used for encryption. Can be shared publicly.
- Private Key (Sbob): Used for decryption. Must be kept secret.
- Encryption: Alice encrypts the message using Bob’s public key: E(Pbob, m).
- Decryption: Bob decrypts the message using his private key: D(Sbob, c).
- Key Exchange: In a group of N people, the number of key exchanges required is N(N-1)/2.
Performance: Public key encryption is slower than symmetric encryption, so it is often used to establish a secret key, which is then used for symmetric encryption.
Public key encryption uses two keys: a public key for encryption and a private key for decryption. The public key can be shared openly, while the private key is kept secret. This allows secure communication between multiple parties without needing to share a secret key in advance. In contrast, symmetric encryption uses a single shared key for both encryption and decryption, which must be securely exchanged between the communicating parties. Symmetric encryption is faster but less scalable for large groups, as each pair of users needs a unique shared key.

Digital Signatures are used to verify the authenticity and integrity of a message.
Key Concepts:
- Key Pair: Alice generates a key pair (SAlice, PAlice).
- Signature: Alice computes a signature s using her private key and sends it along with the message m.
- Verification: Bob uses Alice’s public key and a verification algorithm ν to check the validity of the signature.

PKI is a system for managing public keys and digital certificates.
Key Concepts:
- Certificate Authority (CA): A Certificate Authority (CA) is a trusted entity in Public Key Infrastructure (PKI) that issues digital certificates. These certificates bind a public key to the identity of the key owner (e.g., a person or organization). The CA signs the certificate with its private key, allowing others to verify the certificate’s authenticity using the CA’s public key. This establishes trust in the shared public keys, ensuring secure communication over untrusted networks like the internet.
- X.509 Certificate: Contains the public key, expiration date, and other information, signed by the CA.
- Validation: Alice can verify Bob’s public key using the CA’s public key.
PKI Issues:
- Single Point of Failure: If the CA’s private key is compromised, the entire system is at risk.
- Trust: There must be trust in the CA.

Ciphertext-Only Attack: The attacker knows only the ciphertext and tries to decrypt it.
Known-Plaintext Attack: The attacker knows both the plaintext and the ciphertext and tries to find the encryption key.
Chosen-Plaintext Attack: The attacker can choose plaintexts and obtain the corresponding ciphertexts to recover the key.
Distinguishing Attack: The attacker tries to distinguish between the ideal encryption scheme and the actual one.

Birthday Attack:
- Based on the Birthday Paradox, which states that in a group of 23 people, there is a 50% chance that two people share the same birthday.
- In cryptography, the birthday bound is used to estimate the likelihood of collisions in hash functions.
- Formula: For a hash function with N possible outputs, the number of inputs required to find a collision with 50% probability is approximately √N.
- For an n-bit hash function, the number of inputs required is 2^(n/2).
Meet-in-the-Middle Attack:
- The attacker builds a table of size 2^(n/2) and tries to find a match between two sets of values.
- Formula: If there are N possible values, a collision is expected when PQ/N ≈ 1, where P and Q are the sizes of the two sets.

Security Level refers to the amount of work required to break a cryptographic system.
Exhaustive Search: If a system uses a 256-bit key, it would take 2^256 steps to break it using brute force.
Modern Security Requirement: A secure system should provide at least 128-bit security, which means it should take 2^128 steps to break the system.