Comprehensive Study Notes on Cryptography and Cryptographic Primitives

Cryptographic Primitives

Definition and Etymology of Cryptography
- Cryptography is a method of protecting information and communications through the use of codes, ensuring that only intended recipients can read and process the contents.
- Etymological breakdown:
- Prefix "crypt-" means "hidden" or "vault".
- Suffix "-graphy" stands for "writing".
Historical Evolution of Cryptography
- Ancient Egyptian Hieroglyphs:
- Used as an early form of written secrecy accessible only to divine authorities, such as royalty and priests.
- The term "hieroglyphs" derives from Greek, translating directly to "holy writing".

Mesopotamian Clay Tablets:
- Dated around 1500 BC, clay tablets were encrypted to protect valuable commercial recipes, such as a craftsman's recipe for pottery glaze.
Hebrew Atbash Cipher:
- Developed around 600 BC to 500 BC by Hebrew scholars.
- It is a monoalphabetic substitution cipher where the alphabet is reversed: letter "A" becomes "Z", "B" becomes "Y", and so forth.
Ancient Greek Scytale:
- The term scytale (rhymes with "Italy") derives from the Greek word σκυτάλη, meaning "baton".
- Functioned as a transposition cipher tool used by ancient Greeks, specifically Spartans during military campaigns.
- Mechanics: A strip of parchment or leather is wound around a cylinder of specific diameter. The message is written across the wound strap so that consecutive letters land on consecutive windings.
- Security Properties: Fast to execute and resistant to writing errors. However, it is easily broken, as the physical presence of the leather strip strongly suggests the encryption technique.

Julius Caesar Cipher:
- Created by Julius Caesar to communicate securely with Cicero in Rome while conquering Europe.
- Mechanics: A monoalphabetic substitution cipher where each character in the message is shifted 3 steps to the right in the alphabet, looping back to the beginning upon reaching the end.
- Example:
  - Plaintext: Gaul is a whole divided into three parts
  - Original Alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ
  - Shifted Alphabet (3 steps): DEFGHIJKLMNOPQRSTUVWXYZABC
  - Ciphertext Output: Jdxo lv d zkroh glylghg lqwr wkuhh sduwv
- Vulnerability: Weak against frequency analysis of letters in a given language.
Vigenère Cipher:
- Designed in the 16th century by French cryptographer Blaise de Vigenère.
- Introduced the concept of an encryption key repeated across the message length, producing ciphertext by adding message characters to key characters modulo 26:

$\text{Ciphertext}_i = (\text{Plaintext}_i + \text{Key}_i) \pmod{26}$

* Shifted the foundation of cryptographic security: security relies on the secrecy of the key rather than the secrecy of the system itself.

World War Cryptography & Modern Computing:
- Military conflict established cryptography as a key strategic discipline.
- Notable instance: German Enigma machine (model "Enigma I"), broken secretly by Alan Turing, recognized as the father of computer science.

Military Enigma machine, model "Enigma I"

Mathematical Cryptography Foundations:
- Claude E. Shannon is regarded as the father of mathematical cryptography.
- Authored the paper "A mathematical theory of cryptography" in 1945 during his tenure at Bell Labs, which was later published in the Bell System Technical Journal in 1949.
Public Domain and Government Policy:
- Historic government controls restricted software usage, export, and public dissemination of mathematical concepts.
- The proliferation of the internet made cryptosystems and underlying mathematical principles globally accessible in the public domain.
- Five Primary Functions of Cryptography
Privacy / Confidentiality: Assures that information cannot be understood by unauthorized recipients.
Authentication: Enables senders and receivers to confirm each other's identity and the origin/destination of data.
Integrity: Guarantees that the message has not been modified or altered in transit.
Non-repudiation: Prevents the creator/sender of information from denying their intention or participation in creating/transmitting the data.
Key Exchange: Provides the mechanism by which cryptographic keys are safely shared between entities.
Cryptosystems Scope: Includes mathematical algorithms, computer code, and human procedural rules (e.g., password creation standards, system sign-off procedures, avoiding discussion of operational protocols with outsiders).
- Basic Cryptographic Terminology & Process
Plaintext: Unencrypted data in readable format.
Ciphertext: Encrypted data in non-readable format.
Encryption: Conversion of plaintext to ciphertext.
Decryption: Conversion of ciphertext back to plaintext.

Three Common Types of Cryptographic Primitives

Three common types of cryptographic algorithms

Secret Key Cryptography (SKC):
- Also known as Symmetric Encryption.
- Employs a single secret key for both encryption and decryption.
- Primary Application: Privacy and confidentiality.
- Computation Speed: Evaluated as roughly 1000 times faster than public key cryptography.
Public Key Cryptography (PKC):
- Also known as Asymmetric Encryption.
- Employs a key pair: one key for encryption (public key) and another for decryption (private key).
- Primary Application: Authentication, non-repudiation, and key exchange.
Hash Functions:
- One-way cryptographic transformations that convert input data into a fixed-size value (digital fingerprint).
- Keyless operation; plaintext cannot be recovered from ciphertext/hash.
- Primary Application: Data integrity verification.
- The Kerckhoffs's Principle
Formulated in the 19th century by Netherlands-born cryptographer Auguste Kerckhoffs.
Principle Statement: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.
Rationale: Publicly exposed algorithms undergo rigorous scrutiny by cryptanalysts to find and patch vulnerabilities, making them stronger over time. In contrast, security through obscurity ("hidden algorithms") risks catastrophic failure once an adversary discovers and exploits untested structural flaws.

Security Definitions and Attacks on Cryptographic Primitives

Cryptanalysis
- Etymology: From Greek kryptós ("hidden") and analúein ("to loosen" or "to untie").
- Definition: The study and art of obtaining the plain text meaning or secret key of encrypted information without having prior access to the key.
- Key Metrics Determining Attack Success:
- Time: Number of computational steps (such as test encryptions) required.
- Memory: Volume of storage required to execute the attack.
- Data: Quantity and specific types of plaintexts and ciphertexts required.
Classification of Attack Levels by Available Information
- Systems providing fewer pieces of information to adversaries yield stronger security defenses:

Information Available	Attack Characteristic
Ciphertext Only	The attacker possesses only the ciphertext. Represents the strongest defensive posture for a cryptosystem, as it is the most difficult to crack.
Known Plaintext	The attacker possesses matching pairs of plaintext and resulting ciphertext. Allows conclusions to be drawn regarding the key structure and validates key candidates.
Chosen Plaintext	The attacker can choose arbitrary plaintexts to be encrypted and inspect the output ciphertexts (e.g., when an unattended workstation is accessed). Helps reveal structural key details.
Iterative Chosen Plaintext	Also called Batch Chosen-Plaintext Attack. The attacker submits multiple messages simultaneously and analyzes the resulting ciphertexts. In an Adaptive Chosen-Plaintext Attack, iterative feedback is used to adaptively alter subsequent chosen plaintexts based on earlier results.
Chosen Ciphertext	Represents the weakest defensive condition. The attacker selects arbitrary ciphertexts and passes them through the target decryption algorithm to observe the output plaintext, facilitating rapid key extraction.

General Cryptographic Attack Methods
- Brute Force Attack: Iterates through every possible key combination. Takes the longest time, but is guaranteed to succeed given sufficient time. All cryptosystems with finite key spaces are subject to brute force attacks.
- Dictionary Attack: Utilizes lists of known words, phrases, and common structural variations.
- Weak Key Attack: Exploits key values that cause an encryption algorithm to perform poorly or produce predictable patterns.
- Mathematical Attack: Focuses on algorithms utilizing small key lengths or small data sets (e.g., 40-bit key schemes are weak, whereas 128-bit key schemes are strong). Longer keys exponentially increase the combinations required for brute force iteration.
- Meet-in-the-Middle Attack: Demonstrates that Double-DES provides only marginal security improvements over standard DES. Plaintext is encrypted forward with all possible keys, and ciphertext is decrypted backward with all possible keys, comparing intermediate values to isolate the secret key.
- Birthday Attack: Targets hash functions by exploiting the mathematical birthday paradox. Demonstrates that in a room of 23 people, there is a greater than $50\%$ probability that two individuals share a birthday (whereas matching a specific selected day requires 253 people). Attacker searches for hash collisions between different plaintexts.
- Analytic Attack: Employs algebraic manipulations to reduce the structural complexity of the target algorithm.
- Implementation Attack: Exploits flaws in the physical or logical implementation (software bugs, side channels, or protocol flaws) rather than the underlying mathematics.
- Statistical Attack: Capitalizes on statistical anomalies, such as non-random random number generators (RNG) or floating-point errors.
Examples of Strong Cryptography Standards
- Triple DES (3DES):
- Developed to replace standard Data Encryption Standard (DES).
- Employs 3 distinct 56-bit keys, giving a raw key length of 168 bits, with an effective key strength evaluated at 112 bits.
- Widely used in financial service hardware encryption.
- RSA:
- Standard asymmetric public-key encryption algorithm used for securing internet traffic.
- Uses public keys for encryption and private keys for decryption.
- Output appears as meaningless random data requiring immense processing power to factorize or break.
- Blowfish:
- Symmetric block cipher created by Bruce Schneier as a DES replacement.
- Operates on 64-bit blocks with variable key lengths ranging from 32 bits up to 448 bits.
- Unpatented, royalty-free, and open domain; frequently used in e-commerce payment modules and password managers.
- Twofish:
- Successor to Blowfish, also created by Bruce Schneier.
- Uses 128-bit blocks and keys up to 256 bits in length.
- Symmetric algorithm optimized for high speed across hardware and software platforms; used in open-source applications such as PhotoEncrypt, GPG, and TrueCrypt.
- Advanced Encryption Standard (AES):
- Official U.S. Government standard standard since 2002.
- Symmetric block cipher using a fixed 128-bit block size and key lengths of 128, 192, or 256 bits.
- Considered impervious to all attacks except exhaustive brute force across the key space.

Symmetric Key Cryptography

Core Concept of Symmetric Encryption
- Employs a single secret key for both encryption and decryption.
- Requires secure out-of-band key distribution prior to message transmission.
- Secret keys can be passwords or random strings generated by standard Random Number Generators (RNGs). Banking-grade security requires RNGs certified under standards such as FIPS 140-2.

Operational Steps in Symmetric Key Exchange:
1. Sender and receiver exchange and share the secret key via secure external means.
2. Senders encrypt plaintext with their copy of the secret key.
3. Ciphertext is transmitted over the unsecured communication channel.
4. Receivers decrypt ciphertext using their matching copy of the secret key.
5. Plaintext is successfully restored to readable format.
Symmetric Algorithm Paradigms: Block Ciphers vs. Stream Ciphers

Feature	Block Cipher	Stream Cipher
Definition	Converts plaintext by processing fixed-size blocks at a time.	Converts plaintext by processing continuous single bits or bytes (1 byte at a time).
Bits Converted	Converts blocks of 64 bits or more simultaneously.	Converts at most 8 bits (1 byte) at a time.
Design Principle	Employs both Confusion and Diffusion principles.	Employs only the Confusion principle.
Algorithm Modes	Electronic Code Book (ECB), Cipher Block Chaining (CBC).	Cipher Feedback (CFB), Output Feedback (OFB).
Decryption Complexity	Complex decryption due to multi-bit dependencies.	Simple decryption, typically using bitwise XOR operations.
Memory Usage	Holds data in memory buffer until full block is assembled.	Processes data streams immediately without storing raw data in memory buffers.

Block Cipher Specifications

Block Size Selection Criteria:
- Avoid very small block sizes $m$ : Total combinations equal $2^m$ . Small block sizes allow attackers to build plaintext-ciphertext lookup dictionaries (dictionary attack).
- Avoid excessively large block sizes: Creates processing overhead and requires unnecessary padding.
- Preference for multiples of 8 bits: Matches computer processor word architectures.
Padding: The process of adding redundant bits to the final data block so that its total length matches the scheme's required block size (e.g., padding a 150-bit message divided into two 64-bit blocks and a 22-bit balance block up to 64 bits).
Prominent Block Cipher Implementations:
- DES: Obsolete 1990s standard; considered broken due to small key size.
- Triple DES: Repeated application of DES; secure but computationally inefficient.
- AES: Standardized in 2002; 128-bit block size; supports 128, 192, and 256-bit keys.
- Blowfish: 64-bit block size; variable key lengths from 32 to 448 bits.
- Twofish: 128-bit block size; variable key lengths up to 256 bits.
- Serpent: 128-bit block size; key lengths of 128, 192, or 256 bits; slower but exceptionally secure design.
- Stream Cipher Specifications

Uses a pseudorandom bit generator (keystream generator) to produce an infinite bit stream key.
Technically functions as a block cipher with a block size of 1 bit.
The One-Time Pad (OTP):
- The theoretical ideal stream cipher utilizing a truly random keystream key equal to or longer than the plaintext.
- Provides Perfect Secrecy and total immunity to brute force attacks, but is logistically impractical for general use.
Requirements for Security: Keystream generator output must be unpredictable, and keys must never be reused.
Stream Cipher Algorithms:
- RC4 (Rivest Cipher 4 / ARCFOUR / ARC4): Historically popular stream cipher used in WEP, WPA, and TLS protocols. Prohibited in all TLS versions by RFC 7465 due to discovered vulnerabilities.
- Modern Alternatives: SALSA, SOSEMANUK, PANAMA.
- Practical Matrix Substitution Example
Uses a $6 \times 5$ Letter Matrix key structure:

Coordinate Layout Matrix:
- Row 0: Q(0,0), W(1,0), E(2,0), R(3,0), T(4,0), Y(5,0)
- Row 1: U(0,1), I(1,1), O(2,1), P(3,1), A(4,1), S(5,1)
- Row 2: D(0,2), F(1,2), G(2,2), H(3,2), J(4,2), K(5,2)
- Row 3: L(0,3), Z(1,3), X(2,3), C(3,3), V(4,3), B(5,3)
- Row 4: N(0,4), M(1,4), Q(2,4), W(3,4), E(4,4), R(5,4)
Encryption Example:
- Message: CCS
- C = coordinate (3,3)
- C = coordinate (3,3)
- S = coordinate (5,1)
- Output Ciphertext: (3,3)(3,3)(5,1)
Decryption Example:
- Lookup coordinates in matching matrix copy to restore CCS.

Public Key Cryptography

Fundamentals of Public Key Cryptography
- Also known as Asymmetric Cryptography.
- Utilizes two distinct, mathematically linked keys: a Public Key (distributed openly) and a Private Key (kept strictly confidential).
- Primary protocol basis for SSL/TLS and HTTPS internet communications.
Three-State Lock Analogy

Consider a physical trunk lock mechanism with three positions:
- Position A: Locked (key turned completely to the left).
- Position B: Unlocked (key centered in the middle).
- Position C: Locked (key turned completely to the right).
Key No. 1 (Private Key): Can only turn the lock mechanism to the left.
Key No. 2 (Public Key): Can only turn the lock mechanism to the right.
Operational Scenarios:
- Confidentiality Scenario: Alice locks the trunk turning right to Position C using Key No. 2 (Public Key). Once set to C, only Key No. 1 (Private Key) can turn left back to Position B (Unlocked).
- Authentication / Sender Verification Scenario: Bob locks the trunk turning left to Position A using Key No. 1 (Private Key). Anyone with Key No. 2 (Public Key) can unlock it turning right, proving conclusively that only Bob could have locked it.
- Comparison: Public Key vs. Private Key

Public Key: Published openly to the world; created via complex asymmetric algorithms; used by senders to encrypt data or verify signatures.
Private Key: Kept entirely secret by its owner; generated simultaneously with the public key; used to decrypt ciphertext or sign data.
- Dual Dual-Use Mechanics: Security vs. Identity

Ensuring Security and Identity Using Public and Private Key

Enforcing Message Security (Confidentiality):
- Sender encrypts plaintext using Recipient's Public Key.
- Only Recipient's Private Key can perform decryption.
Enforcing Sender Identity (Authentication / Non-Repudiation):
- Sender encrypts/signs message using Sender's Private Key.
- Any party can decrypt/verify message using Sender's Public Key, confirming origin identity.
- Key Applications of Public Key Cryptography
Web Server Security: Foundations of SSL and TLS protocols enabling secure HTTPS browsing, protecting web traffic against Man-In-The-Middle (MITM) attacks.
Digital Signatures & Document Signing: Private key signing creates a cryptographic digest bound to the message content, verifying identity and preventing document tampering.
Digital Identity Certificates: Replaces standard password systems across mobile devices, IoT, cloud systems, S/MIME email encryption (anti-phishing), and Secure Shell (SSH) server access control keys.

Review Questions and Exercises

Caesar Cipher Decryption Exercise:
- Ciphertext: kimaiz kqxpmza izm dmzg dctvmzijtm bw i jzcbm nwzkm ibbiks
- Decryption Process: Shift each character back by 8 positions in the alphabet ( $k \rightarrow c$ , $i \rightarrow a$ , etc.).
- Plaintext Output: caesar ciphers are very vulnerable to a brute force attack
- Cryptographic Attack Used: Brute force attack / Frequency analysis / Caesar shift derivation.
Letter Matrix Decryption Exercises:
- Matrix Plaintext Lookups:
1. Coordinates (5,2)(3,2)(5,5)(1,1) $\rightarrow$ K H R I
2. Coordinates (3,2)(2,1)(4,4) $\rightarrow$ H O E
3. Coordinates (4,0)(3,0)(1,1)(0,4) $\rightarrow$ T R I N
4. Coordinates (1,1)(2,2)(3,3)(4,4)(5,5) $\rightarrow$ I G C E R
Summative Assessment Questions:
- Importance of Cryptography in E-Commerce: Ensures secure transmission of payment information, protects confidential personal data, authenticates user identities, and guarantees transaction integrity.
- Most Common Attack on Cryptographic Primitives: Brute force attack, targeting key exhaustion across the complete key space.
- Symmetric Encryption Key Requirement: No, symmetric encryption inherently requires a shared secret key; plaintext cannot be encrypted symmetrically without a key.
- Mathematical Bonding of Key Pairs: Yes, public and private key pairs must be mathematically bonded so that data encrypted with one key can be decrypted exclusively by the corresponding key.