9.11 I want to tell you, Holmes, Dr. Watsons 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 gener- ate a long pseudorandom sequence of elements by applying F to some standard se- quence of arguments. The cryptanalyst is assumed to know F and the general nature ofthesequence,whichmaybeassimpleasS,S + 1,S + 2,...,butnotsecretS.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 isnt without flaws and at least it needs some additional conditions to be satisfied by F. Lets 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 wouldnt recommend its use, for example, on the sequence

M = 2, 3, 4, 5, 6,...

But why, Holmes? Dr. Watson apparently didnt understand. Why do you think that the resulting sequence 2K mod N, 3K mod N, 4K mod N, ... is not appropri- ate 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 lets 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 the sequence, even if not all of them, thus this sequence cant 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.