Solutions for Chapter 13 - Cryptography and Network Security - Stallings - 4th edition

Review Questions
13.1 List two disputes that can arise in the context of message authentication. Get solution
13.2 What are the properties a digital signature should have? Get solution
13.3 What requirements should a digital signature scheme satisfy? Get solution
13.4 What is the difference between direct and arbitrated digital signature? Get solution
13.5 In what order should the signature function and the confidentiality function be applied to a message, and why? Get solution
13.6 What are some threats associated with a direct digital signature scheme? Get solution
13.7 Give examples of replay attacks. Get solution
13.8 List three general approaches to dealing with replay attacks. Get solution
13.9 What is a suppress-replay attack?  Get solution

Problems
13.1 Modify the digital signature techniques of Table 13.1a and b to enable the receiver to verify the signature. Get solution

13.2 Modify the digital signature technique of Table 13.1c to avoid triple encryption of the entire message. Get solution

13.3 In discussing Table 13.1c, it was stated that alliances to defraud were impossible. In fact, there is one possibility. Describe it and explain why it would have so little credibility that we can safely ignore it. Get solution

13.4 In Section 13.2, we outlined the public-key scheme proposed in [WOO92a] for the distribution of secret keys.
The revised version includes IDA in steps 5 and 6. What attack, specifically, is countered by this revision? Get solution

13.5 The protocol referred to in Problem 13.1 can be reduced from seven steps to five, having the following sequence:
(1) A --> B:
(2) B -->KDC:
(3) KDC -->B:
(4) B--> A:
(5) A--> B:

Show the message transmitted at each step. Hint: The final message in this protocol is the same as the final message in the original protocol. Get solution

13.6 With reference to the suppress-replay attack described in Section 13.2:
a. Give an example of an attack when a party's clock is ahead of that of the KDC.
b. Give an example of an attack when a party's clock is ahead of that of another party. Get solution

13.7 There are three typical ways to use nonces as challenges. Suppose Na is a nonce generated by A, A and B
share key K, and f() is a function such as increment. The three usages are

 


Describe situations for which each usage is appropriate. Get solution

13.8 Dr. Watson patiently waited until Sherlock Holmes finished. "Some interesting problem to solve, Holmes?" he asked when Holmes finally logged out.
"Oh, not exactly. I merely checked my e-mail and then made a couple of network experiments instead of my usual chemical ones. I have only one client now and I have already solved his problem. If I remember correctly, you once mentioned cryptology among your other hobbies, so it may interest you."

"Well, I am only an amateur cryptologist, Holmes. But of course I am interested in the problem. What is it about?"
"My client is Mr. Hosgrave, director of a small but progressive bank. The bank is fully computerized and of course uses network communications extensively. The bank already uses RSA to protect its data and to digitally sign documents that are communicated. Now the bank wants to introduce some changes in its procedures; in particular, it needs to digitally sign some documents by two signatories so that
1.The first signatory prepares the document, forms its signature, and passes the document to the
second signatory.

2. The second signatory as a first step must verify that the document was really signed by the first
signatory. She then incorporates her signature into the document's signature so that the recipient,
as well as any member of the public, may verify that the document was indeed signed by both
signatories. In addition only the second signatory has to be able to verify the document's
signature after the step (1); that is the recipient (or any member of the public) should be able to
verify only the complete document with signatures of both signatories, but not the document in its
intermediate form where only one signatory has signed it. Moreover, the bank would like to make
use of its existing modules that support RSA-style digital signatures."

"Hm, I understand how RSA can be used to digitally sign documents by one signatory, Holmes. I guess you have solved the problem of Mr. Hosgrave by appropriate generalization of RSA digital signatures."
"Exactly, Watson," nodded Sherlock Holmes. "Originally, the RSA digital signature was formed by encrypting the document by the signatory's private decryption key 'd', and the signature could be verified by anyone through its decryption using publicly known encryption key 'e'. One can verify that the signature S was formed by the person who knows d, which is supposed to be the only signatory. Now the problem of Mr. Hosgrave can be solved in the same way by slight generalization of the process, that is..."
Finish the explanation. Get solution

13.9 DSA specifies that if the signature generation process results in a value of s = 0, a new value of k should be generated and the signature should be recalculated. Why? Get solution

13.10 What happens if a k value used in creating a DSA signature is compromised? Get solution

13.11 The DSS document includes a recommended algorithm for testing a number for primality, as follows:
1. [Choose w] Let w be a random odd integer. Then (w 1) is even and can be expressed in the form
2a m with m odd. That is, 2a is the largest power of 2 that divides (w 1).

2. [Generate b] Let b be a random integer in the range 1 <b < w.
3. [Exponentiate] Set j = 0 and z = bm  mod w.
4. [Done?] If j = 0 and z = 1, or if z = w 1, thenw passes the test and may be prime; go to step 8.
5. [Terminate?] If j > 0 and z = 1, then w is not prime; terminate algorithm for thisw .
[Increase j] Set j = j + 1. If j < a, set z = z2
6. mod w and go to step 4.
7. [Terminate]w is not prime; terminate algorithm for thisw .
8. [Test again?] If enough random values of b have been tested, then accept w as prime and
terminate algorithm; otherwise, go to step 2.

a. Explain how the algorithm works.
b. Show that it is equivalent to the Miller-Rabin test described inC hapter 8. Get solution

13.12 With DSS, because the value of k is generated for each signature, even if the same message is signed twice on different occasions, the signatures will differ. This is not true of RSA signatures. What is the practical implication of this difference? Get solution

13.13 Consider the problem of creating domain parameters for DSA. Suppose we have already found primes p and  q such that q|(p 1). Now we need to findg Zp with g of order q mod p. Consider the following two algorithms:

a. Prove that the value returned by Algorithm 1 has orderq .
b. Prove that the value returned by Algorithm 1 has orderq .
c.Suppose P = 40193 and q = 157. How many loop iterations do you expect Algorithm 1 to make
before it finds a generator?
d. If p is 1024 bits and q is 160 bits, would you recommend using Algorithm 1 to findg ? Explain.
e. Suppose P = 40193 and q = 157. What is the probability that Algorithm 2 computes a generator in
its very first loop iteration? (if it is helpful, you may use the fact that
its very first loop iteration? (if it is helpful, you may use the fact that when answering this question). Get solution

13.14 It is tempting to try to develop a variation on Diffie-Hellman that could be used as a digital signature. Here is one that is simpler than DSA and that does not require a secret random number in addition to the private key.
Public elements:
q prime number
a a < q and a is a primitive root of q
Private key:
X X < q
Public key:
Y = a
X mod q
To sign a message M, compute h = H(M), the hash code of the message. We require that gcd(h, q 1) = 1. If not, append the hash to the message and calculate a new hash. Continue this process until a hash code is produced that is relatively prime to (q 1). Then calculateZ to satisfy Z x h X(mod q 1). The signature of the message is a Z. To verify the signature, a user verifies thaYt = (aZ)h= aX mod q.
a. Show that this scheme works. That is, show that the verification process produces an equality if
the signature is valid.
b.Show that the scheme is unacceptable by describing a simple technique for forging a user's
signature on an arbitrary message. Get solution

13.15 An early proposal for a digital signature scheme using symmetric encryption is based on the following: To
sign an n-bit message, the sender randomly generates in advance 2n 56-bit cryptographic keys:
k1, K1, k2, K2,..., kn, Kn which are kept secret. The sender prepares in advance two sets of corresponding nonsecret 64-bit validation parameters, which are made public:
u1, V1, u2, V2,..., un, Vn and v1, V1, v2, V2,..., vn, Vn
where
vi = E(ki, ui), Vi = E(ki, Ui)
The message M is signed as follows. For the i th bit of the message, either ki or Ki is attached to the
message, depending on whether the message bit is 0 or 1. For example, if the first three bits of the message
are 011, then the first three keys of the signature are k1, K2, K3.
a. How does the receiver validate the message?
b. Is the technique secure?
c. How many times can the same set of secret keys be safely used for different messages?
d. What, if any, practical problems does this scheme present? Get solution

Solutions for Chapter 11 - Cryptography and Network Security - Stallings - 4th edition

Review Questions
11.1 What types of attacks are addressed by message authentication?

11.2 What two levels of functionality comprise a message authentication or digital signature mechanism?

11.3 What are some approaches to producing message authentication?

11.4 When a combination of symmetric encryption and an error control code is used for message authentication, in what order must the two functions be performed?

11.5 What is a message authentication code?

11.6 What is the difference between a message authentication code and a one-way hash function?

11.7 In what ways can a hash value be secured so as to provide message authentication?

11.8 Is it necessary to recover the secret key in order to attack a MAC algorithm?

11.9 What characteristics are needed in a secure hash function?

11.10 What is the difference between weak and strong collision resistance?

11.11 What is the role of a compression function in a hash function?


Problems
11.1 If F is an error-detection function, either internal or external use (Figure 11.2) will provide error-detection capability. If any bit of the transmitted message is altered, this will be reflected in a mismatch of the received FCS and the calculated FCS, whether the FCS function is performed inside or outside the encryption function. Some codes also provide an error-correction capability. Depending on the nature of the function, if one or a small number of bits is altered in transit, the error-correction code contains sufficient redundant information to determine the errored bit or bits and correct them. Clearly, an error-correction code will provide error correction capability when used external to the encryption function. Will it also provide this capability if used internal to the encryption function?


11.2 The data authentication algorithm, described in Section 11.3, can be defined as using the cipher block chaining (CBC) mode of operation of DES with an initialization vector of zero (Figure 11.6). Show that the same result can be produced using the cipher feedback mode.


11.3 The high-speed transport protocol XTP (Xpress Transfer Protocol) uses a 32-bit checksum function defined as the concatenation of two 16-bit functions: XOR and RXOR, defined in Section 11.4 as "two simple hash functions" and illustrated in Figure 11.7.
a. Will this checksum detect all errors caused by an odd number of error bits? Explain.

b. Will this checksum detect all errors caused by an even number of error bits? If not, characterize
the error patterns that will cause the checksum to fail.
c. Comment on the effectiveness of this function for use as a hash function for authentication.


11.4
a. Consider the Davies and Price hash code scheme described in Section 11.4 and assume that
DES is used as the encryption algorithm:
Hi = Hi1+ E(Mi, Hi1)

and recall the complementarity property of DES (Problem 3.14): If Y = E(K, X), then Y' = E(K', X').
Use this property to show how a message consisting of blocks M1, M2,..., MN can be altered
without altering its hash code.
b. Show that a similar attack will succeed against the scheme proposed inM [ EYE88]:
Hi = Mi+ E(Hi1, Mi)
11.5
a. Consider the following hash function. Messages are in the form of a sequence of decimal
numbers, M = (a1, a2,..., ai). The hash value h is calculated as
, for some predefined value n. Does this hash function satisfy any of
the requirements for a hash function listed in Section 11.4? Explain your answer.

b. Repeat part (a) for the hash function
c. Calculate the hash function of part (b) for M = (189, 632, 900, 722, 349) andn = 989.


11.6 It is possible to use a hash function to construct a block cipher with a structure similar to DES. Because a hash function is one way and a block cipher must be reversible (to decrypt), how is it possible?


11.7 Now consider the opposite problem: using an encryption algorithm to construct a one-way hash function.
Consider using RSA with a known key. Then process a message consisting of a sequence of blocks as
follows: Encrypt the first block, XOR the result with the second block and encrypt again, etc. Show that this scheme is not secure by solving the following problem. Given a two-block message B1, B2, and its hash RSAH(B1, B2) = RSA(RSA (B1)+ B2)
Given an arbitrary block C1, choose C2 so that RSAH(C1, C2) = RSAH(B1, B2). Thus, the hash function does not satisfy weak collision resistance.


11.8 Suppose H(m) is a collision resistant hash function that maps a message of arbitrary bit length into an- bit hash value. Is it true that, for all messages x, x' with x != x', we have H(x) != H(x')? Explain your answer.



Solutions for Chapter 10 - Cryptography and Network Security - Stallings - 4th edition

Review Questions
10.1 What are two different uses of public-key cryptography related to key distribution?

10.2 List four general categories of schemes for the distribution of public keys.

10.3 What are the essential ingredients of a public-key directory?

10.4 What is a public-key certificate?

10.5 What are the requirements for the use of a public-key certificate scheme?

10.6 Briefly explain Diffie-Hellman key exchange.

10.7 What is an elliptic curve?

10.8 What is the zero point of an elliptic curve?

10.9 What is the sum of three points on an elliptic curve that lie on a straight line?



Problems
10.1 Users A and B use the Diffie-Hellman key exchange technique with a common prime q = 71 and a primitive root a = 7.
a. If user A has private keyX A = 5, what is A's public key YA?
b. If user B has private keyX B = 12, what is B's public key YB?
c. What is the shared secret key?


10.2 Consider a Diffie-Hellman scheme with a common prime q = 11 and a primitive root a = 2.
a. Show that 2 is a primitive root of 11.
b. If user A has public keyY A = 9, what is A's private key XA?
c. If user B has public keyY B = 3, what is the shared secret key K, shared with A?


10.3 In the Diffie-Hellman protocol, each participant selects a secret number x and sends the other participant ax mod q for some public number a. What would happen if the participants sent each other xa for some public number a instead? Give at least one method Alice and Bob could use to agree on a key. Can Eve break your system without finding the secret numbers? Can Eve find the secret numbers?


10.4 This problem illustrates the point that the Diffie-Hellman protocol is not secure without the step where you take the modulus; i.e. the "Indiscrete Log Problem" is not a hard problem! You are Eve, and have captured Alice and Bob and imprisoned them. You overhear the following dialog.
Bob: Oh, let's not bother with the prime in the Diffie-Hellman protocol, it will make things easier.
Alice: Okay, but we still need a base to raise things to. How about g = 3?
Bob: All right, then my result is 27.
Alice: And mine is 243.
What is Bob's secret XB and Alice's secret XA? What is their secret combined key? (Don't forget to show your work.)


10.5 Section 10.2 describes a man-in-the-middle attack on the Diffie-Hellman key exchange protocol in which the adversary generates two public-private key pairs for the attack. Could the same attack be accomplished with one pair? Explain.


10.6 In 1985, T. ElGamal announced a public-key scheme based on discrete logarithms, closely related to the Diffie-Hellman technique. As with Diffie-Hellman, the global elements of the ElGamal scheme are a prime number q and a, a primitive root of q. A user A selects a private keyX A and calculates a public keyY A as in Diffie-Hellman. User A encrypts a plaintext M < q intended for user B as follows:
1. Choose a random integerk such that 1<= k <=q 1.
2. Compute K = (YB)k mod q.
3. Encrypt M as the pair of integers (C1, C2) where
C1 = ak mod q C2 = KM mod q
User B recovers the plaintext as follows:
Compute K = (C1) XB mod q. 1.
Compute M = (C2K12. ) mod q.
Show that the system works; that is, show that the decryption process does recover the plaintext.


10.7 Consider an ElGamal scheme with a common prime q = 71 and a primitive root a = 7
a. If B has public key YB = 3 and A chose the random integerk = 2, what is the ciphertext of M = 30?
If A now chooses a different value of k, so that the encoding of M = 30 is C = (59, C2), what is the
integer C2?


10.8 Rule (5) for doing arithmetic in elliptic curves over real numbers states that to double a point Q, draw the tangent line and find the other point of intersection S. Then Q + Q = 2Q = S. If the tangent line is not vertical, there will be exactly one point of intersection. However, suppose the tangent line is vertical? In that case, what is the value 2Q? What is the value 3Q?


10.9 Demonstrate that the two elliptic curves of Figure 10.9 each satisfy the conditions for a group over the real numbers.


10.10 Is (4,7) a point on the elliptic curve y2= x3 5x + 5 over real numbers?


10.11 On the elliptic curve over the real numbers y2= x3 36x, let P = (3.5, 9.5) and Q = (2.5, 8.5). Find P + Q and 2P.
10.12 Does the elliptic curve equation y2= x3+ 10x + 5 define a group over Z17?


10.13Consider the elliptic curve E11(1, 6); that is, the curve is defined by y2= x3+ x + 6 with a modulus of p = 11.
Determine all of the points in E11(1, 6). Hint: Start by calculating the right-hand side of the equation for all values of x.


10.14 What are the negatives of the following elliptic curve points over Z17? P = (5, 8); Q = (3, 0); R = (0, 6).
Get 10.14 exercise solution

10.15 For E11(1, 6), consider the point G = (2, 7). Compute the multiples of G from 2G through 13G.


10.16 This problem performs elliptic curve encryption/decryption using the scheme outlined in Section 10.4. The cryptosystem parameters are E11(1, 6) and G = (2, 7). B's secret key is nB = 7.
a. Find B's public key PB.
b. A wishes to encrypt the message Pm = (10, 9) and chooses the random value k = 3. Determine
the ciphertext Cm.
c. Show the calculation by which B recoversP m from Cm.


10.17 The following is a first attempt at an Elliptic Curve signature scheme. We have a global elliptic curve, prime p,and "generator" G. Alice picks a private signing key XA and forms the public verifying key YA = XAG. To sign a message M:
Alice picks a value k.
Alice sends Bob M, k and the signature S = M kXAG.
Bob verifies that M = S + kYA
a. Show that this scheme works. That is, show that the verification process produces an equality if
the signature is valid.

b. Show that the scheme is unacceptable by describing a simple technique for forging a user's
signature on an arbitrary message.


10.18 Here is an improved version of the scheme given in the previous problem. As before, we have a global elliptic curve, prime p, and "generator" G. Alice picks a private signing key XA and forms the public verifying key YA = XAG. To sign a message M,
Bob picks a value k.
Bob sends Alice C1 = kG.
Alice sends Bob M and the signature S = M XAC1-
Bob verifies that M = S + kYA
a. Show that this scheme works. That is, show that the verification process produces an equality if
the signature is valid.
b- Show that forging a message in this scheme is as hard as breaking (ElGamal) Elliptic Curve
Cryptography. (Or find an easier way to forge a message?)
This scheme has an extra "pass" compared to other cryptosystems and signature schemes we
have looked at. What are some drawbacks to this?




Solutions for Chapter 9 - Cryptography and Network Security - Stallings - 4th edition

Review Questions
9.1 What are the principal elements of a public-key cryptosystem?

9.2 What are the roles of the public and private key?

9.3 What are three broad categories of applications of public-key cryptosystems?

9.4 What requirements must a public key cryptosystems fulfill to be a secure algorithm?

9.5 What is a one-way function?

9.6 What is a trapdoor one-way function?

9.7 Describe in general terms an efficient procedure for picking a prime number.



Problems


9.1 Prior to the discovery of any specific public-key schemes, such as RSA, an existence proof was developed whose purpose was to demonstrate that public-key encryption is possible in theory. Consider the functions f1(x1) = z1; f2(x2, y2) = z2; f3(x3, y3) = z3, where all values are integers with 1 < xi, yi, zi <= N. Function f1 can be represented by a vector M1 of length N, in which the kth entry is the value of f1(k). Similarly, f2 and f3 can be represented by N x N matrices M2 and M3. The intent is to represent the encryption/decryption process by table look-ups for tables with very large values of N. Such tables would be impractically huge but could, in principle, be constructed. The scheme works as follows: construct M1 with a random permutation of all integers between 1 and N; that is, each integer appears exactly once in M1. Construct M2 so that each row contains a random permutation of the first N integers. Finally, fill in M3 to satisfy the following condition:

f3(f2(f1(k),p),k) = p
for all k, p with 1 <=k, p<= N
In words,
1. M1 takes an input k and produces an output x.
2. M2 takes inputs x and p giving output z.
3. M3 takes inputs z and k and produces p.
The three tables, once constructed, are made public.

a. It should be clear that it is possible to construct M3 to satisfy the preceding condition. As an example, fill in M3 for the following simple case:
 


Convention: The ith element of M1 corresponds to k = i. The ith row of M2 corresponds x = i; to the jth column of M2 corresponds to p = j. The ith row of M3 corresponds to z = i; the jth column of M3 corresponds to k = j.

b. Describe the use of this set of tables to perform encryption and decryption between two users.
c. Argue that this is a secure scheme.

9.2 Perform encryption and decryption using the RSA algorithm, as inF igure 9.6, for the following:
1. p = 3; q = 11, e = 7; M = 5
2. p = 5; q = 11, e = 3; M = 9
3. p = 7; q = 11, e = 17; M = 8
4. p = 11; q = 13, e = 11; M = 7
5. p = 17; q = 31, e = 7; M = 2. Hint: Decryption is not as hard as you think; use some finesse.


9.3 In a public-key system using RSA, you intercept the ciphertext C = 10 sent to a user whose public key is e = 5, n = 35. What is the plaintext M?
9.4 In an RSA system, the public key of a given user is e = 31, n = 3599. What is the private key of this user? Hint: First use trail and error to determine p and q; then use the extended Euclidean algorithm to find the multiplicative inverse of 31 modulo f(n).


9.5 In using the RSA algorithm, if a small number of repeated encodings give back the plaintext, what is the likely cause?


9.6 Suppose we have a set of blocks encoded with the RSA algorithm and we don't have the private
key. Assume n = pq, e is the public key. Suppose also someone tells us they know one of the plaintext blocks has a common factor with n. Does this help us in any way?


9.7 In the RSA public-key encryption scheme, each user has a public key, e, and a private key, d. Suppose Bob leaks his private key. Rather than generating a new modulus, he decides to generate a new public and a new private key. Is this safe?


9.8 Suppose Bob uses the RSA cryptosystem with a very large modulus n for which the factorization cannot be found in a reasonable amount of time. Suppose Alice sends a message to Bob by representing each alphabetic character as an integer between 0 and 25(A ->0,..., Z-> 25), and then encrypting each number separately using RSA with largee and large n. Is this method secure? If not, describe the most efficient attack against this encryption method.


9.9 Using a spreadsheet (such as Excel), or a calculator, perform the described below operations. Document results of all
intermediate modular multiplications. Determine a number of modular multiplications per each major transformation (such as encryption, decryption, primality testing, etc.).
a. Test all odd numbers in the range from 233 to 241 for primality using the Miller-Rabin test with base 2.
b. Encrypt the message block M = 2 using RSA with the following parameters:e = 23 and n = 233 x 241.
c. Compute a private key (d, p, q) corresponding to the given above public key (e, n).
d. Perform the decryption of the obtained ciphertext using two different methods:
1. without using the Chinese Remainder Theorem,
2. using the Chinese Remainder Theorem.


9.10 Assume that you generate an authenticated and encrypted message by first applying the RSA transformation determined by your private key, and then enciphering the message using recipient's public key (note that you do NOT use hash function before the first transformation). Will this scheme work correctly [i.e., give the possibility to reconstruct the original message at the recipient's side, for all possible relations between the sender's modulus ns and the recipient's modulus nR
(nS > nR, nS < nR, nS = nR)]? Explain your answer. In case your answer is "no," how would you correct this scheme?


9.11 "I want to tell you, Holmes," Dr. Watson's voice was enthusiastic, "that your recent activities in network security have increased my interest in cryptography. And just yesterday I found a way to make one-time pad encryption practical."
"Oh, really?" Holmes' face lost its sleepy look.
"Yes, Holmes. The idea is quite simple. For a given one-way function F, I generate a long pseudorandom sequence of elements by applying F to some standard sequence of arguments. The cryptanalyst is assumed to know F and the general nature of the sequence, which may be as simple as S, S + 1, S + 2,..., but not secret S. And due to the one-way nature of F no one is able to extract S given F(S + i) for some i, thus even if he somehow obtains a certain segment of the sequence, he will not be able to determine the rest."

"I am afraid, Watson, that your proposal isn't without flaws and at least it needs some additional conditions to be satisfied by F. Let's consider, for instance, the RSA encryption function, that is F(M) = MK mod N, K is secret. This function is believed
to be one-way, but I wouldn't recommend its use, for example, on the sequence M = 2, 3, 4, 5, 6,..."
"But why, Holmes?" Dr. Watson apparently didn't understand. "Why do you think that the resulting sequence 2K mod N, 3K mod N, 4K mod N, ... is not appropriate for one-time pad encryption if K is kept secret?"
"Because it isat least partiallypredictable, dear Watson, even if K is kept secret. You have said that the cryptanalyst is assumed to know F and the general nature of the sequence. Now let's assume that he will obtain somehow a short segment of the output sequence. In crypto circles this assumption is generally considered to be a viable one. And for this output sequence, knowledge of just the first two elements will allow him to predict quite a lot of the next elements of thesequence, even if not all of them, thus this sequence can't be considered to be cryptographically strong. And with the
knowledge of a longer segment he could predict even more of the next elements of the sequence. Look, knowing the general nature of the sequence and its first two elements 2K mod N and 3K mod N, you can easily compute its following elements."
Show how this can be done.
9.12 Show how RSA can be represented by matrices M1, M2, and M3 of Problem 9.1.


9.13 Consider the following scheme:
1. Pick an odd number, E.
2. Pick two prime numbers, P and Q, where (P 1)(Q 1) 1 is evenly divisible byE.
3. Multiply P and Q to get N.
4. Calculate   D=((P-1)(Q-1)(E-1)+1)/ E


Is this scheme equivalent to RSA? Show why or why not.
9.14 Consider the following scheme by which B encrypts a message for A.
1. A chooses two large primes P and Q that are also relatively prime to (P 1) and (Q 1).
2. A publishes N = PQ as its public key.
3. A calculates P' and Q' such that PP' 1 (mod Q 1) andQQ' 1 (mod P 1).
4. B encrypts message M as C = MN mod N.
5. A finds M by solving M CP' (mod Q) and M CQ' (mod P).
a. Explain how this scheme works.
b. How does it differ from RSA?
c. Is there any particular advantage to RSA compared to this scheme?
d. Show how this scheme can be represented by matrices M1, M2, and M3 ofP roblem 9.1.


9.15 "This is a very interesting case, Watson," Holmes said. "The young man loves a girl and she loves him too. However, her father is a strange fellow who insists that his would-be son in law must design a simple and secure protocol for an  appropriate public-key cryptosystem he could use in his company's computer network. The young man came up with the
following protocol for communication between two parties, for example, user A wishing to send message M to user B:
(messages exchanged are in the format (sender's name, text, receiver's name)."
1. A sends B the following block: (A, E(PUb, [M, A]), B).
2. B acknowledges receipt by sending to A the following block: (B, E(PUa, [M, B]), A).
 "You can see that the protocol is really simple. But the girl's father claims that the young man has not satisfied his call for asimple protocol, because the proposal contains a certain redundancy and can be further simplified to the following:"
1. A sends B the block: (A, E(PUb, M), B).
2. B acknowledges receipt by sending to A the block: (B, E(PUa, M), A).
"On the basis of that, the girl's father refuses to allow his daughter to marry the young man, thus making them both unhappy. The young man was just here to ask me for help."
"Hmm, I don't see how you can help him." Watson was visibly unhappy with the idea that the sympathetic young man has to lose his love.
"Well, I think I could help. You know, Watson, redundancy is sometimes good to ensure the security of protocol. Thus, the simplification the girl's father has proposed could make the new protocol vulnerable to an attack the original protocol was able to resist," mused Holmes. "Yes, it is so, Watson. Look, all an adversary needs is to be one of the users of the network and to be able to intercept messages exchanged between A and B. Being a user of the network, he has his own public
encryption key and is able to send his own messages to A or to B and to receive theirs. With the help of the simplified protocol, he could then obtain message M user A has previously sent to B using the following procedure:"
Complete the description.


9.16 Use the fast exponentiation algorithm of Figure 9.7 to determine 5596 mod 1234. Show the steps involved in the computation.


9.17 Here is another realization of the fast exponentiation algorithm. Demonstrate that it is equivalent to the one inF igure 9.7.

1. f<- 1; T<- a; E <-b
2. if odd(e) then f d x T
3. E |E/2|
4. T T x T
5. if E > 0 then goto 2
6. output f

9.18 The problem illustrates a simple application of the chosen ciphertext attack. Bob intercepts a ciphertext C intended for Alice and encrypted with Alice's public key e. Bob want to obtain the original message M = Cd mod n. Bob chooses a random value r less than n and computes
Z = re mod n
X = ZC mod n

t = r1 mod n
Next, Bob gets Alice to authenticate (sign) X with her private key (as in Figure 9.3), thereby decrypting X. Alice returns Y = Xd mod n. Show how Bob can use the information now available to him to determine M.


9.19 Show the OAEP decoding operation, used for decryption, that corresponds to the encoding operation oFf igure 9.9.


9.20 Improve on algorithm P1 in Appendix 9B.
a. Develop an algorithm that requires 2n multiplications and n + 1 additions. Hint: xi+1 = xi x x.
b. Develop an algorithm that requires only n + 1 multiplications and n + 1 additions. Hint: P(x) = a0 + x x q(x), where
q(x) is a polynomial of degree (n 1).
Note: The remaining problems concern the knapsack public-key algorithm described in Appendix F.

9.21 What items are in the knapsack in Figure F.1?


9.22 Perform encryption and decryption using the knapsack algorithm for the following:
a. a' = (1, 3, 5, 10); w = 7; m = 20; x = 1101
b. a' = (1, 3, 5, 11, 23, 46, 136, 263));w = 203; m = 491; x = 11101000
c. a' = (2, 3, 6, 12, 25); w = 46; m = 53; x = 11101
d. a' = (15, 92, 108, 279, 563, 1172, 2243, 4468);w = 2393; m = 9291; x = 10110001


9.23 Why is it a requirement that





Solutions for Chapter 8 - Cryptography and Network Security - Stallings - 4th edition

Review Questions
8.1 What is a prime number?

8.2 What is the meaning of the expression a divides b?

8.3 What is Euler's totient function?

8.4 The Miller-Rabin test can determine if a number is not prime but cannot determine if a number is prime. How
can such an algorithm be used to test for primality?

8.5 What is a primitive root of a number?

8.6 What is the difference between an index and a discrete logarithm?



Problems

8.1 The purpose of this problem is to determine how many prime numbers there are. Suppose there are a total of n prime numbers, and we list these in order:
p1 = 2 < p2 = 3 < p3 = 5 < ... < pn.
a. Define X = 1 +p1p2...pn. That is, X is equal to one plus the product of all the primes. Can we find
prime number pm that divides X?
b. What can you say about m?
c. Deduce that the total number of primes cannot be finite.
d. Show that pn+1 <= 1 + p1p2...pn.


8.2 The purpose of this problem is to demonstrate that the probability that two random numbers are relatively prime is about 0.6.
Let P = Pr[gcd(a,b) = 1]. Show that Pr[gcd(a,b) = d] = P/d2
Hint: Consider the quantity gcd (a/d , b/d)

b. The sum of the result of part (a) over all possible values of d is 1. That is:


 8.3 Why is gcd(n,n +1) = 1 for two consecutive integers n and n + 1?


8.4 Using Fermat's theorem, find 3201 mod 11.


8.5 Use Fermat's Theorem to find a number a between 0 and 72 with a congruent to 9794 modulo 73.


8.6 Use Fermat's Theorem to find a number x between 0 and 28 with x85 congruent to 6 modulo 29. (You should not need to use any brute force searching.)


8.7 Use Euler's Theorem to find a number a between 0 and 9 such that a is congruent to 7
1000 modulo 10. (Note that this is the same as the last digit of the decimal expansion of 7
1000.)


8.8 Use Euler's Theorem to find a number x between 0 and 28 with x 85
congruent to 6 modulo 35. (You should not need to use any brute force searching.)


8.9 Notice in Table 8.2 that f(n) is even for n > 2. This is true for all n > 2. Give a concise argument why this is so.


8.10 Prove the following: If p is prime, then f(pi) = pi p i1. Hint: What numbers have a factor in common with p i?


8.11 It can be shown (see any book on number theory) that if gcd(m, n) = 1 then f(mn) = f(m)f(n). Using this property and the property developed in the preceding problem and the property that f(p) = p 1 forp prime, it is straightforward to determine the value of f(n) for any n. Determine the following:
a. f(41)
b. f(27)
c. f(231)
d. f(440)


8.12 It can also be shown that for arbitrary positive integer a,f(a) is given by:


8.13 Consider the function: f(n) = number of elements in the set {a: 0 <=a < n and gcd(a,n) = 1}. What is this function?


8.14 Although ancient Chinese mathematicians did good work coming up with their remainder theorem, they did not always get it right. They had a test for primality. The test said that n is prime if and only if n divides (2n2).
a. Give an example that satisfies the condition using an odd prime.
b. The condition is obviously true for n = 2. Prove that the condition is true if n is an odd prime
(proving the if condition)
c. Give an example of an odd n that is not prime and that does not satisfy the condition. You can do
this with nonprime numbers up to a very large value. This misled the Chinese mathematicians
into thinking that if the condition is true then n is prime.
Unfortunately, the ancient Chinese never tried n = 341, which is non prime (341 = 11 x 31) and yet
341 divides 2 341 = 2 with out remainder. Demonstrate that 2 341 = 2 (mod 341) (disproving theonly if condition). Hint: It is not necessary to calculate 2 341; play around with the congruences instead.


8.15 Show that if n is an odd composite integer, then the Miller-Rabin test will return inconclusive for a = 1 and a = (n 1).


8.16 If n is composite and passes the Miller-Rabin test for the base a, then n is called a strong pseudoprime to the base a. Show that 2047 is a strong pseudoprime to the base 2.


8.17 A common formulation of the Chinese remainder theorem (CRT) is as follows: Let m1,..., mk be integers that are pairwise relatively prime for 1 i, j k, and i j. Define M to be the product of all the mi's. Let a1,..., ak be integers. Then the set of congruences:
x = a1(mod m1)
x = a2(mod m2)
.
.
.

x =  ak(mod mk)
has a unique solution modulo M. Show that the theorem stated in this form is true.


8.18 The example used by Sun-Tsu to illustrate the CRT was x 2(mod 3); x 3(mod 5); x 2(mod 7)
Solve for x.


8.19 Six professors begin courses on Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday,
respectively, and announce their intentions of lecturing at intervals of 2, 3, 4, 1, 6, and 5 days, respectively. The regulations of the university forbid Sunday lectures (so that a Sunday lecture must be omitted). When first will all six professors find themselves compelled to omit a lecture? Hint: Use the CRT.
8.20 Find all primitive roots of 25.


8.21 Given 2 as a primitive root of 29, construct a table of discrete logarithms, and use it to solve the following congruences:
a. 17x2 =  10(mod 29)
b. 4x 16 0(mod 29)
c. x7 = 17(mod 29)


Solutions for Chapter 7 - Cryptography and Network Security - Stallings - 4th edition

Review Questions
7.1 For a user workstation in a typical business environment, list potential locations for confidentiality attacks.

7.2 What is the difference between link and end-to-end encryption?

7.3 What types of information might be derived from a traffic analysis attack?


7.4 What is traffic padding and what is its purpose?


7.5 List ways in which secret keys can be distributed to two communicating parties.


7.6 What is the difference between a session key and a master key?


7.7 What is a nonce?


7.8 What is a key distribution center?


7.9 What is the difference between statistical randomness and unpredictability?



Problems

7.1 Electronic mail systems differ in the manner in which multiple recipients are handled. In some systems, the originating mail-handler makes all the necessary copies, and these are sent out independently. An alternative approach is to determine the route for each destination first. Then a single message is sent out on a common portion of the route, and copies are made only when the routes diverge; this process is referred to as mail bagging.
a. Leaving aside considerations of security, discuss the relative advantages and disadvantages of the two methods.
b. Discuss the security requirements and implications of the two methods.

7.2 Section 7.2 describes the use of message length as a means of constructing a covert channel. Describe three additional schemes for using traffic patterns to construct a covert channel.


7.3 One local area network vendor provides a key distribution facility, as illustrated in Figure 7.15.
a. Describe the scheme.
b. Compare this scheme to that of Figure 7.9. What are the pros and cons?

 

7.4 "We are under great pressure, Holmes." Detective Lestrade looked nervous. "We have learned that copies of sensitive government documents are stored in computers of one foreign embassy here in London. Normally these documents exist in electronic form only on a selected few government computers that satisfy the most stringent security requirements. However, sometimes they must be sent through the network connecting all government computers. But all messages in this network are encrypted using a top secret encryption algorithm certified by our best crypto experts. Even the NSA and the KGB are unable to break it. And now these documents have appeared in hands of diplomats of a small, otherwise insignificant, country. And we have no idea how it could happen."
"But you do have some suspicion who did it, do you?" asked Holmes.
"Yes, we did some routine investigation. There is a man who has legal access to one of the government computers and has frequent contacts with diplomats from the embassy. But the computer he has access to is not one of the trusted ones where these documents are normally stored. He is the suspect, but we have no idea how he could obtain copies of the documents. Even if he could obtain a copy of an encrypted document, he couldn't decrypt it."
"Hmm, please describe the communication protocol used on the network." Holmes opened his eyes, thus proving that he
had followed Lestrade's talk with an attention that contrasted with his sleepy look.
"Well, the protocol is as follows. Each node N of the network has been assigned a unique secret key Kn. This key is usedto secure communication between the node and a trusted server. That is, all the keys are stored also on the server. User A, wishing to send a secret message M to user B, initiates the following protocol:
1. A generates a random number R and sends to the server his name A, destination B, and EK(a, R).
2. Server responds by sending to E(Kb, R) to A.
3. A sends E(R, M) together with E(Kb, R) to B.
4. B knows Kb, thus decrypts E(Kb, R) to get R and will subsequently use R to decrypt E(R, M) to get M.
You see that a random key is generated every time a message has to be sent. I admit the man could intercept messages sent between the top secret trusted nodes, but I see no way he could decrypt them."

"Well, I think you have your man, Lestrade. The protocol isn't secure because the server doesn't authenticate users who send him a request. Apparently designers of the protocol have believed that sending E(Kx, R) implicitly authenticates user X as the sender, as only X (and the server) knows Kx But you know that E(Kx, R) can be intercepted and later replayed.

Once you understand where the hole is, you will be able to obtain enough evidence by monitoring the man's use of the computer he has access to. Most likely he works as follows. After intercepting E(Ka, R) and E(R, M) (see steps 1 and 3 of the protocol), the man, let's denote him as Z, will continue by pretending to be A and ...
Finish the sentence for Holmes.


7.5 If we take the linear congruential algorithm with an additive component of 0:
Xn+1 = (aXn) mod m
then it can be shown that if m is prime, and if a given value of a produces the maximum period of m 1, then ak will also produce the maximum period, provided that k is less than m and that m 1 is not divisible byk. Demonstrate this by using X0= 1 and m = 31 and producing the sequences for a = 3, 3,2, 33, and 34.


7.6 What is the maximum period obtainable from the following generator?
a. Xn+1 = (aXn) mod 24`
b. What should be the value of a?
c. What restrictions are required on the seed?


7.7 You may wonder why the modulus m = 231 1 was chosen for the linear congruential method instead of simply 231, because this latter number can be represented with no additional bits and the mod operation should be easier to perform. In general, the modulus 2k 1 is preferable to 2k. Why is this so?


7.8 With the linear congruential algorithm, a choice of parameters that provides a full period does not necessarily provide a good randomization. For example, consider the following two generators:
Xn+1 = (6Xn) mod 13
Xn+1 = (7Xn) mod 13
Write out the two sequences to show that both are full period. Which one appears more random to you?
7.9 In any use of pseudorandom numbers, whether for encryption, simulation, or statistical design, it is dangerous to trust blindly the random number generator that happens to be available in your computer's system library. [PARK88] found that many contemporary textbooks and programming packages make use of flawed algorithms for pseudorandom number generation. This exercise will enable you to test your system.
The test is based on a theorem attributed to Ernesto Cesaro (see [KNUT98] for a proof), which states the following: Given two randomly chosen integers, x and y, the probability that gcd(x, y) = 1 is 6/p2. Use this theorem in a program to determine statistically the value of p. The main program should call three subprograms: the random number generator from the system library to generate the random integers; a subprogram to calculate the greatest common divisor of two integers using Euclid's Algorithm; and a subprogram that calculates square roots. If these latter two programs are not available, you will have to write them as well. The main program should loop through a large number of random numbers to give an estimate of the aforementioned probability. From this, it is a simple matter to solve for your estimate of p.
If the result is close to 3.14, congratulations! If not, then the result is probably low, usually a value of around 2.7. Why would such an inferior result be obtained?


7.10 Suppose you have a true random bit generator where each bit in the generated stream has the same probability of being a 0 or 1 as any other bit in the stream and that the bits are not correlated; that is the bits are generated from identical independent distribution. However, the bit stream is biased. The probability of a 1 is 0.5 + d and the probability of a 0 is 0.5 d where 0 < d < 0.5. A simple deskewing algorithm is as follows: Examine the bit stream as a sequence of non-overlapping pairs. Discard all 00 and 11 pairs. Replace each 01 pair with 0 and each 10 pair with 1.

a. What is the probability of occurrence of each pair in the original sequence?
b. What is the probability of occurrence of 0 and 1 in the modified sequence?
c. What is the expected number of input bits to producex output bits?
d. Suppose that the algorithm uses overlapping successive bit pairs instead of nonoverlapping successive bit pairs. That is, the first output bit is based on input bits 1 and 2, the second output bit is based on input bits 2 and 3, and so on. What can you say about the output bit stream?
Get 7.10 exercise solution

7.11 Another approach to deskewing is to consider the bit stream as a sequence of non-overlapping groups of n bits each and the output the parity of each group. That is, if a group contains an odd number of ones, the output is 1; otherwise the output is 0.
a. Express this operation in terms of a basic Boolean function.
b. Assume, as in the preceding problem, that the probability of a 1 is 0.5 + d . If each group consists of 2 bits, what is the probability of an output of 1?
c. If each group consists of 4 bits, what is the probability of an output of 1?
d. Generalize the result to find the probability of an output of 1 for input groups onf bits.


7.12 Suppose that someone suggests the following way to confirm that the two of you are both in possession of the same secret key. You create a random bit string the length of the key, XOR it with the key, and send the result over the channel. Your partner XORs the incoming block with the key (which should be the same as your key) and sends it back. You check, and if what you receive is your original random string, you have verified that your partner has the same secret key, yet neither of you has ever transmitted the key. Is there a flaw in this scheme?



Solutions for Chapter 6 - Cryptography and Network Security - Stallings - 4th edition

Review Questions
6.1 What is triple encryption? Get solution

6.2 What is a meet-in-the-middle attack? Get solution

6.3 How many keys are used in triple encryption? Get solution

6.4 Why is the middle portion of 3DES a decryption rather than an encryption? Get solution

6.5 List important design considerations for a stream cipher. Get solution

6.6 Why is it not desirable to reuse a stream cipher key? Get solution

6.7 What primitive operations are used in RC4? Get solution

6.8 Why do some block cipher modes of operation only use encryption while others use both encryption and decryption? Get solution

Problems
6.1 You want to build a hardware device to do block encryption in the cipher block chaining (CBC) mode using an algorithm stronger than DES. 3DES is a good candidate. Figure 6.10 shows two possibilities, both of which follow from the definition of CBC. Which of the two would you choose:
a. For security?
For performance?
Figure 6.10. Use of Triple DES in CBC Mode




6.2 Can you suggest a security improvement to either option in Figure 6.10, using only three DES chips and some number of XOR functions? Assume you are still limited to two keys. Get solution

6.3 The Merkle-Hellman attack on 3DES begins by assuming a value A = 0 of (Figure 6.1b). Then, for each of the 256 possible values of K1, the plaintext P that produces A = 0 is determined. Describe the rest of the algorithm. Get solution

6.4 With the ECB mode of DES, if there is an error in a block of the transmitted ciphertext, only the corresponding plaintext block is affected. However, in the CBC mode, this error propagates. For example, an error in the transmitted C1 (Figure 6.4) obviously corrupts P1 and P2.
a. Are any blocks beyond P2 affected?
b. Suppose that there is a bit error in the source version of P1. Through how many ciphertext blocks is this error propagated? What is the effect at the receiver? Get solution


6.5 If a bit error occurs in the transmission of a ciphertext character in 8-bit CFB mode, how far does the error propagate? Get solution

6.6 Fill in the remainder of this table:

  Get solution

6.7 CBC-Pad is a block cipher mode of operation used in the RC5 block cipher, but it could be used in any block cipher.
CBC-Pad handles plaintext of any length. The ciphertext is longer then the plaintext by at most the size of a single block.
Padding is used to assure that the plaintext input is a multiple of the block length. It is assumed that the original plaintext is an integer number of bytes. This plaintext is padded at the end by from 1 to bb bytes, where bb equals the block size in bytes. The pad bytes are all the same and set to a byte that represents the number of bytes of padding. For example, if there are 8 bytes of padding, each byte has the bit pattern 00001000. Why not allow zero bytes of padding? That is, if the original plaintext is an integer multiple of the block size, why not refrain from padding? Get solution

6.8 Padding may not always be appropriate. For example, one might wish to store the encrypted data in the same memory buffer that originally contained the plaintext. In that case, the ciphertext must be the same length as the original plaintext. A mode for that purpose is the ciphertext stealing (CTS) mode. Figure 6.11a shows an implementation of this mode.
a. Explain how it works.
b. Describe how to decrypt Cn-1 and Cn  Get solution

6.9 Figure 6.11b shows an alternative to CTS for producing ciphertext of equal length to the plaintext when the plaintext is not an integer multiple of the block size.
a. Explain the algorithm.
Explain why CTS is preferable to this approach illustrated in Figure 6.11b.



6.10 What RC4 key value will leave S unchanged during initialization? That is, after the initial permutation of S, the entries of S will be equal to the values from 0 through 255 in ascending order. Get solution

6.11 RC4 has a secret internal state which is a permutation of all the possible values of the vectoSr and the two indices i and j.
a. Using a straightforward scheme to store the internal state, how many bits are used?
Suppose we think of it from the point of view of how much information is represented by the state. In that case, we need to determine how may different states there are, than take the log to the base 2 to find out how many bits of information this represents. Using this approach, how many bits would be needed to represent the state? Get solution

6.12 Alice and Bob agree to communicate privately via email using a scheme based on RC4, but want to avoid using a new secret key for each transmission. Alice and Bob privately agree on a 128-bit key k. To encrypt a message m, consisting of a string of bits, the following procedure is used:
1. Choose a random 80-bit valuev
2. Generate the ciphertext c = RC4(v || k) m
3. Send the bit string (v || C)
a. Suppose Alice uses this procedure to send a message m to Bob. Describe how Bob can recover the message m from (v || C) using k.
b. If an adversary observes several values (v1 || C1), (v2 || C2), ... transmitted between Alice and Bob, how can he/she determine when the same key stream has been used to encrypt two messages?
c. Approximately how many messages can Alice expect to send before the same key stream will be used twice? Use the result from the birthday paradox described in Appendix 11A [Equation (11.7)].
d. What does this imply about the lifetime of the keyk (i.e., the number of messages that can be encrypted usingk )? Get solution

Subscribe to: Posts (Atom)