Cryptography
Open in the Padhaiko app2.1 Cryptography, its importance, plain text and cipher text
Cryptography provides the mathematical foundation for securing data both in transit (over untrusted networks) and at rest (on disks and cloud storage).
Core Cryptographic Terminology
- Plaintext ( or ): The original, human- or machine-readable message or data before encryption.
- Ciphertext (): The scrambled, unintelligible output produced after applying an encryption algorithm and key to the plaintext.
- Encryption (): The mathematical process of transforming plaintext into ciphertext using an algorithm and a key : .
- Decryption (): The reverse process of recovering plaintext from ciphertext using the corresponding decryption key: .
- Cryptography: The science and practice of designing secure communication schemes (ciphers, hashes, signatures) to protect data against adversaries.
- Cryptanalysis: The study of analyzing and breaking cryptographic schemes to recover plaintext or keys without authorized access.
- Cryptology: The combined discipline encompassing both cryptography and cryptanalysis.
Importance of Cryptography
- Confidentiality: Ensures eavesdroppers intercepting packets cannot read sensitive payloads.
- Data Integrity: Cryptographic hashes and MACs detect even a single-bit alteration in transit or storage.
- Authentication: Proves the identity of communicating hosts, servers, and message senders.
- Non-Repudiation: Digital signatures cryptographically bind a sender to a message so the sender cannot later deny authoring it.
2.2 Type of ciphers: Symmetric and Asymmetric ciphers, Block and Stream ciphers
Cryptographic ciphers are classified along two major dimensions: key relationship (symmetric vs. asymmetric) and data processing unit (block vs. stream).
1. Symmetric vs. Asymmetric Ciphers
| Aspect | Symmetric Key Cryptography | Asymmetric (Public-Key) Cryptography |
|---|---|---|
| Keys Used | Single shared secret key for both encryption and decryption | Key pair: a public key (shared openly) and a private key (kept secret) |
| Key Distribution | Difficult; requires a secure out-of-band channel or key-exchange protocol | Easier; public keys can be distributed openly (authenticated via PKI) |
| Key Scaling ( users) | Requires pairwise secret keys | Requires only keys ( key pairs) |
| Speed & Overhead | Very fast (– faster); suitable for bulk data | Slow (heavy modular/elliptic arithmetic); used for key exchange and signatures |
| Security Services | Confidentiality, integrity (via MAC) | Confidentiality, key exchange, authentication, non-repudiation (signatures) |
| Representative Algorithms | AES, DES, 3DES, ChaCha20, RC4 | RSA, ECC, Diffie–Hellman, ElGamal, EdDSA |
In practice, protocols like TLS use hybrid cryptography: asymmetric crypto establishes identity and exchanges a session key, and symmetric crypto (e.g., AES-GCM or ChaCha20) encrypts the bulk data stream.
2. Block Ciphers vs. Stream Ciphers
| Aspect | Block Cipher | Stream Cipher |
|---|---|---|
| Processing Unit | Encrypts fixed-size blocks (e.g., bits in DES, bits in AES) at a time | Encrypts bit or byte at a time by XORing plaintext with a pseudorandom keystream |
| Padding | Requires padding (e.g., PKCS#7) if plaintext is not a multiple of block size | No padding required; ciphertext length equals plaintext length |
| Diffusion & Confusion | High diffusion across bits within each block via multiple rounds | Relies on keystream unpredictability; changing plaintext bit flips only ciphertext bit |
| Modes of Operation | ECB, CBC, CFB, OFB, CTR, GCM | Keystream XOR: (must never reuse a key/nonce pair) |
| Examples | DES, 3DES, AES, Blowfish | RC4 (legacy/broken), ChaCha20, A5/1, Salsa20 |
2.3 Traditional ciphers: Substitution (Mono-alphabetic, Polyalphabetic) and Transposition ciphers
Classical ciphers illustrate Claude Shannon's two foundational design principles: confusion (obscuring the relationship between key and ciphertext, typically via substitution) and diffusion (spreading plaintext statistics across the ciphertext, typically via transposition).
1. Substitution Ciphers
Each plaintext symbol or group is replaced by another symbol according to a key.
- Mono-alphabetic Substitution: A single fixed mapping is used across the entire message.
- Caesar Cipher: Shifts every letter () by a fixed key :
- Weakness: Only non-trivial keys exist (trivial brute force), and general mono-alphabetic ciphers ( keys) preserve letter frequencies (
E,T,A,O,I,N), falling quickly to frequency analysis. - Polyalphabetic Substitution: Uses multiple substitution alphabets across positions to flatten letter frequency distributions.
- Vigenère Cipher: Uses a repeating keyword of length :
- Because the same plaintext letter maps to different ciphertext letters depending on position, single-letter frequency analysis fails (though Kasiski examination and Index of Coincidence can reveal key length ).
2. Transposition Ciphers
Transposition rearranges the positions of plaintext characters without altering the characters themselves (pure diffusion):
- Rail Fence Cipher: Writes plaintext diagonally across "rails" and reads off row by row.
- Columnar Transposition Cipher: Writes plaintext row-by-row into a grid of width (key length), permutes the columns according to alphabetical order of a keyword, and reads out column-by-column.
| Aspect | Substitution Cipher | Transposition Cipher |
|---|---|---|
| Transformation | Replaces characters with other characters; positions stay fixed | Keeps original characters; permutes their positions |
| Shannon Principle | Primarily Confusion | Primarily Diffusion |
| Frequency Profile | Changes letter counts (mono-alphabetic shifts/permutes frequencies; polyalphabetic flattens them) | Exact plaintext letter frequencies remain unchanged |
Vigenère Encryption and Decryption
Encrypt the plaintext SECURE using the Vigenère cipher with keyword KEY (mapping ), and verify decryption of the first two letters.
Convert plaintext and repeating key to numeric indices ():
- Plaintext
SECURE: . - Keyword
KEYrepeated to length (KEYKEY): .
Apply for each letter:
Thus the ciphertext is CIAEVC.
Verify decryption on the first two characters using :
Ciphertext: CIAEVC.
2.4 Symmetric Block Ciphers: DES, AES
1. Data Encryption Standard (DES)
Adopted in 1977, DES is a classic Feistel block cipher:
- Block & Key Size: -bit plaintext block, -bit input key of which bits are parity bits, leaving an effective key length of bits.
- Structure: Initial Permutation (), Feistel rounds, and Final Permutation ().
- Single Feistel Round: Splits the -bit block into -bit halves :
where the round function applies: (1) Expansion ( bits), (2) XOR with -bit subkey , (3) eight -bit S-boxes (non-linear substitution for confusion), and (4) -bit Permutation (diffusion).
- Obsolescence & 3DES: With only possible keys, single DES is vulnerable to brute-force search. Triple DES (3DES) applies Encrypt–Decrypt–Encrypt () to raise effective security to bits (2-key) or bits (3-key), though it is slow and deprecated in favor of AES.
2. Advanced Encryption Standard (AES)
Standardized by NIST in 2001 (Rijndael), AES is a non-Feistel Substitution–Permutation Network (SPN) operating on a -bit block arranged as a matrix of bytes (the state).
- Key Sizes & Rounds:
- AES-128: rounds
- AES-192: rounds
- AES-256: rounds
- Four Round Transformations (after initial
AddRoundKey):- SubBytes: Byte-by-byte non-linear substitution using an invertible -bit S-box in (confusion).
- ShiftRows: Cyclically shifts rows of the state left by bytes respectively (inter-column diffusion).
- MixColumns: Multiplies each column over by a fixed MDS matrix so each output byte depends on all four bytes in that column (omitted in the final round).
- AddRoundKey: Bitwise XOR of the -bit state with the round subkey derived by the AES key schedule.
| Aspect | DES | AES |
|---|---|---|
| Architecture | Feistel Network (encrypts half-block per round) | Substitution–Permutation Network (transforms entire state) |
| Block Size | bits | bits |
| Key Size | bits (effective) | , , or bits |
| Rounds | , , or (by key size) | |
| Security Status | Broken (brute-forced easily) | Current global standard (quantum-resistant at 256-bit against Grover's) |
2.5 Asymmetric ciphers: RSA, ECC
1. RSA (Rivest–Shamir–Adleman)
RSA relies on the computational intractability of factoring the product of two large primes.
RSA Key Generation, Encryption, and Decryption
- Key Generation:
- Choose two distinct large primes and .
- Compute modulus and Euler's totient .
- Choose public exponent such that and .
- Compute private exponent such that (via the Extended Euclidean Algorithm).
- Public Key: . Private Key: (keep secret).
- Encryption (for message ):
- Decryption:
In production, textbook RSA must always be paired with randomized padding (OAEP for encryption, PSS for signatures) to prevent deterministic ciphertext attacks and small-message attacks.
2. Elliptic Curve Cryptography (ECC)
ECC performs public-key operations over the algebraic structure of an elliptic curve over a finite field :
- Point Arithmetic & Scalar Multiplication: Given a public base generator point on the curve and a secret integer , computing is fast via double-and-add.
- Hard Problem (ECDLP): Given and , recovering the scalar (Elliptic Curve Discrete Logarithm Problem) has no known sub-exponential classical algorithm.
- Efficiency: A -bit ECC key provides roughly the same -bit security level as a -bit RSA key, drastically reducing bandwidth, certificate size, and mobile battery consumption (used in TLS 1.3 ECDHE, ECDSA, and Ed25519).
| Aspect | RSA | ECC |
|---|---|---|
| Hard Mathematical Problem | Integer Factorization Problem (IFP) | Elliptic Curve Discrete Logarithm Problem (ECDLP) |
| Key Size for 128-bit Security | bits | bits |
| Speed & Bandwidth | Fast signature verification; slower keygen and larger keys | Much faster key generation/signing and tiny keys/certificates |
| Primary Protocols | Legacy TLS key transport, SSH, X.509 CAs, digital signatures | TLS 1.3 (ECDHE/ECDSA), mobile/IoT security, Signal, cryptocurrencies |
RSA Key Generation, Encryption, and Decryption
In an RSA system, choose primes and , and public exponent . (a) Compute , , and the private key . (b) Encrypt the plaintext and decrypt the resulting ciphertext to recover .
Compute modulus and Euler's totient :
Since , is a valid public exponent.
Find private exponent satisfying :
Public key is and private key is .
Encrypt using square-and-multiply:
Compute powers of :
Since :
Decrypt to verify :
Compute powers of :
Since :
First , and , so:
(a) , , . (b) Ciphertext ; decrypting yields .
2.6 Message digest, Hash functions (MD5, SHA)
A cryptographic hash function maps an arbitrary-length input message to a fixed-length message digest .
Three Required Security Properties of Hash Functions
- Preimage Resistance (One-Wayness): Given a digest , it is computationally infeasible to find any message such that .
- Second-Preimage Resistance (Weak Collision Resistance): Given a specific message , it is computationally infeasible to find a different message with .
- Collision Resistance (Strong Collision Resistance): It is computationally infeasible to find any two distinct messages such that .
Additionally, good hashes exhibit a strong avalanche effect: flipping a single input bit changes roughly of the output digest bits unpredictably. By the birthday paradox, finding a collision on an -bit hash takes evaluations, which is why modern hashes require at least -bit outputs ( collision resistance).
MD5 and SHA Families
- MD5 (Message Digest 5): Produces a -bit digest ( hex characters) from -bit blocks across rounds. Practical chosen-prefix collisions can now be generated in seconds; MD5 must never be used for passwords, certificates, or integrity verification.
- SHA-1: Produces a -bit digest; broken by the 2017 SHAttered collision attack and deprecated across TLS/PKI.
- SHA-2 (SHA-256, SHA-384, SHA-512): Merkle–Damgård construction using rounds (SHA-256) or rounds (SHA-512). SHA-256 (-bit digest) is the industry workhorse for TLS, code signing, and blockchain.
- SHA-3 (Keccak): Uses a sponge construction structurally independent from SHA-2, providing an algorithmic backup at and bits.
| Algorithm | Digest Size | Block Size | Collision Resistance (Ideal) | Current Status |
|---|---|---|---|---|
| MD5 | bits | bits | (broken in practice) | Broken / Do not use |
| SHA-1 | bits | bits | (broken in practice) | Deprecated |
| SHA-256 (SHA-2) | bits | bits | Recommended standard | |
| SHA-512 (SHA-2) | bits | bits | Recommended standard | |
| SHA3-256 (SHA-3) | bits | -bit rate | Recommended standard |
2.7 Message authentication, Digital Signatures and Certificates
Sending an unkeyed hash alongside does not protect against an active attacker, because the attacker can modify to and simply recompute . Protecting both integrity and origin requires a secret key.
1. Message Authentication Codes (MAC & HMAC)
A MAC produces a short authentication tag using a shared secret key and message : . The receiver recomputes and verifies equality.
HMAC builds a provably secure MAC from any cryptographic hash function (e.g., HMAC-SHA256):
where is the block-padded key, repeated, and repeated. Because both sender and receiver share the same , a MAC provides integrity and authentication, but not non-repudiation (either party could have generated the tag).
2. Digital Signatures
A digital signature uses asymmetric cryptography to achieve integrity, origin authentication, and non-repudiation:
- Signing (Sender): Compute digest , then sign with the sender's private key:
Send to the receiver.
- Verification (Receiver): Independently compute and verify using the sender's public key . If valid, only the holder of could have produced for that exact message , preventing repudiation.
3. Digital Certificates (X.509)
A public key alone does not prove who owns it—an attacker in a Man-in-the-Middle position could substitute their own public key. An X.509 Digital Certificate binds a subject's identity (e.g., bank.example.com) to its public key, digitally signed by a trusted Certificate Authority (CA).
Key X.509 certificate fields include:
- Version (v3), Serial Number (unique per CA), and Signature Algorithm (e.g.,
sha256WithRSAEncryptionorecdsa-with-SHA256) - Issuer (CA distinguished name) and Validity Period (
Not Before/Not After) - Subject (owner identity / SAN domain names) and Subject Public Key Info (algorithm + public key)
- Extensions (Key Usage, Extended Key Usage, Subject Alternative Name, Basic Constraints
CA:TRUE/FALSE) - CA Digital Signature over all fields above.
2.8 Public Key Infrastructure (PKI) and its importance
Public Key Infrastructure (PKI) is the ecosystem of hardware, software, policies, roles, and procedures needed to create, manage, distribute, use, store, and revoke digital certificates.
Core PKI Components
- Certificate Authority (CA): The trusted third party that issues, signs, and revokes digital certificates. Production PKI uses an offline Root CA signing online Intermediate CAs so a compromised intermediate never compromises the root trust anchor.
- Registration Authority (RA): Verifies the identity of certificate applicants (e.g., domain validation, organization validation) before forwarding approved requests to the CA.
- Certificate Repository: Publicly accessible storage (LDAP/HTTP) for certificates and revocation data.
- Revocation Mechanisms:
- CRL (Certificate Revocation List): Periodically published signed list of revoked certificate serial numbers.
- OCSP (Online Certificate Status Protocol): Real-time query–response protocol asking an OCSP responder whether a certificate is
good,revoked, orunknown(often optimized via OCSP Stapling in TLS).
How PKI and Digital Signatures Defeat a MITM Attack (Exam Model)
Explain step by step how a web browser uses PKI and X.509 digital certificates to detect an attacker who intercepts a TLS connection and injects a forged server public key.
Present the certificate chain during the TLS handshake: When the browser connects to portal.edu.np, the server (or attacker) sends its leaf X.509 certificate (plus any intermediate CA certificates) claiming the domain name and containing a public key.
Verify the signature chain up to a pre-installed Root CA: The browser hashes the certificate's body and verifies the CA's signature using the parent CA's public key, walking up to an implicitly trusted Root CA stored in the OS/browser trust store. Because the attacker lacks the trusted CA's private key, a forged certificate fails signature verification (or chains to an untrusted self-signed root).
Check identity, validity, and revocation status: The browser verifies that portal.edu.np matches the certificate's Subject Alternative Name (SAN), that the current date lies within Not Before–Not After, and that the certificate is not revoked (via OCSP or CRL). Finally, the server proves possession of the corresponding private key by signing the TLS handshake transcript.
An attacker cannot obtain a valid CA-signed certificate for portal.edu.np without passing RA verification or possessing a trusted CA's private key; thus the browser aborts the connection on signature, SAN, or revocation check failure.
Exercises
Using RSA with , , and , find , , and the private exponent . Encrypt the plaintext and show decryption back to .
Compute , , and :
Check . Solve : , so .
Encrypt :
Compute powers of : , , , . Since :
Decrypt :
Compute powers of : , , , , . Since :
, , ; ; decryption recovers .
Encrypt the word NET () using (a) a Caesar cipher with key , and (b) a Vigenère cipher with key BTB ().
Part (a) — Caesar cipher ():
Ciphertext is QHW.
Part (b) — Vigenère cipher (BTB ):
Ciphertext is OXU.
(a) QHW (b) OXU.
Compare symmetric and asymmetric cryptography on key management, computational speed, and supported security services, and explain why TLS uses a hybrid approach.
Compare symmetric and asymmetric schemes:
- Key management: Symmetric cryptography requires a shared secret key exchanged safely beforehand ( keys for parties), whereas asymmetric cryptography uses a public/private key pair ( keys) where the public key is shared openly.
- Speed: Symmetric ciphers (AES, ChaCha20) execute using fast bitwise/substitution operations in hardware; asymmetric algorithms (RSA, ECC) perform modular exponentiation or elliptic curve scalar multiplication and are orders of magnitude slower.
- Services: Both provide confidentiality; however, symmetric MACs cannot provide third-party non-repudiation because both parties hold the same secret key, whereas asymmetric digital signatures can.
Explain hybrid cryptography in TLS: TLS uses asymmetric cryptography during the handshake to authenticate the server (via X.509 certificates) and agree on a fresh ephemeral symmetric session key (via ECDHE), then switches to fast symmetric authenticated encryption (AES-GCM or ChaCha20-Poly1305) for all application data.
Symmetric crypto is fast with harder key distribution and no non-repudiation; asymmetric crypto solves key exchange and non-repudiation but is slow. Hybrid schemes (like TLS) combine asymmetric key exchange/authentication with symmetric bulk encryption.
Describe the internal structure of a single AES round (for AES-128) and explain how it differs from the Feistel structure of DES.
Outline the four AES round operations on the byte state:
- SubBytes: Non-linear byte substitution via an -bit S-box over (confusion).
- ShiftRows: Cyclic left shifts of rows by bytes (diffusion across columns).
- MixColumns: Linear matrix multiplication of each column over (omitted in round ).
- AddRoundKey: Bitwise XOR of the -bit state with the round subkey.
Contrast with DES's Feistel network: DES operates on -bit blocks split into two -bit halves, transforming only one half per round via and swapping halves over rounds—so encryption and decryption use identical round logic in reverse subkey order. AES is a non-Feistel Substitution–Permutation Network (SPN) that transforms the entire -bit state in every round ( rounds) and requires inverse transformations (InvShiftRows, InvSubBytes, InvMixColumns) for decryption.
Each AES round applies SubBytes, ShiftRows, MixColumns (skipped in the final round), and AddRoundKey to the full -bit SPN state, unlike DES's -bit Feistel half-block swap across rounds with a -bit effective key.
Distinguish between a cryptographic hash, an HMAC, and a digital signature. Which security properties does each guarantee, and what role do CRL and OCSP play in PKI?
Compare Hash, HMAC, and Digital Signature:
- Cryptographic Hash (): Unkeyed fixed-size digest; detects accidental corruption but not an active attacker (who can alter and recompute ).
- HMAC (): Keyed hash using a shared secret ; guarantees integrity and data origin authentication between key holders, but not non-repudiation.
- Digital Signature (): Asymmetric signature verified by anyone holding ; guarantees integrity, authentication, and non-repudiation.
Explain CRL and OCSP in PKI: Because private keys can be compromised before certificate expiration, PKI must revoke invalid certificates early. A CRL is a periodically published CA-signed list of revoked serial numbers, while OCSP lets clients query certificate status (good/revoked) in real time (with OCSP Stapling avoiding extra round trips and privacy leaks).
Hashes give unkeyed digests, HMACs add shared-key integrity/authentication, and digital signatures add public-key non-repudiation; CRL and OCSP allow PKI relying parties to reject certificates revoked prior to expiry.