Today's pervasive computing and communications networks have created an intense need for secure and reliable cryptographic systems. Bringing together a fascinating mixture of topics in engineering, mathematics, computer science, and informatics, this book presents the timeless mathematical theory underpinning cryptosystems both old and new. Major branches of classical and modern cryptography are discussed in detail, from basic block and stream cyphers through to systems based on elliptic and hyperelliptic curves, accompanied by concise summaries of the necessary mathematical background. Practical aspects such as implementation, authentication and protocol-sharing are also covered, as are the possible pitfalls surrounding various cryptographic methods. Written specifically with engineers in mind, and providing a solid grounding in the relevant algorithms, protocols and techniques, this insightful introduction to the foundations of modern cryptography is ideal for graduate students and researchers in engineering and computer science, and practitioners involved in the design of security systems for communications networks.

perfect secrecy. The Vigen`ere cipher has been in use since the sixteenth century. It is vulnerable to multitrack frequency analysis. Hill (1929) proposed a protection against a straightforward frequency-analysis attack by introducing a matrix operation into the encryption, thereby introducing deeper levels of number theory into the subject. The autokey cipher, though not a true cipher, was patented by Guanella as early as 1946. Many books are available that deal with the various topics of secure

q is a power of a prime, then φ(q m − 1)/m is an integer. 2.6 Prove that, in any group, the identity element is unique and the inverse of any element is unique. 2.7 Prove that if α is a generator of a cyclic group of order n, then α i has order n/GCD(n, i). 2.8 Prove that there are φ(n) generators in a cyclic group of order n. 2.9 Prove that all primes other than 2 and 3 are of the form 6k ± 1. Devise a primality test using this fact. 2.10 The following primality test is proposed. Suppose that n

that is a multiple of p or of q will be exceedingly unlikely, occurring in the ratio of p + q to pq. If p and q are 50-digit integers, such an x occurs with probability on the order of 10−50 . It is as unlikely to have such a message as it is to simply guess the factorization of n. The cryptanalyst will try to infer the primes p and q by any means. The digits of p and q must not contain any sequence known to have significance to the decryptor. These should be chosen randomly. The method of

Step 1 and Step 2 can be regarded as precomputations. We will also need to know α −m = 5−4 , which can be computed as follows: 5−1 = 14 5−2 = 142 = 12 5−4 = 122 = 6. To compute log5 y for y = 13, first check the precomputed table to see that log5 13 is not already an entry, in which case the algorithm would halt. Because log5 13 is not an entry in the table, the algorithm continues as follows: compute (5−4 )i y = 6i y for 17:15 Trim: 247mm × 174mm CUUK2503-04 Top: 12.477mm CUUK2503/Blahut

k = 2, this becomes 2 = 32272 . We can conclude that log3 2 = 2272 in F 9871 . If x is not a product of primes in the factor base, the attempt is not yet finished. Test in turn the integer 2k x (mod 9871) for each k to see if it factors totally, as an integer, in the factor base as 3k x = 2i2 5i5 7i7 11i11 13i13 17i17 31i31 . Upon finding such a k, the discrete logarithm is given by log3 x = i2 log3 2 + i3 log3 5 + · · · + i31 log3 31 − k. For a field F p with very large p, it will be intractable