A Classical Introduction to Cryptography: Applications for Communications Security introduces fundamentals of information and communication security by providing appropriate mathematical concepts to prove or break the security of cryptographic schemes.

This advanced-level textbook covers conventional cryptographic primitives and cryptanalysis of these primitives; basic algebra and number theory for cryptologists; public key cryptography and cryptanalysis of these schemes; and other cryptographic protocols, e.g. secret sharing, zero-knowledge proofs and undeniable signature schemes.

A Classical Introduction to Cryptography: Applications for Communications Security is rich with algorithms, including exhaustive search with time/memory tradeoffs; proofs, such as security proofs for DSA-like signature schemes; and classical attacks such as collision attacks on MD4. Hard-to-find standards, e.g. SSH2 and security in Bluetooth, are also included.

A Classical Introduction to Cryptography: Applications for Communications Security is designed for upper-level undergraduate and graduate-level students in computer science. This book is also suitable for researchers and practitioners in industry. A separate exercise/solution booklet is available as well, please go to www.springeronline.com under author: Vaudenay for additional details on how to purchase this booklet.

y = h(x) 3: if there is a (y, x ′ ) pair in the hash table then 4: yield (x, x ′ ) and stop 5: end if 6: add (y, x) in the hash table 7: end for 8: search failed Figure 3.7. Collision search with the birthday paradox. birthdays are independent and uniformly distributed among 365 days, then at least two of them are likely to share the same birthday. It can be mathematically expressed as follows. Theorem 3.2.√If we pick independent random numbers in {1, 2, . . . , N } with uniform distribution θ N

instance of the family is defined by two constants Cst1 and Cst2 , a MAC length t, and a function H which maps a message block and a constant to a message block. Given a message block L, we let HL denote the function which maps the remaining constant to a message block. OMAC works as follows. Let us assume that we are given a MAC key K and a message M = x1 ||x2 || · · · ||xn where all xi (except xn ) are full message blocks and the length of xn is at most the size of a full message block. 1. Let

(K,time,N,IS ,T,L),ticket=CKS (flags,K,IC ,T,L) ←−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− ticket,CK (IC ,T ) −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−→ CK (T +1) ←−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− Figure 5.5. The Kerberos authentication protocol. AS AS (pick K0 ) TGS TGS (pick K) S S Security Protocols with Conventional Cryptography 5.4.3 145 ⋆Merkle Puzzles In 1978, Ralph Merkle published a paper (Ref. [129]) which explains how to perform confidential communication when the two parties do not

= n. If the obtained gcd is 1, we get the Bezout relationship 1 = xu + nv, which means u ≡ x −1 (mod n). If the gcd is not 1, x and n have a common factor greater than 1, so xu − qn also shares this common factor for any q ∈ Z, therefore xu mod n cannot be equal to 1: x is not invertible modulo n. As an example, we can invert 22 modulo 35. We run the algorithm with a = 22 and b = 35. We obtain the following sequence of vectors. Iteration 0 1 2 3 4 5 6 x⃗ y⃗ q (22, 1, 0) (35, 0, 1) (22, 1, 0)

6.4 Finite Fields Finite fields are useful in communication systems, and in cryptography in particular. In addition to all Z p fields, we have other finite fields. We give without proof the following theorem which characterizes the finite fields.4 Theorem 6.7. We have the following results. 1. The cardinality of any finite field is a prime power p k . 2. For any prime power p k , there exists a finite field of cardinality p k . p is called the characteristic of the field. 3. Two finite fields of