Algorithms and Computation

in Mathematics Volume 3
Editors
Manuel Bronstein Arjeh M. Cohen
Henri Cohen David Eisenbud
Bernd Sturmfels

Springer-Verlag Berlin Heidelberg GmbH

Neal Koblitz

Algebraic Aspects
of Cryptography
With an Appendix on
Hyperelliptic Curves by
Alfred J. Menezes,
Yi-Hong Wu, and
Robert J. Zuccherato

With 7 Figures

Springer

Neal Koblitz

Yi-HongWu

Department of Mathematics
University of Washington
Seattle, WA 98195, USA
e-mail:
[email protected]

Department of Discrete and

Statistical Sciences
Auburn University
Auburn, AL 36849, USA

Alfred J. Menezes

Robert J. Zuccherato

Department of Combinatrics
and Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L3G1
e-mail:
[email protected]

Entrust Technologies
750 Heron Road
Ottawa, Ontario
Canada K1V1A7
e-mail:
[email protected]

lst ed. 1998. Corr. 1nd printing 1999, 3rd printing 1004

Mathematics Subject Classification (2000): llT71, 94A60, 68P25, llY16, llY40

Cataloging-in-Publication Data applied for

A catalog record for tbis book is available from tbe Library of Congress.
Bibliographic information published by Die Deutsche Bibliotbek
Die Deutsche Bibliotbek lists tbis publication in tbe Deutsche Nationalbibliografie;
detaiIed bibliographic data is avaiIable in tbe Internet at http://dnb.ddb.de

ISSN 1431-1550
ISBN 978-3-642-08332-7
ISBN 978-3-662-03642-6 (eBook)
DOI 10.1007/978-3-662-03642-6
This work is subject to copyright. All rights are reserved, whetber tbe whole or part of tbe material
is concerned, specificaJJy tbe rights of translation, reprinting, reuse of illustrations, recitation,
broadcasting, reproduction on microfilm or in any otber way, and storage in data banks. Duplication
of tbis publication or parts tbereof is permitted onJy under tbe provisions of tbe German Copyright
Law of September 9, 1965, in its current version, and permission for use must always be obtained
from Springer-VerJag. VioJations are liable for prosecution under tbe German Copyright Law.
springeronline.com

e Springer-Verlag Berlin Heidelberg 1998

Origina1ly published by Springer-Veriag Berlin Heidelberg New York in 1998
Softcover reprint of tbe hardcover lst edition 1998

The use of general descriptive names, registered names, trademarks, etc. in tbis publication does not
imply, even in tbe absence of a specific statement, that such names are exempt from tbe relevant protective laws and regulations and tberefore free for general use.
Typeset by tbe autbor using a Springer BrJll( macro package
Cover design: design & production GmbH, Heidelberg
Printed on acid-free paper

46/3141db - 5 4 3 1-

Preface

This book is intended as a text for a course on cryptography with emphasis on

algebraic methods. It is written so as to be accessible to graduate or advanced
undergraduate students, as well as to scientists in other fields. The first three
chapters form a self-contained introduction to basic concepts and techniques. Here
my approach is intuitive and informal. For example, the treatment of computational
complexity in Chapter 2, while lacking formalistic rigor, emphasizes the aspects
of the subject that are most important in cryptography.
Chapters 4-6 and the Appendix contain material that for the most part has not
previously appeared in textbook form. A novel feature is the inclusion of three
types of cryptography - "hidden monomial" systems, combinatorial-algebraic systems, and hyperelliptic systems - that are at an early stage of development. It is
too soon to know which, if any, of these cryptosystems will ultimately be of
practical use. But in the rapidly growing field of cryptography it is worthwhile
to continually explore new one-way constructions coming from different areas of
mathematics. Perhaps some of the readers will contribute to the research that still
needs to be done.
This book is designed not as a comprehensive reference work, but rather as
a selective textbook. The many exercises (with answers at the back of the book)
make it suitable for use in a math or computer science course or in a program of
independent study.
I wish to thank the participants in the Mathematical Sciences Research Institute's Summer Graduate Student Program in Algebraic Aspects of Cryptography
(Berkeley, 16-27 June 1997) for giving me the opportunity to test-teach parts ofthe
manuscript of this book and for finding errors and unclarities that needed fixing.
I am especially grateful to Alfred Menezes for carefully reading the manuscript
and making many valuable corrections and suggestions. Finally, I would like to
thank Jacques Patarin for letting me report on his work (some of it not yet published) in Chapter 4; and Alfred Menezes, Yi-Hong Wu, and Robert Zuccherato
for agreeing to let me include their elementary treatment of hyperelliptic curves
as an Appendix.
Seattle, September 1997

Neal Koblitz

Contents

Chapter 1. Cryptography

..................................... .

1. Early History ..............................................

2. The Idea of Public Key Cryptography ..........................
3. The RSA Cryptosystem .....................................
4. Diffie-Hellman and the Digital Signature Algorithm ..............
5. Secret Sharing, Coin Flipping, and Time Spent on Homework ......
6. Passwords, Signatures, and Ciphers ............................
7. Practical Cryptosystems and Useful Impractical Ones .............
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1
2
5
8
10
12
13
17

Chapter 2. Complexity of Computations

18

1. The Big-O Notation ........................................

Exercises .................................................
2. Length of Numbers .........................................
Exercises .................................................
3. Time Estimates ............................................
Exercises .................................................
4. P, NP, and NP-Completeness .................................
Exercises .................................................
5. Promise Problems ..........................................
6. Randomized Algorithms and Complexity Classes .................
Exercises .................................................
7. Some Other Complexity Classes ..............................
Exercises .................................................

18
21
22
23
24
31
34
41
44
45
48
48
52

Chapter 3. Algebra

53

1. Fields ....................................................
Exercises .................................................
2. Finite Fields ...............................................
Exercises .................................................
3. The Euclidean Algorithm for Polynomials ......................
Exercises .................................................
4. Polynomial Rings ..........................................
Exercises .................................................

53
55
55
61
63
64
65
70

VITI

Contents

5. Grobner Bases
Exercises ................................................ .

70

Chapter 4. Hidden Monomial Cryptosystems

80

1. The Imai-Matsumoto System .................................

78

Exercises .................................................
2. Patarin's Little Dragon ......................................
Exercises .................................................
3. Systems That Might Be More Secure ..........................
Exercises .................................................

80
86
87
95
96
102

Chapter 5. Combinatorial-Algebraic Cryptosystems

...............

103

1. History ...................................................
2. Irrelevance of Brassard's Theorem .............................
Exercises .................................................
3. Concrete Combinatorial-Algebraic Systems .....................
Exercises .................................................
4. The Basic Computational Algebra Problem ......................
Exercises .................................................
5. Cryptographic Version of Ideal Membership .....................
6. Linear Algebra Attacks ......................................
7. Designing a Secure System ..................................

103
104
105
105
109
111
112
112
113
114

Chapter 6. EUiptic and HypereUiptic Cryptosystems

...............

117

1. Elliptic Curves .............................................

Exercises .................................................
2. Elliptic Curve Cryptosystems .................................
Exercises .................................................
3. Elliptic Curve Analogues of Classical Number Theory Problems ....
Exercises .................................................
4. Cultural Background: Conjectures on Elliptic Curves
and Surprising Relations with Other Problems ...................
5. Hyperelliptic Curves ........................................
Exercises .................................................
6. Hyperelliptic Cryptosystems ..................................
Exercises .................................................

117
129
131
136
137
139
139
144
148
148
154

Appendix. An Elementary Introduction to HypereUiptic Curves

by Alfred J. Menezes, Yi-Hong Wu, and Robert J. Zuccherato ..........

155

1.
2.
3.
4.

156
159
161
167

Basic Definitions and Properties ...............................

Polynomial and Rational Functions ............................
Zeros and Poles ............................................
Divisors ..................................................

Contents

IX

5. Representing Semi-Reduced Divisors ..........................

6. Reduced Divisors ..........................................
7. Adding Reduced Divisors ....................................
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..

169
171
172
178

Answers to Exercises

179

..........................................

Bibliography

193

Subject Index

201