Basic Cryptography and Modern Cryptographic Systems Study Guide

Fundamentals and Definitions of Cryptography

  • Cryptography: Defined as the art and science of crafting ciphers. The word "Cipher" is synonymous with "secret."

  • Cryptanalysis: The art and science of breaking ciphers to recover information without knowing the key.

  • Cryptology: An umbrella term that encompasses both cryptography and cryptanalysis.

  • Cryptosystem: Also referred to as a cipher system. It is a system providing a method for protecting information by encrypting it so that only authorized users or systems can access and use it.

  • Plaintext: The original, readable message.

  • Ciphertext: The encrypted, unreadable version of the message produced after applying an algorithm.

  • Encryption: The process of changing plaintext into ciphertext.

  • Decryption: The process of changing ciphertext back into plaintext.

Goals and Approaches to Secure Communication

  • Fundamental Problem: Cryptography addresses the security of communication over an insecure medium.

  • Definition of Secure Communication:     * Privacy (Secrecy/Confidentiality): Ensuring only the intended recipient can see the communication.     * Authenticity (Integrity): Ensuring the communication is generated by the alleged sender and has not been altered.     * Adversaries: Generally refers to "bad guys" or unauthorized entities, often personified as "Eve."

  • Two Approaches to Security:     * Steganography: Translates to "covered writing." Its goal is to hide the very existence of a message.     * Cryptography: Translates to "hidden writing." Its goal is to hide the meaning of a message.

Cryptographic Algorithms and Strength

  • History: Dates back to ancient Assyrians and Egyptians. Originally a manual process, the use of machines began in the twentieth century.

  • Algorithm Definition: A step-by-step procedure for solving a particular problem. In crypto, it defines how encryption is applied, how data is held, and how it is decrypted by the receiver.

  • Cryptographic Strength: Measured by the number of trials required to break the cipher.     * Brute Force Metric: Relates to effective key size.     * Example: A 1616-bit key requires an average of 282^8 trials to guess.     * Reduction of Strength: Back doors or knowledge of cipher properties can significantly reduce the number of trials needed to break a cipher.     * Example: SHA-1 generates a fixed 160160-bit hash. While theoretically requiring 2802^{80} trials, it can be broken down in 2632^{63} trials.

Types of Cryptographic Attack

  • Brute Force Attack: Trying every possible case/key under the assumption of eventual success. Modern specialized hardware can execute more than 101110^{11} key tests per second.

  • Known Plaintext / Ciphertext Attacks: These reduce brute force costs by using examples of matching plaintext and ciphertext.     * Can involve injecting known plaintext to observe the resulting ciphertext.     * Can involve injecting ciphertext to observe the decrypted result.

  • Differential Attacks: The attacker explores differences in an input to observe effects on the output differences.     * In data streams, a non-random behavior such as (C1−C2)=(P1−P2)(C_1 - C_2) = (P_1 - P_2) can be exploited.     * In block ciphers, attackers trace differences through network transformations to find non-random patterns and discover the key.

Cipher Building Blocks and Properties

  • Substitution Block (S-Box): Each letter or symbol is exchanged for another. This provides Confusion, making it difficult to relate plaintext symbols to ciphertext symbols. Substitution is often represented as a non-linear table.

  • Permutation/Transposition Block (P-Box): Letters or symbols are rearranged or moved. This provides Diffusion.

  • Diffusion: Spreading information from a region of plaintext widely over the ciphertext.     * Changing one character in plaintext should result in several character changes in the ciphertext (and vice versa).     * Ensures every part of the input affects every part of the output.

Historical Substitution and Transposition Ciphers

  • Fixed Substitution: A character is always replaced by the same corresponding cipher character (e.g., if "y" becomes "V", it always becomes "V").     * Exercise: Decrypt "UBZBSJOJNFJTIBGJLB". Hint: Replace every letter with the previous letter in the alphabet.

  • Caesar Cipher: Julius Caesar used this by shifting the alphabet by 3 positions.     * Example Shift of 3:         * Plain: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z         * Cipher: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C     * Exercise: Encrypt "A user is the weakest link in information security chain" and "Firewalls help to protect the organization and its data" using a shift of 3.     * Exercise: Decrypt "F R Q J U D W X O D W L R Q V B R X J R W L W" using Caesar shift of 3.

  • Columnar Transposition Cipher: Writing plaintext in rows and reading ciphertext in columns.     * Width of rows and column order are defined by a Keyword (e.g., "ZEBRAS").     * Example: Keyword "ZEBRAS" (length 6). Alphabetical order of letters (A=1, B=2, E=3, R=4, S=5, Z=6) gives order "6 3 2 4 1 5".     * Regular version: Spare spaces are filled with nulls (e.g., "X").     * Irregular version: Spaces are left blank.     * Example Transcription for "HATUKO SALAMATENAKIMBIENI UPESI":         * Grid (under ZEBRAS / 6 3 2 4 1 5):             * Row 1: H A T U K O             * Row 2: S A L A M A             * Row 3: T E N A K I             * Row 4: M B I E N I             * Row 5: U P E S I X         * Ciphertext (read by columns 1 through 6): KMKNI TLNIE AAEBP UAAES OAIIX HSTMU     * Decryption: Calculate column length by (Total Message Length / Key Length), write out in columns, and reorder based on the keyword.

Modern Symmetric Key Cryptography

  • Core Difference: Modern systems rely on the secrecy of the cryptographic key, whereas old systems relied on the secrecy of the algorithm.

  • Symmetric Key (Shared Secret): Both parties (sender and receiver) know and possess the same secret key.

  • Functionality: Primarily used for bulk encryption. It only provides Confidentiality.

  • Models of Symmetric Encryption:     * One-Time Pad (OTP): Uses a randomly generated private key only once.         * The key must be as long as the message.         * Each encryption is unique and unrelated to others.         * Operation is a bitwise XOR (Exclusive OR).         * XOR Rule: Output is 1 if inputs differ, and 0 if inputs are identical (0,0→00,0 \rightarrow 0; 1,1→01,1 \rightarrow 0; 0,1→10,1 \rightarrow 1; 1,0→11,0 \rightarrow 1).     * Stream Ciphers: Encrypts 1 bit or byte at a time. Requires an internal state and an unpredictable pseudorandom generator. The key must never be reused.     * Block Ciphers: Encrypts a fixed size of nn-bits (usually 64,128,25664, 128, 256 bits).         * Short plaintext is handled via Padding Schemes.         * Most modern symmetric ciphers are block-based: DES, Triple DES, AES, IDEA, Blowfish.

Block Cipher Encryption Modes

  • Electronic Code Book (ECB): Each plaintext block has a defined corresponding ciphertext block. Deterministic and not secure for repeating data as the same input always produces the same output.

  • Cipher Block Chaining (CBC): Each plaintext block is XORed with the preceding ciphertext block before encryption. Requires an Initialization Vector (IV) for the first block.

  • Other Modes: Cipher Feedback (CFB), Output Feedback (OFB), Counter Mode (CTR).

Data Encryption Standard (DES) and Triple DES (3DES)

  • DES: Published by the US Government in 1977. Superseded by AES in December 2001.     * Specifications: 6464-bit block, 5656-bit key length.     * Process: 1616 rounds of XOR operations.     * Security: The "DES Challenge" decrypted a phrase ("Strong cryptography makes the world a safer place") in 4 months (1997) and in under 22 hours (1999) via brute force (1818 quadrillion keys).

  • Triple DES (3DES): Developed to improve DES security. Effective key lengths and methods vary:     * DES-EEE3: E(K1,E(K2,E(K3,P)))E(K_1, E(K_2, E(K_3, P))), effective key length 168168 bits.     * DES-EDE3: E(K1,D(K2,E(K3,P)))E(K_1, D(K_2, E(K_3, P))), uses three keys.     * DES-EEE2: E(K1,E(K2,E(K1,P)))E(K_1, E(K_2, E(K_1, P))), effective key length 112112 bits.     * DES-EDE2: E(K1,D(K2,E(K1,P)))E(K_1, D(K_2, E(K_1, P))), effective key length 112112 bits.     * Usage: Used in bank cards and RFID chips; expected to be secure until 2030.

Comparison of Modern Symmetric Algorithms

Name

Block Size (bits)

Key Size (bits)

DES

6464

5656

Triple DES (3DES)

6464

168168

AES (Rijndael)

Variable

128,192,256128, 192, 256

Twofish

128128

1−2561-256

Blowfish (used in SSH)

Variable

1−4481-448

IDEA (used in PGP)

128128

128128

RC5 (RSA-based)

32,64,12832, 64, 128

0−20480-2048

RC4 (RSA-based)

Streaming

128128

RC2 (RSA-based)

6464

128128

Skipjack

6464

8080

Symmetric Key Management Issues

  • Key Distribution: How do Bob and Alice agree on a key if they have never met?

  • Nonrepudiation: Impossible to implement because any party with the shared secret can encrypt/decrypt; source cannot be proven.

  • Scalability: Requires individuals to have unique keys for every possible pair.     * Formula: Number of Keys=n×(n−1)2\text{Number of Keys} = \frac{n \times (n - 1)}{2}     * Example Scale: 22 parties = 11 key; 33 parties = 22 keys (from transcript table); 10,00010,000 parties = 49,995,00049,995,000 keys.

  • Key Regeneration: If one participant leaves, all keys they were involved in must be discarded.

  • Solutions: Diffie-Hellman protocol, Key servers (Kerberos), or Asymmetric encryption.

Asymmetric (Public Key) Cryptography

  • Terminology: Uses two mathematically related keys that cannot be derived from each other.     * Private Key: Known only to the owner.     * Public Key: Known to everyone.

  • Operational Rules:     * A public key cannot decrypt a message it was used to encrypt.     * Private keys cannot be determined through public keys.

  • Security Services:     * Authentication: Message enciphered by Alice's private key can be deciphered by anyone using her public key, proving it came from Alice.     * Confidentiality: Message enciphered by Bob's public key can only be read by Bob (using his private key).

  • Performance: Requires significant computation power and is time-consuming. Messages are often handled by hashing or summarizing first.

The Diffie-Hellman Key Agreement Protocol

  • Purpose: Allows two parties to create a shared secret key without physical exchange or PKI. Released in 1976.

  • Mathematical Basis: Uses Modulus arithmetic: a(modb)=na \pmod{b} = n. Parameters include a generator gg (often 160160 bits) and a prime pp (often 10241024 bits).

  • The Exchange Process:     1. Alice and Bob agree on public primes gg and pp.     2. Alice picks secret number aa; computes A=ga(modp)A = g^a \pmod{p} and sends AA to Bob.     3. Bob picks secret number bb; computes B=gb(modp)B = g^b \pmod{p} and sends BB to Alice.     4. Alice computes Ba(modp)B^a \pmod{p}.     5. Bob computes Ab(modp)A^b \pmod{p}.     6. The result of step 4 and 5 is identical due to the property: (ga(modp))b(modp)=gab(modp)(g^a \pmod{p})^b \pmod{p} = g^{ab} \pmod{p}. This is the Shared Secret Key.

Cryptographic Hash Functions

  • Purpose: To guarantee Integrity (testing if a message is intact).

  • Mechanism: Takes an arbitrarily long message and produces a fixed-length string (hash value, fingerprint, or message digest).

  • Logic: Alice sends a message and its hash; Bob re-computes the hash upon receipt. If the values match, the message is intact.

  • Properties of Secure One-Way Hashes:     1. Given MM, it is easy to compute h=H(M)h = H(M).     2. Given hh, it is hard to compute MM such that h=H(M)h = H(M).     3. Given MM, it is hard to find M′≠MM' \neq M such that H(M)=H(M′)H(M) = H(M').     4. Hard to find any two different M,M′M, M' such that H(M)=H(M′)H(M) = H(M') (Collision resistance).

  • Algorithm Performance:     * MD4: 128128-bit hash, 270 MB/s270\,MB/s.     * MD5: 128128-bit hash, 216 MB/s216\,MB/s.     * SHA-1: 160160-bit hash, 68 MB/s68\,MB/s. (Theoretically broken but practically infeasible to break currently).     * SHA-2: 256256-bit hash, 44.5 MB/s44.5\,MB/s. (Considered secure).

Message Authentication Codes (MAC)

  • Problem: In standard hashing, if the hash value itself is not protected, it could be tampered with.

  • Solution: MAC is a keyed hash function (symmetric key KK).

  • Notation: MACK(M)MAC_K(M). The message sent is M∣∣MACK(M)M || MAC_K(M).

  • Usage: Can be applied to encrypted text (C∣∣MACK(C)C || MAC_K(C)).

  • Common MACs:     * HMAC: Hash function MAC.     * CBC-MAC: Code Book Chaining mode MAC.     * PMAC.

Key Management and Digital Certificates

  • Key Certificate: An assertion that a specific key belongs to a specific entity, digitally signed by a trusted third party (TTP).

  • Certificate Authority (CA): The role of the authority is to check the identity of a person and issue a certificate containing their public key and identification (signed by the CA's private key).

  • Public Key Infrastructure (PKI): The overall infrastructure resulting from CAs and certificates.

  • Web Authentication Example: Gmail sends its public key and a certificate to the browser. The certificate is signed by "Thawte Consulting (Pty) Ltd." The browser verifies the signature using the built-in Thawte key.

  • Revocation: If a secret key is compromised, the CA must invalidate the certificate by signing a statement (Certificate Revocation List).


Cryptography aims to make communication safe, especially when it's happening over channels that others might intercept. Here are the main ideas:

  1. Main Issue: Cryptography focuses on keeping communication secure when it’s vulnerable to outsiders.

  2. What Secure Communication Means:

    • Privacy: Only the person meant to receive the message can read it. This ensures secrets are kept safe.

    • Authenticity: The message really comes from who it says it does, and it hasn’t been changed by someone else during the transmission.

  3. Bad Actors: These are the unauthorized people (often called "Eve" in examples) trying to eavesdrop on conversations.

  4. Ways to Secure Communication:

    • Steganography: This hides the very existence of a message. It’s like sending a secret note tucked inside another document so that nobody even knows you’re sending a message.

    • Cryptography: This hides the content of a message, meaning that even if someone sees the message, they can't understand it without a key.