Is there something special about the XOR operation in one time pads?

59 Views Asked by At

In an alphabet with two letters (0 and 1), a message $m=m_1m_2...m_l$ can be encrypted with a key $k=k_1k_2...k_l$ of the same length by applying the exclusive or operation to each corresponding letter in the message and key to product a ciphertext $c=c_1c_2..c_l$.

$$c_h=m_h\oplus k_h$$

Given the usual assumptions this system is perfectly secure because in the Cayley table for the $\oplus$ operator:

$$\begin{array}{c|c} \oplus & 0 & 1 \\ \hline 0& 0&1 \\ \hline 1& 1&0\\ \end{array}$$

In every line and every column all the letters appear, so any given ciphertext can be generated by any message of the same length. This can easily be extended to an alphabet with $n$ letters by letting $\oplus$ be addition modulo $n$. Similarly, we could let $\oplus$ be the group operation of another (other than cyclical) group. For example the Klein 4 group:

$$\begin{array}{c|c|c|c} \oplus & 0 & 1 & 2 & 3\\ \hline 0&0 & 1 & 2 & 3\\ \hline 1& 1&0 &3 & 2\\ \hline 2& 2&3 &0&1\\ \hline 3& 3&2 &1&0\\ \end{array}$$

But it gets more interesting if we choose a non-abelian group. For example the dihedral group of degree 3:

$$\begin{array}{c|c|c|c|c|c} \oplus & 0 & 1 & 2 & 3 & 4 & 5\\ \hline 0&0 & 1 & 2 & 3 &4 & 5\\ \hline 1& 1&0 &4 & 5 & 2 & 3\\ \hline 2& 2&5 &0&4&3&1\\ \hline 3& 3&4 &5&0&1&2\\ \hline 4& 4&3&1&2&5&0\\ \hline 5& 5&2 &3&1&0&4\\ \end{array}$$

Because now this cryptosystem is suddenly asymmetric. Since $0$ is the identity, we must choose a public key $p$ and a private key $k$ so that $p\oplus k=0$ and then we can encrypt with $c=m\oplus p$ and decrypt with $m=c\oplus k$. Or applying the key on the left side of the operand: $k\oplus p=0$, $c=p\oplus m$ and $m=k\oplus c$

Of course, in this group calculating inverses is easy so a group with large order and difficult to compute inverses must be chosen, lest the private key be found from the public one.

Do these cryptosystems, especially the ones associated with a non-abelian group, have the same properties as regular one time pads? And has anyone ever used them?

1

There are 1 best solutions below

0
On BEST ANSWER

It indeed doesn't matter what group we use, all that matters really is that given $p$ and $c$ there is a unique $k$ to produce $c$ from $p$. We can use different combining functions $f(p,k)=c$ as long as we have invertability in a unique way, so to speak. We need that all combinations of $(p,k)$ that produce $c$ are all equally likely if $k$ is chosen uniformly at random for perfect secrecy.

Vernam chose bits because of the fact that he was working with binary encoded letters (5 bit telex alphabet) and xor is easy to build, and self-inverseness saves building of a separate decryption machine. In WW2, addition mod 26 was used as a combining function for one-time pads of text messages (in the SOE at least). The Russians encoded stuff in digits first and used addition mod 10. Etc.