Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1143.94001
Katz, Jonathan; Lindell, Yehuda
Introduction to modern cryptography. (English)
[B] Chapman \& Hall/CRC Cryptography and Network Security. Boca Raton, FL: Chapman \& Hall/CRC. xviii, 534~p. \sterling~39.99; \$~79.95 (2008). ISBN 978-1-58488-551-1/hbk

The book is a wide and complete survey of modern cryptography. Its emphasis is on the information-theoretical analysis of the methods, but several applications are introduced in a well motivated manner. The exercises are illustrative of the methods and pose important challenges not only to novel readers but also to crypto professionals profiting of the book as a reference source. The book is highly recommended as a textbook in cryptography courses at graduate or advanced undergraduate levels. As a general procedure, the authors determine the security of protocols in terms of the probability to break them. For each protocol an experiment is proposed: An adversary is provided of the input of the protocol, and two allegedly output strings: one is the real output result and the other is a hypothetical result chosen uniform randomly over the output space of the protocol. The adversary task consists in deciding which is the real output string. It is supposed that the adversary has an unbounded computational power, realized indeed as a probabilistic polynomial-time Turing machine. Then the protocol is considered secure if the adversary's success probability differs from 1/2 by a negligible function on the size of the input, i.e. the difference is eventually bounded by the reciprocal of any polynomial function. This is an approach proper of more advanced expositions [{\it O. Goldreich}, Modern Cryptography, Probabilistic Proofs, and Pseudorandomness. Algorithms and Combinatorics. 17. Berlin: Springer (1999; Zbl 0907.94002); {\it S. Goldwasser} and {\it M. Bellare}, Lecture notes on cryptography. Summer Course ``Cryptography and Computer Security'' at MIT, 1996--1999 (1999)] of cryptographic methods. However it is indeed characteristic of modern cryptography. I consider it as a relevant achievement of the authors to put this kind of expositions at the reach of undergraduate students. The book consists of three parts: Introduction and classical cryptography, private-key cryptography, and public-key cryptography. The first part consists of two chapters. Kerckhoffs' principle is stated: ``The cipher method must not be required to be secret, and it must be able to fall into the hands of an enemy without inconvenience'' which is essential to modern cryptography, and three important principles in design: There should be a precise definition of security; if unproven assumptions are assumed, they should be clearly stated; and cryptographic constructions should be accompanied by rigorous proofs of security. In a historical review, the following methods are mentioned: Caesar, mono-alphabetic substitution (weak against frequency analysis), and Vigenère or poly-alphabetic substitution (weak against a modified frequency analysis, the so called Kasiski's method). The notion of perfectly secret schemes is introduced, and some characterizations of them are given. Vernam's cipher is proved to be perfectly secret. Among the characterizations, Shannon's Theorem is recalled: In a scheme where the spaces of messages, keys and ciphers have the same cardinality, a scheme is perfectly secret if and only if the keys are chosen uniformly and for each message the map associating to each key the corresponding cipher is an isomorphism. This theorem marks a limitation to get perfect secrecy in practice. The second part exposes private-key cryptography. It is a characteristic feature of the approach selected by the authors. It presents the fundamentals of symmetric cryptography with rigorous definitions of security. The authors explain in detail, in a clear, concise and readable exposition the notions of computationally-secure encryption. This part consists of four chapters, dealing with pseudorandomness, message authentication codes, and practical implementations and analysis of pseudo random permutations. \par Any encryption scheme is determined by algorithms for key generation, encryption and decryption. In order to determine the computational security of a scheme, it is subject to an ``eavesdropper experiment'': an adversary generates two messages, he sends both messages to the scheme server, who generates uniform-randomly a key, and sends back the cipher text, called challenge cipher text, corresponding to just one message. The adversary's task is to determine to which message corresponds the challenge cipher text.\par The encryption scheme is computationally secure whenever the success probability is either 1/2 or it differs from this value by a negligible amount, for any adversary that is computing his guesses in probabilistic polynomial-time. In this case, it is said that the scheme has indistinguishable encryptions in the presence of an eavesdropper. Some characterizations of computational security are provided. Pseudorandomness is a key notion in order to get highly reliable encryption schemes. Although most schemes may not be perfectly secret due to Shannon's Theorem, some schemes may be computationally secret, e.g. robust against efficient adversaries running programs in polynomial times with negligible probabilities of success. A distinguisher is a probabilistic polynomial-time algorithm giving an output for a given input in a set. A random generator is a map transforming seeds, which are strings of a certain length, into strings of a given length (a polynomial function of the seed's length), such that the generated string is computationally indistinguishable from an uniformly chosen string. It is shown that whenever the keys are generated with a random generator and encryption is done through addition modulo 2 of masking messages with keys, then one obtains a scheme in which encryptions are indistinguishable in the presence of an eavesdropper. Secure encryption is discussed also with respect to stream ciphers and chosen-plain attacks. In this last attacks, the adversary has access to the encryption device as an oracle during the eavesdropper experiment. The construction of secure encryption against chosen-plain attacks can be effectively performed using pseudorandom functions, which are maps $F:(k,\sigma)\mapsto \tau=F(k,\sigma)$ transforming a string and a key into a string, such that the family $\left(F_k:\sigma\mapsto F(k,\sigma)\right)_k$ consists of maps indistinguishable from a map $\sigma\mapsto \tau$ chosen uniformly. The existence of pseudorandom functions is proved through conventional methods using block ciphers; and in this context several modes of operation are exposed. Security against chosen-ciphertext attacks (the adversary has access also to an decryption device as an oracle, with the obvious restriction that he is not allowed to ask for the decryption of the challenge ciphertext) is discussed. When exposing message authentication codes, it is explained that authentication and privacy are different requirements. Encryption is not enough to authenticate parts in a private exchange, and the authors provide several examples. Given a message, it should be provided of a tag (e.g. fingerprint, checksum, digest, etc.) in order to verify that the message is authentic and unmodified. A message authentication code consists of algorithms for key generation, tag-construction and tag-verification. Here, an eavesdropper experiment is proposed: For a given value $n$, a key is generated and the adversary is provided with $n$ and access to an oracle constructing tags with the generated key, then the adversary outputs a pair $(m,t)$, without using $m$ as a query to the tag-construction oracle. The adversary's task is to make the tag-verifier to accept the pair $(m,t)$. The message-authentication code is secure if every efficient adversary has a negligible probability of success. It is shown that whenever there is a pseudorandom function $F$, for an uniform randomly selected key $k$ the tagging $m\mapsto t=F(k,m)$ (provided that $m$ and $k$ have the same length) with verification consisting in acceptation of a pair $(m,t)$ only if $t=F(k,m)$, gives a secure message authentication code. Also, the case for arbitrary key lengths, treated with modes of operation of stream block ciphers, is studied. Naturally, in this chapter collision-resistant hash functions are exposed. A collision-finding experiment is stated, and the resistance of hash functions is formulated in terms of negligible probabilities in succeeding to find a collision. The Merkle-Damgård transform is presented as a procedure to build collision-resistant hash functions and other variants as NMAC ({\it nested message authenticated code}) and HMAC ({\it key-hashed message authenticated code}). An encryption scheme resistant against chosen-plain attacks together with a message-authentication code may be assembled to obtain an encryption scheme resistant against chosen-cipher attacks: any ciphertext is authenticated with a proper tag. Also there are discussed three ways to obtain privacy and message authentication: encrypt-and-authenticate, authenticate-then-encrypt and encrypt-then-authenticate; and they are compared with respect to security features. When exposing the practical constructions of pseudorandom permutations, their existence and construction are realized through block ciphers and they are exemplified with DES (Data Encryption Standard) and AES (Advanced Encryption Standard). The confusion-diffusion paradigm receives blocks of length $2^n$ bits, and an integer $m<n$, each block $x$ of $2^n$ bits is parsed as the join of $2^{n-m}$ sublocks $x_{0},\dots,x_{2^{n-m}-1}$, each of length $2^m$. For a key $k$, $2^{n-m}$ permutations are selected $\pi_{k,0},\dots,\pi_{k,2^{n-m}-1}$ in the symmetric group $S_{2^m}$. Thus the map $F_k:x\mapsto \pi_{k,0}(x_{0})\cdot \cdots \cdot \pi_{k,2^{n-m}-1}(x_{2^{n-m}-1})$ introduces a confusion. Since each permutation requires approximately $m2^m$ bits to be determined [{\it D.~E. Knuth}, Combinatorica 11, No. 1, 33--43 (1991; Zbl 0803.20005)], $F_k$ requires around $2^{n-m}m2^m=m2^n$ bits, instead of $n2^n$ bits to specify a whole permutation in the $2^n$ bits. A permutation $\rho$ in $S_{2^n}$ is used as diffusion. A round is a map $\rho\circ F_k$. The confusion-diffusion paradigm consists of the composition of several rounds. The substitution-permutation networks work in a similar way as confusion-diffusion paradigm, except that the permutations at each round are fixed. The confusion permutations are called S-boxes and the diffusion permutations, mixing permutations. The key is partitioned into subkeys to be used as masks for the intermediate results of rounds, according to a key schedule. It is explained how attacks with a pair (plaintext, ciphertext) can be successful within a substitution-permutation network consisting of at most three rounds (obviously, the case of just one round is rather simple). Feistel networks are also discussed as an alternative to build block ciphers. They involve S-boxes, mixing permutations and key schedules, but the S-boxes are not permutations. However, the construction of each round determines a permutation on the words of size the size of blocks. DES is described entirely as a 16-round Feistel network, with block size 64 bits and key length 56 bits. Its security is discussed and the major risk, with respect to contemporary computational power, is posed by the length of its keys: it is too short at present time. Triple DES iterates DES and may either double or triple the key sizes. However, iteration impacts on the speed of ciphering. AES appeared as a reply to the 1997 call for proposals submitted by NIST. AES proceeds on blocks of size 128 bits and may use keys of lengths either 128, 192 or 256 bits. The description of AES is quite general and although implementation details are not provided, the text gives a general idea of its procedures. Finally, differential and linear cryptanalysis are introduced. These attacks appeared in the last two decades of the last century and by collecting pairs of plain and cipher texts they may succeed in recognizing key fragments, reducing in this way the size of the search space thus rendering feasible brute force attacks. When discussing the theoretical construction of pseudorandom objects, it is proved that pseudorandom generators and pseudorandom permutations do exist. Initially, one-way functions are introduced: A map is one-way if whenever a value $y=f(x)$, with $x$ being of length $n$, is given to an adversary, he would be able to produce in probabilistic polynomial time, just with a negligible probability, a value $x'$ such that $f(x')=y$. The notion of hard-core predicate for a given function is also introduced: The truth value of the predicate can be obtained with a probabilistic polynomial-time oracle over the function with a probability that differs from 1/2 by a negligible function. Then it is proved that if $f$ is one-way, there can be constructed a map $g$ and a hard core $h$ predicate for $g$; and in this case the pair $(g,h)$ is a pseudorandom generator with expansion factor $n\mapsto n+1$. It is shown that if there exists a pseudorandom generator with expansion $n\mapsto n+1$ then for any polynomial there exists a pseudorandom generator with expansion given by that polynomial. It is shown as well that such generators give rise to pseudorandom functions. All these results are proved in full detail. The third part teaches public-key cryptography. Two chapters introduce hard number-theoretical problems, four chapters discuss key management, the public-key revolution, and several public-key encryption schemes. One chapter is devoted to digital signature schemes, and the two last chapters deal with information-theoretical notions of security for public-key cryptography. Initially some seemingly one-way functions resulting from number theory are discussed: factorization and the discrete logarithm problem. The basics of number theory are introduced: the divisibility relation on the ring of integers, group theory and the multiplicative group of remainders modulo an integer. The Chinese Remainder Theorem is stated in the following way: If $p$ and $q$ are relatively prime, and $n=pq$ then $\Bbb Z_n\cong \Bbb Z_p\times\Bbb Z_q$ and $\Bbb Z_n^{\star}\cong \Bbb Z_p^{\star}\times\Bbb Z_q^{\star}$ and the map $x\mapsto (x\mod {p},x\mod q)$ is an isomorphism in both cases. Prime numbers are discussed in two aspects: Primality testing and prime generation. For prime generation, a basic algorithm consists of repeating either until a success condition or a given number of times the following step: fixed a size $n$, generate a random string of $n-1$ bits and prepend it with a 1. If this is the base 2 representation of a prime, then stop. The procedure is successful with a high probability due to the Prime Number Theorem. With respect to prime testing, the Miller-Rabin test is explained: given a prospective prime $p$, test for a certain number $t$ of integers $a$ in the interval $[1,p-1]$ whether $a$ is relatively prime with $p$ and $a^{p-1}\equiv 1 \mod p$. Naturally a failure would witness the compositeness of $p$. Otherwise, there could be claimed with a great certainty that $p$ is prime. Miller-Rabin may give a wrong answer when the tested number is composite with a probability lower than $q^t$, for some $q\in[0,1/2]$. Suppose given a procedure {\tt GenModulus}$:\sigma\mapsto (N,p,q)$, where $p,q$ are primes and $N=pq$. The {\it factoring experiment} is the following: Produce a triplet $(N,p,q)=\text{\tt GenModulus}(1^n)$, and send $N$ to an adversary, who replies with a pair of integers $(p_1,q_1)$, both greater than 1. The adversary success if $N=p_1q_1$. It is said that {\it factoring is hard relative to }{\tt GenModulus} if any adversary using probabilistic polynomial-time resources succeeds with a negligible probability. The {\it factoring assumption} asserts that there is a procedure {\tt GenModulus} for which factoring is hard. The authors explain that the factoring assumption is generally admitted although there is no a full proof of it. RSA is the most popular algorithm for public key cryptography. Given two secret primes $p,q$, it is taken $N=pq$ and $e$ as an integer relatively prime with $N$. The public key is the pair $(n,e)$ and the secret key is $(n,d)$ where $d=e^{-1}\mod \varphi(N)$, where $\varphi$ is Euler's totient function. The problem of calculating $d$ from $N$ and $e$ entails the problem of factoring $N$. For a plaintext $x\in\Bbb Z_{N}^{\star}$, its ciphertext for the public key $(N,e)$ is $y=x^e\mod N$. Clearly, $x=y^d\mod N$. A key generator is a procedure {\tt GenRSA}$:\sigma\mapsto (N,e,d)$. The {\it RSA experiment} is the following: Let $(N,e,d)=\text{\tt GenRSA}(1^n)$ and let $y\in\Bbb Z_{N}^{\star}$. The adversary is granted to receive $N$, $e$ and $y$ and outputs a value $x\in\Bbb Z_{N}^{\star}$. The adversary success if $y=x^e\mod N$. It is said that {\it RSA problem is hard relative to} {\tt GenRSA} if any adversary using probabilistic polynomial-time resources succeeds with a negligible probability. The procedure {\tt GenRSA} may depend on the procedure {\tt GenModulus}, and in general RSA hardness depends on factoring hardness. Then the Discrete Logarithm Problem (DLP) and the Diffie-Hellman assumptions are discussed. Given a cyclic group $G$, its order $q$ and a generator $g\in G$, for any element $h\in G$ an integer $n$ is sought such that $g^n=h$ in $G$. This problem is stated as an experiment, relative to a way to generate a triplet $(G,q,g)$, and the hardness of this problem is defined relative to that process. DLP for a composite order $q$ can be reduced to instances of DLP corresponding to its factors. Thus in general it is considered the case of cyclic groups of prime order, where the decision of whether $z=g^{\log_g x\,\log_g y}$ is close to an uniform distribution for uniformly chosen values $x,y$. If $q$ is a Sophie Germain prime ($p=2q+1$ is also a prime) then the quadratic residues of $\Bbb Z^p$ form a cyclic group or order $q$. Then by selecting an element $x\ne \pm1$ in $\Bbb Z_p^*$ then $g=x^2$ is a generator of a group $G$ of order $q$. Then elliptic curves and their group structures are introduced. The existence of one-way functions is discussed in terms of the factoring problem. Also one-way permutations are introduced. Collision-resistant hash functions are also constructed as follows: let $s=(G,q,g.h)$ be a key consisting of a cyclic group $G$ of prime order $q$, $g$ a generator and $h\in G$ a random element. The map $\Bbb Z_q\times\Bbb Z_q\to G$, $(x_0,x_1)\mapsto g^{x_0} h^{x_1}$ is a collision-resistant hashing provided that the discrete logarithm problem is hard. Factoring consists in finding $p$ and $q$ given a number $N=pq$. Pollard's $p-1$ method is introduced. If it happens that $p-1$ has small prime factors then this method is rather efficient. In general, for integers which are not just products of two primes, Pollard's rho method can be used, although it involves an exponential complexity in terms of the length of the number to be factored. Also the Quadratic Sieve method is explained in detail. It is a subexponential method in the length of the number to be factored. For the discrete logarithm problem, in a general cyclic group, first Shanks' Baby-step/Giant-step is presented. It is an $O(q^{\frac{1}{2}}\ \text{polylog}(q))$-time algorithm (where $q$ is the order of the group). The Pohlig-Hellman algorithm then is discussed. If the greatest factor of the order $q$ is the prime $p$, then this algorithm has time complexity $O(p^{\frac{1}{2}}\ \text{polylog}(q))$. For the particular case of the cyclic group $\Bbb Z_p^*$, the Index Calculus method is exposed. It has a time complexity $2^{O(\sqrt{n\log n})}$ where $n$ is the length of $p$. Naturally, the main problem in private-key cryptography is the agreement and management of keys. When exposing this problem, some protocols using a key distribution center are sketched, among them the Needham-Schroeder protocol. The Diffie-Hellman key exchange protocol appeared as an effective alternative: Two parts, Alice and Bob should agree in a common key, they exchange some pieces of information and with some other calculations they arrive at a common value which may serve as a key. Any eavesdropper who may collect the interchanged pieces of information is unable to reconstruct the agreed key. The security is also defined through an experiment: Two parties perform the protocol and they agree in a common key $k$, a bit is randomly chosen, if it is 1 then $k'=k$, else $k'$ is a random $n$-length string of bits. The adversary is provided with the transcript of the protocol session and with $k'$. He should decide whether $k'$ is the agreed common key. If the discrete logarithm problem is hard, then the Diffie-Hellman key exchange protocol is secure. The exposition of public-key encryption begins with a general definition of public-key encryption schemes. A corresponding eavesdropper indistinguishability experiment is introduced as well as a chosen-plaintext attack experiment. Perfect secrecy is defined within this context and it is proved that no deterministic public-key scheme can be perfectly-secret. Hybrid encryption is discussed: When encrypting, public encryption is used to encrypt a random session key and a plaintext is ciphered with private key encryption with that session key. The final ciphertext is an envelope containing the ciphered used key and the ciphertext of the message. Performance and security are analyzed. The authors warn that ``textbook RSA'' public-key encryption, being deterministic, is not a perfectly-secret scheme. The protocol is explained with simple residue arithmetic, and using the Chinese Remainder Theorem it is explained that decryption can be speed up by a factor of 4: $c^d\mod N \leftrightarrow (c^{d\mod{(p-1)}}\mod p,c^{d\mod {(q-1)}}\mod q)$. Indeed, several attacks are explained: low exponent $e$ and low message $m$, small exponent $e$ and common modulus. Padded RSA using padding blocks of logarithmic size with respect to public keys size has indistinguishable encryptions under chosen-plaintext attacks. It is explained that this is the approach followed by the standard PKCS \#1 v 1.5. The El Gamal encryption scheme is exposed and it is proved that whenever the decision Diffie-Hellman problem is hard, relative to an instance generator, then this scheme has indistinguishable encryptions under chosen-plaintext attacks. Some implementations issues, as the choice of public parameters and binary strings encoding are discussed. As additional public-key encryption schemes, there are introduced the following public-key encryption schemes: {\it Goldwasser-Micali scheme} based on the hardness to distinguish quadratic residues and quadratic non-residues modulo a composite number. It is a provably chosen-plaintext secure scheme. {\it Rabin scheme} proved to be secure whenever factoring is hard; and {\it Paillier scheme} also related to factoring. The basic facts of quadratic residues are reviewed. Modulo a prime number $p$, there are $(p-1)/2$ quadratic residues and each has two square roots. The Jacobi symbol distinguishes quadratic residues: $J_p(x)=x^{(p-1)/2}\mod p$ equals +1 whenever $x$ is a quadratic residue and $-1$ otherwise. If $N=pq$ is a composite, then each $y\in \Bbb Z_N^*$ corresponds to the pair $(y_p,y_q)=(y\mod p,y\mod q)$ and it is a quadratic residue if and only if $y_p$ and $y_q$ are quadratic residues over $\Bbb Z_p$ and $\Bbb Z_q$. Each quadratic has exactly 4 square roots. The Jacobi symbol $J_N$ is the product of the Jacobi symbols $J_p$ and $J_q$. Thus any quadratic residue $y$ satisfies $J_N(y)=1$, however $J_N^{-1}(1)$ has twice the number of quadratic residues, or, whenever $J_N(y)=1$ there is a half probability that it is a quadratic residue. Without knowing the factorization of $N$ it is difficult to decide whether this is a quadratic residue or not. The Goldwasser-Micali scheme is the following: Public key is $(N,z)$ with $N=pq$ and $z$ quadratic non-residue in $\Bbb Z_N^*$ with Jacobi symbol 1. Private key is $(p,q)$. Given a message $m\in(0+1)$ choose a random $x\in\Bbb Z_N^*$ and output the ciphertext $c=zx^2\mod N$. In order to decrypt, given $c$ decide whether $c$ is a quadratic residue or a quadratic non-residue (it is not difficult after the knowledge of $p$ and $q$). Output 0 in the first case and 1 in the second case. If factoring is hard, then this scheme has indistinguishable encryptions under chosen-plaintext attacks. \par Rabin scheme is based on calculations of square roots. Digital signature schemes appeared in a direct way from public-key schemes, they allow to authenticate not just the messages but also the senders. Signature schemes based on ``textbook RSA'' are weak and hashed RSA is an acceptable alternative. Lamport's one-time signature scheme and chain-based schemes are fully explained as well as their own securities. Finally the notion of certificate, which is in the core of public-key infrastructures, is discussed. \par The book covers in a splendid way the main notions of current cryptography from the point of view of information-theoretical security. This corresponds indeed to a modern cryptography approach. All the covered themes were known from last decade, but a textbook containing all of them in a readable fashion at the reach of undergraduate students was lacking. The current book covers this lack in a self-contained way.
[Guillermo Morales-Luna (Mexico)]

MSC 2000:: *94-01 Textbooks (information and communication)
94A60 Cryptography
94A62 Authentication and secret sharing
11T71 Algebraic coding theory
94A55 Shift register sequences

Keywords: perfectly-secret encryption; private-key encryption; public-key encryption; pseudorandomness; message authentication codes; digital signature schemes

Citations: Zbl 0907.94002; Zbl 0803.20005

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.
	Elementary number theory. Primes, congruences, and secrets.

Simple Search

Zentralblatt MATH Berlin [Germany]