Large Prime Numbers and Cybersecurity

Write a  2 page paper explaining the need for large prime numbers in the cybersecurity field.


William Stallings

Boston Columbus Indianapolis New York San Francisco Hoboken Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montréal Toronto

Delhi Mexico City São Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo



For Tricia: never dull, never boring, the smartest and bravest person

I know

ISBN 10:1-292-15858-1 ISBN 13: 978-1-292-15858-7

10 9 8 7 6 5 4 3 2 1

British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library

Vice President and Editorial Director, ECS: Marcia J. Horton Executive Editor: Tracy Johnson (Dunkelberger) Editorial Assistant: Kristy Alaura Acquisitions Editor, Global Editions: Abhijit Baroi Program Manager: Carole Snyder Project Manager: Robert Engelhardt Project Editor, Global Editions: K.K. Neelakantan Media Team Lead: Steve Wright R&P Manager: Rachel Youdelman R&P Senior Project Manager: William Opaluch Senior Operations Specialist: Maura Zaldivar-Garcia Inventory Manager: Meredith Maresca

Inventory Manager: Meredith Maresca Senior Manufacturing Controller, Global Editions: Trudy Kimber Media Production Manager, Global Editions: Vikram Kumar Product Marketing Manager: Bram Van Kempen Marketing Assistant: Jon Bryant Cover Designer: Lumina Datamatics Cover Art: © goghy73 / Shutterstock Full-Service Project Management: Chandrakala Prakash, SPi Global Composition: SPi Global

Credits and acknowledgments borrowed from other sources and reproduced, with permission, in this textbook appear on page 753.

© Pearson Education Limited 2017

The right of William Stallings to be identified as the author of this work has been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Authorized adaptation from the United States edition, entitled Cryptography and Network Security: Principles and Practice, 7th Edition, ISBN 978-0-13-444428-4, by William Stallings published by Pearson Education © 2017.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without either the prior written permission of the publisher or a license permitting restricted copying in the United Kingdom issued by the Copyright Licensing Agency Ltd, Saffron House, 6–10 Kirby Street, London EC1N 8TS.

All trademarks used herein are the property of their respective owners. The use of any trademark in this text does not vest in the author or publisher any trademark ownership rights in such trademarks, nor does the use of such trademarks imply any affiliation with or endorsement of this book by such owners.

Pearson Education Limited Edinburgh Gate Harlow Essex CM20 2JE England

and Associated Companies throughout the world

Visit us on the World Wide Web at:

Typeset by SPi Global Printed and bound in Malaysia.



CONTENTS Notation 10

Preface 12

About the Author 18


Chapter 1 Computer and Network Security Concepts 19

1.1 Computer Security Concepts 21 1.2 The OSI Security Architecture 26 1.3 Security Attacks 27 1.4 Security Services 29 1.5 Security Mechanisms 32 1.6 Fundamental Security Design Principles 34 1.7 Attack Surfaces and Attack Trees 37 1.8 A Model for Network Security 41 1.9 Standards 43 1.10 Key Terms, Review Questions, and Problems 44

Chapter 2 Introduction to Number Theory 46

2.1 Divisibility and the Division Algorithm 47 2.2 The Euclidean Algorithm 49 2.3 Modular Arithmetic 53 2.4 Prime Numbers 61 2.5 Fermat’s and Euler’s Theorems 64 2.6 Testing for Primality 68 2.7 The Chinese Remainder Theorem 71 2.8 Discrete Logarithms 73 2.9 Key Terms, Review Questions, and Problems 78 Appendix 2A The Meaning of Mod 82


Chapter 3 Classical Encryption Techniques 85

3.1 Symmetric Cipher Model 86 3.2 Substitution Techniques 92 3.3 Transposition Techniques 107 3.4 Rotor Machines 108 3.5 Steganography 110 3.6 Key Terms, Review Questions, and Problems 112

Chapter 4 Block Ciphers and the Data Encryption Standard 118

4.1 Traditional Block Cipher Structure 119 4.2 The Data Encryption Standard 129 4.3 A DES Example 131 4.4 The Strength of DES 134




4.5 Block Cipher Design Principles 135 4.6 Key Terms, Review Questions, and Problems 137

Chapter 5 Finite Fields 141

5.1 Groups 143 5.2 Rings 145 5.3 Fields 146 5.4 Finite Fields of the Form GF(p) 147 5.5 Polynomial Arithmetic 151 5.6 Finite Fields of the Form GF(2n) 157 5.7 Key Terms, Review Questions, and Problems 169

Chapter 6 Advanced Encryption Standard 171

6.1 Finite Field Arithmetic 172 6.2 AES Structure 174 6.3 AES Transformation Functions 179 6.4 AES Key Expansion 190 6.5 An AES Example 193 6.6 AES Implementation 197 6.7 Key Terms, Review Questions, and Problems 202 Appendix 6A Polynomials with Coefficients in GF(28) 203

Chapter 7 Block Cipher Operation 207

7.1 Multiple Encryption and Triple DES 208 7.2 Electronic Codebook 213 7.3 Cipher Block Chaining Mode 216 7.4 Cipher Feedback Mode 218 7.5 Output Feedback Mode 220 7.6 Counter Mode 222 7.7 XTS-AES Mode for Block-Oriented Storage Devices 224 7.8 Format-Preserving Encryption 231 7.9 Key Terms, Review Questions, and Problems 245

Chapter 8 Random Bit Generation and Stream Ciphers 250

8.1 Principles of Pseudorandom Number Generation 252 8.2 Pseudorandom Number Generators 258 8.3 Pseudorandom Number Generation Using a Block Cipher 261 8.4 Stream Ciphers 267 8.5 RC4 269 8.6 True Random Number Generators 271 8.7 Key Terms, Review Questions, and Problems 280


Chapter 9 Public-Key Cryptography and RSA 283

9.1 Principles of Public-Key Cryptosystems 285 9.2 The RSA Algorithm 294 9.3 Key Terms, Review Questions, and Problems 308




Chapter 10 Other Public-Key Cryptosystems 313

10.1 Diffie-Hellman Key Exchange 314 10.2 Elgamal Cryptographic System 318 10.3 Elliptic Curve Arithmetic 321 10.4 Elliptic Curve Cryptography 330 10.5 Pseudorandom Number Generation Based on an Asymmetric Cipher 334 10.6 Key Terms, Review Questions, and Problems 336


Chapter 11 Cryptographic Hash Functions 339

11.1 Applications of Cryptographic Hash Functions 341 11.2 Two Simple Hash Functions 346 11.3 Requirements and Security 348 11.4 Hash Functions Based on Cipher Block Chaining 354 11.5 Secure Hash Algorithm (SHA) 355 11.6 SHA-3 365 11.7 Key Terms, Review Questions, and Problems 377

Chapter 12 Message Authentication Codes 381

12.1 Message Authentication Requirements 382 12.2 Message Authentication Functions 383 12.3 Requirements for Message Authentication Codes 391 12.4 Security of MACs 393 12.5 MACs Based on Hash Functions: HMAC 394 12.6 MACs Based on Block Ciphers: DAA and CMAC 399 12.7 Authenticated Encryption: CCM and GCM 402 12.8 Key Wrapping 408 12.9 Pseudorandom Number Generation Using Hash Functions and MACs 413 12.10 Key Terms, Review Questions, and Problems 416

Chapter 13 Digital Signatures 419

13.1 Digital Signatures 421 13.2 Elgamal Digital Signature Scheme 424 13.3 Schnorr Digital Signature Scheme 425 13.4 NIST Digital Signature Algorithm 426 13.5 Elliptic Curve Digital Signature Algorithm 430 13.6 RSA-PSS Digital Signature Algorithm 433 13.7 Key Terms, Review Questions, and Problems 438


Chapter 14 Key Management and Distribution 441

14.1 Symmetric Key Distribution Using Symmetric Encryption 442 14.2 Symmetric Key Distribution Using Asymmetric Encryption 451 14.3 Distribution of Public Keys 454 14.4 X.509 Certificates 459




14.5 Public-Key Infrastructure 467 14.6 Key Terms, Review Questions, and Problems 469

Chapter 15 User Authentication 473

15.1 Remote User-Authentication Principles 474 15.2 Remote User-Authentication Using Symmetric Encryption 478 15.3 Kerberos 482 15.4 Remote User-Authentication Using Asymmetric Encryption 500 15.5 Federated Identity Management 502 15.6 Personal Identity Verification 508 15.7 Key Terms, Review Questions, and Problems 515


Chapter 16 Network Access Control and Cloud Security 519

16.1 Network Access Control 520 16.2 Extensible Authentication Protocol 523 16.3 IEEE 802.1X Port-Based Network Access Control 527 16.4 Cloud Computing 529 16.5 Cloud Security Risks and Countermeasures 535 16.6 Data Protection in the Cloud 537 16.7 Cloud Security as a Service 541 16.8 Addressing Cloud Computing Security Concerns 544 16.9 Key Terms, Review Questions, and Problems 545

Chapter 17 Transport-Level Security 546

17.1 Web Security Considerations 547 17.2 Transport Layer Security 549 17.3 HTTPS 566 17.4 Secure Shell (SSH) 567 17.5 Key Terms, Review Questions, and Problems 579

Chapter 18 Wireless Network Security 581

18.1 Wireless Security 582 18.2 Mobile Device Security 585 18.3 IEEE 802.11 Wireless LAN Overview 589 18.4 IEEE 802.11i Wireless LAN Security 595 18.5 Key Terms, Review Questions, and Problems 610

Chapter 19 Electronic Mail Security 612

19.1 Internet Mail Architecture 613 19.2 Email Formats 617 19.3 Email Threats and Comprehensive Email Security 625 19.4 S/MIME 627 19.5 Pretty Good Privacy 638 19.6 DNSSEC 639 19.7 DNS-Based Authentication of Named Entities 643 19.8 Sender Policy Framework 645 19.9 DomainKeys Identified Mail 648




19.10 Domain-Based Message Authentication, Reporting, and Conformance 654 19.11 Key Terms, Review Questions, and Problems 659

Chapter 20 IP Security 661

20.1 IP Security Overview 662 20.2 IP Security Policy 668 20.3 Encapsulating Security Payload 673 20.4 Combining Security Associations 681 20.5 Internet Key Exchange 684 20.6 Cryptographic Suites 692 20.7 Key Terms, Review Questions, and Problems 694


Appendix A Projects for Teaching Cryptography and Network Security 696

A.1 Sage Computer Algebra Projects 697 A.2 Hacking Project 698 A.3 Block Cipher Projects 699 A.4 Laboratory Exercises 699 A.5 Research Projects 699 A.6 Programming Projects 700 A.7 Practical Security Assessments 700 A.8 Firewall Projects 701 A.9 Case Studies 701 A.10 Writing Assignments 701 A.11 Reading/Report Assignments 702 A.12 Discussion Topics 702

Appendix B Sage Examples 703

B.1 Linear Algebra and Matrix Functionality 704 B.2 Chapter 2: Number Theory 705 B.3 Chapter 3: Classical Encryption 710 B.4 Chapter 4: Block Ciphers and the Data Encryption Standard 713 B.5 Chapter 5: Basic Concepts in Number Theory and Finite Fields 717 B.6 Chapter 6: Advanced Encryption Standard 724 B.7 Chapter 8: Pseudorandom Number Generation and Stream Ciphers 729 B.8 Chapter 9: Public-Key Cryptography and RSA 731 B.9 Chapter 10: Other Public-Key Cryptosystems 734 B.10 Chapter 11: Cryptographic Hash Functions 739 B.11 Chapter 13: Digital Signatures 741

References 744

Credits 753

Index 754






Chapter 21 Malicious Software

21.1 Types of Malicious Software (Malware) 21.2 Advanced Persistent Threat 21.3 Propagation—Infected Content—Viruses 21.4 Propagation—Vulnerability Exploit—Worms 21.5 Propagation—Social Engineering—Spam E-mail, Trojans 21.6 Payload—System Corruption 21.7 Payload—Attack Agent—Zombie, Bots 21.8 Payload—Information Theft—Keyloggers, Phishing, Spyware 21.9 Payload—Stealthing—Backdoors, Rootkits 21.10 Countermeasures 21.11 Distributed Denial of Service Attacks 21.12 References 21.13 Key Terms, Review Questions, and Problems

Chapter 22 Intruders

22.1 Intruders 22.2 Intrusion Detection 22.3 Password Management 22.4 References 22.5 Key Terms, Review Questions, and Problems

Chapter 23 Firewalls

23.1 The Need for Firewalls 23.2 Firewall Characteristics and Access Policy 23.3 Types of Firewalls 23.4 Firewall Basing 23.5 Firewall Location and Configurations 23.6 References 23.7 Key Terms, Review Questions, and Problems


Chapter 24 Legal and Ethical Aspects

24.1 Cybercrime and Computer Crime 24.2 Intellectual Property 24.3 Privacy 24.4 Ethical Issues 24.5 Recommended Reading 24.6 References 24.7 Key Terms, Review Questions, and Problems 24.A Information Privacy

1Online chapters, appendices, and other documents are at the Companion Website, available via the access card at the front of this book.




Appendix C Sage Exercises

Appendix D Standards and Standard-Setting Organizations

Appendix E Basic Concepts from Linear Algebra

Appendix F Measures of Secrecy and Security

Appendix G Simplified DES

Appendix H Evaluation Criteria for AES

Appendix I Simplified AES

Appendix J The Knapsack Algorithm

Appendix K Proof of the Digital Signature Algorithm

Appendix L TCP/IP and OSI

Appendix M Java Cryptographic APIs

Appendix N MD5 Hash Function

Appendix O Data Compression Using ZIP

Appendix P PGP

Appendix Q The International Reference Alphabet

Appendix R Proof of the RSA Algorithm

Appendix S Data Encryption Standard

Appendix T Kerberos Encryption Techniques

Appendix U Mathematical Basis of the Birthday Attack

Appendix V Evaluation Criteria for SHA-3

Appendix W The Complexity of Algorithms

Appendix X Radix-64 Conversion

Appendix Y The Base Rate Fallacy





Symbol Expression Meaning

D, K D(K, Y) Symmetric decryption of ciphertext Y using secret key K

D, PRa D(PRa, Y) Asymmetric decryption of ciphertext Y using A’s private key PRa

D, PUa D(PUa, Y) Asymmetric decryption of ciphertext Y using A’s public key PUa

E, K E(K, X) Symmetric encryption of plaintext X using secret key K

E, PRa E(PRa, X) Asymmetric encryption of plaintext X using A’s private key PRa

E, PUa E(PUa, X) Asymmetric encryption of plaintext X using A’s public key PUa

K Secret key

PRa Private key of user A

PUa Public key of user A

MAC, K MAC(K, X) Message authentication code of message X using secret key K

GF(p) The finite field of order p, where p is prime.The field is defined as the set Zp together with the arithmetic operations modulo p.

GF(2n) The finite field of order 2n

Zn Set of nonnegative integers less than n

gcd gcd(i, j) Greatest common divisor; the largest positive integer that divides both i and j with no remainder on division.

mod a mod m Remainder after division of a by m

mod, K a K b (mod m) a mod m = b mod m

mod, [ a [ b (mod m) a mod m ≠ b mod m

dlog dloga,p(b) Discrete logarithm of the number b for the base a (mod p)

w f(n) The number of positive integers less than n and relatively prime to n. This is Euler’s totient function.

Σ a n

i=1 ai a1 + a2 + g + an

Π q n

i=1 ai a1 * a2 * g * an

� i � j i divides j, which means that there is no remainder when j is divided by i

� , � �a � Absolute value of a





Symbol Expression Meaning

} x } y x concatenated with y

≈ x ≈ y x is approximately equal to y

⊕ x⊕ y Exclusive-OR of x and y for single-bit variables; Bitwise exclusive-OR of x and y for multiple-bit variables

:, ; :x; The largest integer less than or equal to x ∈ x∈ S The element x is contained in the set S.

· A · (a1, a2, c ak)

The integer A corresponds to the sequence of integers (a1, a2, c ak)





In the four years since the sixth edition of this book was published, the field has seen contin- ued 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 sixth 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:

■ Fundamental security design principles: Chapter 1 includes a new section discussing the security design principles listed as fundamental by the National Centers of Academic Excellence in Information Assurance/Cyber Defense, which is jointly sponsored by the U.S. National Security Agency and the U.S. Department of Homeland Security.

■ Attack surfaces and attack trees: Chapter 1 includes a new section describing these two concepts, which are useful in evaluating and classifying security threats.

■ Number theory coverage: The material on number theory has been consolidated into a single chapter, Chapter 2. This makes for a convenient reference. The relevant portions of Chapter 2 can be assigned as needed.

■ Finite fields: The chapter on finite fields has been revised and expanded with addi- tional text and new figures to enhance understanding.

■ Format-preserving encryption: This relatively new mode of encryption is enjoying increasing commercial success. A new section in Chapter 7 covers this method.

■ Conditioning and health testing for true random number generators: Chapter 8 now provides coverage of these important topics.

■ User authentication model: Chapter 15 includes a new description of a general model for user authentication, which helps to unify the discussion of the various approaches to user authentication.

■ Cloud security: The material on cloud security in Chapter 16 has been updated and expanded to reflect its importance and recent developments.

■ Transport Layer Security (TLS): The treatment of TLS in Chapter 17 has been updated, reorganized to improve clarity, and now includes a discussion of the new TLS version 1.3.

■ Email Security: Chapter 19 has been completely rewritten to provide a comprehensive and up-to-date discussion of email security. It includes:

— New: discussion of email threats and a comprehensive approach to email security.

— New: discussion of STARTTLS, which provides confidentiality and authentication for SMTP.





— Revised: treatment of S/MIME has been updated to reflect the latest version 3.2.

— New: discussion of DNSSEC and its role in supporting email security.

— New: discussion of DNS-based Authentication of Named Entities (DANE) and the use of this approach to enhance security for certificate use in SMTP and S/MIME.

— New: discussion of Sender Policy Framework (SPF), which is the standardized way for a sending domain to identify and assert the mail senders for a given domain.

— Revised: discussion of DomainKeys Identified Mail (DKIM) has been revised.

— New: discussion of Domain-based Message Authentication, Reporting, and Confor- mance (DMARC) allows email senders to specify policy on how their mail should be handled, the types of reports that receivers can send back, and the frequency those reports should be sent.


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. The changes to this edition are intended to provide support of the ACM/IEEE Computer Science Curricula 2013 (CS2013). CS2013 adds Information Assurance and Security (IAS) to the curriculum rec- ommendation 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

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.




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 eight parts.

■ Background

■ Symmetric Ciphers

■ Asymmetric Ciphers

■ Cryptographic Data Integrity Algorithms

■ Mutual Trust

■ Network and Internet Security

■ System Security

■ Legal and Ethical Issues

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. Each chap- ter includes a list of key words, review questions, homework problems, and suggestions for further reading. 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.

■ Sample syllabuses: The text contains more material than can be conveniently covered in one semester. Accordingly, instructors are provided with several sample syllabuses that guide the use of the text within limited time.

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 To gain access to the IRC, please contact your local Pearson sales representative.




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 projects 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 algo- rithm 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.

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. See Appendix A in this book for details.


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. This book provides a large number of examples of the use of Sage covering many cryptographic concepts in Appendix B, which is included in this book.

Appendix C lists exercises in each of these topic areas to enable the student to gain hands-on experience with cryptographic algorithms. This appendix is available to instruc- tors at the IRC for this book. Appendix C 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—Number Theory and Finite Fields: Euclidean and extended Euclidean algorithms, polynomial arithmetic, GF(24), Euler’s Totient function, Miller–Rabin, fac- toring, modular exponentiation, discrete logarithm, and Chinese remainder theorem.

■ Chapter 3—Classical Encryption: 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—Pseudorandom Number 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.


For this new edition, a tremendous amount of original supporting material for students has been made available online.

Purchasing this textbook new also grants the reader six months of access to the Companion Website, which includes the following materials:

■ Online chapters: To limit the size and cost of the book, four chapters of the book are provided in PDF format. This includes three chapters on computer security and one on legal and ethical issues. The chapters are listed in this book’s table of contents.

■ Online appendices: There are numerous interesting topics that support material found in the text but whose inclusion is not warranted in the printed text. A total of 20 online appendices cover these topics for the interested student. The appendices are listed in this book’s table of contents.




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

■ Key papers: A number of papers from the professional literature, many hard to find, are provided for further reading.

■ Supporting documents: A variety of other useful documents are referenced in the text and provided online.

■ Sage code: The Sage code from the examples in Appendix B is useful in case the student wants to play around with the examples.

To access the Companion Website, follow the instructions for “digital resources for students” found in the front of this book.


This new edition has benefited from review by a number of people who gave generously of their time and expertise. The following professors reviewed all or a large part of the manuscript: Hossein Beyzavi (Marymount University), Donald F. Costello (University of Nebraska–Lincoln), James Haralambides (Barry University), Anand Seetharam (California State University at Monterey Bay), Marius C. Silaghi (Florida Institute of Technology), Shambhu Upadhyaya (University at Buffalo), 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: Dino M. Amaral, Chris Andrew, Prof. (Dr). C. Annamalai, Andrew Bain, Riccardo Bernardini, Olivier Blazy, Zervopoulou Christina, Maria Christofi, Dhananjoy Dey, Mario Emmanuel, Mike Fikuart, Alexander Fries, Pierpaolo Giacomin, Pedro R. M. Inácio, Daniela Tamy Iwassa, Krzysztof Janowski, Sergey Katsev, Adnan Kilic, Rob Knox, Mina Pourdashty, Yuri Poeluev, Pritesh Prajapati, Venkatesh Ramamoorthy, Andrea Razzini, Rami Rosen, Javier Scodelaro, Jamshid Shokrollahi, Oscar So, and David Tillemans.

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 in Appendices B and C. 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, program manager Carole Snyder, and production manager Bob Engelhardt. Thanks also to the marketing and sales staffs at Pearson, without whose efforts this book would not be in front of you.


Pearson would like to thank and acknowledge Somitra Kumar Sanadhya (Indraprastha Institute of Information Technology Delhi), and Somanath Tripathy (Indian Institute of Technology Patna) for contributing to the Global Edition, and Anwitaman Datta (Nanyang Technological University Singapore), Atul Kahate (Pune University), Goutam Paul (Indian Statistical Institute Kolkata), and Khyat Sharma for reviewing the Global Edition.


Dr. William Stallings has authored 18 titles, and counting revised editions, over 40 books on computer security, computer networking, and computer architecture. His writings have appeared in numerous publications, including the Proceedings of the IEEE, ACM Computing Reviews, and Cryptologia.

He has 13 times received the award 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. As a consultant, he has advised gov- ernment agencies, computer and software vendors, and major users on the design, selection, and use of networking software and products.

He created and maintains the Computer Science Student Resource Site at 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 MIT in computer science and a BS from Notre Dame in electrical engineering.






Computer and Network Security Concepts

1.1 Computer Security Concepts

A Definition of Computer Security Examples The Challenges of Computer Security

1.2 The OSI Security Architecture

1.3 Security Attacks

Passive Attacks Active Attacks

1.4 Security Services

Authentication Access Control Data Confidentiality Data Integrity Nonrepudiation Availability Service

1.5 Security Mechanisms

1.6 Fundamental Security Design Principles

1.7 Attack Surfaces and Attack Trees

Attack Surfaces Attack Trees

1.8 A Model for Network Security

1.9 Standards

1.10 Key Terms, Review Questions, and Problems





This book focuses on two broad areas: cryptographic algorithms and protocols, which have a broad range of applications; and network and Internet security, which rely heavily on cryptographic techniques.

Cryptographic algorithms and protocols can be grouped into four main areas:

■ Symmetric encryption: Used to conceal the contents of blocks or streams of data of any size, including messages, files, encryption keys, and passwords.

■ Asymmetric encryption: Used to conceal small blocks of data, such as encryp- tion keys and hash function values, which are used in digital signatures.

■ Data integrity algorithms: Used to protect blocks of data, such as messages, from alteration.

■ Authentication protocols: These are schemes based on the use of crypto- graphic algorithms designed to authenticate the identity of entities.

The field of network and Internet security consists of measures to deter, prevent, detect, and correct security violations that involve the transmission of information. That is a broad statement that covers a host of possibilities. To give you a feel for the areas covered in this book, consider the following examples of security violations:

1. User A transmits a file to user B. The file contains sensitive information (e.g., payroll records) that is to be protected from disclosure. User C, who is not authorized to read the file, is able to monitor the transmission and capture a copy of the file during its transmission.

2. A network manager, D, transmits a message to a computer, E, under its man- agement. The message instructs computer E to update an authorization file to include the identities of a number of new users who are to be given access to that computer. User F intercepts the message, alters its contents to add or delete entries, and then forwards the message to computer E, which accepts the mes- sage as coming from manager D and updates its authorization file accordingly.


After studying this chapter, you should be able to:

◆ Describe the key security requirements of confidentiality, integrity, and availability.

◆ Describe the X.800 security architecture for OSI.

◆ Discuss the types of security threats and attacks that must be dealt with and give examples of the types of threats and attacks that apply to differ- ent categories of computer and network assets.

◆ Explain the fundamental security design principles.

◆ Discuss the use of attack surfaces and attack trees.

◆ List and briefly describe key organizations involved in cryptography standards.




3. Rather than intercept a message, user F constructs its own message with the desired entries and transmits that message to computer E as if it had come from manager D. Computer E accepts the message as coming from manager D and updates its authorization file accordingly.

4. An employee is fired without warning. The personnel manager sends a mes- sage to a server system to invalidate the employee’s account. When the invali- dation is accomplished, the server is to post a notice to the employee’s file as confirmation of the action. The employee is able to intercept the message and delay it long enough to make a final access to the server to retrieve sensitive information. The message is then forwarded, the action taken, and the confir- mation posted. The employee’s action may go unnoticed for some consider- able time.

5. A message is sent from a customer to a stockbroker with instructions for vari- ous transactions. Subsequently, the investments lose value and the customer denies sending the message.

Although this list by no means exhausts the possible types of network security viola- tions, it illustrates the range of concerns of network security.


A Definition of Computer Security

The NIST Computer Security Handbook [NIST95] defines the term computer secu- rity as follows:

Computer Security: The protection afforded to an automated information system in order to attain the applicable objectives of preserving the integrity, availability, and confidentiality of information system resources (includes hardware, software, firmware, information/data, and telecommunications).

This definition introduces three key objectives that are at the heart of com- puter 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 re- lated to them may be collected and stored and by whom and to whom that information may be disclosed.

1RFC 4949 defines information as “facts and ideas, which can be represented (encoded) as various forms of data,” and data as “information in a specific physical representation, usually a sequence of symbols that have meaning; especially a representation of information that can be processed or produced by a computer.” Security literature typically does not make much of a distinction, nor does this book.




■ Integrity: This term covers two related concepts:

Data integrity: Assures that information (both stored and in transmit- ted packets) and programs are changed only in a specified and authorized manner.

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 objec- tives for information and for information systems. FIPS 199 provides a useful char- acterization 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 propri- etary information. A loss of confidentiality is the unauthorized disclosure of information.

■ Integrity: Guarding against improper information modification or destruc- tion, 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 estab- lished, 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:

Figure 1.1 Essential Network and Computer Security Requirements

Data and




A ccountability

A ut

he nt

ic ity

Co nfid

ent iali





■ 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 nonrepudia- tion, 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.


We now provide some examples of applications that illustrate the requirements just enumerated.2 For these examples, we use three levels of impact on organizations or individuals should there be a breach of security (i.e., a loss of confidentiality, integ- rity, or availability). These levels are defined in FIPS PUB 199:

■ Low: The loss could be expected to have a limited adverse effect on organi- zational operations, organizational assets, or individuals. A limited adverse effect means that, for example, the loss of confidentiality, integrity, or avail- ability might (i) cause a degradation in mission capability to an extent and duration that the organization is able to perform its primary functions, but the effectiveness of the functions is noticeably reduced; (ii) result in minor dam- age to organizational assets; (iii) result in minor financial loss; or (iv) result in minor harm to individuals.

■ Moderate: The loss could be expected to have a serious adverse effect on organizational operations, organizational assets, or individuals. A serious adverse effect means that, for example, the loss might (i) cause a signifi- cant degradation in mission capability to an extent and duration that the organization is able to perform its primary functions, but the effectiveness of the functions is significantly reduced; (ii) result in significant damage to organizational assets; (iii) result in significant financial loss; or (iv) result in significant harm to individuals that does not involve loss of life or serious, life-threatening injuries.

■ High: The loss could be expected to have a severe or catastrophic adverse effect on organizational operations, organizational assets, or individuals. A  severe or catastrophic adverse effect means that, for example, the loss might (i) cause a severe degradation in or loss of mission capability to an extent and duration that the organization is not able to perform one or more of its primary functions; (ii) result in major damage to organizational assets; (iii) result in major financial loss; or (iv) result in severe or catastrophic harm to individuals involving loss of life or serious, life-threatening injuries.

2These examples are taken from a security policy document published by the Information Technology Security and Privacy Office at Purdue University.




CONFIDENTIALITY Student grade information is an asset whose confidentiality is considered to be highly important by students. In the United States, the release of such information is regulated by the Family Educational Rights and Privacy Act (FERPA). Grade information should only be available to students, their parents, and employees that require the information to do their job. Student enrollment information may have a moderate confidentiality rating. While still covered by FERPA, this information is seen by more people on a daily basis, is less likely to be targeted than grade information, and results in less damage if disclosed. Directory information, such as lists of students or faculty or departmental lists, may be as- signed a low confidentiality rating or indeed no rating. This information is typically freely available to the public and published on a school’s Web site.

INTEGRITY Several aspects of integrity are illustrated by the example of a hospital patient’s allergy information stored in a database. The doctor should be able to trust that the information is correct and current. Now suppose that an employee (e.g., a nurse) who is authorized to view and update this information deliberately falsifies the data to cause harm to the hospital. The database needs to be restored to a trusted basis quickly, and it should be possible to trace the error back to the person responsible. Patient allergy information is an example of an asset with a high requirement for integrity. Inaccurate information could result in serious harm or death to a patient and expose the hospital to massive liability.

An example of an asset that may be assigned a moderate level of integrity requirement is a Web site that offers a forum to registered users to discuss some specific topic. Either a registered user or a hacker could falsify some entries or deface the Web site. If the forum exists only for the enjoyment of the users, brings in little or no advertising revenue, and is not used for something important such as research, then potential damage is not severe. The Web master may experience some data, financial, and time loss.

An example of a low integrity requirement is an anonymous online poll. Many Web sites, such as news organizations, offer these polls to their users with very few safeguards. However, the inaccuracy and unscientific nature of such polls is well understood.

AVAILABILITY The more critical a component or service, the higher is the level of availability required. Consider a system that provides authentication services for critical systems, applications, and devices. An interruption of service results in the inability for customers to access computing resources and staff to access the re- sources they need to perform critical tasks. The loss of the service translates into a large financial loss in lost employee productivity and potential customer loss.

An example of an asset that would typically be rated as having a moderate availability requirement is a public Web site for a university; the Web site provides information for current and prospective students and donors. Such a site is not a critical component of the university’s information system, but its unavailability will cause some embarrassment.

An online telephone directory lookup application would be classified as a low availability requirement. Although the temporary loss of the application may be an annoyance, there are other ways to access the information, such as a hardcopy directory or the operator.




The Challenges of Computer Security

Computer and network security is both fascinating and complex. Some of the reasons follow:

1. Security is not as simple as it might first appear to the novice. The require- ments seem to be straightforward; indeed, most of the major requirements for security services can be given self-explanatory, one-word labels: confidential- ity, authentication, nonrepudiation, or 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 con- sidered 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 in- formation (e.g., an encryption key), which raises questions about the creation, distribution, and protection of that secret information. There also may be a re- liance 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. Computer and network security is essentially a battle of wits between a per- petrator 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 per- ceive 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.


To assess effectively the security needs of an organization and to evaluate and choose various security products and policies, the manager responsible for security needs some systematic way of defining the requirements for security and character- izing the approaches to satisfying those requirements. This is difficult enough in a centralized data processing environment; with the use of local and wide area net- works, the problems are compounded.

ITU-T3 Recommendation X.800, Security Architecture for OSI, defines such a systematic approach.4 The OSI security architecture is useful to managers as a way of organizing the task of providing security. Furthermore, because this architecture was developed as an international standard, computer and communications vendors have developed security features for their products and services that relate to this structured definition of services and mechanisms.

For our purposes, the OSI security architecture provides a useful, if abstract, overview of many of the concepts that this book deals with. The OSI security archi- tecture focuses on security attacks, mechanisms, and services. These can be defined briefly as

■ Security attack: Any action that compromises the security of information owned by an organization.

■ Security mechanism: A process (or a device incorporating such a process) that is designed to detect, prevent, or recover from a security attack.

■ Security service: A processing or communication service that enhances the security of the data processing systems and the information transfers of an organization. The services are intended to counter security attacks, and they make use of one or more security mechanisms to provide the service.

In the literature, the terms threat and attack are commonly used to mean more or less the same thing. Table 1.1 provides definitions taken from RFC 4949, Internet Security Glossary.

3The International Telecommunication Union (ITU) Telecommunication Standardization Sector (ITU-T) is a United Nations-sponsored agency that develops standards, called Recommendations, relating to tele- communications and to open systems interconnection (OSI). 4The OSI security architecture was developed in the context of the OSI protocol architecture, which is described in Appendix L. However, for our purposes in this chapter, an understanding of the OSI proto- col architecture is not required.





A useful means of classifying security attacks, used both in X.800 and RFC 4949, is in terms of passive attacks and active attacks (Figure 1.2). A passive attack attempts to learn or make use of information from the system but does not affect system re- sources. An active attack attempts to alter system resources or affect their operation.

Passive Attacks

Passive attacks (Figure 1.2a) are in the nature of eavesdropping on, or monitoring of, transmissions. The goal of the opponent 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 conver- sation, 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 appar- ently 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 pre- vent the success of these attacks, usually by means of encryption. Thus, the empha- sis in dealing with passive attacks is on prevention rather than detection.

Active Attacks

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

Threat A potential for violation of security, which exists when there is a circumstance, capability, action, or event that could breach security and cause harm. That is, a threat is a possible danger that might exploit a vulnerability.

Attack An assault on system security that derives from an intelligent threat; that is, an intelligent act that is a deliberate attempt (especially in the sense of a method or technique) to evade security services and violate the security policy of a system.

Table 1.1 Threats and Attacks (RFC 4949)




A masquerade takes place when one entity pretends to be a different entity (path 2 of Figure 1.2b is active). 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 retrans- mission to produce an unauthorized effect (paths 1, 2, and 3 active).

Modification of messages simply means that some portion of a legitimate mes- sage is altered, or that messages are delayed or reordered, to produce an unauthor- ized effect (paths 1 and 2 active). For example, a message meaning “Allow John Smith to read confidential file accounts” is modified to mean “Allow Fred Brown to read confidential file accounts.”

Figure 1.2 Security Attacks

(a) Passive attacks


(b) Active attacks






Internet or other communications facility

Internet or other communications facility

1 2 3




The denial of service prevents or inhibits the normal use or management of communications facilities (path 3 active). 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 mes- sages 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 of the wide variety of potential physical, software, and network vulnerabilities. Instead, the goal is to detect active attacks and to recover from any disruption or delays caused by them. If the detection has a deterrent effect, it may also contribute to prevention.


X.800 defines a security service as a service that is provided by a protocol layer of communicating open systems and that ensures adequate security of the systems or of data transfers. Perhaps a clearer definition is found in RFC 4949, which provides the following definition: a processing or communication service that is provided by a system to give a specific kind of protection to system resources; security services implement security policies and are implemented by security mechanisms.

X.800 divides these services into five categories and fourteen specific services (Table 1.2). We look at each category in turn.5


The authentication service is concerned with assuring that a communication is au- thentic. 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 con- nection of a terminal to a host, two aspects are involved. First, at the time of connec- tion 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 imple- ment to same protocol in different systems; for example two TCP modules in two communicating systems. Peer entity authentication is provided for

5There is no universal agreement about many of the terms used in the security literature. For example, the term integrity is sometimes used to refer to all aspects of information security. The term authentication is sometimes used to refer both to verification of identity and to the various functions listed under integrity in this chapter. Our usage here agrees with both X.800 and RFC 4949.





The assurance that the communicating entity is the one that it claims to be.

Peer Entity Authentication Used in association with a logical connection to provide confidence in the identity of the entities connected.

Data-Origin Authentication In a connectionless transfer, provides assurance that the source of received data is as claimed.


The prevention of unauthorized use of a resource (i.e., this service controls who can have access to a resource, under what conditions access can occur, and what those accessing the resource are allowed to do).


The protection of data from unauthorized disclosure.

Connection Confidentiality The protection of all user data on a connection.

Connectionless Confidentiality The protection of all user data in a single data block.

Selective-Field Confidentiality The confidentiality of selected fields within the user data on a connection or in a single data block.

Traffic-Flow Confidentiality The protection of the information that might be derived from observation of traffic flows.


The assurance that data received are exactly as sent by an authorized entity (i.e., contain no modi- fication, insertion, deletion, or replay).

Connection Integrity with Recovery Provides for the integrity of all user data on a connec- tion and detects any modification, insertion, deletion, or replay of any data within an entire data sequence, with recovery attempted.

Connection Integrity without Recovery As above, but provides only detection without recovery.

Selective-Field Connection Integrity Provides for the integrity of selected fields within the user data of a data block transferred over a connec- tion and takes the form of determination of whether the selected fields have been modified, inserted, deleted, or replayed.

Connectionless Integrity Provides for the integrity of a single connectionless data block and may take the form of detection of data modification. Additionally, a limited form of replay detection may be provided.

Selective-Field Connectionless Integrity Provides for the integrity of selected fields within a single connectionless data block; takes the form of determination of whether the selected fields have been modified.


Provides protection against denial by one of the entities involved in a communication of having par- ticipated in all or part of the communication.

Nonrepudiation, Origin Proof that the message was sent by the specified party.

Nonrepudiation, Destination Proof that the message was received by the specified party.

Table 1.2 Security Services (X.800)

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 modifica- tion of data units. This type of service supports applications like electronic mail, where there are no prior interactions between the communicating entities.




Access Control

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.

Data Confidentiality

Confidentiality is the protection of transmitted data from passive attacks. With re- spect to the content of a data transmission, several levels of protection can be iden- tified. 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 desti- nation, frequency, length, or other characteristics of the traffic on a communications facility.

Data Integrity

As with confidentiality, integrity can apply to a stream of messages, a single mes- sage, 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 mes- sages, 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 mes- sage stream modification and denial of service. On the other hand, a connection- less 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 avail- able 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 mes- sage. 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 Service

Both X.800 and RFC 4949 define availability to be 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 avail- able 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 authentica- tion 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 ser- vice 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.


Table 1.3 lists the security mechanisms defined in X.800. The mechanisms are divided into those that are implemented in a specific protocol layer, such as TCP or an application-layer protocol, and those that are not specific to any particular pro- tocol layer or security service. These mechanisms will be covered in the appropriate

SPECIFIC SECURITY MECHANISMS May be incorporated into the appropriate protocol layer in order to provide some of the OSI security services.

Encipherment The use of mathematical algorithms to transform data into a form that is not readily intelligible. The transformation and subsequent recovery of the data depend on an algorithm and zero or more encryption keys.

Digital Signature Data appended to, or a cryptographic transformation of, a data unit that allows a recipient of the data unit to prove the source and integrity of the data unit and protect against forgery (e.g., by the recipient).

Access Control A variety of mechanisms that enforce access rights to resources.

Data Integrity A variety of mechanisms used to assure the integrity of a data unit or stream of data units.


Mechanisms that are not specific to any particular OSI security service or protocol layer.

Trusted Functionality That which is perceived to be correct with respect to some criteria (e.g., as established by a security policy).

Security Label The marking bound to a resource (which may be a data unit) that names or designates the security attri- butes of that resource.

Event Detection Detection of security-relevant events.

Security Audit Trail Data collected and potentially used to facilitate a security audit, which is an independent review and examination of system records and activities.

Security Recovery Deals with requests from mechanisms, such as event handling and management functions, and takes recovery actions.

Table 1.3 Security Mechanisms (X.800)




places in the book. So we do not elaborate now, except to comment on the defini- tion of encipherment. X.800 distinguishes between reversible encipherment mech- anisms and irreversible encipherment mechanisms. A reversible encipherment mechanism is simply an encryption algorithm that allows data to be encrypted and subsequently decrypted. Irreversible encipherment mechanisms include hash algo- rithms and message authentication codes, which are used in digital signature and message authentication applications.

Table 1.4, based on one in X.800, indicates the relationship between security services and security mechanisms.


Authentication Exchange A mechanism intended to ensure the identity of an entity by means of information exchange.

Traffic Padding The insertion of bits into gaps in a data stream to frustrate traffic analysis attempts.

Routing Control Enables selection of particular physically secure routes for certain data and allows routing changes, especially when a breach of security is suspected.

Notarization The use of a trusted third party to assure certain properties of a data exchange.




















Peer entity authentication



En cip

he rm

en t

Di git

al sig

na tur


Ac ces

s c on

tro l

Da ta

int eg

rit y

Au the

nti cat

ion ex

ch an


Tr affi

c p ad

din g

Ro uti

ng co

ntr ol

No tar

iza tio


Data origin authentication

Access control


Traffic flow confidentiality

Data integrity



Table 1.4 Relationship Between Security Services and Mechanisms





Despite years of research and development, it has not been possible to develop security design and implementation techniques that systematically exclude security flaws and prevent all unauthorized actions. In the absence of such foolproof tech- niques, it is useful to have a set of widely agreed design principles that can guide the development of protection mechanisms. The National Centers of Academic Excellence in Information Assurance/Cyber Defense, which is jointly sponsored by the U.S. National Security Agency and the U.S. Department of Homeland Security, list the following as fundamental security design principles [NCAE13]:

■ Economy of mechanism

■ Fail-safe defaults

■ Complete mediation

■ Open design

■ Separation of privilege

■ Least privilege

■ Least common mechanism

■ Psychological acceptability

■ Isolation

■ Encapsulation

■ Modularity

■ Layering

■ Least astonishment

The first eight listed principles were first proposed in [SALT75] and have withstood the test of time. In this section, we briefly discuss each principle.

Economy of mechanism means that the design of security measures embod- ied in both hardware and software should be as simple and small as possible. The motivation for this principle is that relatively simple, small design is eas- ier to test and verify thoroughly. With a complex design, there are many more opportunities for an adversary to discover subtle weaknesses to exploit that may be difficult to spot ahead of time. The more complex the mechanism, the more likely it is to possess exploitable flaws. Simple mechanisms tend to have fewer exploitable flaws and require less maintenance. Further, because configuration management issues are simplified, updating or replacing a simple mechanism becomes a less intensive process. In practice, this is perhaps the most difficult principle to honor. There is a constant demand for new features in both hard- ware and software, complicating the security design task. The best that can be done is to keep this principle in mind during system design to try to eliminate unnecessary complexity.

Fail-safe defaults means that access decisions should be based on permission rather than exclusion. That is, the default situation is lack of access, and the protec- tion scheme identifies conditions under which access is permitted. This approach




exhibits a better failure mode than the alternative approach, where the default is to permit access. A design or implementation mistake in a mechanism that gives explicit permission tends to fail by refusing permission, a safe situation that can be quickly detected. On the other hand, a design or implementation mistake in a mechanism that explicitly excludes access tends to fail by allowing access, a failure that may long go unnoticed in normal use. Most file access systems and virtually all protected services on client/server systems use fail-safe defaults.

Complete mediation means that every access must be checked against the access control mechanism. Systems should not rely on access decisions retrieved from a cache. In a system designed to operate continuously, this principle requires that, if access decisions are remembered for future use, careful consideration be given to how changes in authority are propagated into such local memories. File access systems appear to provide an example of a system that complies with this principle. However, typically, once a user has opened a file, no check is made to see if permissions change. To fully implement complete mediation, every time a user reads a field or record in a file, or a data item in a database, the system must exercise access control. This resource-intensive approach is rarely used.

Open design means that the design of a security mechanism should be open rather than secret. For example, although encryption keys must be secret, encryption algorithms should be open to public scrutiny. The algorithms can then be reviewed by many experts, and users can therefore have high confidence in them. This is the philosophy behind the National Institute of Standards and Technology (NIST) program of standardizing encryption and hash algorithms, and has led to the wide- spread adoption of NIST-approved algorithms.

Separation of privilege is defined in [SALT75] as a practice in which mul- tiple privilege attributes are required to achieve access to a restricted resource. A good example of this is multifactor user authentication, which requires the use of multiple techniques, such as a password and a smart card, to authorize a user. The term is also now applied to any technique in which a program is divided into parts that are limited to the specific privileges they require in order to perform a specific task. This is used to mitigate the potential damage of a computer security attack. One example of this latter interpretation of the principle is removing high privilege operations to another process and running that process with the higher privileges required to perform its tasks. Day-to-day interfaces are executed in a lower privi- leged process.

Least privilege means that every process and every user of the system should operate using the least set of privileges necessary to perform the task. A good example of the use of this principle is role-based access control. The system security policy can identify and define the various roles of users or processes. Each role is assigned only those permissions needed to perform its functions. Each permission specifies a permitted access to a particular resource (such as read and write access to a specified file or directory, connect access to a given host and port). Unless a permission is granted explicitly, the user or process should not be able to access the protected resource. More generally, any access control system should allow each user only the privileges that are authorized for that user. There is also a temporal aspect to the least privilege principle. For example, system programs or administra- tors who have special privileges should have those privileges only when necessary;




when they are doing ordinary activities the privileges should be withdrawn. Leaving them in place just opens the door to accidents.

Least common mechanism means that the design should minimize the func- tions shared by different users, providing mutual security. This principle helps reduce the number of unintended communication paths and reduces the amount of hardware and software on which all users depend, thus making it easier to verify if there are any undesirable security implications.

Psychological acceptability implies that the security mechanisms should not interfere unduly with the work of users, while at the same time meeting the needs of those who authorize access. If security mechanisms hinder the usability or accessibil- ity of resources, then users may opt to turn off those mechanisms. Where possible, security mechanisms should be transparent to the users of the system or at most introduce minimal obstruction. In addition to not being intrusive or burdensome, security procedures must reflect the user’s mental model of protection. If the protec- tion procedures do not make sense to the user or if the user must translate his image of protection into a substantially different protocol, the user is likely to make errors.

Isolation is a principle that applies in three contexts. First, public access sys- tems should be isolated from critical resources (data, processes, etc.) to prevent dis- closure or tampering. In cases where the sensitivity or criticality of the information is high, organizations may want to limit the number of systems on which that data is stored and isolate them, either physically or logically. Physical isolation may include ensuring that no physical connection exists between an organization’s public access information resources and an organization’s critical information. When implement- ing logical isolation solutions, layers of security services and mechanisms should be established between public systems and secure systems responsible for protecting critical resources. Second, the processes and files of individual users should be iso- lated from one another except where it is explicitly desired. All modern operating systems provide facilities for such isolation, so that individual users have separate, isolated process space, memory space, and file space, with protections for prevent- ing unauthorized access. And finally, security mechanisms should be isolated in the sense of preventing access to those mechanisms. For example, logical access control may provide a means of isolating cryptographic software from other parts of the host system and for protecting cryptographic software from tampering and the keys from replacement or disclosure.

Encapsulation can be viewed as a specific form of isolation based on object- oriented functionality. Protection is provided by encapsulating a collection of pro- cedures and data objects in a domain of its own so that the internal structure of a data object is accessible only to the procedures of the protected subsystem, and the procedures may be called only at designated domain entry points.

Modularity in the context of security refers both to the development of security functions as separate, protected modules and to the use of a modular architecture for mechanism design and implementation. With respect to the use of separate security modules, the design goal here is to provide common security functions and services, such as cryptographic functions, as common modules. For example, numerous proto- cols and applications make use of cryptographic functions. Rather than implement- ing such functions in each protocol or application, a more secure design is provided by developing a common cryptographic module that can be invoked by numerous




protocols and applications. The design and implementation effort can then focus on the secure design and implementation of a single cryptographic module and includ- ing mechanisms to protect the module from tampering. With respect to the use of a modular architecture, each security mechanism should be able to support migration to new technology or upgrade of new features without requiring an entire system redesign. The security design should be modular so that individual parts of the secu- rity design can be upgraded without the requirement to modify the entire system.

Layering refers to the use of multiple, overlapping protection approaches addressing the people, technology, and operational aspects of information systems. By using multiple, overlapping protection approaches, the failure or circumven- tion of any individual protection approach will not leave the system unprotected. We will see throughout this book that a layering approach is often used to provide multiple barriers between an adversary and protected information or services. This technique is often referred to as defense in depth.

Least astonishment means that a program or user interface should always respond in the way that is least likely to astonish the user. For example, the mechanism for authorization should be transparent enough to a user that the user has a good intui- tive understanding of how the security goals map to the provided security mechanism.


In Section 1.3, we provided an overview of the spectrum of security threats and attacks facing computer and network systems. Section 22.1 goes into more detail about the nature of attacks and the types of adversaries that present security threats. In this section, we elaborate on two concepts that are useful in evaluating and clas- sifying threats: attack surfaces and attack trees.

Attack Surfaces

An attack surface consists of the reachable and exploitable vulnerabilities in a sys- tem [MANA11, HOWA03]. Examples of attack surfaces are the following:

■ Open ports on outward facing Web and other servers, and code listening on those ports

■ Services available on the inside of a firewall

■ Code that processes incoming data, email, XML, office documents, and indus- try-specific custom data exchange formats

■ Interfaces, SQL, and Web forms

■ An employee with access to sensitive information vulnerable to a social engineering attack

Attack surfaces can be categorized as follows:

■ Network attack surface: This category refers to vulnerabilities over an enterprise network, wide-area network, or the Internet. Included in this category are net- work protocol vulnerabilities, such as those used for a denial-of-service attack, disruption of communications links, and various forms of intruder attacks.




■ Software attack surface: This refers to vulnerabilities in application, utility, or operating system code. A particular focus in this category is Web server software.

■ Human attack surface: This category refers to vulnerabilities created by personnel or outsiders, such as social engineering, human error, and trusted insiders.

An attack surface analysis is a useful technique for assessing the scale and severity of threats to a system. A systematic analysis of points of vulnerability makes developers and security analysts aware of where security mechanisms are required. Once an attack surface is defined, designers may be able to find ways to make the surface smaller, thus making the task of the adversary more difficult. The attack surface also provides guidance on setting priorities for testing, strengthening security measures, and modifying the service or application.

As illustrated in Figure 1.3, the use of layering, or defense in depth, and attack surface reduction complement each other in mitigating security risk.

Attack Trees

An attack tree is a branching, hierarchical data structure that represents a set of poten- tial techniques for exploiting security vulnerabilities [MAUW05, MOOR01, SCHN99]. The security incident that is the goal of the attack is represented as the root node of the tree, and the ways that an attacker could reach that goal are iteratively and incre- mentally represented as branches and subnodes of the tree. Each subnode defines a subgoal, and each subgoal may have its own set of further subgoals, and so on. The final nodes on the paths outward from the root, that is, the leaf nodes, represent differ- ent ways to initiate an attack. Each node other than a leaf is either an AND-node or an OR-node. To achieve the goal represented by an AND-node, the subgoals represented by all of that node’s subnodes must be achieved; and for an OR-node, at least one of the subgoals must be achieved. Branches can be labeled with values representing dif- ficulty, cost, or other attack attributes, so that alternative attacks can be compared.

Figure 1.3 Defense in Depth and Attack Surface

Attack surface

Medium security risk

High security risk

Low security riskD

ee p

L ay

er in


Sh al

lo w

Small Large

Medium security risk




The motivation for the use of attack trees is to effectively exploit the infor- mation available on attack patterns. Organizations such as CERT publish security advisories that have enabled the development of a body of knowledge about both general attack strategies and specific attack patterns. Security analysts can use the attack tree to document security attacks in a structured form that reveals key vul- nerabilities. The attack tree can guide both the design of systems and applications, and the choice and strength of countermeasures.

Figure 1.4, based on a figure in [DIMI07], is an example of an attack tree analysis for an Internet banking authentication application. The root of the tree is the objective of the attacker, which is to compromise a user’s account. The shaded boxes on the tree are the leaf nodes, which represent events that comprise the attacks. Note that in this tree, all the nodes other than leaf nodes are OR-nodes. The analysis to generate this tree considered the three components involved in authentication:

Figure 1.4 An Attack Tree for Internet Banking Authentication

Bank account compromise

User credential compromise

User credential guessing

UT/U1a User surveillance

UT/U1b Theft of token and handwritten notes

Malicious software installation Vulnerability exploit

UT/U2a Hidden code

UT/U2b Worms

UT/U3a Smartcard analyzers

UT/U2c Emails with malicious code

UT/U3b Smartcard reader manipulator

UT/U3c Brute force attacks with PIN calculators

CC2 Sniffing

UT/U4a Social engineering

IBS3 Web site manipulation

UT/U4b Web page obfuscation

CC1 Pharming

Redirection of communication toward fraudulent site

CC3 Active man-in-the middle attacks

IBS1 Brute force attacks

User communication with attacker

Injection of commands

Use of known authenticated session by attacker

Normal user authentication with specified session ID

CC4 Pre-defined session IDs (session hijacking)

IBS2 Security policy violation




■ User terminal and user (UT/U): These attacks target the user equipment, including the tokens that may be involved, such as smartcards or other pass- word generators, as well as the actions of the user.

■ Communications channel (CC): This type of attack focuses on communica- tion links.

■ Internet banking server (IBS): These types of attacks are offline attacks against the servers that host the Internet banking application.

Five overall attack strategies can be identified, each of which exploits one or more of the three components. The five strategies are as follows:

■ User credential compromise: This strategy can be used against many ele- ments of the attack surface. There are procedural attacks, such as monitoring a user’s action to observe a PIN or other credential, or theft of the user’s token or handwritten notes. An adversary may also compromise token information using a variety of token attack tools, such as hacking the smart- card or using a brute force approach to guess the PIN. Another possible strategy is to embed malicious software to compromise the user’s login and password. An adversary may also attempt to obtain credential information via the communication channel (sniffing). Finally, an adversary may use various means to engage in communication with the target user, as shown in Figure 1.4.

■ Injection of commands: In this type of attack, the attacker is able to intercept communication between the UT and the IBS. Various schemes can be used to be able to impersonate the valid user and so gain access to the banking system.

■ User credential guessing: It is reported in [HILT06] that brute force attacks against some banking authentication schemes are feasible by sending ran- dom usernames and passwords. The attack mechanism is based on distributed zombie personal computers, hosting automated programs for username- or password-based calculation.

■ Security policy violation: For example, violating the bank’s security policy in combination with weak access control and logging mechanisms, an em- ployee may cause an internal security incident and expose a customer’s account.

■ Use of known authenticated session: This type of attack persuades or forces the user to connect to the IBS with a preset session ID. Once the user authen- ticates to the server, the attacker may utilize the known session ID to send packets to the IBS, spoofing the user’s identity.

Figure 1.4 provides a thorough view of the different types of attacks on an Internet banking authentication application. Using this tree as a starting point, secu- rity analysts can assess the risk of each attack and, using the design principles out- lined in the preceding section, design a comprehensive security facility. [DIMO07] provides a good account of the results of this design effort.





A model for much of what we will be discussing is captured, in very general terms, in Figure 1.5. A message is to be transferred from one party to another across some sort of Internet service. The two parties, who are the principals in this transaction, must cooperate for the exchange to take place. A logical information channel is established by defining a route through the Internet from source to destination and by the coop- erative use of communication protocols (e.g., TCP/IP) by the two principals.

Security aspects come into play when it is necessary or desirable to protect the information transmission from an opponent who may present a threat to confidentiality, authenticity, and so on. All the techniques for providing security have two components:

■ A security-related transformation on the information to be sent. Examples include the encryption of the message, which scrambles the message so that it is unreadable by the opponent, and the addition of a code based on the con- tents of the message, which can be used to verify the identity of the sender.

■ Some secret information shared by the two principals and, it is hoped, unknown to the opponent. An example is an encryption key used in conjunc- tion with the transformation to scramble the message before transmission and unscramble it on reception.6

A trusted third party may be needed to achieve secure transmission. For example, a third party may be responsible for distributing the secret information

6Part Two discusses a form of encryption, known as a symmetric encryption, in which only one of the two principals needs to have the secret information.

Figure 1.5 Model for Network Security

Information channelSecurity-related



Secret information

M es

sa ge

M es

sa ge

Se cu

re m

es sa


Se cu

re m

es sa




Trusted third party (e.g., arbiter, distributer of secret information)

Security-related transformation

Secret information




to the two principals while keeping it from any opponent. Or a third party may be needed to arbitrate disputes between the two principals concerning the authenticity of a message transmission.

This general model shows that there are four basic tasks in designing a par- ticular security service:

1. Design an algorithm for performing the security-related transformation. The algorithm should be such that an opponent cannot defeat its purpose.

2. Generate the secret information to be used with the algorithm.

3. Develop methods for the distribution and sharing of the secret information.

4. Specify a protocol to be used by the two principals that makes use of the security algorithm and the secret information to achieve a particular security service.

Parts One through Five of this book concentrate on the types of security mechanisms and services that fit into the model shown in Figure 1.5. However, there are other security-related situations of interest that do not neatly fit this model but are considered in this book. A general model of these other situations is illustrated in Figure 1.6, which reflects a concern for protecting an information system from unwanted access. Most readers are familiar with the concerns caused by the existence of hackers, who attempt to penetrate systems that can be accessed over a network. The hacker can be someone who, with no malign intent, simply gets satisfaction from breaking and entering a computer system. The intruder can be a disgruntled employee who wishes to do damage or a criminal who seeks to exploit computer assets for financial gain (e.g., obtaining credit card numbers or perform- ing illegal money transfers).

Another type of unwanted access is the placement in a computer system of logic that exploits vulnerabilities in the system and that can affect application pro- grams as well as utility programs, such as editors and compilers. Programs can pres- ent two kinds of threats:

■ Information access threats: Intercept or modify data on behalf of users who should not have access to that data.

■ Service threats: Exploit service flaws in computers to inhibit use by legitimate users.

Figure 1.6 Network Access Security Model

Computing resources (processor, memory, I/O)




Internal security controls

Information system

Gatekeeper function

Opponent —human (e.g., hacker) —software (e.g., virus, worm)

Access channel



1.9 / STANDARDS 43

Viruses and worms are two examples of software attacks. Such attacks can be introduced into a system by means of a disk that contains the unwanted logic con- cealed in otherwise useful software. They can also be inserted into a system across a network; this latter mechanism is of more concern in network security.

The security mechanisms needed to cope with unwanted access fall into two broad categories (see Figure 1.6). The first category might be termed a gatekeeper function. It includes password-based login procedures that are designed to deny access to all but authorized users and screening logic that is designed to detect and reject worms, viruses, and other similar attacks. Once either an unwanted user or unwanted software gains access, the second line of defense consists of a vari- ety of internal controls that monitor activity and analyze stored information in an attempt to detect the presence of unwanted intruders. These issues are explored in Part Six.


Many of the security techniques and applications described in this book have been specified as standards. Additionally, standards have been developed to cover man- agement practices and the overall architecture of security mechanisms and services. Throughout this book, we describe the most important standards in use or that are being developed for various aspects of cryptography and network security. Various organizations have been involved in the development or promotion of these stan- dards. The most important (in the current context) of these organizations are as follows:

■ National Institute of Standards and Technology: NIST is a U.S. federal agency that deals with measurement science, standards, and technology related to U.S. government use and to the promotion of U.S. private-sector innovation. Despite its national scope, NIST Federal Information Processing Standards (FIPS) and Special Publications (SP) have a worldwide impact.

■ Internet Society: ISOC is a professional membership society with world- wide organizational and individual membership. It provides leadership in addressing issues that confront the future of the Internet and is the organiza- tion home for the groups responsible for Internet infrastructure standards, including the Internet Engineering Task Force (IETF) and the Internet Architecture Board (IAB). These organizations develop Internet stan- dards and related specifications, all of which are published as Requests for Comments (RFCs).

■ ITU-T: The International Telecommunication Union (ITU) is an interna- tional organization within the United Nations System in which governments and the private sector coordinate global telecom networks and services. The ITU Telecommunication Standardization Sector (ITU-T) is one of the three sectors of the ITU. ITU-T’s mission is the development of technical standards covering all fields of telecommunications. ITU-T standards are referred to as Recommendations.




■ ISO: The International Organization for Standardization (ISO)7 is a world- wide federation of national standards bodies from more than 140 countries, one from each country. ISO is a nongovernmental organization that promotes the development of standardization and related activities with a view to fa- cilitating the international exchange of goods and services and to developing cooperation in the spheres of intellectual, scientific, technological, and eco- nomic activity. ISO’s work results in international agreements that are pub- lished as International Standards.

A more detailed discussion of these organizations is contained in Appendix D.


7ISO is not an acronym (in which case it would be IOS), but it is a word, derived from the Greek, mean- ing equal.

Key Terms

access control active attack authentication authenticity availability data confidentiality data integrity

denial of service encryption integrity intruder masquerade nonrepudiation OSI security architecture

passive attack replay security attacks security mechanisms security services traffic analysis

Review Questions

1.1 What is the OSI security architecture? 1.2 List and briefly define the three key objectives of computer security. 1.3 List and briefly define categories of passive and active security attacks. 1.4 List and briefly define categories of security services. 1.5 List and briefly define categories of security mechanisms. 1.6 List and briefly define the fundamental security design principles. 1.7 Explain the difference between an attack surface and an attack tree.


1.1 Consider an automated cash deposit machine in which users provide a card or an ac- count number to deposit cash. Give examples of confidentiality, integrity, and avail- ability requirements associated with the system, and, in each case, indicate the degree of importance of the requirement.

1.2 Repeat Problem 1.1 for a payment gateway system where a user pays for an item using their account via the payment gateway.




1.3 Consider a financial report publishing system used to produce reports for various organizations. a. Give an example of a type of publication in which confidentiality of the stored

data is the most important requirement. b. Give an example of a type of publication in which data integrity is the most im-

portant requirement. c. Give an example in which system availability is the most important requirement.

1.4 For each of the following assets, assign a low, moderate, or high impact level for the loss of confidentiality, availability, and integrity, respectively. Justify your answers. a. A student maintaining a blog to post public information. b. An examination section of a university that is managing sensitive information

about exam papers. c. An information system in a pathological laboratory maintaining the patient’s data. d. A student information system used for maintaining student data in a university

that contains both personal, academic information and routine administrative in- formation (not privacy related). Assess the impact for the two data sets separately and the information system as a whole.

e. A University library contains a library management system which controls the distribution of books amongst the students of various departments. The library management system contains both the student data and the book data. Assess the impact for the two data sets separately and the information system as a whole.

1.5 Draw a matrix similar to Table 1.4 that shows the relationship between security ser- vices and attacks.

1.6 Draw a matrix similar to Table 1.4 that shows the relationship between security mechanisms and attacks.

1.7 Develop an attack tree for gaining access to the contents of a physical safe. 1.8 Consider a company whose operations are housed in two buildings on the same prop-

erty; one building is headquarters, the other building contains network and computer services. The property is physically protected by a fence around the perimeter, and the only entrance to the property is through this fenced perimeter. In addition to the perimeter fence, physical security consists of a guarded front gate. The local net- works are split between the Headquarters’ LAN and the Network Services’ LAN. Internet users connect to the Web server through a firewall. Dial-up users get access to a particular server on the Network Services’ LAN. Develop an attack tree in which the root node represents disclosure of proprietary secrets. Include physical, social engineering, and technical attacks. The tree may contain both AND and OR nodes. Develop a tree that has at least 15 leaf nodes.

1.9 Read all of the classic papers cited in the Recommended Reading section for this chapter, available at the Author Web site at The papers are available at Compose a 500–1000 word paper (or 8–12 slide PowerPoint presentation) that summarizes the key concepts that emerge from these papers, emphasizing concepts that are common to most or all of the papers.




2.1 Divisibility and The Division Algorithm Divisibility The Division Algorithm

2.2 The Euclidean Algorithm Greatest Common Divisor Finding the Greatest Common Divisor

2.3 Modular Arithmetic The Modulus Properties of Congruences Modular Arithmetic Operations Properties of Modular Arithmetic Euclidean Algorithm Revisited The Extended Euclidean Algorithm

2.4 Prime Numbers

2.5 Fermat’s and Euler’s Theorems

Fermat’s Theorem Euler’s Totient Function Euler’s Theorem

2.6 Testing for Primality

Miller–Rabin Algorithm A Deterministic Primality Algorithm Distribution of Primes

2.7 The Chinese Remainder Theorem

2.8 Discrete Logarithms

The Powers of an Integer, Modulo n Logarithms for Modular Arithmetic Calculation of Discrete Logarithms

2.9 Key Terms, Review Questions, and Problems

Appendix 2A The Meaning of Mod


Introduction to Number Theory




Number theory is pervasive in cryptographic algorithms. This chapter provides sufficient breadth and depth of coverage of relevant number theory topics for under- standing the wide range of applications in cryptography. The reader familiar with these topics can safely skip this chapter.

The first three sections introduce basic concepts from number theory that are needed for understanding finite fields; these include divisibility, the Euclidian algo- rithm, and modular arithmetic. The reader may study these sections now or wait until ready to tackle Chapter 5 on finite fields.

Sections 2.4 through 2.8 discuss aspects of number theory related to prime num- bers and discrete logarithms. These topics are fundamental to the design of asymmetric (public-key) cryptographic algorithms. The reader may study these sections now or wait until ready to read Part Three.

The concepts and techniques of number theory are quite abstract, and it is often difficult to grasp them intuitively without examples. Accordingly, this chapter includes a number of examples, each of which is highlighted in a shaded box.



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


After studying this chapter, you should be able to:

◆ Understand the concept of divisibility and the division algorithm.

◆ Understand how to use the Euclidean algorithm to find the greatest com- mon divisor.

◆ Present an overview of the concepts of modular arithmetic.

◆ Explain the operation of the extended Euclidean algorithm.

◆ Discuss key concepts relating to prime numbers.

◆ Understand Fermat’s theorem.

◆ Understand Euler’s theorem.

◆ Define Euler’s totient function.

◆ Make a presentation on the topic of testing for primality.

◆ Explain the Chinese remainder theorem.

◆ Define discrete logarithms.




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

■ If a � 1, then a = {1. ■ If a �b and b � a, then a = {b. ■ Any b ≠ 0 divides 0. ■ If a �b and b � c, then a � c:

The positive divisors of 24 are 1, 2, 3, 4, 6, 8, 12, and 24.

13 � 182; -5 � 30; 17 � 289; -3 � 33; 17 � 0

11 � 66 and 66 � 198 1 11 � 198

b = 7; g = 14; h = 63; m = 3; n = 2 7 � 14 and 7 � 63. To show 7 � (3 * 14 + 2 * 63), we have (3 * 14 + 2 * 63) = 7(3 * 2 + 2 * 9), and it is obvious that 7 � (7(3 * 2 + 2 * 9)).

■ If b � g and b �h, then b � (mg + nh) for arbitrary integers m and n.

To see this last point, note that

■ If b � g, then g is of the form g = b * g1 for some integer g1. ■ If b �h, then h is of the form h = b * h1 for some integer h1.


mg + nh = mbg1 + nbh1 = b * (mg1 + nh1)

and therefore b divides mg + nh.

The Division Algorithm

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

a = qn + r 0 … r 6 n; q = :a/n; (2.1) where :x; is the largest integer less than or equal to x. Equation (2.1) is referred to as the division algorithm.1

1Equation (2.1) expresses a theorem rather than an algorithm, but by tradition, this is referred to as the division algorithm.




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

a = 11; n = 7; 11 = 1 * 7 + 4; r = 4 q = 1 a = -11; n = 7; -11 = (-2) * 7 + 3; r = 3 q = -2

Figure 2.1b provides another example.

Figure 2.1 The Relationship a = qn + r; 0 … r 6 n


n 2n 3n qn (q + 1)na


r(a) General relationship

0 15



30 = 2 × 15


(b) Example: 70 = (4 × 15) + 10

45 = 3 × 15

60 = 4 × 15

75 = 5 × 15


One of the basic techniques of number theory is the Euclidean algorithm, which is a simple procedure for determining the greatest common divisor of two positive integers. First, we need a simple definition: Two integers are relatively prime if and only if their only common positive integer factor is 1.

Greatest Common Divisor

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




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

1. c is a divisor of a and of b.

2. any divisor of a and b is a divisor of c.

An equivalent definition is the following:

gcd(a, b) = max[k, such that k � a and k �b]

Because we require that the greatest common divisor be positive, gcd(a, b) = gcd(a, -b) = gcd(-a, b) = gcd(-a, -b). In general, gcd(a, b) = gcd( � a � , �b � ).

gcd(60, 24) = gcd(60, -24) = 12

8 and 15 are relatively prime because the positive divisors of 8 are 1, 2, 4, and 8, and the positive divisors of 15 are 1, 3, 5, and 15. So 1 is the only integer on both lists.

Also, because all nonzero integers divide 0, we have gcd(a, 0) = � a � . We stated that two integers a and b are relatively prime if and only if their

only common positive integer factor is 1. This is equivalent to saying that a and b are relatively prime if gcd(a, b) = 1.

Finding the Greatest Common Divisor

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 fol- lowing points:

1. Suppose we wish to determine the greatest common divisor d of the integers a and b; that is determine d = gcd(a, b). Because gcd( � a � , �b � ) = gcd(a, b), there is no harm in assuming a Ú b 7 0.

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

a = q1b + r1 0 … r1 6 b (2.2)

3. First consider the case in which r1 = 0. Therefore b divides a and clearly no larger number divides both b and a, because that number would be larger than b. So we have d = gcd(a, b) = b.

4. The other possibility from Equation (2.2) is r1 ≠ 0. For this case, we can state that d � r1. This is due to the basic properties of divisibility: the relations d � a and d �b together imply that d � (a – q1b), which is the same as d � r1.

5. Before proceeding with the Euclidian algorithm, we need to answer the ques- tion: What is the gcd(b, r1)? We know that d �b and d � r1. Now take any arbi- trary integer c that divides both b and r1. Therefore, c � (q1b + r1) = a. Because c divides both a and b, we must have c … d, which is the greatest common divisor of a and b. Therefore d = gcd(b, r1).




Let us now return to Equation (2.2) and assume that r1 ≠ 0. Because b 7 r1, we can divide b by r1 and apply the division algorithm to obtain:

b = q2r1 + r2 0 … r2 6 r1

As before, if r2 = 0, then d = r1 and if r2 ≠ 0, then d = gcd(r1, r2). 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 (n + 1)th stage where rn – 1 is divided by rn. The result is the following system of equations:


a = q1b + r1 0 6 r1 6 b b = q2r1 + r2 0 6 r2 6 r1 r1 = q3r2 + r3 0 6 r3 6 r2

~ ~

~ ~ ~ ~

rn – 2 = qnrn – 1 + rn 0 6 rn 6 rn – 1 rn – 1 = qn + 1rn + 0 d = gcd(a, b) = rn

w (2.3) At each iteration, we have d = gcd(ri, ri+ 1) until finally d = gcd(rn, 0) = rn.

Thus, we can find the greatest common divisor of two integers by repetitive appli- cation of the division algorithm. This scheme is known as the Euclidean algorithm. Figure 2.3 illustrates a simple example.

We have essentially argued from the top down that the final result is the gcd(a, b). We can also argue from the bottom up. The first step is to show that rn divides a and b. It follows from the last division in Equation (2.3) that rn divides rn – 1. The next to last division shows that rn divides rn – 2 because it divides both

Figure 2.2 Euclidean Algorithm


No Yes a > b?

r > 0? Swap

a and b

Replace b with r

Replace a with b

Divide a by b, calling the

remainder r

GCD is the final

value of b


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

710 = 2 × 310 + 90

310 = 3 × 90 + 40

90 = 2 × 40 + 10

40 = 4 × 10


Same GCD




terms on the right. Successively, one sees that rn divides all ri>s and finally a and b. It remains to show that rn is the largest divisor that divides a and b. If we take any arbitrary integer that divides a and b, it must also divide r1, as explained previously. We can follow the sequence of equations in Equation (2.3) down and show that c must divide all ri>s. Therefore c must divide rn, so that rn = gcd(a, b).

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

To find d = gcd(a, b) = gcd(1160718174, 316258250)

a = q1b + r1 1160718174 = 3 * 316258250 + 211943424 d = gcd(316258250, 211943424) b = q2r1 + r2 316258250 = 1 * 211943424 + 104314826 d = gcd(211943424, 104314826) r1 = q3r2 + r3 211943424 = 2 * 104314826 + 3313772 d = gcd(104314826, 3313772) r2 = q4r3 + r4 104314826 = 31 * 3313772 + 1587894 d = gcd(3313772, 1587894) r3 = q5r4 + r5 3313772 = 2 * 1587894 + 137984 d = gcd(1587894, 137984) r4 = q6r5 + r6 1587894 = 11 * 137984 + 70070 d = gcd(137984, 70070) r5 = q7r6 + r7 137984 = 1 * 70070 + 67914 d = gcd(70070, 67914) r6 = q8r7 + r8 70070 = 1 * 67914 + 2156 d = gcd(67914, 2156) r7 = q9r8 + r9 67914 = 31 * 2156 + 1078 d = gcd(2156, 1078) r8 = q10r9 + r10 2156 = 2 * 1078 + 0 d = gcd(1078, 0) = 1078 Therefore, d = gcd(1160718174, 316258250) = 1078

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 ri- 2 = qiri- 1 + ri, where ri- 2 is the dividend, ri- 1 is the divisor, qi is the quotient, and ri is the remainder. Table 2.1 sum- marizes the results.

Dividend Divisor Quotient Remainder

a = 1160718174 b = 316258250 q1 = 3 r1 = 211943424

b = 316258250 r1 = 211943434 q2 = 1 r2 = 104314826

r1 = 211943424 r2 = 104314826 q3 = 2 r3 = 3313772

r2 = 104314826 r3 = 3313772 q4 = 31 r4 = 1587894

r3 = 3313772 r4 = 1587894 q5 = 2 r5 = 137984

r4 = 1587894 r5 = 137984 q6 = 11 r6 = 70070

r5 = 137984 r6 = 70070 q7 = 1 r7 = 67914

r6 = 70070 r7 = 67914 q8 = 1 r8 = 2156

r7 = 67914 r8 = 2156 q9 = 31 r9 = 1078

r8 = 2156 r9 = 1078 q10 = 2 r10 = 0

Table 2.1 Euclidean Algorithm Example





The Modulus

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

a = qn + r 0 … r 6 n; q = :a/n; a = :a/n; * n + (a mod n)

11 mod 7 = 4; -11 mod 7 = 3

73 K 4 (mod 23); 21 K -9 (mod 10)

Two integers a and b are said to be congruent modulo n, if (a mod n) = (b mod n). This is written as a K b (mod n).2

2We have just used the operator mod in two different ways: first as a binary operator that produces a re- mainder, as in the expression a mod b; second as a congruence relation that shows the equivalence of two integers, as in the expression a K b (mod n). See Appendix 2A for a discussion.

Note that if a K 0 (mod n), then n � a.

Properties of Congruences

Congruences have the following properties:

1. a K b (mod n) if n � (a – b). 2. a K b (mod n) implies b K a (mod n). 3. a K b (mod n) and b K c (mod n) imply a K c (mod n).

To demonstrate the first point, if n � (a – b), then (a – b) = kn for some k. So we can write a = b + kn. Therefore, (a mod n) = (remainder when b + kn is divided by n) = (remainder when b is divided by n) = (b mod n).

23 K 8 (mod 5) because 23 – 8 = 15 = 5 * 3 -11 K 5 (mod 8) because -11 – 5 = -16 = 8 * (-2) 81 K 0 (mod 27) because 81 – 0 = 81 = 27 * 3

The remaining points are as easily proved.




Modular Arithmetic Operations

Note that, by definition (Figure 2.1), the (mod n) operator maps all integers into the set of integers {0, 1, c , (n – 1)}. 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:

1. [(a mod n) + (b mod n)] mod n = (a + b) mod n 2. [(a mod n) – (b mod n)] mod n = (a – b) mod n 3. [(a mod n) * (b mod n)] mod n = (a * b) mod n

We demonstrate the first property. Define (a mod n) = ra and (b mod n) = rb. Then we can write a = ra + jn for some integer j and b = rb + kn for some integer k. Then

(a + b) mod n = (ra + jn + rb + kn) mod n = (ra + rb + (k + j)n) mod n = (ra + rb) mod n = [(a mod n) + (b mod n)] mod n

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

11 mod 8 = 3; 15 mod 8 = 7 [(11 mod 8) + (15 mod 8)] mod 8 = 10 mod 8 = 2 (11 + 15) mod 8 = 26 mod 8 = 2 [(11 mod 8) – (15 mod 8)] mod 8 = -4 mod 8 = 4 (11 – 15) mod 8 = -4 mod 8 = 4 [(11 mod 8) * (15 mod 8)] mod 8 = 21 mod 8 = 5 (11 * 15) mod 8 = 165 mod 8 = 5

To find 117 mod 13, we can proceed as follows:

112 = 121 K 4 (mod 13) 114 = (112)2 K 42 K 3 (mod 13) 117 = 11 * 112 * 114

117 K 11 * 4 * 3 K 132 K 2 (mod 13)

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 reg- ular 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 modu- lar arithmetic. In this case, the negative of an integer x is the integer y such that (x + y) mod 8 = 0. To find the additive inverse of an integer in the left-hand col- umn, 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, (2 + 6) mod 8 = 0. Similarly, the entries in the multiplication table are straightforward. In modular arithmetic mod 8, the multiplicative inverse of x is the integer y such that (x * y) mod 8 = 1 mod 8. 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, (3 * 3) mod 8 = 1. Note that not all integers mod 8 have a multiplicative inverse; more about that later.

Properties of Modular Arithmetic

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

Zn = {0, 1, c , (n – 1)}

Table 2.2 Arithmetic Modulo 8 + 0 1 2 3 4 5 6 7

0 0 1 2 3 4 5 6 7

1 1 2 3 4 5 6 7 0

2 2 3 4 5 6 7 0 1

3 3 4 5 6 7 0 1 2

4 4 5 6 7 0 1 2 3

5 5 6 7 0 1 2 3 4

6 6 7 0 1 2 3 4 5

7 7 0 1 2 3 4 5 6

(a) Addition modulo 8

* 0 1 2 3 4 5 6 7

0 0 0 0 0 0 0 0 0

1 0 1 2 3 4 5 6 7

2 0 2 4 6 0 2 4 6

3 0 3 6 1 4 7 2 5

4 0 4 0 4 0 4 0 4

5 0 5 2 7 4 1 6 3

6 0 6 4 2 0 6 4 2

7 0 7 6 5 4 3 2 1

(b) Multiplication modulo 8

w -w w-1

0 0 —

1 7 1

2 6 —

3 5 3

4 4 —

5 3 5

6 2 —

7 1 7

(c) Additive and multiplicative inverse modulo 8




This is referred to as the set of residues, or residue classes (mod n). To be more pre- cise, each integer in Zn represents a residue class. We can label the residue classes (mod n) as [0], [1], [2], c , [n – 1], where

[r] = {a: a is an integer, a K r (mod n)}

The residue classes (mod 4) are

[0] = {c , -16, -12, -8, -4, 0, 4, 8, 12, 16, c } [1] = {c , -15, -11, -7, -3, 1, 5, 9, 13, 17, c } [2] = {c , -14, -10, -6, -2, 2, 6, 10, 14, 18, c } [3] = {c , -13, -9, -5, -1, 3, 7, 11, 15, 19, c }

Property Expression

Commutative Laws (w + x) mod n = (x + w) mod n (w * x) mod n = (x * w) mod n

Associative Laws [(w + x) + y] mod n = [w + (x + y)] mod n [(w * x) * y] mod n = [w * (x * y)] mod n

Distributive Law [w * (x + y)] mod n = [(w * x) + (w * y)] mod n

Identities (0 + w) mod n = w mod n (1 * w) mod n = w mod n

Additive Inverse (-w) For each w∈ Zn, there exists a z such that w + z K 0 mod n

Table 2.3 Properties of Modular Arithmetic for Integers in Zn

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 k is congruent modulo n is called reducing k modulo n.

If we perform modular arithmetic within Zn, the properties shown in Table 2.3 hold for integers in Zn. We show in the next section that this implies that Zn 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:

if (a + b) K (a + c) (mod n) then b K c (mod n) (2.4)

(5 + 23) K (5 + 7)(mod 8); 23 K 7(mod 8)

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

((-a) + a + b) K ((-a) + a + c)(mod n) b K c (mod n)




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

if (a * b) K (a * c)(mod n) then b K c(mod n) if a is relatively prime to n (2.5)

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 a to both sides of Equation (2.5), we have

((a-1)ab) K ((a-1)ac)(mod n) b K c(mod n)

To see this, consider an example in which the condition of Equation (2.5) does not hold. The integers 6 and 8 are not relatively prime, since they have the common factor 2. We have the following:

6 * 3 = 18 K 2(mod 8) 6 * 7 = 42 K 2(mod 8)

Yet 3 [ 7 (mod 8).

The reason for this strange result is that for any general modulus n, a multi- plier a that is applied in turn to the integers 0 through (n – 1) will fail to produce a complete set of residues if a and n have any factors in common.

With a = 6 and n = 8,

Z8 0 1 2 3 4 5 6 7 Multiply by 6 0 6 12 18 24 30 36 42 Residues 0 6 4 2 0 6 4 2

Because we do not have a complete set of residues when multiplying by 6, more than one integer in Z8 maps into the same residue. Specifically, 6 * 0 mod 8 = 6 * 4 mod 8; 6 * 1 mod 8 = 6 * 5 mod 8; and so on. Because this is a many-to-one mapping, there is not a unique inverse to the multiply operation.

However, if we take a = 5 and n = 8, whose only common factor is 1,

Z8 0 1 2 3 4 5 6 7 Multiply by 5 0 5 10 15 20 25 30 35 Residues 0 5 2 7 4 1 6 3

The line of residues contains all the integers in Z8, in a different order.




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

Euclidean Algorithm Revisited

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

gcd(a, b) = gcd(b, a mod b) (2.6)

gcd(55, 22) = gcd(22, 55 mod 22) = gcd(22, 11) = 11

gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6 gcd(11, 10) = gcd(10, 1) = gcd(1, 0) = 1

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

a = kb + r K r (mod b) a mod b = r

with k, r integers. Therefore, (a mod b) = a – kb for some integer k. But because d �b, it also divides kb. We also have d � a. Therefore, d � (a mod b). This shows that d is a common divisor of b and (a mod b). Conversely, if d is a common divisor of b and (a mod b), then d �kb and thus d � [kb + (a mod b)], which is equivalent to d � a. Thus, the set of common divisors of a and b is equal to the set of common divisors of b and (a mod b). 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.

Euclidean Algorithm

Calculate Which satisfies

r1 = a mod b a = q1b + r1 r2 = b mod r1 b = q2r1 + r2 r3 = r1 mod r2 r1 = q3r2 + r3







rn = rn – 2 mod rn – 1 rn – 2 = qnrn – 1 + rn rn + 1 = rn – 1 mod rn = 0 rn – 1 = qn + 1rn + 0

d = gcd(a, b) = rn

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);

The Extended Euclidean Algorithm

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 algo- rithms, such as RSA. For given integers a and b, the extended Euclidean algorithm not only calculates the greatest common divisor d but also two additional integers x and y that satisfy the following equation.

ax + by = d = gcd(a, b) (2.7)

It should be clear that x and y will have opposite signs. Before examining the algorithm, let us look at some of the values of x and y when a = 42 and b = 30. Note that gcd(42, 30) = 6. Here is a partial table of values3 for 42x + 30y.

x − 3 − 2 − 1 0 1 2 3


-3 -216 -174 -132 -90 -48 -6 36 -2 -186 -144 -102 -60 -18 24 66 -1 -156 -114 -72 -30 12 54 96

0 -126 -84 -42 0 42 84 126 1 -96 -54 -12 30 72 114 156 2 -66 -24 18 60 102 144 186 3 -36 6 48 90 132 174 216

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

Now let us show how to extend the Euclidean algorithm to determine (x, y, d) given a and b. We again go through the sequence of divisions indicated in Equation (2.3), and we assume that at each step i we can find integers xi and yi that satisfy ri = axi + byi. We end up with the following sequence.

a = q1b + r1 r1 = ax1 + by1 b = q2r1 + r2 r2 = ax2 + by2 r1 = q3r2 + r3 r3 = ax3 + by3

f f rn – 2 = qnrn – 1 + rn rn = axn + byn rn – 1 = qn + 1rn + 0

3This example is taken from [SILV06].




Now, observe that we can rearrange terms to write

ri = ri- 2 – ri- 1qi (2.8)

Also, in rows i – 1 and i – 2, we find the values

ri- 2 = axi- 2 + byi- 2 and ri- 1 = axi- 1 + byi- 1

Substituting into Equation (2.8), we have

ri = (axi- 2 + byi- 2) – (axi- 1 + byi- 1)qi = a(xi- 2 – qixi- 1) + b(yi- 2 – qiyi- 1)

But we have already assumed that ri = axi + byi. Therefore,

xi = xi- 2 – qixi- 1 and yi = yi- 2 – qiyi- 1

We now summarize the calculations:

Extended Euclidean Algorithm

Calculate Which satisfies Calculate Which satisfies

r-1 = a x-1 = 1; y-1 = 0 a = ax-1 + by-1 r0 = b x0 = 0; y0 = 1 b = ax0 + by0 r1 = a mod b q1 = :a/b;

a = q1b + r1 x1 = x-1 – q1x0 = 1 y1 = y-1 – q1y0 = -q1

r1 = ax1 + by1

r2 = b mod r1 q2 = :b/r1;

b = q2r1 + r2 x2 = x0 – q2x1 y2 = y0 – q2y1

r2 = ax2 + by2

r3 = r1 mod r2 q3 = :r1/r2;

r1 = q3r2 + r3 x3 = x1 – q3x2 y3 = y1 – q3y2

r3 = ax3 + by3













rn = rn – 2 mod rn – 1 qn = :rn – 2/rn – 1;

rn – 2 = qnrn – 1 + rn xn = xn – 2 – qnxn – 1 yn = yn – 2 – qnyn – 1

rn = axn + byn

rn + 1 = rn – 1 mod rn = 0 qn + 1 = :rn – 1/rn;

rn – 1 = qn + 1rn + 0 d = gcd(a, b) = rn x = xn; y = yn

We need to make several additional comments here. In each row, we calculate a new remainder ri based on the remainders of the previous two rows, namely ri- 1 and ri- 2. To start the algorithm, we need values for r0 and r-1, which are just a and b. It is then straightforward to determine the required values for x-1, y-1, x0, and y0.

We know from the original Euclidean algorithm that the process ends with a remainder of zero and that the greatest common divisor of a and b is d = gcd(a, b) = rn. But we also have determined that d = rn = axn + byn. Therefore, in Equation (2.7), x = xn and y = yn.

As an example, let us use a = 1759 and b = 550 and solve for 1759x + 550y = gcd(1759, 550). The results are shown in Table 2.4. Thus, we have 1759 * (-111) + 550 * 355 = -195249 + 195250 = 1.





A central concern of number theory is the study of prime numbers. Indeed, whole books have been written on the subject (e.g., [CRAN01], [RIBE96]). In this section, we provide an overview relevant to the concerns of this book.

An integer p 7 1 is a prime number if and only if its only divisors5 are {1 and {p. Prime numbers play a critical role in number theory and in the techniques dis- cussed in this chapter. Table 2.5 shows the primes less than 2000. Note the way the primes are distributed. In particular, note the number of primes in each range of 100 numbers.

Any integer a 7 1 can be factored in a unique way as

a = p1a1 * p2a2 * g * ptat (2.9)

where p1 6 p2 6 c 6 pt are prime numbers and where each ai is a positive inte- ger. This is known as the fundamental theorem of arithmetic; a proof can be found in any text on number theory.

4In this section, unless otherwise noted, we deal only with the nonnegative integers. The use of negative integers would introduce no essential differences. 5Recall from Section 2.1 that integer a is said to be a divisor of integer b if there is no remainder on division. Equivalently, we say that a divides b.

i ri qi xi yi

-1 1759 1 0

0 550 0 1

1 109 3 1 -3

2 5 5 -5 16

3 4 21 106 -339

4 1 1 -111 355

5 0 4

Result: d = 1; x = -111; y = 355

Table 2.4 Extended Euclidean Algorithm Example

91 = 7 * 13 3600 = 24 * 32 * 52

11011 = 7 * 112 * 13

It is useful for what follows to express this another way. If P is the set of all prime numbers, then any positive integer a can be written uniquely in the following form:

a = q p∈P

pap where each ap Ú 0




2 10

1 21

1 30

7 40

1 50

3 60

1 70

1 80

9 90

7 10

09 11

03 12

01 13

01 14

09 15

11 16

01 17

09 18

01 19


3 10

3 22

3 31

1 40

9 50

9 60

7 70

9 81

1 91

1 10

13 11

09 12

13 13

03 14

23 15

23 16

07 17

21 18

11 19


5 10

7 22

7 31

3 41

9 52

1 61

3 71

9 82

1 91

9 10

19 11

17 12

17 13

07 14

27 15

31 16

09 17

23 18

23 19


7 10

9 22

9 31

7 42

1 52

3 61

7 72

7 82

3 92

9 10

21 11

23 12

23 13

19 14

29 15

43 16

13 17

33 18

31 19


11 11

3 23

3 33

1 43

1 54

1 61

9 73

3 82

7 93

7 10

31 11

29 12

29 13

21 14

33 15

49 16

19 17

41 18

47 19


13 12

7 23

9 33

7 43

3 54

7 63

1 73

9 82

9 94

1 10

33 11

51 12

31 13

27 14

39 15

53 16

21 17

47 18

61 19


17 13

1 24

1 34

7 43

9 55

7 64

1 74

3 83

9 94

7 10

39 11

53 12

37 13

61 14

47 15

59 16

27 17

53 18

67 19


19 13

7 25

1 34

9 44

3 56

3 64

3 75

1 85

3 95

3 10

49 11

63 12

49 13

67 14

51 15

67 16

37 17

59 18

71 19


23 13

9 25

7 35

3 44

9 56

9 64

7 75

7 85

7 96

7 10

51 11

71 12

59 13

73 14

53 15

71 16

57 17

77 18

73 19


29 14

9 26

3 35

9 45

7 57

1 65

3 76

1 85

9 97

1 10

61 11

81 12

77 13

81 14

59 15

79 16

63 17

83 18

77 19


31 15

1 26

9 36

7 46

1 57

7 65

9 76

9 86

3 97

7 10

63 11

87 12

79 13

99 14

71 15

83 16

67 17

87 18

79 19

Leave a Reply

Your email address will not be published. Required fields are marked *