In the three years since the seventh edition of this book was published, the field has seen continued innovations and improvements. In this new edition, I try to capture these changes while maintaining a broad and comprehensive coverage of the entire field. To begin this process of revision, the seventh edition of this book was extensively reviewed by a number of professors who teach the subject and by professionals working in the field. The result is that, in many places, the narrative has been clarified and tightened, and illustrations have been improved.

Beyond these refinements to improve pedagogy and user-friendliness, there have been substantive changes throughout the book. Roughly the same chapter organization has been retained, but much of the material has been revised and new material has been added. The most noteworthy changes are as follows:

• Trust and trustworthiness: Chapter 1 includes a new section describing these two concepts, which are key concepts in computer and network security.

• Stream ciphers: With the growing importance of stream ciphers, the treatment of stream ciphers has been significantly expanded. There is a new section on stream ciphers based on linear feedback shift registers (LFSRs), and several examples of contemporary stream ciphers are provided.

• Lightweight cryptography: The Internet of Things and other small embedded systems require new approaches to cryptography to accommodate the low power requirements, minimum memory, and limited processing power of IoT devices. Two new sections cover this rapidly emerging topic.

• Post-quantum cryptography: In anticipation of the potential threat posed by quantum computers, there has been considerable research and development of cryptographic algorithms that are resistant to the threat. Two new sections cover this rapidly emerging topic.

• Cloud security: The discussion of cloud security has been expanded, and an entire chapter is devoted to this topic in the new edition.

• IoT network security: Similarly, IoT networks have resulted in new requirements for network security protocols, which are covered.

It is the purpose of this book to provide a practical survey of both the principles and practice of cryptography and network security. In the first part of the book, the basic issues to be addressed by a network security capability are explored by providing a tutorial and survey of cryptography and network security technology. The latter part of the book deals with the practice of network security: practical applications that have been implemented and are in use to provide network security.

The subject, and therefore this book, draws on a variety of disciplines. In particular, it is impossible to appreciate the significance of some of the techniques discussed in this book without a basic understanding of number theory and some results from probability theory. Nevertheless, an attempt has been made to make the book self-contained. The book not only presents the basic mathematical results that are needed but provides the reader with an intuitive understanding of those results. Such background material is introduced as needed. This approach helps to motivate the material that is introduced, and the author considers this preferable to simply presenting all of the mathematical material in a lump at the beginning of the book.

The book is intended for both academic and professional audiences. As a textbook, it is intended as a one-semester undergraduate course in cryptography and network security for computer science, computer engineering, and electrical engineering majors. This edition supports the recommendations of the ACM/IEEE Computer Science Curricula 2013 (CS2013). CS2013 adds Information Assurance and Security (IAS) to the curriculum recommendation as one of the Knowledge Areas in the Computer Science Body of Knowledge. The document states that IAS is now part of the curriculum recommendation because of the critical role of IAS in computer science education. CS2013 divides all course work into three categories: Core-Tier 1 (all topics should be included in the curriculum), Core-Tier-2 (all or almost all topics should be included), and elective (desirable to provide breadth and depth). In the IAS area, CS2013 recommends topics in Fundamental Concepts and Network Security in Tier 1 and Tier 2, and Cryptography topics as elective. This text covers virtually all of the topics listed by CS2013 in these three categories.

The book also serves as a basic reference volume and is suitable for self-study.

The book is divided into six parts.

• Background

• Symmetric Ciphers

• Asymmetric Ciphers

• Cryptographic Data Integrity Algorithms

• Mutual Trust

• Network and Internet Security

The book includes a number of pedagogic features, including the use of the computer algebra system Sage and numerous figures and tables to clarify the discussions. Most chapters include a list of key words, review questions, suggestions for further reading, and recommended Web sites. Most chapters also include homework problems. The book also includes an extensive glossary, a list of frequently used acronyms, and a bibliography. In addition, a test bank is available to instructors.

The major goal of this text is to make it as effective a teaching tool for this exciting and fast-moving subject as possible. This goal is reflected both in the structure of the book and in the supporting material. The text is accompanied by the following supplementary material that will aid the instructor:

• Solutions manual: Solutions to all end-of-chapter Review Questions and Problems.

• Projects manual: Suggested project assignments for all of the project categories listed below.

• PowerPoint slides: A set of slides covering all chapters, suitable for use in lecturing.

• PDF files: Reproductions of all figures and tables from the book.

• Test bank: A chapter-by-chapter set of questions with a separate file of answers.

• Supplemental homework problems and solutions: To aid the student in understanding the material, a separate set of homework problems with solutions are available.

All of these support materials are available at the Instructor Resource Center (IRC) for this textbook, which can be reached through the publisher’s Web site www.pearson.com/stallings or by clicking on the link labeled Pearson Resources for Instructors at this book’s Companion Web site at WilliamStallings.com/Cryptography. To gain access to the IRC, please contact your local Pearson sales representative via www.pearson.com/us/contact-us/find-your-rep.html.

For many instructors, an important component of a cryptography or network security course is a project or set of projects by which the student gets hands-on experience to reinforce concepts from the text. This book provides an unparalleled degree of support, including a project’s component in the course. The IRC not only includes guidance on how to assign and structure the projects, but also includes a set of project assignments that covers a broad range of topics from the text:

• Sage projects: Described in the next section.

• Hacking project: Exercise designed to illuminate the key issues in intrusion detection and prevention.

• Block cipher projects: A lab that explores the operation of the AES encryption algorithm by tracing its execution, computing one round by hand, and then exploring the various block cipher modes of use. The lab also covers DES. In both cases, an online Java applet is used (or can be downloaded) to execute AES or DES.

• Lab exercises: A series of projects that involve programming and experimenting with concepts from the book.

• Research projects: A series of research assignments that instruct the student to research a particular topic on the Internet and write a report.

• Programming projects: A series of programming projects that cover a broad range of topics and that can be implemented in any suitable language on any platform.

• Practical security assessments: A set of exercises to examine current infrastructure and practices of an existing organization.

• Firewall projects: A portable network firewall visualization simulator, together with exercises for teaching the fundamentals of firewalls.

• Case studies: A set of real-world case studies, including learning objectives, case description, and a series of case discussion questions.

• Writing assignments: A set of suggested writing assignments, organized by chapter.

• Reading/report assignments: A list of papers in the literature—one for each chapter—that can be assigned for the student to read and then write a short report.

• Discussion topics: These topics can be used in a classroom, chat room, or message board environment to explore certain areas in greater depth and to foster student collaboration.

This diverse set of projects and other student exercises enables the instructor to use the book as one component in a rich and varied learning experience and to tailor a course plan to meet the specific needs of the instructor and students.

One of the most important features of this book is the use of Sage for cryptographic examples and homework assignments. Sage is an open-source, multiplatform, freeware package that implements a very powerful, flexible, and easily learned mathematics and computer algebra system. Unlike competing systems (such as Mathematica, Maple, and MATLAB), there are no licensing agreements or fees involved. Thus, Sage can be made available on computers and networks at school, and students can individually download the software to their own personal computers for use at home. Another advantage of using Sage is that students learn a powerful, flexible tool that can be used for virtually any mathematical application, not just cryptography.

The use of Sage can make a significant difference to the teaching of the mathematics of cryptographic algorithms. Two documents available at the IRC support student use of Sage. The first document provides a large number of examples of the use of Sage covering many cryptographic concepts. The second document provides exercises in each of these topic areas to enable the student to gain hands-on experience with cryptographic algorithms. This appendix is available to instructors at the IRC for this book. It also includes a section on how to download and get started with Sage, a section on programming with Sage, and exercises that can be assigned to students in the following categories:

• Chapter 2—Introduction to Number Theory: Euclidean and extended Euclidean algorithms, polynomial arithmetic, GF(2⁴), Euler’s Totient function, Miller Rabin, factoring, modular exponentiation, discrete logarithm, and Chinese remainder theorem.

• Chapter 3—Classical Encryption Techniques: Affine ciphers and the Hill cipher.

• Chapter 4—Block Ciphers and the Data Encryption Standard: Exercises based on SDES.

• Chapter 6—Advanced Encryption Standard: Exercises based on SAES.

• Chapter 8—Random Bit Generation and Stream Ciphers: Blum Blum Shub, linear congruential generator, and ANSI X9.17 PRNG.

• Chapter 9—Public-Key Cryptography and RSA: RSA encrypt/decrypt and signing.

• Chapter 10—Other Public-Key Cryptosystems: Diffie-Hellman, elliptic curve.

• Chapter 11—Cryptographic Hash Functions: Number-theoretic hash function.

• Chapter 13—Digital Signatures: DSA.

This new edition has benefited from review by a number of people who gave generously of their time and expertise. The following people reviewed all or a large part of the manuscript: Hossein Beyzavi (Marymount University), Donald F. Costello (University of Nebraska Lincoln), James Haralambides (Barry University), Tenette Prevatte (Fayetteville Technical Community College), Anand Seetharam (California State University Monterey Bay), Tenette Prevatte (Fayetteville Technical Community College), Marius C. Silaghi (Florida Institute of Technology), Shambhu Upadhyaya (University at Buffalo), Rose Volynskiy (Howard Community College), Katherine Winters (University of Tennessee at Chattanooga), Zhengping Wu (California State University at San Bernardino), Liangliang Xiao (Frostburg State University), Seong-Moo (Sam) Yoo (The University of Alabama in Huntsville), and Hong Zhang (Armstrong State University).

Thanks also to the people who provided detailed technical reviews of one or more chapters: Amaury Behague, Olivier Blazy, Dhananjoy Dey, Matt Frost, Markus Koskinen, Manuel J. Martínez, Veena Nayak, Pritesh Prajapati, Bernard Roussely, Jim Sweeny, Jim Tunnicliffe, and Jose Rivas Vidal.

In addition, I was fortunate to have reviews of individual topics by “subject-area gurus,” including Jesse Walker of Intel (Intel’s Digital Random Number Generator), Russ Housley of Vigil Security (key wrapping), Joan Daemen (AES), Edward F. Schaefer of Santa Clara University (Simplified AES), Tim Mathews, formerly of RSA Laboratories (S/MIME), Alfred Menezes of the University of Waterloo (elliptic curve cryptography), William Sutton, Editor/Publisher of The Cryptogram (classical encryption), Avi Rubin of Johns Hopkins University (number theory), Michael Markowitz of Information Security Corporation (SHA and DSS), Don Davis of IBM Internet Security Systems (Kerberos), Steve Kent of BBN Technologies (X.509), and Phil Zimmerman (PGP).

Nikhil Bhargava (IIT Delhi) developed the set of online homework problems and solutions. Dan Shumow of Microsoft and the University of Washington developed all of the Sage examples and assignments. Professor Sreekanth Malladi of Dakota State University developed the hacking exercises. Lawrie Brown of the Australian Defence Force Academy provided the AES/DES block cipher projects and the security assessment assignments.

Sanjay Rao and Ruben Torres of Purdue University developed the laboratory exercises that appear in the IRC. The following people contributed project assignments that appear in the instructor’s supplement: Henning Schulzrinne (Columbia University); Cetin Kaya Koc (Oregon State University); and David Balenson (Trusted Information Systems and George Washington University). Kim McLaughlin developed the test bank.

Finally, I thank the many people responsible for the publication of this book, all of whom did their usual excellent job. This includes the staff at Pearson, particularly my editor Tracy Johnson and production manager Carole Snyder. Thanks also to the marketing and sales staffs at Pearson, without whose efforts this book would not be in front of you.

A comprehensive treatment of computer security technology, including algorithms, protocols, and applications. Covers cryptography, authentication, access control, database security, cloud security, intrusion detection and prevention, malicious software, denial of service, firewalls, software security, physical security, human factors, auditing, legal and ethical aspects, and trusted systems. Received the 2008 TAA award for the best Computer Science and Engineering Textbook of the year.

This book provides a practical guide to applying the vast body of Best Practices and Standards documents related to the implementation of cybersecurity. The objective of this book is to organize, consolidate, and explain all of this material to enable the reader to make effective use of it. The book covers the planning, managing, designing, implementing, and assessing cybersecurity functions and services in IT systems.

This book provides a practical guide to designing and implementing information privacy in IT systems. The book introduces information privacy concepts and discusses privacy requirements, threats, and vulnerabilities. The book discusses in detail the implementation of privacy controls, privacy management, and privacy monitoring and auditing. Finally, the book discusses legal and regulatory requirements, especially the EU General Data Protection Regulation and the body of U.S. privacy laws and regulations.

A tutorial and survey on network security technology. Each of the basic building blocks of network security, including conventional and public-key cryptography, authentication, and digital signatures, is covered. Provides a thorough mathematical background for such algorithms as AES and RSA. The book also covers the recent development of lightweight cryptography and post-quantum cryptography. The book covers important network security tools and applications, including S/MIME, IP Security, Kerberos, SSL/TLS, network access control, and Wi-Fi security. The second edition of this book received the TAA award for the best Computer Science and Engineering Textbook of 1999.

A tutorial and survey on network security technology. The book covers important network security tools and applications, including S/MIME, IP Security, Kerberos, SSL/TLS, network access control, and Wi-Fi security. In addition, methods for countering hackers and viruses are explored.

A state-of-the art survey of operating system principles. Covers fundamental technology as well as contemporary design issues, such as threads, SMPs, multicore, real-time systems, multiprocessor scheduling, embedded OSs, distributed systems, clusters, security, and object-oriented design. The third, fourth, and sixth editions received the TAA award for the best Computer Science and Engineering Textbook of the year.

A unified view of this broad field. Covers fundamentals such as CPU, control unit, microprogramming, instruction set, I/O, and memory. Also covers advanced topics such as multicore, superscalar, and parallel organization. This book is five-time winner of the TAA award for the best Computer Science and Engineering Textbook of the year.

A comprehensive survey that has become the standard in the field, covering (1) data communications, including transmission, media, signal encoding, link control, and multiplexing; (2) communication networks, including circuit- and packet-switched, frame relay, ATM, and LANs; (3) the TCP/IP protocol suite, including IPv6, TCP, MIME, and HTTP, as well as a detailed treatment of network security. Received the 2007 Text and Academic Authors Association (TAA) award for the best Computer Science and Engineering Textbook of the year.

A comprehensive, state-of-the art survey. Covers fundamental wireless communications topics, including antennas and propagation, signal encoding techniques, spread spectrum, and error correction techniques. Examines satellite, cellular, wireless local loop networks and wireless LANs, including Bluetooth and 802.11. Covers wireless mobile networks and applications.

An in-depth up-to-date survey and tutorial on Software Defined Networking, Network Functions Virtualization, Quality of Experience, Internet of Things, and Cloud Computing and Networking. Examines standards, technologies, and deployment issues. Also treats security and career topics.

Dr. William Stallings has authored 18 textbooks, and, counting revised editions, over 70 books on computer security, computer networking, and computer architecture. His writings have appeared in numerous ACM and IEEE publications, including the Proceedings of the IEEE and ACM Computing Reviews. He has received the award 13 times for the best Computer Science textbook of the year from the Text and Academic Authors Association.

In over 30 years in the field, he has been a technical contributor, technical manager, and an executive with several high-technology firms. He has designed and implemented both TCP/IP-based and OSI-based protocol suites on a variety of computers and operating systems, ranging from microcomputers to mainframes. Currently he is an independent consultant whose clients have included computer and networking manufacturers and customers, software development firms, and leading-edge government research institutions.

He created and maintains the Computer Science Student Resource Site at http://www.computersciencestudent.com/. This site provides documents and links on a variety of subjects of general interest to computer science students and professionals. He is a member of the editorial board of Cryptologia, a scholarly journal devoted to all aspects of cryptology.

Dr. Stallings holds a PhD from the Massachusetts Institute of Technology in Computer Science and a B.S. from Notre Dame in electrical engineering.

The cybersecurity definition introduces three key objectives that are at the heart of information and network security:

• Confidentiality: This term covers two related concepts:

  • – Data1 confidentiality: Assures that private or confidential information is not made available or disclosed to unauthorized individuals.

  • – Privacy: Assures that individuals control or influence what information related to them may be collected and stored and by whom and to whom that information may be disclosed.

• Integrity: This term covers two related concepts:

  • – Data integrity: Assures that data (both stored and in transmitted packets) and programs are changed only in a specified and authorized manner. This concept also encompasses data authenticity, which means that a digital object is indeed what it claims to be or what it is claimed to be, and nonrepudiation, which is assurance that the sender of information is provided with proof of delivery and the recipient is provided with proof of the sender’s identity, so neither can later deny having processed the information.

  • – System integrity: Assures that a system performs its intended function in an unimpaired manner, free from deliberate or inadvertent unauthorized manipulation of the system.

• Availability: Assures that systems work promptly and service is not denied to authorized users.

These three concepts form what is often referred to as the CIA triad. The three concepts embody the fundamental security objectives for both data and for information and computing services. For example, the NIST standard FIPS 199 (Standards for Security Categorization of Federal Information and Information Systems) lists confidentiality, integrity, and availability as the three security objectives for information and for information systems. FIPS 199 provides a useful characterization of these three objectives in terms of requirements and the definition of a loss of security in each category:

• Confidentiality: Preserving authorized restrictions on information access and disclosure, including means for protecting personal privacy and proprietary information. A loss of confidentiality is the unauthorized disclosure of information.

• Integrity: Guarding against improper information modification or destruction, including ensuring information nonrepudiation and authenticity. A loss of integrity is the unauthorized modification or destruction of information.

• Availability: Ensuring timely and reliable access to and use of information. A loss of availability is the disruption of access to or use of information or an information system.

Although the use of the CIA triad to define security objectives is well established, some in the security field feel that additional concepts are needed to present a complete picture (Figure 1.1). Two of the most commonly mentioned are as follows:

• Authenticity: The property of being genuine and being able to be verified and trusted; confidence in the validity of a transmission, a message, or message originator. This means verifying that users are who they say they are and that each input arriving at the system came from a trusted source.

• Accountability: The security goal that generates the requirement for actions of an entity to be traced uniquely to that entity. This supports nonrepudiation, deterrence, fault isolation, intrusion detection and prevention, and after-action recovery and legal action. Because truly secure systems are not yet an achievable goal, we must be able to trace a security breach to a responsible party. Systems must keep records of their activities to permit later forensic analysis to trace security breaches or to aid in transaction disputes.

Figure 1.1 Essential Information and Network Security Objectives

Information and network security are both fascinating and complex. Some of the reasons follow:

1. Security is not as simple as it might first appear to the novice. The requirements seem to be straightforward; indeed, most of the major requirements for security services can be given self-explanatory, one-word labels: confidentiality, authentication, nonrepudiation, and integrity. But the mechanisms used to meet those requirements can be quite complex, and understanding them may involve rather subtle reasoning.

2. In developing a particular security mechanism or algorithm, one must always consider potential attacks on those security features. In many cases, successful attacks are designed by looking at the problem in a completely different way, therefore exploiting an unexpected weakness in the mechanism.

3. Because of point 2, the procedures used to provide particular services are often counterintuitive. Typically, a security mechanism is complex, and it is not obvious from the statement of a particular requirement that such elaborate measures are needed. It is only when the various aspects of the threat are considered that elaborate security mechanisms make sense.

4. Having designed various security mechanisms, it is necessary to decide where to use them. This is true both in terms of physical placement (e.g., at what points in a network are certain security mechanisms needed) and in a logical sense [e.g., at what layer or layers of an architecture such as TCP/IP (Transmission Control Protocol/Internet Protocol) should mechanisms be placed].

5. Security mechanisms typically involve more than a particular algorithm or protocol. They also require that participants be in possession of some secret information (e.g., an encryption key), which raises questions about the creation, distribution, and protection of that secret information. There also may be a reliance on communications protocols whose behavior may complicate the task of developing the security mechanism. For example, if the proper functioning of the security mechanism requires setting time limits on the transit time of a message from sender to receiver, then any protocol or network that introduces variable, unpredictable delays may render such time limits meaningless.

6. Information and network security are essentially a battle of wits between a perpetrator who tries to find holes and the designer or administrator who tries to close them. The great advantage that the attacker has is that he or she need only find a single weakness, while the designer must find and eliminate all weaknesses to achieve perfect security.

7. There is a natural tendency on the part of users and system managers to perceive little benefit from security investment until a security failure occurs.

8. Security requires regular, even constant, monitoring, and this is difficult in today’s short-term, overloaded environment.

9. Security is still too often an afterthought to be incorporated into a system after the design is complete rather than being an integral part of the design process.

10. Many users and even security administrators view strong security as an impediment to efficient and user-friendly operation of an information system or use of information.

The difficulties just enumerated will be encountered in numerous ways as we examine the various security threats and mechanisms throughout this book.

Passive attacks are in the nature of eavesdropping on, or monitoring of, transmissions. The goal of the attacker is to obtain information that is being transmitted. Two types of passive attacks are the release of message contents and traffic analysis.

The release of message contents is easily understood. A telephone conversation, an electronic mail message, and a transferred file may contain sensitive or confidential information. We would like to prevent an opponent from learning the contents of these transmissions.

A second type of passive attack, traffic analysis, is subtler. Suppose that we had a way of masking the contents of messages or other information traffic so that opponents, even if they captured the message, could not extract the information from the message. The common technique for masking contents is encryption. If we had encryption protection in place, an opponent might still be able to observe the pattern of these messages. The opponent could determine the location and identity of communicating hosts and could observe the frequency and length of messages being exchanged. This information might be useful in guessing the nature of the communication that was taking place.

Passive attacks are very difficult to detect because they do not involve any alteration of the data. Typically, the message traffic is sent and received in an apparently normal fashion and neither the sender nor receiver is aware that a third party has read the messages or observed the traffic pattern. However, it is feasible to prevent the success of these attacks, usually by means of encryption. Thus, the emphasis in dealing with passive attacks is on prevention rather than detection.

Active attacks involve some modification of the data stream or the creation of a false stream and can be subdivided into four categories: replay, masquerade, modification of messages, and denial of service.

A masquerade takes place when one entity pretends to be a different entity. A masquerade attack usually includes one of the other forms of active attack. For example, authentication sequences can be captured and replayed after a valid authentication sequence has taken place, thus enabling an authorized entity with few privileges to obtain extra privileges by impersonating an entity that has those privileges.

Replay involves the passive capture of a data unit and its subsequent retransmission to produce an unauthorized effect.

Data modification simply means that some portion of a legitimate message is altered, or that messages are delayed or reordered, to produce an unauthorized effect. For example, a message stating, “Allow John Smith to read confidential file accounts” is modified to say, “Allow Fred Brown to read confidential file accounts.”

The denial of service prevents or inhibits the normal use or management of communication facilities. This attack may have a specific target; for example, an entity may suppress all messages directed to a particular destination (e.g., the security audit service). Another form of service denial is the disruption of an entire network, either by disabling the network or by overloading it with messages so as to degrade performance.

Active attacks present the opposite characteristics of passive attacks. Whereas passive attacks are difficult to detect, measures are available to prevent their success. On the other hand, it is quite difficult to prevent active attacks absolutely, because to do so would require physical protection of all communication facilities and paths at all times. Instead, the goal is to detect them and to recover from any disruption or delays caused by them. Because the detection has a deterrent effect, it may also contribute to prevention.

Figure 1.3 illustrates the types of attacks in the context of a client/server interaction. A passive attack (Figure 1.3b) does not disturb the information flow between the client and server, but is able to observe that flow.

Figure 1.3 Security Attacks

A masquerade can take the form of a man-in-the-middle attack (Figure 1.3c). In this type of attack, the attacker intercepts masquerades as the client to the server and as the server to the client. We see specific applications of this attack in defeating key exchange and distribution protocols (Chapters 10 and 14) and in message authentication protocols (Chapter 11). More generally, it can be used to impersonate the two ends of a legitimate communication. Another form of masquerade is illustrated in Figure 1.3d. Here, an attacker is able to access server resources by masquerading as an authorized user.

Data modification may involve a man-in-the middle attack, in which the attacker selectively modifies communicated data between a client and server (Figure 1.3c). Another form of data modification attack is the modification of data residing on a serve or other system after an attacker gains unauthorized access (Figure 1.3d).

Figure 1.3e illustrates the replay attack. As in a passive attack, the attacker does not disturb the information flow between client and server, but does capture client message. The attacker can then subsequently replay any client message to the server.

Figure 1.3d also illustrates denial of service in the context of a client/server environment. The denial of service can take two forms: (1) flooding the server with an overwhelming amount of data; and (2) triggering some action on the server that consumes substantial computing resources.

The authentication service is concerned with assuring that a communication is authentic. In the case of a single message, such as a warning or alarm signal, the function of the authentication service is to assure the recipient that the message is from the source that it claims to be from. In the case of an ongoing interaction, such as the connection of a client to a server, two aspects are involved. First, at the time of connection initiation, the service assures that the two entities are authentic, that is, that each is the entity that it claims to be. Second, the service must assure that the connection is not interfered with in such a way that a third party can masquerade as one of the two legitimate parties for the purposes of unauthorized transmission or reception.

Two specific authentication services are defined in X.800:

• Peer entity authentication: Provides for the corroboration of the identity of a peer entity in an association. Two entities are considered peers if they implement the same protocol in different systems; for example, two TCP modules in two communicating systems. Peer entity authentication is provided for use at the establishment of, or at times during the data transfer phase of, a connection. It attempts to provide confidence that an entity is not performing either a masquerade or an unauthorized replay of a previous connection.

• Data origin authentication: Provides for the corroboration of the source of a data unit. It does not provide protection against the duplication or modification of data units. This type of service supports applications like electronic mail, where there are no ongoing interactions between the communicating entities.

In the context of network security, access control is the ability to limit and control the access to host systems and applications via communications links. To achieve this, each entity trying to gain access must first be identified, or authenticated, so that access rights can be tailored to the individual.

Confidentiality is the protection of transmitted data from passive attacks. With respect to the content of a data transmission, several levels of protection can be identified. The broadest service protects all user data transmitted between two users over a period of time. For example, when a TCP connection is set up between two systems, this broad protection prevents the release of any user data transmitted over the TCP connection. Narrower forms of this service can also be defined, including the protection of a single message or even specific fields within a message. These refinements are less useful than the broad approach and may even be more complex and expensive to implement.

The other aspect of confidentiality is the protection of traffic flow from analysis. This requires that an attacker not be able to observe the source and destination, frequency, length, or other characteristics of the traffic on a communications facility.

As with confidentiality, integrity can apply to a stream of messages, a single message, or selected fields within a message. Again, the most useful and straightforward approach is total stream protection.

A connection-oriented integrity service, one that deals with a stream of messages, assures that messages are received as sent with no duplication, insertion, modification, reordering, or replays. The destruction of data is also covered under this service. Thus, the connection-oriented integrity service addresses both message stream modification and denial of service. On the other hand, a connectionless integrity service, one that deals with individual messages without regard to any larger context, generally provides protection against message modification only.

We can make a distinction between service with and without recovery. Because the integrity service relates to active attacks, we are concerned with detection rather than prevention. If a violation of integrity is detected, then the service may simply report this violation, and some other portion of software or human intervention is required to recover from the violation. Alternatively, there are mechanisms available to recover from the loss of integrity of data, as we will review subsequently. The incorporation of automated recovery mechanisms is, in general, the more attractive alternative.

Nonrepudiation prevents either sender or receiver from denying a transmitted message. Thus, when a message is sent, the receiver can prove that the alleged sender in fact sent the message. Similarly, when a message is received, the sender can prove that the alleged receiver in fact received the message.

Availability is the property of a system, or a system resource being accessible and usable upon demand by an authorized system entity, according to performance specifications for the system (i.e., a system is available if it provides services according to the system design whenever users request them). A variety of attacks can result in the loss of or reduction in availability. Some of these attacks are amenable to automated countermeasures, such as authentication and encryption, whereas others require some sort of physical action to prevent or recover from loss of availability of elements of a distributed system.

X.800 treats availability as a property to be associated with various security services. However, it makes sense to call out specifically an availability service. An availability service is one that protects a system to ensure its availability. This service addresses the security concerns raised by denial-of-service attacks. It depends on proper management and control of system resources and thus depends on access control service and other security services.

Keyless algorithms are deterministic functions that have certain properties useful for cryptography.

One important type of keyless algorithm is the cryptographic hash function. A hash function turns a variable amount of text into a small, fixed-length value called a hash value, hash code, or digest. A cryptographic hash function is one that has additional properties that make it useful as part of another cryptographic algorithm, such as a message authentication code or a digital signature.

A pseudorandom number generator produces a deterministic sequence of numbers or bits that has the appearance of being a truly random sequence. Although the sequence appears to lack any definite pattern, it will repeat after a certain sequence length. Nevertheless, for some cryptographic purposes this apparently random sequence is sufficient.

Single-key cryptographic algorithms depend on the use of a secret key. This key may be known to a single user; for example, this is the case for protecting stored data that is only going to be accessed by the data creator. Commonly, two parties share the secret key so that communication between the two parties is protected. For certain applications, more than two users may share the same secret key. In this last case, the algorithm protects data from those outside the group who share the key.

Encryption algorithms that use a single key are referred to as symmetric encryption algorithms. With symmetric encryption, an encryption algorithm takes as input some data to be protected and a secret key and produces an unintelligible transformation on that data. A corresponding decryption algorithm takes the transformed data and the same secret key and recovers the original data. Symmetric encryption takes the following forms:

• Block cipher: A block cipher operates on data as a sequence of blocks. A typical block size is 128 bits. In most versions of the block cipher, known as modes of operation, the transformation depends not only on the current data block and the secret key but also on the content of preceding blocks.

• Stream cipher: A stream cipher operates on data as a sequence of bits. Typically, an exclusive-OR operation is used to produce a bit-by-bit transformation. As with the block cipher, the transformation depends on a secret key.

Another form of single-key cryptographic algorithm is the message authentication code (MAC). A MAC is a data element associated with a data block or message. The MAC is generated by a cryptographic transformation involving a secret key and, typically, a cryptographic hash function of the message. The MAC is designed so that someone in possession of the secret key can verify the integrity of the message. Thus, the MAC algorithm takes as input a message and secret key and produces the MAC. The recipient of the message plus the MAC can perform the same calculation on the message; if the calculated MAC matches the MAC accompanying the message, this provides assurance that the message has not been altered.

Two-key algorithms involve the use of two related keys. A private key is known only to a single user or entity, whereas the corresponding public key is made available to a number of users. Encryption algorithms that use two keys are referred to as asymmetric encryption algorithms. Asymmetric encryption can work in two ways:

1. An encryption algorithm takes as input some data to be protected and the private key and produces an unintelligible transformation on that data. A corresponding decryption algorithm takes the transformed data and the corresponding public key and recovers the original data. In this case, only the possessor of the private key can have performed the encryption and any possessor of the public key can perform the decryption.

2. An encryption algorithm takes as input some data to be protected and a public key and produces an unintelligible transformation on that data. A corresponding decryption algorithm takes the transformed data and the corresponding private key and recovers the original data. In this case, any possessor of the public key can have performed the encryption and only the possessor of the private key can perform the decryption.

Asymmetric encryption has a variety of applications. One of the most important is the digital signature algorithm. A digital signature is a value computed with a cryptographic algorithm and associated with a data object in such a way that any recipient of the data can use the signature to verify the data’s origin and integrity. Typically, the signer of a data object uses the signer’s private key to generate the signature, and anyone in possession of the corresponding public key can verify that validity of the signature.

Asymmetric algorithms can also be used in two other important applications. Key exchange is the process of securely distributing a symmetric key to two or more parties. User authentication is the process of authenticating that a user attempting to access an application or service is genuine and, similarly, that the application or service is genuine. These concepts are explained in detail in subsequent chapters.

In the context of network security, communications security deals with the protection of communications through the network, including measures to protect against both passive and active attacks (Figure 1.3).

Communications security is primarily implemented using network protocols. A network protocol consists of the format and procedures that governs the transmitting and receiving of data between points in a network. A protocol defines the structure of the individual data units (e.g., packets) and the control commands that manage the data transfer.

With respect to network security, a security protocol may be an enhancement that is part of an existing protocol or a standalone protocol. Examples of the former are IPsec, which is part of the Internet Protocol (IP) and IEEE 802.11i, which is part of the IEEE 802.11 Wi-Fi standard. Examples of the latter are Transport Layer Security (TLS) and Secure Shell (SSH). Part Six examines these and other secure network protocols.

One common characteristic of all of these protocols is that they use a number of cryptographic algorithms as part of the mechanism to provide security.

The other aspect of network security is the protection of network devices, such as routers and switches, and end systems connected to the network, such as client systems and servers. The primary security concerns are intruders that gain access to the system to perform unauthorized actions, insert malicious software (malware), or overwhelm system resources to diminish availability. Three types of device security are noteworthy:

• Firewall: A hardware and/or software capability that limits access between a network and devices attached to the network, in accordance with a specific security policy. The firewall acts as a filter that permits or denies data traffic, both incoming and outgoing, using a set of rules based on traffic content and/or traffic pattern.

• Intrusion detection: Hardware or software products that gather and analyze information from various areas within a computer or a network for the purpose of finding, and providing real-time or near-real-time warning of, attempts to access system resources in an unauthorized manner.

• Intrusion prevention: Hardware or software products designed to detect intrusive activity and attempt to stop the activity, ideally before it reaches its target.

These device security capabilities are more closely related to the field of computer security than network security. Accordingly, they are dealt with more briefly than communications security in Part Six. For a more detailed treatment, see [STAL18].

One of the most widely accepted and most cited definitions of trust in the organizational science literature is from [MAYE95], which defines trust as follows: the willingness of a party to be vulnerable to the actions of another party based on the expectation that the other will perform a particular action important to the truster, irrespective of the ability to monitor or control that other party.

Three related concepts are relevant to a trust model:

• Trustworthiness: A characteristic of an entity that reflects the degree to which that entity is deserving of trust.

• Propensity to trust: A tendency to be willing to trust others across a broad spectrum of situations and trust targets. This suggests that every individual has some baseline level of trust that will influence the person’s willingness to rely on the words and actions of others.

• Risk: A measure of the extent to which an entity is threatened by a potential circumstance or event, and typically a function of 1) the adverse impacts that would arise if the circumstance or event occurs; and 2) the likelihood of occurrence.

Figure 1.6, adapted from [MAYE95], illustrates the relationship among these concepts. Trust is a function of the truster’s propensity to trust and the perceived trustworthiness of the trustee. Propensity can also be expressed as the level of risk that an entity (individual or organization) is prepared to tolerate.

Figure 1.6 Trust Model

Typically, a truster uses a number of factors to establish the trustworthiness of an entity. Three general factors are commonly cited:

• Ability: Also referred to as competence, this relates to the potential ability of the evaluated entity to do a given task or be entrusted with given information.

• Benevolence: This implies a disposition of goodwill towards the trusting party. That is, a trustworthy party does not intend to cause harm to the trusting party.

• Integrity: This can be defined as the truster’s perception that the trustee adheres to a set of principles that the truster finds acceptable. Integrity implies that a benevolent party takes such measures are necessary to assure that it in fact does not cause harm to the trusting party.

The goal of trust, in the model of Figure 1.6, is to determine what course of action, if any, the trusting party is willing to take in relation to the trusted party. Based on the level of trust, and the perceived risk, the trusting party may decide to take some action that involves some degree of risk taking. The outcome of the risk taking could be a reliance on the trusted party to perform some action or the disclosure of information to the trusted party with the expectation that the information will be protected as agreed between the parties.

Trust is confidence that an entity will perform in a way the will not prejudice the security of the user of the system of which that entity is a part. Trust is always restricted to specific functions or ways of behavior and is meaningful only in the context of a security policy. Generally, an entity is said to trust a second entity when the first entity assumes that the second entity will behave exactly as the first entity expects. This trust may apply only for some specific function. In this context, the term entity may refer to a single hardware component or software module, a piece of equipment identified by make and model, a site or location, or an organization.

The methods used by an organization to establish a trust relationship with various entities will depend on a variety of factors, such as laws and regulations, risk tolerance, and the criticality and sensitivity of the relationship. SP 800-39 describes the following methods:

• Validated trust: Trust is based on evidence obtained by the trusting organization about the trusted organization or entity. The information may include information security policy, security measures, and level of oversight. An example would be for one organization to develop an application or information system and provide evidence (e.g., security plan, assessment results) to a second organization that supports the claims by the first organization that the application/system meets certain security requirements and/or addresses the appropriate security controls.

• Direct historical trust: This type of trust is based on the security-related track record exhibited by an organization in the past, particularly in interactions with the organization seeking to establish trust.

• Mediated trust: Mediated trust involves the use of a third party that is mutually trusted by two parties, with the third party providing assurance or guarantee of a given level of trust between the first two parties. An example of this form of trust establishment is the use of public-key certificate authorities, described in Chapter 14.

• Mandated trust: An organization establishes a level of trust with another organization based on a specific mandate issued by a third party in a position of authority. For example, an organization may be given the responsibility and the authority to issue public key certificates for a group of organizations.

An organization is likely to use a combination of these methods to establish relationships with a number of other entities.

• access control

• active attack

• asymmetric encryption algorithms

• attack

• authentication

• authentication exchange

• authenticity

• availability

• block cipher

• confidentiality

• cryptographic hash function

• cryptography

• cybersecurity

• data authenticity

• data confidentiality

• data integrity

• data origin authentication

• denial of service

• digital signature algorithms

• eavesdropping

• encryption

• firewall

• information security

• intrusion detection

• intrusion prevention

• key exchange

• keyless algorithm

• man-in-the-middle attack

• masquerade

• message authentication code

• network security

• notarization

• OSI security architecture

• passive attack

• peer entity authentication

• privacy

• pseudorandom number generator

• replay

• routing control

• security attack

• security mechanism

• security service

• single-key algorithm

• stream cipher

• symmetric encryption algorithms

• system integrity

• threat

• trust

• trust relationship

• trustworthiness

• two-key algorithm

• user authentication

We say that a nonzero divides if for some , where , and are integers. That is, divides if there is no remainder on division. The notation is commonly used to mean divides . Also, if we say that is a divisor of .

Subsequently, we will need some simple properties of divisibility for integers, which are as follows:

• If then

• If and then

• Any divides 0.

• If and then

• If and then for arbitrary integers and .

To see this last point, note that

• If then is of the form for some integer

• If then is of the form for some integer

So

and therefore divides

Given any positive integer and any nonnegative integer , if we divide by , we get an integer quotient and an integer remainder that obey the following relationship:

where is the largest integer less than or equal to . Equation (2.1) is referred to as the division algorithm.1

Figure 2.1a demonstrates that, given and positive , it is always possible to find and that satisfy the preceding relationship. Represent the integers on the number line; will fall somewhere on that line (positive is shown, a similar demonstration can be made for negative ). Starting at 0, proceed to , , up to , such that and The distance from to is , and we have found the unique values of and . The remainder is often referred to as a residue.

Figure 2.1 The Relationship

Recall that nonzero is defined to be a divisor of if for some , where , and are integers. We will use the notation gcd() to mean the greatest common divisor of and . The greatest common divisor of and is the largest integer that divides both and . We also define

More formally, the positive integer is said to be the greatest common divisor of and if

1. is a divisor of and of .

2. any divisor of and is a divisor of .

An equivalent definition is the following:

Because we require that the greatest common divisor be positive, In general,

Also, because all nonzero integers divide 0, we have

We stated that two integers and are relatively prime if and only if their only common positive integer factor is 1. This is equivalent to saying that and are relatively prime if

We now describe an algorithm credited to Euclid for easily finding the greatest common divisor of two integers (Figure 2.2). This algorithm has broad significance in cryptography. The explanation of the algorithm can be broken down into the following points:

1. Suppose we wish to determine the greatest common divisor of the integers and ; that is determine Because there is no harm in assuming

2. Dividing by and applying the division algorithm, we can state:

   (2.2)

3. First consider the case in which Therefore divides and clearly no larger number divides both and because that number would be larger than . So we have

4. The other possibility from Equation (2.2) is For this case, we can state that This is due to the basic properties of divisibility: the relations and together imply that which is the same as

5. Before proceeding with the Euclidian algorithm, we need to answer the question: What is the We know that and Now take any arbitrary integer that divides both and Therefore, Because divides both and , we must have which is the greatest common divisor of and . Therefore

Figure 2.2 Euclidean Algorithm

Let us now return to Equation (2.2) and assume that Because we can divide by and apply the division algorithm to obtain:

As before, if then and if then Note that the remainders form a descending series of nonnegative values and so must terminate when the remainder is zero. This happens, say, at the stage where is divided by The result is the following system of equations:

At each iteration, we have until finally Thus, we can find the greatest common divisor of two integers by repetitive application of the division algorithm. This scheme is known as the Euclidean algorithm. Figure 2.3 illustrates a simple example.

Figure 2.3 Euclidean Algorithm Example: gcd(710, 310)

We have essentially argued from the top down that the final result is the gcd(). We can also argue from the bottom up. The first step is to show that divides and . It follows from the last division in Equation (2.3) that divides The next to last division shows that divides because it divides both terms on the right. Successively, one sees that divides all and finally and . It remains to show that is the largest divisor that divides and . If we take any arbitrary integer that divides and , it must also divide as explained previously. We can follow the sequence of equations in Equation (2.3) down and show that must divide all Therefore must divide so that

Let us now look at an example with relatively large numbers to see the power of this algorithm:

In this example, we begin by dividing 1160718174 by 316258250, which gives 3 with a remainder of 211943424. Next we take 316258250 and divide it by 211943424. The process continues until we get a remainder of 0, yielding a result of 1078.

It will be helpful in what follows to recast the above computation in tabular form. For every step of the iteration, we have where is the dividend, is the divisor, is the quotient, and is the remainder. Table 2.1 summarizes the results.

If is an integer and is a positive integer, we define mod to be the remainder when is divided by . The integer is called the modulus. Thus, for any integer , we can rewrite Equation (2.1) as follows:

Two integers and are said to be congruent modulo , if This is written as 2

Note that if then

Congruences have the following properties:

1. if

2. implies

3. and imply

To demonstrate the first point, if then for some . So we can write Therefore,

The remaining points are as easily proved.

Note that, by definition (Figure 2.1), the (mod ) operator maps all integers into the set of integers This suggests the question: Can we perform arithmetic operations within the confines of this set? It turns out that we can; this technique is known as modular arithmetic.

Modular arithmetic exhibits the following properties:

We demonstrate the first property. Define and Then we can write for some integer and for some integer . Then

The remaining properties are proven as easily. Here are examples of the three properties:

Exponentiation is performed by repeated multiplication, as in ordinary arithmetic.

Thus, the rules for ordinary arithmetic involving addition, subtraction, and multiplication carry over into modular arithmetic.

Table 2.2 provides an illustration of modular addition and multiplication modulo 8. Looking at addition, the results are straightforward, and there is a regular pattern to the matrix. Both matrices are symmetric about the main diagonal in conformance to the commutative property of addition and multiplication. As in ordinary addition, there is an additive inverse, or negative, to each integer in modular arithmetic. In this case, the negative of an integer is the integer such that To find the additive inverse of an integer in the left-hand column, scan across the corresponding row of the matrix to find the value 0; the integer at the top of that column is the additive inverse; thus, Similarly, the entries in the multiplication table are straightforward. In modular arithmetic mod 8, the multiplicative inverse of is the integer such that Now, to find the multiplicative inverse of an integer from the multiplication table, scan across the matrix in the row for that integer to find the value 1; the integer at the top of that column is the multiplicative inverse; thus, Note that not all integers mod 8 have a multiplicative inverse; more about that later.

Define the set as the set of nonnegative integers less than :

This is referred to as the set of residues, or residue classes (mod ). To be more precise, each integer in represents a residue class. We can label the residue classes (mod ) as , where

Of all the integers in a residue class, the smallest nonnegative integer is the one used to represent the residue class. Finding the smallest nonnegative integer to which is congruent modulo is called reducing modulo .

If we perform modular arithmetic within the properties shown in Table 2.3 hold for integers in We show in Chapter 5 that this implies that is a commutative ring with a multiplicative identity element.

There is one peculiarity of modular arithmetic that sets it apart from ordinary arithmetic. First, observe that (as in ordinary arithmetic) we can write the following:

Equation (2.4) is consistent with the existence of an additive inverse. Adding the additive inverse of to both sides of Equation (2.4), we have

However, the following statement is true only with the attached condition:

Recall that two integers are relatively prime if their only common positive integer factor is 1. Similar to the case of Equation (2.4), we can say that Equation (2.5) is consistent with the existence of a multiplicative inverse. Applying the multiplicative inverse of to both sides of Equation (2.5), we have

The reason for this strange result is that for any general modulus , a multiplier that is applied in turn to the integers 0 through will fail to produce a complete set of residues if and have any factors in common.

In general, an integer has a multiplicative inverse in if and only if that integer is relatively prime to . Table 2.2c shows that the integers 1, 3, 5, and 7 have a multiplicative inverse in but 2, 4, and 6 do not.

The Euclidean algorithm can be based on the following theorem: For any integers , with

To see that Equation (2.6) works, let Then, by the definition of gcd, and For any positive integer , we can express as

with integers. Therefore, for some integer . But because it also divides . We also have Therefore, This shows that is a common divisor of and ( mod ). Conversely, if is a common divisor of and ( mod ), then and thus which is equivalent to Thus, the set of common divisors of and is equal to the set of common divisors of and ( mod ). Therefore, the gcd of one pair is the same as the gcd of the other pair, proving the theorem.

Equation (2.6) can be used repetitively to determine the greatest common divisor.

This is the same scheme shown in Equation (2.3), which can be rewritten in the following way.

We can define the Euclidean algorithm concisely as the following recursive function.

Euclid(a,b)
    if (b=0) then return a;
    else return Euclid(b, a mod b);

We now proceed to look at an extension to the Euclidean algorithm that will be important for later computations in the area of finite fields and in encryption algorithms, such as RSA. For given integers and , the extended Euclidean algorithm not only calculates the greatest common divisor but also two additional integers and that satisfy the following equation.

It should be clear that and will have opposite signs. Before examining the algorithm, let us look at some of the values of and when and Note that Here is a partial table of values3 for

Observe that all of the entries are divisible by 6. This is not surprising, because both 42 and 30 are divisible by 6, so every number of the form is a multiple of 6. Note also that appears in the table. In general, it can be shown that for given integers and , the smallest positive value of is equal to gcd().

Now let us show how to extend the Euclidean algorithm to determine () given and . We again go through the sequence of divisions indicated in Equation (2.3), and we assume that at each step we can find integers and that satisfy We end up with the following sequence.

Now, observe that we can rearrange terms to write

Also, in rows and we find the values

Substituting into Equation (2.8), we have

But we have already assumed that Therefore,

We now summarize the calculations:

We need to make several additional comments here. In each row, we calculate a new remainder based on the remainders of the previous two rows, namely and To start the algorithm, we need values for and which are just and . It is then straightforward to determine the required values for and

We know from the original Euclidean algorithm that the process ends with a remainder of zero and that the greatest common divisor of and is But we also have determined that Therefore, in Equation (2.7), and

As an example, let us use and and solve for The results are shown in Table 2.4. Thus, we have

Fermat’s theorem states the following: If is prime and is a positive integer not divisible by , then

Proof: Consider the set of positive integers less than and multiply each element by , modulo , to get the set None of the elements of is equal to zero because does not divide . Furthermore, no two of the integers in are equal. To see this, assume that where Because is relatively prime7 to , we can eliminate from both sides of the equation [see Equation (2.5)] resulting in This last equality is impossible, because and are both positive integers less than . Therefore, we know that the elements of are all positive integers with no two elements equal. We can conclude the consists of the set of integers in some order. Multiplying the numbers in both sets ( and ) and taking the result mod yields

We can cancel the term because it is relatively prime to [see Equation (2.5)]. This yields Equation (2.10), which completes the proof.

An alternative form of Fermat’s theorem is also useful: If is prime and is a positive integer, then

Note that the first form of the theorem [Equation (2.10)] requires that be relatively prime to , but this Equation (2.11) does not.

Before presenting Euler’s theorem, we need to introduce an important quantity in number theory, referred to as Euler’s totient function. This function, written is defined as the number of positive integers less than and relatively prime to . By convention,

Table 2.6 lists the first 30 values of The value is without meaning but is defined to have the value 1.

It should be clear that, for a prime number ,

Now suppose that we have two prime numbers and with Then we can show that, for

To see that consider that the set of positive integers less than is the set The integers in this set that are not relatively prime to are the set and the set To see this, consider that any integer that divides must divide either of the prime numbers or . Therefore, any integer that does not contain either or as a factor is relatively prime to . Further note that the two sets just listed are non-overlapping: Because and are prime, we can state that none of the integers in the first set can be written as a multiple of , and none of the integers in the second set can be written as a multiple of . Thus the total number of unique integers in the two sets is Accordingly,

Euler’s theorem states that for every and that are relatively prime:

Proof: Equation (2.12) is true if is prime, because in that case, and Fermat’s theorem holds. However, it also holds for any integer . Recall that is the number of positive integers less than that are relatively prime to . Consider the set of such integers, labeled as

That is, each element of is a unique positive integer less than with Now multiply each element by , modulo :

The set is a permutation8 of , by the following line of reasoning:

1. Because is relatively prime to and is relatively prime to , must also be relatively prime to . Thus, all the members of are integers that are less than and that are relatively prime to .

2. There are no duplicates in . Refer to Equation (2.5). If

Therefore,

which completes the proof. This is the same line of reasoning applied to the proof of Fermat’s theorem.

As is the case for Fermat’s theorem, an alternative form of the theorem is also useful:

Again, similar to the case with Fermat’s theorem, the first form of Euler’s theorem [Equation (2.12)] requires that be relatively prime to , but this form does not. It is sufficient for Equation (2.13) that is squarefree. An integer is squarefree if its prime decomposition contains no repeated factors.

The algorithm due to Miller and Rabin [MILL75, RABI80] is typically used to test a large number for primality. Before explaining the algorithm, we need some back-ground. First, any positive odd integer can be expressed as

To see this, note that is an even integer. Then, divide by 2 until the result is an odd number , for a total of divisions. If is expressed as a binary number, then the result is achieved by shifting the number to the right until the rightmost digit is a 1, for a total of shifts. We now develop two properties of prime numbers that we will need.

TEST (n)
1. Find integers , , with k > 0,  odd, so that (n − 1 = 2k q);
2. Select a random integer , 1 < a < n - 1;
3. if aq mod n = 1 then return(”inconclusive”);
4. for j = 0 to k - 1 do
5. if  n = n - 1 then return(”inconclusive”);
6. return(”composite”);

Prior to 2002, there was no known method of efficiently proving the primality of very large numbers. All of the algorithms in use, including the most popular (Miller–Rabin), produced a probabilistic result. In 2002 (announced in 2002, published in 2004), Agrawal, Kayal, and Saxena [AGRA04] developed a relatively simple deterministic algorithm that efficiently determines whether a given large number is a prime. The algorithm, known as the AKS algorithm, does not appear to be as efficient as the Miller–Rabin algorithm. Thus far, it has not supplanted this older, probabilistic technique.

It is worth noting how many numbers are likely to be rejected before a prime number is found using the Miller–Rabin test, or any other test for primality. A result from number theory, known as the prime number theorem, states that the primes near are spaced on the average one every ln () integers. Thus, on average, one would have to test on the order of ln() integers before a prime is found. Because all even integers can be immediately rejected, the correct figure is 0.5 ln(). For example, if a prime on the order of magnitude of were sought, then about   trials would be needed to find a prime. However, this figure is just an average. In some places along the number line, primes are closely packed, and in other places there are large gaps.

Recall from Euler’s theorem [Equation (2.12)] that, for every and that are relatively prime,

where Euler’s totient function, is the number of positive integers less than and relatively prime to . Now consider the more general expression:

If and are relatively prime, then there is at least one integer that satisfies Equation (2.18), namely, The least positive exponent for which Equation (2.18) holds is referred to in several ways:

• The order of (mod )

• The exponent to which belongs (mod )

• The length of the period generated by

Table 2.7 shows all the powers of , modulo 19 for all positive The length of the sequence for each base value is indicated by shading. Note the following:

1. All sequences end in 1. This is consistent with the reasoning of the preceding few paragraphs.

2. The length of a sequence divides That is, an integral number of sequences occur in each row of the table.

3. Some of the sequences are of length 18. In this case, it is said that the base integer generates (via powers) the set of nonzero integers modulo 19. Each such integer is called a primitive root of the modulus 19.

More generally, we can say that the highest possible exponent to which a number can belong (mod ) is If a number is of this order, it is referred to as a primitive root of . The importance of this notion is that if is a primitive root of , then its powers

are distinct (mod ) and are all relatively prime to . In particular, for a prime number , if is a primitive root of , then

are distinct (mod ). For the prime number 19, its primitive roots are 2, 3, 10, 13, 14, and 15.

Not all integers have primitive roots. In fact, the only integers with primitive roots are those of the form 2, 4, and where is any odd prime and is a positive integer. The proof is not simple but can be found in many number theory books, including [ORE76].

With ordinary positive real numbers, the logarithm function is the inverse of exponentiation. An analogous function exists for modular arithmetic.

Let us briefly review the properties of ordinary logarithms. The logarithm of a number is defined to be the power to which some positive base (except 1) must be raised in order to equal the number. That is, for base and for a value ,

The properties of logarithms include

Consider a primitive root for some prime number (the argument can be developed for nonprimes as well). Then we know that the powers of from 1 through produce each integer from 1 through exactly once. We also know that any integer satisfies

by the definition of modular arithmetic. It follows that for any integer and a primitive root of prime number , we can find a unique exponent such that

This exponent is referred to as the discrete logarithm of the number for the base (mod ). We denote this value as 11

Note the following:

Now consider

Using the rules of modular multiplication,

But now consider Euler’s theorem, which states that, for every and that are relatively prime,

Any positive integer can be expressed in the form with Therefore, by Euler’s theorem,

Applying this to the foregoing equality, we have

and generalizing,

This demonstrates the analogy between true logarithms and discrete logarithms.

Keep in mind that unique discrete logarithms mod to some base exist only if is a primitive root of .

Table 2.8, which is directly derived from Table 2.7, shows the sets of discrete logarithms that can be defined for modulus 19.

Consider the equation

Given , , and , it is a straightforward matter to calculate . At the worst, we must perform repeated multiplications, and algorithms exist for achieving greater efficiency (see Chapter 9).

However, given , , and , it is, in general, very difficult to calculate (take the discrete logarithm). The difficulty seems to be on the same order of magnitude as that of factoring primes required for RSA. At the time of this writing, the asymptotically fastest known algorithm for taking discrete logarithms modulo a prime number is on the order of [BETH91]:

which is not feasible for large primes.

• bijection

• commutative

• composite number

• discrete logarithm

• divisor

• greatest common divisor

• identity element

• index

• modular arithmetic

• modulus

• order

• prime number

• primitive root

• relatively prime

• residue

The operator mod is used in this book and in the literature in two different ways: as a binary operator and as a congruence relation. This appendix explains the distinction and precisely defines the notation used in this book regarding parentheses. This notation is common but, unfortunately, not universal.

If is an integer and is a positive integer, we define mod to be the remainder when is divided by . The integer is called the modulus, and the remainder is called the residue. Thus, for any integer , we can always write

Formally, we define the operator mod as

As a binary operation, mod takes two integer arguments and returns the remainder. For example, The arguments may be integers, integer variables, or integer variable expressions. For example, all of the following are valid, with the obvious meanings:

where all of the variables are integers. For each of the above expressions, the value is the remainder that results when the left-hand term is divided by the right-hand term [see Equation (2.1)]. Note that if either the left- or right-hand argument is an expression, the expression is parenthesized. The operator mod is not inside parentheses.

In fact, the mod operation also works if the two arguments are arbitrary real numbers, not just integers. In this book, we are concerned only with the integer operation.

As a congruence relation, mod expresses that two arguments have the same remainder with respect to a given modulus. For example, expresses the fact that both 7 and 4 have a remainder of 1 when divided by 3. The following two expressions are equivalent:

Another way of expressing it is to say that the expression is the same as saying that is an integral multiple of . Again, all the arguments may be integers, integer variables, or integer variable expressions. For example, all of the following are valid, with the obvious meanings:

where all of the variables are integers. Two conventions are used. The congruence sign is The modulus for the relation is defined by placing the mod operator followed by the modulus in parentheses.

The congruence relation is used to define residue classes. Those numbers that have the same remainder when divided by form a residue class (mod ). There are residue classes (mod ). For a given remainder , the residue class to which it belongs consists of the numbers

According to our definition, the congruence

signifies that the numbers and differ by a multiple of . Consequently, the congruence can also be expressed in the terms that and belong to the same residue class (mod ).

Cryptographic systems are characterized along three independent dimensions:

1. The type of operations used for transforming plaintext to ciphertext. All encryption algorithms are based on two general principles: substitution, in which each element in the plaintext (bit, letter, group of bits or letters) is mapped into another element, and transposition, in which elements in the plaintext are rearranged. The fundamental requirement is that no information be lost (i.e., that all operations are reversible). Most systems, referred to as product systems, involve multiple stages of substitutions and transpositions.

2. The number of keys used. If both sender and receiver use the same key, the system is referred to as symmetric, single-key, secret-key, or conventional encryption. If the sender and receiver use different keys, the system is referred to as asymmetric, two-key, or public-key encryption.

3. The way in which the plaintext is processed. A block cipher processes the input one block of elements at a time, producing an output block for each input block. A stream cipher processes the input elements continuously, producing output one element at a time, as it goes along.

Typically, the objective of attacking an encryption system is to recover the key in use rather than simply to recover the plaintext of a single ciphertext. There are two general approaches to attacking a conventional encryption scheme:

• Cryptanalysis: Cryptanalytic attacks rely on the nature of the algorithm plus perhaps some knowledge of the general characteristics of the plaintext or even some sample plaintext–ciphertext pairs. This type of attack exploits the characteristics of the algorithm to attempt to deduce a specific plaintext or to deduce the key being used.

• Brute-force attack: The attacker tries every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained. On average, half of all possible keys must be tried to achieve success.

If either type of attack succeeds in deducing the key, the effect is catastrophic: All future and past messages encrypted with that key are compromised.

The earliest known, and the simplest, use of a substitution cipher was by Julius Caesar. The Caesar cipher involves replacing each letter of the alphabet with the letter standing three places further down the alphabet. For example,

plain:  meet me after the toga party
cipher: PHHW PH DIWHU WKH WRJD SDUWB

Note that the alphabet is wrapped around, so that the letter following Z is A. We can define the transformation by listing all possibilities, as follows:

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

Let us assign a numerical equivalent to each letter:

Then the algorithm can be expressed as follows. For each plaintext letter , substitute the ciphertext letter 2

A shift may be of any amount, so that the general Caesar algorithm is

where takes on a value in the range 1 to 25. The decryption algorithm is simply

If it is known that a given ciphertext is a Caesar cipher, then a brute-force cryptanalysis is easily performed: simply try all the 25 possible keys. Figure 3.3 shows the results of applying this strategy to the example ciphertext. In this case, the plaintext leaps out as occupying the third line.

Figure 3.3 Brute-Force Cryptanalysis of Caesar Cipher

Three important characteristics of this problem enabled us to use a brute-force cryptanalysis:

1. The encryption and decryption algorithms are known.

2. There are only 25 keys to try.

3. The language of the plaintext is known and easily recognizable.

In most networking situations, we can assume that the algorithms are known. What generally makes brute-force cryptanalysis impractical is the use of an algorithm that employs a large number of keys. For example, the triple DES algorithm, examined in Chapter 7, makes use of a 168-bit key, giving a key space of or greater than possible keys.

The third characteristic is also significant. If the language of the plaintext is unknown, then plaintext output may not be recognizable. Furthermore, the input may be abbreviated or compressed in some fashion, again making recognition difficult. For example, Figure 3.4 shows a portion of a text file compressed using an algorithm called ZIP. If this file is then encrypted with a simple substitution cipher (expanded to include more than just 26 alphabetic characters), then the plaintext may not be recognized when it is uncovered in the brute-force cryptanalysis.

Figure 3.4 Sample of Compressed Text

With only 25 possible keys, the Caesar cipher is far from secure. A dramatic increase in the key space can be achieved by allowing an arbitrary substitution. Before proceeding, we define the term permutation. A permutation of a finite set of elements is an ordered sequence of all the elements of , with each element appearing exactly once. For example, if there are six permutations of :

In general, there are ! permutations of a set of elements, because the first element can be chosen in one of ways, the second in ways, the third in ways, and so on.

Recall the assignment for the Caesar cipher:

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

If, instead, the “cipher” line can be any permutation of the 26 alphabetic characters, then there are 26! or greater than possible keys. This is 10 orders of magnitude greater than the key space for DES and would seem to eliminate brute-force techniques for cryptanalysis. Such an approach is referred to as a monoalphabetic substitution cipher, because a single cipher alphabet (mapping from plain alphabet to cipher alphabet) is used per message.

There is, however, another line of attack. If the cryptanalyst knows the nature of the plaintext (e.g., noncompressed English text), then the analyst can exploit the regularities of the language. To see how such a cryptanalysis might proceed, we give a partial example here that is adapted from one in [SINK09]. The ciphertext to be solved is

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

As a first step, the relative frequency of the letters can be determined and compared to a standard frequency distribution for English, such as is shown in Figure 3.5 (based on [LEWA00]). If the message were long enough, this technique alone might be sufficient, but because this is a relatively short message, we cannot expect an exact match. In any case, the relative frequencies of the letters in the ciphertext (in percentages) are as follows:

Figure 3.5 Relative Frequency of Letters in English Text

Comparing this breakdown with Figure 3.5, it seems likely that cipher letters P and Z are the equivalents of plain letters e and t, but it is not certain which is which. The letters S, U, O, M, and H are all of relatively high frequency and probably correspond to plain letters from the set The letters with the lowest frequencies (namely, A, B, G, Y, I, J) are likely included in the set

There are a number of ways to proceed at this point. We could make some tentative assignments and start to fill in the plaintext to see if it looks like a reasonable “skeleton” of a message. A more systematic approach is to look for other regularities. For example, certain words may be known to be in the text. Or we could look for repeating sequences of cipher letters and try to deduce their plaintext equivalents.

A powerful tool is to look at the frequency of two-letter combinations, known as digrams. A table similar to Figure 3.5 could be drawn up showing the relative frequency of digrams. The most common such digram is th. In our ciphertext, the most common digram is ZW, which appears three times. So we make the correspondence of Z with t and W with h. Then, by our earlier hypothesis, we can equate P with e. Now notice that the sequence ZWP appears in the ciphertext, and we can translate that sequence as “the.” This is the most frequent trigram (three-letter combination) in English, which seems to indicate that we are on the right track.

Next, notice the sequence ZWSZ in the first line. We do not know that these four letters form a complete word, but if they do, it is of the form th_t. If so, S equates with a.

So far, then, we have

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
 t a       e  e te  a that e e a     a
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
   e t   ta t ha e ee  a e th     t a
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
 e  e e tat  e   the   t

Only four letters have been identified, but already we have quite a bit of the message. Continued analysis of frequencies plus trial and error should easily yield a solution from this point. The complete plaintext, with spaces added between words, follows:

it was disclosed yesterday that several informal but
direct contacts have been made with political
representatives of the viet cong in moscow

Monoalphabetic ciphers are easy to break because they reflect the frequency data of the original alphabet. A countermeasure is to provide multiple substitutes, known as homophones, for a single letter. For example, the letter e could be assigned a number of different cipher symbols, such as 16, 74, 35, and 21, with each homophone assigned to a letter in rotation or randomly. If the number of symbols assigned to each letter is proportional to the relative frequency of that letter, then single-letter frequency information is completely obliterated. The great mathematician Carl Friedrich Gauss believed that he had devised an unbreakable cipher using homophones. However, even with homophones, each element of plaintext affects only one element of ciphertext, and multiple-letter patterns (e.g., digram frequencies) still survive in the ciphertext, making cryptanalysis relatively straightforward.

Two principal methods are used in substitution ciphers to lessen the extent to which the structure of the plaintext survives in the ciphertext: One approach is to encrypt multiple letters of plaintext, and the other is to use multiple cipher alphabets. We briefly examine each.

The best-known multiple-letter encryption cipher is the Playfair, which treats digrams in the plaintext as single units and translates these units into ciphertext digrams.3

The Playfair algorithm is based on the use of a matrix of letters constructed using a keyword. Here is an example, solved by Lord Peter Wimsey in Dorothy Sayers’s Have His Carcase:4

In this case, the keyword is monarchy. The matrix is constructed by filling in the letters of the keyword (minus duplicates) from left to right and from top to bottom, and then filling in the remainder of the matrix with the remaining letters in alphabetic order. The letters I and J count as one letter. Plaintext is encrypted two letters at a time, according to the following rules:

1. Repeating plaintext letters that are in the same pair are separated with a filler letter, such as x, so that balloon would be treated as ba lx lo on.

2. Two plaintext letters that fall in the same row of the matrix are each replaced by the letter to the right, with the first element of the row circularly following the last. For example, ar is encrypted as RM.

3. Two plaintext letters that fall in the same column are each replaced by the letter beneath, with the top element of the column circularly following the last. For example, mu is encrypted as CM.

4. Otherwise, each plaintext letter in a pair is replaced by the letter that lies in its own row and the column occupied by the other plaintext letter. Thus, hs becomes BP and ea becomes IM (or JM, as the encipherer wishes).

The Playfair cipher is a great advance over simple monoalphabetic ciphers. For one thing, whereas there are only 26 letters, there are digrams, so that identification of individual digrams is more difficult. Furthermore, the relative frequencies of individual letters exhibit a much greater range than that of digrams, making frequency analysis much more difficult. For these reasons, the Playfair cipher was for a long time considered unbreakable. It was used as the standard field system by the British Army in World War I and still enjoyed considerable use by the U.S. Army and other Allied forces during World War II.

Despite this level of confidence in its security, the Playfair cipher is relatively easy to break, because it still leaves much of the structure of the plaintext language intact. A few hundred letters of ciphertext are generally sufficient.

One way of revealing the effectiveness of the Playfair and other ciphers is shown in Figure 3.6. The line labeled plaintext plots a typical frequency distribution of the 26 alphabetic characters (no distinction between upper and lower case) in ordinary text. This is also the frequency distribution of any monoalphabetic substitution cipher, because the frequency values for individual letters are the same, just with different letters substituted for the original letters. The plot is developed in the following way: The number of occurrences of each letter in the text is counted and divided by the number of occurrences of the most frequently used letter. Using the results of Figure 3.5, we see that e is the most frequently used letter. As a result, e has a relative frequency of 1, t of and so on. The points on the horizontal axis correspond to the letters in order of decreasing frequency.

Figure 3.6 Relative Frequency of Occurrence of Letters

Figure 3.6 also shows the frequency distribution that results when the text is encrypted using the Playfair cipher. To normalize the plot, the number of occurrences of each letter in the ciphertext was again divided by the number of occurrences of e in the plaintext. The resulting plot therefore shows the extent to which the frequency distribution of letters, which makes it trivial to solve substitution ciphers, is masked by encryption. If the frequency distribution information were totally concealed in the encryption process, the ciphertext plot of frequencies would be flat, and cryptanalysis using ciphertext only would be effectively impossible. As the figure shows, the Playfair cipher has a flatter distribution than does plaintext, but nevertheless, it reveals plenty of structure for a cryptanalyst to work with. The plot also shows the Vigenère cipher, discussed subsequently. The Hill and Vigenère curves on the plot are based on results reported in [SIMM93].

Another interesting multiletter cipher is the Hill cipher, developed by the mathematician Lester Hill in 1929.

Another way to improve on the simple monoalphabetic technique is to use different monoalphabetic substitutions as one proceeds through the plaintext message. The general name for this approach is polyalphabetic substitution cipher. All these techniques have the following features in common:

1. A set of related monoalphabetic substitution rules is used.

2. A key determines which particular rule is chosen for a given transformation.

key:          deceptivedeceptivedeceptive
plaintext:    wearediscoveredsaveyourself
ciphertext:   ZICVTWQNGRZGVTWAVZHCQYGLMGJ

key:          deceptivewearediscoveredsav
plaintext:    wearediscoveredsaveyourself
ciphertext:   ZICVTWQNGKZEIIGASXSTSLVVWLA

Vernam Cipher

The ultimate defense against such a cryptanalysis is to choose a keyword that is as long as the plaintext and has no statistical relationship to it. Such a system was introduced by an AT&T engineer named Gilbert Vernam in 1918.

His system works on binary data (bits) rather than letters. The system can be expressed succinctly as follows (Figure 3.7):

where

Figure 3.7 Vernam Cipher

Figure 3.7 Full Alternative Text

Compare this with Equation (3.3) for the Vigenère cipher.

Thus, the ciphertext is generated by performing the bitwise XOR of the plaintext and the key. Because of the properties of the XOR, decryption simply involves the same bitwise operation:

which compares with Equation (3.4).

The essence of this technique is the means of construction of the key. Vernam proposed the use of a running loop of tape that eventually repeated the key, so that in fact the system worked with a very long but repeating keyword. Although such a scheme, with a long key, presents formidable cryptanalytic difficulties, it can be broken with sufficient ciphertext, the use of known or probable plaintext sequences, or both.

An Army Signal Corp officer, Joseph Mauborgne, proposed an improvement to the Vernam cipher that yields the ultimate in security. Mauborgne suggested using a random key that is as long as the message, so that the key need not be repeated. In addition, the key is to be used to encrypt and decrypt a single message, and then is discarded. Each new message requires a new key of the same length as the new message. Such a scheme, known as a one-time pad, is unbreakable. It produces random output that bears no statistical relationship to the plaintext. Because the ciphertext contains no information whatsoever about the plaintext, there is simply no way to break the code.

An example should illustrate our point. Suppose that we are using a Vigenère scheme with 27 characters in which the twenty-seventh character is the space character, but with a one-time key that is as long as the message. Consider the ciphertext

ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS

We now show two different decryptions using two different keys:

ciphertext:   ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS
key:          pxlmvmsydofuyrvzwc tnlebnecvgdupahfzzlmnyih
plaintext:    mr mustard with the candlestick in the hall
ciphertext:   ANKYODKYUREPFJBYOJDSPLREYIUNOFDOIUERFPLUYTS
key:          pftgpmiydgaxgoufhklllmhsqdqogtewbqfgyovuhwt
plaintext:    miss scarlet with the knife in the library

Suppose that a cryptanalyst had managed to find these two keys. Two plausible plaintexts are produced. How is the cryptanalyst to decide which is the correct decryption (i.e., which is the correct key)? If the actual key were produced in a truly random fashion, then the cryptanalyst cannot say that one of these two keys is more likely than the other. Thus, there is no way to decide which key is correct and therefore which plaintext is correct.

In fact, given any plaintext of equal length to the ciphertext, there is a key that produces that plaintext. Therefore, if you did an exhaustive search of all possible keys, you would end up with many legible plaintexts, with no way of knowing which was the intended plaintext. Therefore, the code is unbreakable.

The security of the one-time pad is entirely due to the randomness of the key. If the stream of characters that constitute the key is truly random, then the stream of characters that constitute the ciphertext will be truly random. Thus, there are no patterns or regularities that a cryptanalyst can use to attack the ciphertext.

In theory, we need look no further for a cipher. The one-time pad offers complete security but, in practice, has two fundamental difficulties:

1. There is the practical problem of making large quantities of random keys. Any heavily used system might require millions of random characters on a regular basis. Supplying truly random characters in this volume is a significant task.

2. Even more daunting is the problem of key distribution and protection. For every message to be sent, a key of equal length is needed by both sender and receiver. Thus, a mammoth key distribution problem exists.

Because of these difficulties, the one-time pad is of limited utility and is useful primarily for low-bandwidth channels requiring very high security.

The one-time pad is the only cryptosystem that exhibits what is referred to as perfect secrecy. This concept is explored in Appendix B.

• block cipher

• brute-force attack

• cipher

• ciphertext

• computationally secure

• conventional encryption

• cryptanalysis

• cryptographic system

• cryptography

• cryptology

• deciphering

• decryption

• digram

• enciphering

• encryption

• monoalphabetic substitution cipher

• one-time pad

• permutation

• plaintext

• polyalphabetic substitution cipher

• single-key encryption

• stream cipher

• symmetric encryption

• unconditionally secure