2
$\begingroup$

I am reading an intro book about cryptography and the author tries to explain why using pseudo random number generators is vulnerable.

Given PRNG equation;

\begin{align} S_0 &= \text{seed}\\ S_{i+1} &\equiv A\cdot S_i + B \mod m, i = 0,1,\ldots \end{align}

where we choose $m$ to be 100 bits long and $S_i,A,B \in \{0,1,\ldots,m−1\}.$ Since this is a stream cipher, we can encrypt

$$y_i \equiv x_i + s_i \mod 2$$

Further in the text:

But Oscar can easily launch an attack. Assume he knows the first 300 bits of plaintext (this is only 300/8=37.5 byte), e.g., file header information, or he guesses part of the plaintext. Since he certainly knows the ciphertext, he can now compute the first 300 bits of key stream as: (Equation 1) $s_i \equiv y_i + x_i \mod m, \; i=1,2,\ldots,300$

There are several things about the paragraph above that I don't understand.

  • Firstly, by what mechanism could Oscar gain the first 300 bits of plaintext? It makes little sense for Alice (the person who tries to securely communicate with Bob) to send encrypted and plain text together.
  • Is there a situation this happens?
  • How exactly could Oscar predict the word and location of cyphertext?

Secondly, I don't understand how Equation 1 was derived?

I appreciate any help.

$\endgroup$
2
$\begingroup$
  • Firstly, by what mechanism could Oscar gain the first 300 bits of plaintext? It makes little sense for Alice (the person who tries to securely communicate with Bob) to send encrypted and plain text together.

This is called a Known-Plaintext Attack (KPA). In some real-world examples, this attack makes sense. Also, we want our cipher to resist to KPA, we don't rely on some attackers who cannot able to find known-plaintexts around.

Why would Alice send the plaintext together with ciphertext? If so, what is the aim of encryption?

  • Is there a situation this happens?

This is taken from Mark Burnett's anwer

Example: We saw this with the old pkzip encryption method. In this case if you had any of the unencrypted files in the archive, you could use that to obtain the key to break the rest.

Also, in some militaries, the message must be started with

FROM: Name_of_the_Sender
TO: Name_of_the_Receiver

If you are intercepting the encrypted messages, this means that you know at least the first line plus 3 more characters from the plaintext.

  • How exactly could Oscar predict the word and location of cyphertext?

If you know the context, you can guess about the plaintext. Then you need to solve the equations for position $i$ to get the key. Once a candidate key is found, decrypt the rest of the cyphertext to see that is is not a false positive key. If false-positive, try next guess, if not wanderful.

Cryptoanalysis is not an easy job but once successful gives lots of pleasure.

$\endgroup$
  • $\begingroup$ I see. Thank you! Also every html page would start with <!DOCTYPE>. DO you have an idea from where equation 1 came? $\endgroup$ – sanjihan Sep 20 at 12:06
  • $\begingroup$ From the PRNG equation. could you check my $LaTeX$ edits? $\endgroup$ – kelalaka Sep 20 at 12:10
  • $\begingroup$ In this context, $x_i$ is plaintext, $y_i$ is ciphertext, and $s_i$ is the key stream. $\endgroup$ – kelalaka Sep 20 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.