RSA and
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