10.9 Exercises

 <  Free Open Study  >  

1:

Show that formula F = ( v 1 ) ( v 2 v 3 ) ( v 3 v 1 ) is satisfiable, and justify that formula G = ( v 1 ) ( v 2 v 3 ) ( v 3 v 1 ) ( v 2 ) is not.

2:

Are there any other cliques in the graph of Figure 10-1?

3:

Give a procedure for locating a clique of size n in any given graph. What is the time complexity of your algorithm?

4:

An algorithm with a GUESS statement can be replaced by two clones of procedures executing the algorithm, one clone executing as if TRUE had been the correct guess, and the other executing as if FALSE had been correct. If one of these clones later encounters another guess, it clones itself again, so that two clones become three. Suppose an algorithm executes in n steps. What is a limit to the number of cloned processes needed to simulate that algorithm?

5:

Explain why 2 n is the difficulty factor for a deterministic solution to a nondeterministic problem of time n . That is, justify that the time bound 2 n is correct.

6:

Differentiate between a problem and an instance of a problem. Cite an example of each.

7:

Suppose an encryption algorithm is based on the satisfiability problem. Estimate the number of machine instructions necessary to solve the satisfiability problem by testing all cases. Using current technology hardware, how many variables are needed in the formula so that the time to solve this problem exceeds one year? What is the corresponding figure for hardware of five years ago? Ten years ago? Assuming similar speed improvements in the next five years, how long will it take to solve today's one-year- sized problem?

8:

Compute gcd(1875, 405).

9:

Justify that NP EXP ; that is, that NP EXP . Hint: the way to do this is to show a problem in EXP that cannot be in NP .

10:

Justify that ( a * b ) mod n = (( a mod n ) * ( b mod n )) mod n .

11:

Write the addition and multiplication tables for the integers mod 4 and for the integers mod 7.

12:

By Fermat's theorem, what is the multiplicative inverse of 2 in the field of integers mod 11?

13:

With a public key encryption, suppose A wants to send a message to B. Let A PUB and A PRIV be A's public key and private key, respectively; similarly for B. Suppose C knows both public keys but neither private key. If A sends a message to B, what encryption should A use so that only B can decrypt the message? (This property is called secrecy.) Can A encrypt a message so that anyone receiving the message will be assured the message came only from A? (This property is called authenticity.) How or why not? Can A achieve both secrecy and authenticity for one message? How or why not?

14:

Given the knapsack [17, 38, 23, 14, 11, 21], is there a solution for the target 42? Is there a solution for the target 43? Is there a solution for the target 44?

15:

Convert the superincreasing knapsack [1, 3, 5, 11, 23, 47, 97] to a hard knapsack by multiplying by 7 mod 11; by 7 mod 29.

16:

Encrypt the message 1011011010010l by each of the two hard knapsacks of the previous exercise.

17:

Encrypt the message 10110110100101 by each of the two simple knapsacks of the previous exercise.

18:

Is the Merkle “Hellman algorithm an "onto" algorithm? That is, is every number k , 0 k < n , the result of encrypting some number using a fixed knapsack?

19:

Explain why the graph of w * h i is discontinuous when w * h i > n.

20:

Find keys d and e for the RSA cryptosystem where p = 7 and q = 11.

21:

Find primes p and q so that 12-bit plaintext blocks could be encrypted with RSA.

22:

Is the DES an onto function; that is, is every 64-bit binary string the result of encrypting some string?

23:

Prove the complement property for the DES.

24:

Is a product cipher necessarily as hard to break, more hard, or less hard than the product of the difficulties of the constituent ciphers? Justify your answer.

25:

Could the full 64 bits of a DES key be used, thereby giving it a strength of 2 64 instead of 2 56 ? Justify your answer.

26:
  1. Assume each S-box substitution takes 8 units of time (because of the eight 6-bit substitutions), each P-box permutation takes 4 units of time (counting 1 unit per byte), each expansion permutation takes 8 units of time (because of the eight 4-bit expansions and permutations ) and each initial and final permutation takes 8 units. Compute the number of units of time for an entire 16-round cycle of the DES.

  2. Now suppose DES were redesigned to work with a 112-bit key and a cycle on 128 bits of input, by increasing the number of S- and P-boxes. You do not have to define the details of this design. Using similar timing assumptions as in the first part of this question, compute the number of units of time for an entire 16-round cycle of 112-bit DES.

  3. Perform a similar estimate for the timing of triple DES, using E ( k 1 , D ( k 2 , E ( k 1 , m ))).

27:

Explain how the AES key length would be expanded to 256 + 64 = 320 bits. That is, explain what changes to the algorithm would be needed.

28:

The Rijndael algorithm uses a byte substitution table that comes from a formula applied to GF(2 8 ). Is it necessary to use that formula? That is, would any substitution table work? What restrictions are there on the form of the table?

29:

A property of the Rijndael algorithm is that it is quite regular. Why is this both a good and bad property for a cryptographic algorithm?

30:

Suppose you are designing a processor that would compute with encrypted data. For example, given two encrypted data values E ( x ) and E ( y ), the processor would compute E ( x ) E ( y ), where is an encrypted addition operator that performs addition on encrypted numbers . D ( E ( x ) E ( y )) must be the same as x + y . None of the encryption algorithms of this chapter has the property that E ( x ) + E ( y ) = E ( x + y ), although the encrypted addition operator does not necessarily have to be +. For the three algorithms of this chapter, is there a relationship between E ( x ), E ( y ), E ( x + y )?

 <  Free Open Study  >  


Security in Computing
Security in Computing, 4th Edition
ISBN: 0132390779
EAN: 2147483647
Year: 2002
Pages: 129

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net