Introductory Number Theory Textbook

This subsection establishes the fundamental concept that any positive integer can be uniquely represented in any positive integer base. It contrasts this with the commonly used decimal (base-10) system. The core idea centers on converting integers between decimal notation and other base systems. The text uses the example of the Babylonian base-60 system, suggesting a possible reason for our base-10 preference (ten fingers). A proof is presented, using mathematical notation (∃ m, n ∈ Z such that mx + ny = 1), demonstrating the unique representation. The text further explores the differences between equations and congruences, highlighting that dividing both sides of a congruence by an integer doesn't always maintain the congruence. This concept is critical for later sections dealing with modular arithmetic, a cornerstone of many cryptographic techniques. The Pigeonhole Principle is invoked to illustrate a point about congruences and their behavior with infinite sets and finite congruence classes. While this subsection lays out a fundamental mathematical concept, its relevance to more advanced topics like cryptography and computer science is implied, setting the stage for later chapters that delve into those areas. The connection between number theory and the practicality of different base systems is subtly made, suggesting a deeper relationship between abstract mathematical concepts and their applications in practical fields.

Building upon the foundation of different number bases, this subsection delves into the properties of congruences. It explains that unlike equations, dividing both sides of a congruence by the same integer does not necessarily preserve the congruence. The concept is illustrated using set notation, considering the set { [a^p]_n | p ∈ N }, where [a^p]_n represents the congruence class of a^p modulo n. The Pigeonhole Principle (Theorem 1.1.2) is then applied to show that with infinitely many natural numbers (p ∈ N) and only n congruence classes in Z/nZ, there must be at least two distinct values of p and q such that [a^p] = [a^q]. This implies that a^p-q ≡ 1 (mod n), a crucial idea in modular arithmetic. The text then takes an unexpected turn, briefly mentioning the existence of lying among humans. Though seemingly unrelated, it subtly foreshadows later sections on the security implications of cryptography, suggesting the need to trust the integrity of data against malicious actors. The unexpected transition between number theory concepts and human behavior acts as a bridge to link the inherent abstractness of mathematical principles to the very real challenges of maintaining data integrity, hinting at the crucial role that mathematical constructs play in addressing such real-world problems. The subsection connects the apparently abstract mathematical concepts to the concrete realities of information security.

This subsection introduces the Scytale cipher, an ancient Greek cryptographic system. The Scytale was a cylindrical rod around which a strip of parchment was wrapped to write a message. When unwrapped, the letters appeared jumbled, requiring the recipient to have an identical rod to decipher the message. The diameter of the rod served as the encryption key. The text points out that even with a key, the Scytale cipher's vulnerabilities are apparent; Athens lost the Peloponnesian War, a historical context that hints at the limitations of the system. This early example serves as a foundation for understanding the evolution of cryptography. The description of the Scytale cipher provides a tangible illustration of a basic substitution cipher. The text then transitions into a discussion of a fundamental shift in cryptographic thinking. The text emphasizes the inherent weaknesses in keeping cryptographic algorithms secret, advocating for public algorithms and the secrecy of keys only. This point is pivotal in understanding the approach of modern cryptography, emphasizing transparency and rigorous community review to improve the security and reliability of systems. It implicitly contrasts the Scytale's method with modern principles, highlighting the evolution from secrecy of the algorithm itself to secrecy of the key only.

The section moves beyond historical examples, focusing on key concepts of modern cryptography. A formal definition of a 'key' is provided: additional information used in encryption and decryption. The key in the Scytale cipher was the rod's diameter. The text suggests that the Scytale might have offered simple authentication: only someone with a matching rod could decipher the message. The section then highlights a crucial paradigm shift in cryptography: making the algorithms public and keeping only the key secret. This change is justified by the inherent impossibility of anticipating all potential cryptanalytic attacks. The open nature allows for broader scrutiny and improved robustness, aligning with the scientific method's emphasis on reproducibility and peer review. The discussion of the key's role and the reasons for public algorithms emphasizes the fundamental principles governing modern cryptography. The section further explains that despite the public nature of algorithms, confidentiality can be maintained. It illustrates this point using the example of the Scytale cipher and its key (the rod's diameter). The concept of authentication is also touched upon, using the Scytale cipher as an illustrative example, showing how the same system can provide different functionalities like encryption and authentication. The contrast between ancient practices and modern cryptographic principles underscores the development of the field.

This subsection delves into ROT13, a simple letter substitution cipher where each letter is shifted 13 positions down the alphabet. Encryption and decryption are identical, making it a reversible transformation. While inherently weak as a security measure, it found use in early internet forums and bulletin boards to obscure spoilers or other content. The text notes that despite its known insecurity, some commercial products briefly employed ROT13 for security reasons, a notable example being parts of some Windows operating systems. This example highlights the evolution of techniques and highlights that sometimes even insecure methods might still find a niche application where very high security isn't absolutely critical. The text emphasizes the irony and historical context of its use. It highlights a specific, albeit flawed, application in early Internet culture, contrasting its simplicity with the more complex cryptographic systems explained later in the text. The discussion of ROT13's use, despite its inherent weakness, provides an illustrative example of the intersection between theoretical cryptographic principles and the practical challenges of maintaining confidentiality and controlling access to information.

This subsection introduces the Caesar cipher, a basic substitution cipher where each letter in the plaintext is shifted a fixed number of positions down the alphabet. The shift value, denoted as 'k', acts as the encryption key, known only to the sender (Alice) and the receiver (Bob). The text emphasizes that the message is first processed by removing spaces and punctuation and converting all letters to the same case (upper or lower). The process is straightforward: shift each letter k places, wrapping around from Z to A if necessary. This simple cipher serves as a foundational example for understanding more complex cryptographic techniques. The Caesar cipher's historical context is mentioned, suggesting its ancient origins and use by Julius Caesar. The small size of its keyspace (only 26 possible keys for a modern 26-letter alphabet) is implicitly highlighted as a significant weakness. This simple cipher is presented as a baseline for comparison with more sophisticated techniques discussed later in the text, setting the stage for the introduction of more robust cryptographic methods and the analysis of their security.

The section moves on to discuss the inherent vulnerabilities of the Caesar cipher. Its small keyspace makes it susceptible to a brute-force attack, where all possible keys are tested until the correct decryption is found. Even in Caesar's time, the limited number of keys allowed for easy decryption, rendering the cipher easily breakable. The text further points out that a random choice of key has a surprisingly high probability of resulting in a correct decryption purely by chance. The small keyspace of the Caesar cipher is contrasted with more complex ciphers, illustrating a weakness and setting the stage for the explanation of more robust encryption techniques in the following sections. The text mentions that the Caesar cipher was broken before 1000 CE, a historical fact that emphasizes its limitations. This vulnerability is a crucial point used to motivate the need for stronger encryption schemes. The section also highlights that a few commercial products mistakenly relied on ROT13 (a Caesar cipher variant with k=13) for security, despite its clear weaknesses. This historical fact is used to underscore the importance of understanding the strengths and limitations of different cryptographic systems, highlighting a common misconception in the security field. The brief mention of the one-time pad and the introduction of the Vigenere cipher prepares the reader for the exploration of more sophisticated encryption approaches in the subsequent sections.

This subsection introduces the Vigenère cipher, an extension of the Caesar cipher. Instead of a single shift value, the Vigenère cipher uses a key sequence (k₁, k₂, ..., kℓ) where each letter in the plaintext is shifted by a different value from the key. The key sequence is repeated as needed. If the key length (ℓ) is one, it is exactly the same as the Caesar cipher. The text states that the Vigenère cipher is essentially ℓ + 1 times harder to crack than the Caesar cipher because an attacker doesn't even know the key length (ℓ). Despite initially being deemed unbreakable and used extensively, it too was eventually broken. The text mentions that the Vigenère cipher’s improved security over the Caesar cipher stems from its use of a key sequence instead of a single key value, increasing the complexity of the ciphertext. It's described as essentially running multiple Caesar ciphers in parallel. The introduction of the Vigenère cipher illustrates the iterative process of improving cryptographic techniques, building upon the fundamentals of the Caesar cipher while addressing its limitations. The inherent difficulty in determining the key length for the Vigenère cipher further highlights the more complex aspects of cryptanalysis. The section introduces the complexities involved in breaking such a cipher compared to simpler algorithms.

This subsection introduces frequency analysis as a method for cryptanalysis. It explains that this technique involves comparing the frequency of letters in a ciphertext to the expected frequency of letters in the plaintext language. The text notes that the use of frequency analysis in cryptanalysis was first described by the 9th-century Muslim philosopher and mathematician al-Kindi in his work, Manuscript on Deciphering Cryptographic Messages. The text points out that simply looking for the most frequent letter may not be sufficient, suggesting a more sophisticated approach. The introduction of frequency analysis as a cryptanalytic technique contrasts with previous methods. The section describes frequency analysis as a method of comparing letter frequencies in the intercepted ciphertext to the expected frequencies of letters in the plaintext language, establishing it as a fundamental tool in cryptanalysis. The historical context, including the mention of al-Kindi, provides an interesting historical perspective on the evolution of cryptanalysis. The limitations of simply focusing on the most frequent letter are pointed out, laying the groundwork for more advanced techniques described further in the section. The subsection highlights that frequency analysis moves beyond a simple comparison of the most frequent letter in the ciphertext with the most frequent letter in the expected language.

This subsection applies frequency analysis to the Caesar cipher. Since the Caesar cipher has a small keyspace (26 possible shifts), it's relatively straightforward to try all possible decryptions and compare the resulting letter frequency tables to the expected frequency table for English (or another language). The text explains this process, emphasizing that the best decryption is the one that yields a letter frequency distribution that is closest to the known frequency distribution of the language. This method highlights how frequency analysis can efficiently crack the Caesar cipher despite its limited complexity. The simplicity of the Caesar cipher's structure allows for a direct demonstration of the efficacy of frequency analysis. The process of testing all possible keys and evaluating the resulting letter frequency distribution demonstrates a straightforward and effective cryptanalytic technique. The section points out that comparing the whole frequency distribution to that of a known language provides more accurate results than solely relying on comparing the most frequent letters. The Caesar cipher serves as a simple, illustrative example to explain the core principle of frequency analysis before moving on to more complex scenarios. It implicitly suggests that the strength of frequency analysis lies in its ability to deal with both the simple and the complex ciphers.

This subsection extends the use of frequency analysis to the more complex Vigenère cipher. The major challenge with the Vigenère cipher is determining the key length. The text explains that once the key length is known, the ciphertext can be divided into smaller segments, each corresponding to a specific element of the key. Each segment can then be treated as a Caesar cipher, and frequency analysis can be applied to determine the individual shifts (key values). The text suggests a systematic approach: try different key lengths, perform Caesar cracker analysis on each segment, and choose the key length that produces the most coherent decrypted text. The text references Amazon's Mechanical Turk as a potential solution to the brute force attack but suggests writing a computer program as a better solution. This transition highlights the increasing reliance on computation in modern cryptanalysis. The method describes a systematic approach to find the key length by trying various possibilities, and its effectiveness hinges on the ability to distinguish real language from gibberish, again highlighting the importance of statistical analysis in breaking codes. This analysis showcases the power of frequency analysis in breaking more robust ciphers than the simple Caesar cipher. The limitations of manual analysis and the transition to computer-aided cryptanalysis is implicitly shown.

This section introduces the RSA cryptosystem, a fundamental algorithm in public-key cryptography. The text highlights that the security of RSA relies on the difficulty of factoring large numbers, a computationally intensive task even for powerful computers. A significant example cited is the factorization of RSA-768, a 232-digit number, which took approximately two years using a network of hundreds of computers. The concept of a cryptographic one-way function is introduced—a function easy to compute but infeasible to reverse. This is central to RSA's security. The section establishes that RSA's strength rests on the computational difficulty of factoring large composite numbers. It provides a real-world example, the RSA-768 challenge, which showcases this computational difficulty and the scale of resources needed to break such encryption. The introduction of the concept of a cryptographic one-way function provides a framework for understanding the underlying mathematical principles that underpin RSA's security. This concept establishes the foundation for discussing the practical applications of RSA in a secure communication scenario.

This subsection addresses practical challenges in implementing RSA. The primary issue is how to use RSA to transmit messages beyond simple numbers. The text discusses the need for encoding messages, character by character, into numerical representations. ASCII is presented as a long-standing standard, with its 7-bit (later 8-bit) encoding of characters. The rise of Unicode and its encoding (UTF-8 and UTF-16) is mentioned due to its broader character support. The section deals with the practical issues of applying the RSA algorithm. It emphasizes that the RSA algorithm operates on numbers and therefore necessitates encoding messages into numerical representations. The discussion of ASCII and Unicode as encoding schemes showcases the evolution of encoding standards to meet the increasing need for supporting various character sets. The shift from ASCII to Unicode highlights the need to adapt encoding strategies to accommodate global languages and writing systems. The text poses an exercise, encouraging readers to develop a more efficient exponentiation algorithm for RSA, which would speed up calculations, highlighting the optimization aspects of implementing such an algorithm.

This subsection focuses on improving the efficiency of RSA encryption. The text prompts the reader to develop a faster exponentiation algorithm, suggesting a polynomial-time approach as opposed to the initial exponential-time method. Hints are provided, including using a table of successive squares and binary representation of the exponent (k). The goal is to optimize the computation of a^k (mod n), a critical step in RSA encryption. The section implicitly acknowledges that faster computation is crucial for practical RSA implementation. It proposes an exercise challenging the reader to improve the computational efficiency of exponentiation, a key step in the RSA algorithm. The hints provided offer guidance in designing an optimized algorithm, leveraging techniques like successive squaring and binary representation of the exponent. This subsection emphasizes practical considerations in the implementation of the RSA algorithm, showing that while the mathematical basis is complex, the efficiency of calculation is crucial for practical use.

This subsection introduces digital signatures as a crucial element of the modern digital economy. The text explains that digital signatures aim to provide the equivalent of a physical signature on electronic documents, making forgery difficult. The use case of Bob sending a legally binding contract via email or Alice and Bob emailing a signed lease to their landlord, Larry, is used to illustrate the practical importance. The core function of a digital signature is to provide assurance that the document originates from the claimed sender, thus building trust in digital communication. Digital signatures are presented as an essential feature of secure digital transactions, overcoming challenges associated with verifying the authenticity of electronic documents. The text highlights the practical need for digital signatures in legally binding scenarios, such as contracts and leases. The use cases are presented as examples to motivate the discussion and showcase the importance of digital signatures in creating secure and trustworthy digital interactions. The need for confidence in the origin of an email, especially in legally significant scenarios, highlights the core function of digital signatures in secure electronic transactions.

This subsection explains how cryptographic hash functions are essential for digital signatures. The text notes that a hash function takes input of arbitrary length and produces a fixed-size output, a process that inherently involves collisions (multiple inputs producing the same output). The creation of these functions is described as a complex process, with successful algorithms being often quite ad hoc and resistant to inversion or breaking collision resistance. Specific examples like MD5 and SHA-1 are mentioned, highlighting their past prominence and known vulnerabilities. The text emphasizes the importance of the collision resistance property of hash functions. The creation of cryptographic hash functions is described as a complex process, and the reason why many successful algorithms are often ad hoc. The section discusses that successful cryptographic hash functions are often designed with a less structured approach, as more structured algorithms have proven vulnerable to various attacks. MD5 and SHA-1 are introduced as examples of widely used hash functions, with SHA-1 being eventually replaced due to vulnerability concerns. The inherent limitations of hash functions due to the finite output size and infinite potential input size are implicitly explained and contextualized.

This subsection provides specific examples of cryptographic hash functions: MD5 and SHA-1. MD5, developed by Ron Rivest and published in 1992, had a 128-bit output size. The text notes that while flaws were suspected since the mid-1990s, it wasn't until 2004 that a published attack demonstrated its lack of collision resistance. Despite this, MD5 is still used for verifying data integrity, not for security. SHA-1, developed by the NSA and adopted by NIST, faced similar vulnerability concerns, leading NIST to mandate its replacement in 2010 for many US federal data protection applications. This subsection provides practical examples of hash functions and their vulnerabilities. MD5 and SHA-1 are presented as case studies that illustrate how even widely used algorithms can have underlying flaws and ultimately be deemed insecure, highlighting the dynamic nature of cryptographic security. The information on MD5 and SHA-1 provides specific examples of the black art of cryptographic hash function design and the ongoing evolution to strengthen security against increasingly sophisticated attacks. It reinforces the point about the need for ongoing review and improvement in the field of cryptography.

This subsection introduces the concept of man-in-the-middle (MITM) attacks in the context of public-key cryptography. The text highlights the crucial distinction between the actual sender (Bob, as a person) and the bits claiming to be from Bob that arrive at the receiver (Alice or Larry). While a passive observer (Eve) may only intercept communications, an active attacker (Eve with more network control) can replace communications with their own versions. This attack completely undermines the confidentiality and integrity of the communication, as the attacker can both modify the message and make it appear to originate legitimately from the intended sender. The text emphasizes that this attack highlights a critical gap between the theoretical properties of cryptographic tools and their practical application. It contrasts passive observation with active manipulation of the communication channel, introducing the concept of a MITM attack that involves actively intercepting, modifying, and relaying communications between Alice and Bob. The attacker Eve intercepts communications and replaces the message with their own modified version. Bob receives the altered message, which appears to be legitimate but is actually under the control of Eve, demonstrating the vulnerability of the system to MITM attacks.

This subsection provides a detailed example of a MITM attack using public-key cryptography. The scenario involves Alice sending a message to Bob via the internet. Eve intercepts Bob's public key, replacing it with her own, and then intercepts Alice's encrypted message and decrypts it using her own private key. Eve can then modify the message, re-encrypt it using Bob's actual public key, and forward it to Bob. Bob decrypts the message, which now appears to be from Alice but is actually modified by Eve. This illustrates how an attacker can violate both confidentiality and integrity. The example illustrates how Eve intercepts communications between Alice and Bob, substitutes her public key for Bob’s, and decrypts the message using her private key, allowing her to modify it before re-encrypting and forwarding it to Bob. The attacker, Eve, modifies the message, ensuring that the modified message appears legitimate when decrypted with Bob’s key, which is unknown to Alice. The illustration depicts how an active attacker can completely compromise the confidentiality and integrity of the communication without Alice or Bob realizing it. This underscores the necessity for mechanisms to establish and validate trust in online communication.

This subsection addresses the problem of establishing trust in public-key cryptography. The text contrasts the ease of establishing trust in symmetric cryptosystems (where parties meet to exchange a key) with the difficulties inherent in asymmetric cryptosystems where online keys need to be linked to real-world identities. The role of Certificate Authorities (CAs) is introduced as a way to verify public keys, although the text notes that CAs often only verify internet-based tokens (like email addresses) and not real-world identities. The limitations of CAs are acknowledged. An alternative approach based on personal trust and chains of digitally signed keys is suggested, where individuals verify keys by following a chain of signatures from trusted individuals, but this still relies on trust. The challenges associated with verifying the authenticity and integrity of public keys are addressed. The difficulty of establishing a trustworthy connection between real-world identities and online public keys is highlighted, comparing symmetric and asymmetric cryptosystems in terms of trust. The role of Certificate Authorities (CAs) is introduced, acknowledging their limitations in verifying real-world identities. An alternative approach of establishing trust within communities is suggested, involving chains of digitally signed keys from personally trusted individuals. This solution still relies on individual trust rather than complete anonymity or centralized certification.

This subsection introduces the Diffie-Hellman Key Exchange (DHKE) as a method for two parties to establish a shared secret key over an insecure channel without ever directly transmitting the secret. The text emphasizes that the security of DHKE relies on the difficulty of computing discrete logarithms. If a feasible algorithm for computing discrete logarithms were discovered, an attacker (Eve) could break DHKE's security by computing the shared secret (S) from the publicly available values. The core concept is that despite the public exchange of information, the shared secret remains computationally infeasible to derive for an eavesdropper. The section introduces DHKE as a method for establishing a shared secret key over an insecure channel without requiring prior exchange of secrets. It explains how the difficulty of computing discrete logarithms protects the shared secret. The text suggests that the security of the DHKE protocol depends on the assumption that computing discrete logarithms is computationally infeasible.

This subsection details the vulnerability of DHKE to efficient discrete logarithm computation. The text explains that if an attacker could compute discrete logarithms efficiently, they could easily derive the shared secret (S) from the publicly exchanged values (A and B). The attacker would compute α = ind_r(A) and β = ind_r(B), and then calculate S as either B^α, A^β, or r^αβ. Having the shared secret S would allow the attacker to decrypt any communications protected by that key. This illustrates a critical security aspect of DHKE and its reliance on the computational hardness of the discrete logarithm problem. The subsection explains that if an attacker (Eve) could compute discrete logarithms quickly, she could easily break the security of the DHKE protocol. This would entail computing α and β from the public values A and B, and subsequently calculating S which is the shared secret key. Once this secret key is known, Eve could decrypt the communications between the two parties.

This subsection connects the security of DHKE to the properties of modular exponentiation as a one-way function. The text explains that modular exponentiation is computationally feasible in the forward direction (calculating A and B), but its inverse, the discrete logarithm, is considered computationally infeasible. This asymmetry is precisely what underlies the security of DHKE. The section illustrates that the security of DHKE hinges on the one-way nature of modular exponentiation. It highlights that while computing modular exponentiation is feasible, computing the inverse (discrete logarithm) is computationally intractable, which is the core basis of the security of DHKE. The text emphasizes that the feasibility of modular exponentiation and the infeasibility of its inverse (the discrete logarithm) are central to the security of the DHKE protocol. This asymmetry is the foundation upon which the security of DHKE rests, meaning that the assumption of the computational intractability of the discrete logarithm problem is a crucial factor in DHKE’s security.

This subsection introduces the ElGamal cryptosystem as a public-key cryptosystem. The text emphasizes that its security, like Diffie-Hellman Key Exchange (DHKE), relies on the computational difficulty of the discrete logarithm problem. The ElGamal system uses modular exponentiation (in mod p, where p is a prime) as a one-way function: easy to compute forward but infeasible to reverse. This asymmetry is the basis of the cryptosystem's security. The section introduces the ElGamal cryptosystem as a public-key system whose security relies on the difficulty of computing discrete logarithms. It explains how the system uses modular exponentiation in mod p (where p is a prime) as a one-way function, where the forward operation is easy but the inverse (computing discrete logarithms) is computationally infeasible. This subsection makes a direct connection between the ElGamal cryptosystem and the discrete logarithm problem, highlighting that the computational intractability of the discrete logarithm problem is the core security assumption of this public-key cryptosystem.

This subsection details how the security of the ElGamal cryptosystem depends on the infeasibility of computing discrete logarithms. The text explains that if an efficient algorithm for computing discrete logarithms were found, an attacker (Eve) could break the system. This is because the cryptosystem's security relies on the difficulty of computing the discrete logarithm with respect to a primitive root (r) modulo p, even when p and r are public. This is similar to the security considerations of DHKE. This subsection elaborates on the security considerations of the ElGamal cryptosystem by discussing the discrete logarithm problem. It explains that the system’s security rests on the assumption that computing discrete logarithms is computationally infeasible. The text clearly states that if an efficient algorithm for computing discrete logarithms were to be discovered, the ElGamal cryptosystem could be broken, emphasizing the critical role this problem plays in the security of the system. The connection between the computational intractability of the discrete logarithm problem and the security of the ElGamal cryptosystem is directly and explicitly stated, highlighting this crucial security assumption.

This subsection provides a practical example and exercise demonstrating the use of the ElGamal cryptosystem and its application to digital signatures. An example involves sending the message '42' using a given public key. An exercise involves verifying a digital signature for a test score using ElGamal. A public key (p, r, a) = (11717, 103, 1020) and a signature (6220, 10407) are given for this exercise. This subsection provides a practical illustration of the ElGamal cryptosystem through an example of encrypting a message. Then it provides an exercise that involves verifying a digital signature created using the ElGamal digital signature scheme, providing a hands-on application of the concepts discussed. The public key provided is (p, r, a) = (11717, 103, 1020), and the signature value is (6220, 10407). The specific example and the exercise illustrate the practical use and verification of ElGamal, showing how to use the public key to encrypt a message and subsequently verify the digital signature in this specific context. This strengthens the understanding of the practical application of ElGamal and its use in creating digital signatures, moving beyond theoretical explanations to concrete examples.