PUBLIC-KEY

CRYPTOGRAPHY

© 2003 by CRC Press LLC

DISCRETE

MATHEMATICS

and

ITS APPLICATIONS Series Editor

Kenneth H. Rosen, Ph.D.

AT&T Labs

Abstract Algebra Applications with Maple,

Richard E. Klima, Ernest Stitzinger, and Neil P. Sigmon

Algebraic Number Theory, Richard A. Mollin

An Atlas of The Smaller Maps in Orientable and Nonorientable Surfaces,

David M. Jackson and Terry I. Visentin

An Introduction to Crytography, Richard A. Mollin

Combinatorial Algorithms: Generation Enumeration and Search,

Donald L. Kreher and Douglas R. Stinson

The CRC Handbook of Combinatorial Designs,

Charles J. Colbourn and Jeffrey H. Dinitz

Cryptography: Theory and Practice, Second Edition, Douglas R. Stinson

Design Theory, Charles C. Lindner and Christopher A. Rodgers

Frames and Resolvable Designs: Uses, Constructions, and Existence,

Steven Furino, Ying Miao, and Jianxing Yin

Fundamental Number Theory with Applications, Richard A. Mollin

Graph Theory and Its Applications, Jonathan Gross and Jay Yellen

Handbook of Applied Cryptography,

Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone

Handbook of Constrained Optimization,

Herbert B. Shulman and Venkat Venkateswaran

Handbook of Discrete and Combinatorial Mathematics, Kenneth H. Rosen

Handbook of Discrete and Computational Geometry,

Jacob E. Goodman and Joseph O™Rourke

Introduction to Information Theory and Data Compression,

Darrel R. Hankerson, Greg A. Harris, and Peter D. Johnson

© 2003 by CRC Press LLC

Continued Titles

Network Reliability: Experiments with a Symbolic Algebra Environment,

Daryl D. Harms, Miroslav Kraetzl, Charles J. Colbourn, and John S. Devitt

RSA and Public-Key Cryptography

Richard A. Mollin

Quadratics, Richard A. Mollin

Verificaton of Computer Codes in Computational Science and Engineering,

Patrick Knupp and Kambiz Salari

© 2003 by CRC Press LLC

DISCRETE MATHEMATICS AND ITS APPLICATIONS

Series Editor KENNETH H. ROSEN

RSA and

PUBLIC-KEY

CRYPTOGRAPHY

Richard A. Mollin

CHAPMAN & HALL/CRC

A CRC Press Company

Boca Raton London New York Washington, D.C.

© 2003 by CRC Press LLC

Library of Congress Cataloging-in-Publication Data

Mollin, Richard A., 1947-

RSA and public-key cryptography / Richard A. Mollin.

p. cm. ” (Discrete mathematics and its applicatoins)

Includes bibliographical references and index.

ISBN 1-58488-338-3

1. Coding theory. 2. Public key cryptography. I. Title. II. Series.

QA268 .M655 2002

652′.8”dc21 2002031096

This book contains information obtained from authentic and highly regarded sources. Reprinted material

is quoted with permission, and sources are indicated. A wide variety of references are listed. Reasonable

efforts have been made to publish reliable data and information, but the author and the publisher cannot

assume responsibility for the validity of all materials or for the consequences of their use.

Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic

or mechanical, including photocopying, micro¬lming, and recording, or by any information storage or

retrieval system, without prior permission in writing from the publisher.

The consent of CRC Press LLC does not extend to copying for general distribution, for promotion, for

creating new works, or for resale. Speci¬c permission must be obtained in writing from CRC Press LLC

for such copying.

Direct all inquiries to CRC Press LLC, 2000 N.W. Corporate Blvd., Boca Raton, Florida 33431.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are

used only for identi¬cation and explanation, without intent to infringe.

Visit the CRC Press Web site at www.crcpress.com

© 2003 by CRC Press LLC

No claim to original U.S. Government works

International Standard Book Number 1-58488-338-3

Library of Congress Card Number 2002031096

Printed in the United States of America 1 2 3 4 5 6 7 8 9 0

Printed on acid-free paper

© 2003 by CRC Press LLC

Preface

This book is intended for a second course in cryptography at the undergrad-

uate level, where the student is assumed to have had a course in introductory

number theory. Also, the book is intended as a source book for those in the

cryptography business, who will ¬nd collected together herein numerous facts

that are currently scattered throughout the literature on public-key cryptogra-

phy and related issues described in the Table of Contents. The impetus for the

writing of this text arose from the author™s involvement in the establishment of

an iCORE (Informatics Circle of Research Excellence) Chair in cryptography at

the University of Calgary in September of 2001, and the launching of an associ-

ated Centre for Information Security and Cryptography (CISAC). In addition to

the education of numerous graduate students and postdoctoral fellows in cryp-

tology, we have an ongoing commitment to the development of a new stream

of cryptography courses for the Mathematics Department. This text will serve

as the text for one of them at the senior undergraduate level. No suitable text

for that course was on the market, nor is there one at the time of this writing,

hence the appearance of this one.

x Features of This Text

• The book is ideal for the student since it o¬ers a wealth of exercises with 350

problems. The more challenging exercises are marked with a °. Also, complete

and detailed solutions to all of the odd-numbered exercises are provided at the

back of the text. Complete and detailed solutions of the even-numbered exercises

are included in a Solutions Manual, which is available from the publisher for

the instructor who adopts the text for a course. Moreover, the exercises are

presented at the end of each section, rather than at the end of each chapter.

• The text is accessible to anyone from the senior undergraduate to the

research scientist, and all levels of readers will ¬nd challenging and inspira-

tional data. To ensure that the book is as self-contained as possible, we have

three appendices of relevant background information. Appendix A has a brief,

but highly informative, overview of letter frequency analysis (of the English

language) to assist in our cryptanalytic travels. Appendix B has a solid back-

ground review and analysis of elementary complexity theory to provide us with

the necessary tools for algorithmic analysis and related phenomena. Lastly,

Appendix C contains the fundamentals of the number-theoretic results used in

the text together with any other relevant information that we will need such as

vector space basics, matrix theory fundamentals, and some facts on continued

fractions.

• There are over 100 footnotes containing nearly 40 biographies of the indi-

viduals who helped develop cryptologic concepts, together with historical data

of interest, as well as other information which the discerning reader may want

to explore at leisure. These are woven throughout the text, to give a human face

v

© 2003 by CRC Press LLC

vi RSA and Public-Key Cryptography

to the cryptology being presented. A knowledge of the lives of these individ-

uals can only deepen our appreciation of the development of PKC and related

concepts. The footnote presentation of this material allows the reader to have

immediate information at will, or to treat them as digressions, and access them

later without signi¬cantly interfering with the main discussion.

• There are optional topics, denoted by , which add additional material

for the more advanced reader or the reader requiring more challenging material

which goes beyond the basics presented in the core data.

• There are more than 60 examples, diagrams, ¬gures, and tables throughout

the text to illustrate the concepts presented.

• For ease of search, the reader will ¬nd consecutive numbering, namely

object N.m is the mth object in Chapter N (or Appendix N ), exclusive of

footnotes and exercises, which are numbered separately and consecutively unto

themselves. Thus, for instance, Diagram 3.5 is the 5th numbered object in

Chapter Three; exclusive of footnotes and exercises; Exercise 4.37 is the 37th

exercise in Chapter Four; and Footnote 9.2 is the second footnote in Chapter

Nine.

• The bibliography contains nearly 250 references for further reading.

• The index has more than 2,000 entries, and has been devised in such a way

to ensure that there is maximum ease in getting information from the text.

• The webpage cited below will contain a ¬le for comments, and any ty-

pos/errors that are found. Furthermore, comments via the e-mail address below

are also welcome. Lastly, if the instructor for a given course, using this text, has

any di¬culty in getting the solutions manual for the even-numbered exercises,

contacting the author will expedite matters.

x Acknowledgments First of all, thanks go to Hugh Williams for discus-

sions prior to the writing of this book that inspired my creating the original

template for a table of contents. As iCORE Chair in cryptography at U. of

C., he has brought a new dimension and exciting prospects for the future. The

author is grateful for the proofreading done by the following people, each of

whom lent his own (largely non-intersecting) expertise and valuable time: John

Brillhart (U.S.A.), John Burke (U.S.A.), Jacek Fabrykowski (U.S.A.), Bart God-

dard (U.S.A.), Franz Lemmermeyer (U.S.A.), John Robertson (U.S.A.), Kjell

Wooding (Canada), graduate student in cryptography at U. of C., Thomas

Zaplachinski (Canada), a former student, now cryptographer, and Robert Zuc-

cherato (U.S.A.).

Richard Mollin, Calgary, September 1, 2002

website: http://www.math.ucalgary.ca/˜ramollin/

e-mail: ramollin@math.ucalgary.ca

© 2003 by CRC Press LLC

The Author vii

About the Author

Richard Anthony Mollin received his Ph.D. in mathematics (1975) from

Queen™s University, Kingston, Ontario, Canada, where he was born. He is now

a full professor in the Mathematics Department at the University of Calgary,

Alberta, Canada. He has over 160 publications in algebra, number theory,

computational mathematics, and cryptology to his credit. This book is his

seventh, with [160]“[165] being the other six. He resides in Calgary with his

wife Bridget and two cats. When not engaged in mathematics or entertaining

friends and mathematical visitors from all over the world, he and Bridget enjoy

hiking in the Canadian Rockies.

© 2003 by CRC Press LLC

To Bridget ” as always

ix

© 2003 by CRC Press LLC

Contents

1 History and Basic Cryptographic Concepts 1

1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Classical Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.3 Classi¬cation of Attacks . . . . . . . . . . . . . . . . . . . . . 25

2 Protocols, Discrete Log, and Di¬e-Hellman 33

2.1 Cryptographic Protocols . . . . . . . . . . . . . . . . . . . . . 33

2.2 The Discrete Log Problem . . . . . . . . . . . . . . . . . . . 39

2.3 Exponentiation Ciphers and Di¬e-Hellman . . . . . . . . . 47

3 Public-Key Cryptography 53

3.1 One-Way Functions . . . . . . . . . . . . . . . . . . . . . . . . 53

3.2 Public-Key Cryptosystems and RSA . . . . . . . . . . . . . 60

3.3 ElGamal Cryptosystems . . . . . . . . . . . . . . . . . . . . . 67

3.4 Symmetric vs. Asymmetric Cryptosystems . . . . . . . . . 73

3.5 Secret History of Public-Key Cryptography . . . . . . . . 77

4 Probabilistic Primality Tests 79

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

4.2 Pseudoprimes and Carmichael Numbers . . . . . . . . . . . 81

4.3 Solovay-Strassen Test . . . . . . . . . . . . . . . . . . . . . . . 84

4.4 Miller-Selfridge-Rabin Test . . . . . . . . . . . . . . . . . . . 87

5 Factoring 93

5.1 Universal Exponent Method . . . . . . . . . . . . . . . . . . 93

5.2 Pollard™s p ’ 1 Method . . . . . . . . . . . . . . . . . . . . . . 96

5.3 Lenstra™s Elliptic Curve Method . . . . . . . . . . . . . . 99

5.4 Multipolynomial Quadratic Sieve . . . . . . . . . . . . . . . 104

5.5 The Number Field Sieve . . . . . . . . . . . . . . . . . . . 108

6 Security of RSA 111

6.1 Implementation Attacks . . . . . . . . . . . . . . . . . . . . . 111

6.2 Exponent Attacks . . . . . . . . . . . . . . . . . . . . . . . . . 115

6.3 Strong Moduli . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

xi

© 2003 by CRC Press LLC

xii RSA and Public-Key Cryptography

6.4 Generation of Random Primes . . . . . . . . . . . . . . . . . 124

7 Authentication 127

7.1 Identi¬cation, Impersonation, and Signatures . . . . . . . 127

7.2 Digital Signature Schemes . . . . . . . . . . . . . . . . . . . . 135

7.3 Digital Cash and Electronic Commerce . . . . . . . . . . . 143

8 Key Management 153

8.1 Secret Sharing . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

8.2 Key Establishment . . . . . . . . . . . . . . . . . . . . . . . . 160

8.3 Public-Key Infrastructure (PKI) . . . . . . . . . . . . . . . 173

9 Applications and the Future 179

9.1 Secrecy and Authentication . . . . . . . . . . . . . . . . . . . 179

9.2 Other Threats to System Security . . . . . . . . . . . . . . . 185

9.3 Wireless Security . . . . . . . . . . . . . . . . . . . . . . . . . 190

9.4 Smart Cards and Biometrics . . . . . . . . . . . . . . . . . . 198

Appendix A: Letter Frequency Analysis . . . . . . . . . . . . . . . . . . . . . 203

Appendix B: Elementary Complexity Theory . . . . . . . . . . . . . . . . 205

Appendix C: Fundamental Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

Solutions to Odd-Numbered Exercises . . . . . . . . . . . . . . . . . . . . . . . 224

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

© 2003 by CRC Press LLC