# Stream ciphers

So far, we have illustrated cryptosystems that “reuse” the same key to encrypt letters or blocks of the plaintext. This is usually referred to as block ciphers. $\begin{matrix} x_1 & x_2& \ldots ~~~~~~& x_n\\\downarrow& \downarrow&&\downarrow\\k\rightarrow\fbox{E}~~~~~~&k\rightarrow\fbox{E}~~~~~~&\ldots~~~~~~&k\rightarrow\fbox{E}~~~~~~\\\downarrow&\downarrow& &\downarrow\\y_1 & y_2 & \ldots ~~~~~~& y_n\end{matrix}$

This scheme can be generalized by considering a stream of keys instead of a fixed one. Let $z_1, z_2, \ldots, z_n$ be such a stream. The idea is to encrypt the first letter of the plaintext with $z_1$, the second with $z_2$ and so on. It does not matter much if we encrypt a letter or a block, the important difference is that the used key is always different. $\begin{matrix} x_1 & x_2 & \ldots ~~~~~~~& x_n\\\downarrow&\downarrow& &\downarrow\\z_1\rightarrow\fbox{E}~~~~~~~&z_2\rightarrow\fbox{E}~~~~~~~&\ldots~~~~~~~&z_n\rightarrow\fbox{E}~~~~~~~\\\downarrow&\downarrow& &\downarrow\\y_1 & y_2 & \ldots ~~~~~~~& y_n\end{matrix}$

Having a different key for each letter or block of the plaintext is of course appealing but not much practical. The stream of key is thus usually derived starting from an initial key $k$. To make the stream more complex it can also depend on previous part of the plaintext. In general we say that $z_i = f_i(k,x_1,\ldots,x_{i-1})$. To understand why a key $z_i$ cannot depend on plaintexts with indexes greater than or equal to $i$, it is useful to reason on the decryption scheme: $\begin{matrix} y_1 & \ldots ~~~~~~~& y_i & \ldots ~~~~~~~& y_n\\\downarrow&&\downarrow& &\downarrow\\z_1\rightarrow\fbox{D}~~~~~~~&\ldots~~~~~~~&z_i\rightarrow\fbox{D}~~~~~~~&\ldots~~~~~~~&z_n\rightarrow\fbox{D}~~~~~~~\\\downarrow& &\downarrow& &\downarrow\\x_1 & \ldots ~~~~~~~& x_2 & \ldots ~~~~~~~& x_n\end{matrix}$

Now, $z_1 = f_1(k)$ meaning that we can compute it with not knowledge of the plaintext. To compute $z_2 = f_2(k,x_1)$, instead, we need to know $x_1$. As a consequence, we have to decrypt $y_1$ with $z_1$ before computing $z_2$. Once we have this key we can decrypt $x_3$ and compute $z_3$, and so on. The values are thus computed in the following sequence: $z_1,x_1,z_2,x_2, \ldots, z_n,x_n$. It should be evident, now, that we cannot let $z_i$ depend, e.g., on $x_i$ as we would need that plaintext to compute the key.

Notice that block ciphers are, clearly, a simple instance of stream ciphers where $z_i = k$ for all $i$.It is also useful to classify these ciphers depending on certain properties of the key stream:

#### Periodic

A stream cipher is periodic its key stream has the following form $z_1,z_2,\ldots,z_d,z_{1},z_2,\ldots,z_d,z_1\ldots$, i.e., if it repeats after $d$ steps.

Exercise. Vigenére cipher can be seen as a stream cipher acting on single letters and with a periodic key stream. Formalize the cipher giving $({\cal P},{\cal C},{\cal K},E,D)$  and defining the key stream $z_i$.

Synchronous. A stream cipher is synchronous if its key stream does not depend on plaintexts, i.e., $z_i = f_i(k)$ for all $i$. When this happens, we have that the key stream can be generated starting from $k$ and independently on the plaintext. This is particularly useful to improve efficiency: we do not need to obtain $x_{i}$ to compute $z_{i+1}$. In fact, the key stream can be generated offline, before the actual ciphertext is received.

Asynchronous. This is the general case where $z_i = f_i(k,x_1,\ldots,x_{i-1})$. As mentioned above, we need to decrypt and compute the keys stream at the same time, as a key can depend on previous plaintexts. We give a simple example of a cipher of this class, called Autokey. We let ${\cal P}={\cal C}={\cal K}=\mathbb{Z}_{26}$. $E_z(x) = x+z \mod 26$ and $D_z(y) = y-z \mod 26$, i.e., encryption and decryption are exactly as in a shift cipher. The key stream is defined as $z_1 = k$ and $z_i = x_{i-1}$ for $i\geq 2$, meaning that the first key in the stream is the initial key $k$ while the next keys are the same as the previous plaintext. $\begin{matrix} x_1 & x_2& \ldots ~~~~~~& x_n\\\downarrow& \downarrow&&\downarrow\\k\rightarrow\fbox{E}~~~~~~&x_1\rightarrow\fbox{E}~~~~~~~&\ldots~~~~~~&x_{n-1}\rightarrow\fbox{E}~~~~~~~~~~~\\\downarrow&\downarrow& &\downarrow\\y_1 & y_2 & \ldots ~~~~~~& y_n\end{matrix}$

Exercise: try to break the following ciphertext encrypted with the above autokey cipher:

GUAAMLXOOVTMRVTKXOWSSDXNVJSTVTACALTNQFTPNIHUXRPWLV

This site uses Akismet to reduce spam. Learn how your comment data is processed.