For password cracking, generally the most realistic situation is Case IV of Section XXXXXXXXXXIn this case, the amount of work that Trudy must do to determine a password depends on the size öf the...

For password cracking, generally the most realistic situation is Case IV of Section 7.3.5. In this case, the amount of work that Trudy must do to determine a password depends on the size öf the dictionary, the probability that a given password is in the dictionary, and the size of the password file. Suppose Trudy's dictionary is of size 2™, the probability that a password is in the dictionary is p, and the password file is of size M. Show that if p is small and M is sufficiently large, then Trudy's expected work is about 2"/p. Hint: Use the result of Problem 24.