# Lehmer random number generator - cipher?

Let's consider linear congruential generator:

$$X_{k+1} = a \cdot X_{k} \mod 2^{128}$$

Such that $$a$$ is some number which for every 128-bit input $$X_{k}$$ from $$0$$ to $$2^{128}-1$$ will give us different output $$X_{k+1}$$ from $$0$$ to $$2^{128}-1$$. So we got bijection here (we can find many such $$a$$).

Now let's say we will choose such 128-bit $$a_{1},a_{2}, ..., a_{10}$$ as a keys, randomly. We make $$10$$ rounds of encryption and every round compute:

1. $$a_{i} \cdot INPUT \mod 2^{128}$$
2. Reverse 128-bit block.

So the next round input is an inverted block of previous round output. And it looks like it make a big difference. If we wouldn't reverse block - we got just keyed Lehmer random number generator with a modulus which is a power of two - and it is definitely not secure (because the low $$k$$ bits form a modulo-$$2^{k}$$ generator all by themselves).

But with "reversing" we get completely different results! It looks chaotic. I have no idea is 10 rounds enough - just guessing. Is this type of encryption secure? Do you see any obvious weaknesses? To analyze it we can choose smaller keys and smaller operating mode - for example 5-bit or 10-bit. A detailed analysis of this cipher can be difficult, my question is rather about some obvious weaknesses. The cipher appears to be unexpectedly good, despite being only a minor modification of the linear congruential generator. So either I don't notice something or it is quite a non-trivial proposition.

Comment 1: let's skip the encryption problems with zero-block - it can be solve easily, for example if we will use xoring before every round.

• "we can find many such $a$" can be replaced by: "that is odd $a$". – fgrieu Sep 17 at 19:47

Nope (even if you make all the $$a_i$$ values odd, which you need to make it invertible).
It turns out that there are high probability differentials in this structure; in particular, you have a one-round differential with an input xor difference of (01111...11110) (that is, all bits except the first and last are flipped) and the output xor difference of (01111...11110); this differential holds with probability $$> 0.5$$. Because the output differential of round $$X$$ is the input differential of round $$X+1$$, the entire differential holds through the entire cipher with probability $$> 2^{-10}$$
• If I understand it properly, if we add third step: move with wrapping obtained block by $0-127$ steps, then to attack it in the same way, we have $128$ times smaller differential probability in every round. If we make $20$ rounds, we could have entire differential holds with probability about $128^{20}$. Then it could be secure from that type of attack. – Tom Sep 20 at 18:43