I want to tell you, Holmes, Dr. Watson's voice was enthusiastic, that your recent activities in network
Question:
"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 \(\mathrm{F}\) to some standard sequence of arguments. The cryptanalyst is assumed to know \(\mathrm{F}\) and the general nature of the sequence, which may be as simple as \(S, S+1, S+2, \ldots\), but not secret \(S\). And due to the one-way nature of \(\mathrm{F}\), no one is able to extract \(\mathrm{S}\) given \(\mathrm{F}(\mathrm{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 \(\mathrm{F}(M)=M^{K} \bmod 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, \ldots "\)
"But why, Holmes?" Dr. Watson apparently didn't understand. "Why do you think that the resulting sequence \(2^{K} \bmod N, 3^{K} \bmod N, 4^{K} \bmod N, \ldots\) is not appropriate for one-time pad encryption if \(K\) is kept secret?"
"Because it is-at least partially—predictable, dear Watson, even if \(K\) is kept secret. You have said that the cryptanalyst is assumed to know \(\mathrm{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 the sequence, 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 \(2^{K} \bmod N\) and \(3^{K} \bmod N\), you can easily compute its following elements."
Show how this can be done.
Step by Step Answer: