ENC: Review of Cryptanalysis book?

[Mads Rasmussen]

Remember I asked some time ago about a review for Samuel Wagstaff's
recent book on cryptanalysis of number theoretic ciphers?

I still haven't found any, but I wrote to Samuel to ask him if he knew
if any existed.

Below I have, with his permission, copied his answer.

Regards,

Mads

-----Mensagem original-----
De: Samuel S Wagstaff [mailto:ssw at cerias.purdue.edu] 
Enviada em: quarta-feira, 2 de abril de 2003 17:44
Para: Mads Rasmussen
Assunto: Re: Review of Cryptanalysis book?

Dear Mads,

In fact I have not seen a review of my book yet.  I think it
is too soon for one to be published, although I expect that
reviews of it are being prepared.

If I wrote a review, of course it would be favorably biased
and so not much use to you.

An announcement (flyer) describing the book is available at the
URL <http://www.cerias.purdue.edu/homes/ssw/contc/index.html>

Part of the Preface to the book is appended to this note.
Perhaps that will satisfy your employer.

Sincerely,

Sam Wagstaff

--

>From the Preface of Cryptanalysis of Number Theoretic Ciphers:

This work has its origins in a cryptography course taught by the
author many times during the past twenty years in the Computer
Science Department at Purdue University.

Part I gives the mathematical background for cryptography as well as
some definitions and simple examples from cryptography.  The
cryptographic definitions appear in the first chapter.

The second chapter treats some topics from elementary probability
theory which are needed most for cryptanalysis.

Chapters 3 through 7 give a standard first course in elementary number
theory, but with a slant toward computation and with the needs of
cryptography always in mind.  Thus, Chapter 3, on divisibility, also
tells how to perform arithmetic with large integers and Chapter 4,
which is about primes, discusses the probability that a ``random''
large integer will have only small prime factors.  This topic is rarely
discussed in the chapter on primes in an elementary number theory book,
but is needed to estimate the difficulty of breaking certain ciphers.

Chapter 5 introduces congruences, which are used in many modern
cryptographic algorithms.  Chapter 6 proves Fermat's little theorem and
Euler's generalization of it.  These important results are used
throughout the rest of the book.  This chapter also introduces
primitive roots and discrete logarithms, which are needed for many
ciphers and protocols.

Chapter 7 deals with the solution of quadratic congruences.  We do not
prove the quadratic reciprocity law, but do explain its importance in
computation.  We state this law in a form useful for programming rather
than in the slick concise way found in many number theory texts.

Chapter 8 introduces information theory and gives examples of some
obsolete ciphers.

Chapter 9 offers a selection of topics from modern algebra that are
used in later chapters to make and break various ciphers.

Chapters 10 through 13 treat the complementary problems of factoring
large integers and identifying large primes.  Many cryptographic
algorithms begin by choosing large primes.  Some ciphers and protocols
can be broken by factoring a large integer.  Slow but nevertheless
important factoring methods are the topic of Chapter 10.  In Chapter
11, the reader learns how to tell whether a large integer is probably
prime, how to give a rigorous proof that a large number is prime, and
how to construct large primes that have an easy rigorous proof of
primality.  Chapter 12 deals with the important elliptic curve groups
used in prime proofs, in factoring integers, and directly in ciphers
and protocols.  The fastest known factoring algorithms are described in
Chapter 13.

Chapter 14 discusses the best ways to break certain ciphers by
computing ``discrete logarithms.'' We describe several good methods for
choosing random numbers in Chapter 15.  Cryptographic algorithms that
need secret random integers can be compromised if the numbers are not
sufficiently random.

Part II describes a selection of cryptographic algorithms, most of
which use number theory.  Chapter 16 presents some single-key ciphers,
in which all keys are supposed to remain secret.  Rijndael, the new
Advanced Encryption Standard, is the fastest of these ciphers.  The
Pollig-Hellman ciphers are slower, but enjoy special properties which
make them useful in certain protocols.  Chapter 17 introduces
public-key ciphers, including those of Rivest, Shamir and Adleman,
Massey-Omura, ElGamal, and Rabin-Williams.

Methods of signing messages electronically are presented in Chapter
18.  Chapter 19 explains ways for two users to exchange keys in a
secure manner, so that no one else can discover these keys by
eavesdropping on their messages, and so that the users can be sure that
they are talking to each other and not to an impersonator.

In Chapter 20 we describe simple protocols for playing games, sharing
secrets, signing documents without seeing them, and establishing one's
identity.  The protocols in Chapter 21 are more complicated, and
include signing contracts over the Internet, holding an election over
the Internet and using digital ``cash'' to purchase goods.  Chapter 22
explains two complete cryptographic systems, Kerberos for user
authentication and Pretty Good Privacy for secure electronic mail.

Some attacks on the cryptographic algorithms are discussed as the
algorithms are presented in Part II.  In Part III, we collect together
some general methods of attack on the cryptographic algorithms of Part
II and assess their effectiveness.

Chapter 23 treats direct attacks in which the attacker has no contact
with the victim and the victim does nothing wrong.  These attacks
involve a direct assault on a secret key.  They are analogous to the
attacker breaking into the victim's house when he is away and taking
his money.

In the attack techniques of Chapter 24, either the victim or his
computer makes an error which allows an attacker to learn a secret
key.  These methods are similar to an attacker entering a victim's
house and taking his money when the victim left the door unlocked or
the lock is broken.

In the attacks of Chapter 25, the attacker interacts with the victim
and either steals a secret key or makes the victim do something he
wishes he had not done.  These attacks are like being mugged or raped.

The second and third parts of the book give copious references to the
theorems in the first part, so that the reader can learn more about why
the cryptography works and the nature of the attacks on it.

More than 200 interesting exercises test the reader's understanding of
the text.  The exercises range in difficulty from nearly trivial to
quite challenging.  We hope you enjoy the antics of Alice, Bob, and
their gang.

The prerequisites for reading this book are calculus and linear
algebra.  From calculus, you should know how to differentiate,
integrate, and find extrema.  You should be familiar with the logarithm
and exponential functions and with Newton's method for finding zeros of
functions.  You should know that sums may be approximated by
integrals.  You should know the rudiments of set theory, intersections,
unions, and subsets.  From linear algebra, you should be familiar with
matrices and know how to solve a system of linear equations in several
unknowns.  For complete understanding of this book, you should also be
familiar with proof by mathematical induction.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com