Error in Applied Cryptography 2nd Ed

[John S. Denker]

Finding errors in _Applied Cryptography_ is like finding
sand on the beach.

My favorite example is the discussion of modular arithmetic
and Galois fields, on pages 254 and 255.  These errors are
pretty amazing, considering the pivotal role modular arithmetic
plays in modern crypto.

 1) It says modular arithmetic on integers is a finite field 
whenever the modulus "is prime or the power of a large prime".
I don't think so.  For integers, the modulus had better be a 
plain old prime.  (If the modulus were of the form p^n, then p 
itself would be a zero-divisor ... not good.)  And BTW, if 
powers of primes were allowed, the "largeness" of the prime 
would not be part of the definition.

 2) It says "A polynomial that is a generator in a given 
field is called primitive".  That is not the way the term
"primitive" is defined in any math book I've ever seen.

The mis-definition is obviously inconsistent with the statement 
a few paragraphs later that "the trinomial must be primitive" 
when using it as a modulus;  obviously you can't have something
that is both a generator and a modulus!

The standard definition is that if the monomial x is a
generator in the field modulo a polynomial p[x], then 
p[x] is primitive.  This definition captures the property
that is important to technology, because the monomial x
represents a simple shift of a shift register.  So when
choosing a modulus, it's smart to choose one that is
primitive in the standard sense. 

Note that "primitive" is also mis-defined in [HAC] chapter 
2 (def. 2.214) but the correct definition is given in 
[HAC] chapter 4 (start of section 4.5).

 3) The table of values of n "for which x^n + x + 1 is
primitive" is out to lunch.  The given n values correspond
roughly (but with errors) to irreducible polynomials, but
only some of these are primitive.  It even lists n=1, for 
which the given from is not even a trinomial.  The tables 
chapter 4 of [HAC] appear to be much more trusthworty.

 4) It says that in a generator, "all its coefficients
must be relatively prime".  I don't think so.  It's 
obvious that you want their GCD to be unity, but that's
a very different statement.

=================

Remark:  I asked Mr. Schneier about this and he blew
me off.


References: 

[AC} _Applied Cryptography_ by Bruce Schneier.  

There is a page of errata at
  http://www.counterpane.com/ac2errv30.html

[HAC] _Handbook of Applied Cryptography_ by Alfred J. 
Menezes, Paul C. van Oorschot and Scott A. Vanstone.

The whole book can be downloaded (subject to restrictions)
from http://www.cacr.math.uwaterloo.ca/hac/

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