Cryptography Basics Quiz

Introduction to Cryptography

• The textbook, Understanding Cryptography, by Christof Paar and Jan Pelzl, is a resource for students and practitioners
• The book's version is dated October 28, 2010
• The slides were prepared by Christof Paar and Jan Pelzl

Terms of Use

• The slides can be used freely
• Copyrights remain with Christof Paar and Jan Pelzl
• The book title (“Understanding Cryptography”) and authors’ names must remain on each slide
• Modifications must maintain credits to the book authors and title
• Reproduction of slides in printed form is prohibited without written consent from the authors

Chapter Content

• Overview of cryptography
• Basics of symmetric cryptography
• Cryptanalysis
• Substitution Cipher
• Modular arithmetic
• Shift (or Caesar) Cipher and Affine Cipher

Further Reading

• Handbook of Applied Cryptography by A. Menezes, P. van Oorschot, S. Vanstone (CRC Press, 1996)
• Encyclopedia of Cryptography and Security by H.v. Tilborg (Springer, 2005)
• The Code Book: The Science of Secrecy, by S. Singh (Anchor, 2000)
• The Codebreakers: The Comprehensive History of Secret Communication, by D. Kahn (Scribner, 1996)
• Cryptool software (http://www.cryptool.de)

Classification of Cryptology

• Cryptology branches into Cryptography and Cryptanalysis
• Cryptography further branches into Symmetric Ciphers (Block Ciphers, Stream Ciphers) and Asymmetric Ciphers
• Protocols are also part of this classification

Basic Crypto Facts

• Early encryption signs were discovered in Egypt around 2000 B.C.
• Letter-based schemes (e.g., Caesar cipher) were common
• All encryption schemes before 1976 were symmetric
• Asymmetric cryptography was introduced in 1976 by Diffie, Hellman, and Merkle
• Modern protocols often use hybrid schemes combining symmetric and asymmetric ciphers

Symmetric Cryptography

• Also known as private-key, single-key, or secret-key cryptography
• Alice and Bob need to communicate securely over an insecure channel (e.g., internet, WLAN)
• Oscar (a malicious third party) might eavesdrop
• Encryption and decryption use the same key (K)

Symmetric Cryptography (Solution)

• Oscar only receives ciphertext (y) which should seem random
• Alice uses encryption (e(x)) to encrypt plaintext (x) with key (K) to create ciphertext (y)
• Bob applies decryption (d(y)) using the same key (K) to recover the plaintext (x)
• A secure channel (e.g., a physical courier, secure WiFi protocol) is needed to transmit the key

Symmetric Cryptography (Equations)

• Encryption equation: y = e_k(x)
• Decryption equation: x = d_k(y)

Symmetric Cryptography (Important Point)

• The security of the scheme depends on the secrecy of the key K, not the algorithm.

Cryptanalysis

• No mathematical proof exists for the security of most ciphers
• Cryptanalysis is needed to evaluate a cipher's security, testing its ability to resist attacks
• By understanding and analyzing a crypto-system, potential vulnerabilities can be discovered

Cryptanalysis Attacks

• Classical Attacks (mathematical analysis, Brute-force attack)
• Implementation Attacks (reverse engineering, power measurement)
• Social Engineering (tricking users into divulging information)

Brute-Force Attack

• The attacker tries every possible key until the correct one is found
• The key length determines the key space size, thus affects the time taken by a brute-force attack
• Security time greatly increases with key length

Substitution Cipher

• Replaces each plaintext letter with a fixed other letter
• Example: A becomes k, B becomes d, C becomes w
• A historically significant cipher
• Useful for understanding brute-force vs. analytical attacks

Attacks on Substitution Ciphers

• Exhaustive Key Search (Brute-Force): Testing all possible substitution tables until the correct one produces understandable plaintext
• Letter Frequency Analysis: Exploiting the consistent frequency patterns of letters in typical natural languages to identify plaintext letters from ciphertext.

Breaking Substitution Ciphers

• Finding the most frequent letter in the ciphertext, which in natural language is usually 'e'
• Using the calculated frequency to guess other characters and decipher the plaintext gradually leading to a full decryption

Modular Arithmetic

• Important for asymmetric cryptography (e.g., RSA, elliptic curves)
• Useful for describing historical ciphers (e.g., Caesar, affine ciphers)

Modular Arithmetic: Properties

• Remainder is not always unique
• By convention, the smallest positive integer 'r' is chosen as the remainder (0 ≤ r ≤ m-1)
• The inverse of a number 'a' exists in modulo m only if their Greatest Common Divisor (GCD) is 1 (gcd(a, m) = 1)

Shift (Caesar) Cipher

• An ancient cipher, likely used by Julius Caesar
• Shifts each letter in the plaintext by a fixed number of positions (k) in the alphabet
• The mathematical description uses modular arithmetic to handle wrapping around the end of the alphabet.

Affine Cipher

• An extension of the Shift cipher, adding multiplication to letter shifting
• The encryption formula employs modular arithmetic and necessitates the existence of a modular multiplicative inverse (a⁻¹) for efficient decryption

Lessons Learned

• Never develop your own encryption algorithm without experienced cryptanalysts' scrutiny.
• Avoid unsupported encryption algorithms and protocols
• Attackers target the weakest points and a large key space doesn't guarantee security
• Key lengths (e.g., 64-bit, 128-bit, 256-bit) affect security against exhaustive attacks
• Modular arithmetic facilitates the mathematical modeling of historical ciphers like the affine cipher.