# Pohlig-Hellman exponentiation block cipher

Let $G$ be a group of order $n$ and let $e,d$ be integers such that $ed\equiv 1 \pmod{n}$. Then the exponentiation maps $x \mapsto x^e$ and $y \mapsto y^d$ are inverse maps on $G$.

These maps give us the Pohlig-Hellman exponentiation cipher. The secret key is the two numbers $e$ and $d$. The group $G$ and its order $n$ may or may not be secret. This block cipher is not secure (i.e. not a pseudo-random permutation) and very slow. However, it seems to me that it has some interesting properties when a suitable group is used.

1. The block cipher can be used in OFB mode: We want to encrypt a message $m = m_1m_2\dots m_k$. The first ciphertext block $c_0 = r_0$ is chosen uniformly at random from $G$, then $$r_i = r_{i-1}^e, \qquad c_i = r_i m_i, \qquad i = 1, 2, \dots, k.$$ Under the assumption that $r,r^e,r^{e^2},\dots,r^{e^k}$ is random-looking, this is secure. (Let me stress that $e$ is secret and $r$ is random.)

2. This block cipher can be used in CBC mode: We want to encrypt a message $m = m_1m_2\dots m_k$. The first ciphertext block $c_0$ is chosen uniformly at random from $G$, then $$c_i = (c_{i-1} m_i)^e, \qquad i = 1,2,\dots,k.$$ If OFB mode is secure, then this should also be secure, since the ciphertext is the random-looking sequence $c_0,c_0^e,c_0^{e^2},\dots,c_0^{e^k}$ multiplied with some stuff that only depends on the message and $e$.

3. The block cipher can be used in CTR mode: Let $g\in G$ be a generator, which may be secret and part of the key. We want to encrypt a message $m = m_1m_2\dots m_k$. The first ciphertext block $c_0=r$ is chosen uniformly at random from $G$, then $$c_i = (r g^i)^e m_i, \qquad i=1,2,\dots,k.$$ This is not secure. An easy attack is to observe that $c_i/c_{i-1} = g^e m_i/m_{i-1}$ when $i>1$.

I believe all of this is well-known folklore, but the question is: Has anyone written this up anywhere?

• Why would you define CTR mode that way? A better alternative seems to be $c_i = (g^{r^i})^em_i$. Unless I am mistaken, both $g$ and $r$ might be left public with such a construct. – Henrick Hellström Dec 11 '13 at 13:17
• There are many possible ways to define CTR mode. But the "moral" idea is that the successor function should be easy to compute relative to the cost of computing the block cipher. Given $rg^{i-1}$, it is easy to compute $rg^i$. Given $g^{r^{i-1}}$, it is expensive to compute $g^{r^i}$. Also, this alternative is insecure, since it is easy to decide if an element is an $r$th power of some other element when you know $r$. – K.G. Dec 11 '13 at 13:38
• OK, that seems to point to the conclusion that a secure CTR mode would require a way to enumerate the elements of $G$ in a way that is completely independent of the group operation in $G$. – Henrick Hellström Dec 11 '13 at 14:51