# Lehmer random number generator cipher - looking for differentials

I'm looking for differentials in my kind of toy encryption scheme. I can't find any.

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 odd $$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 like that:

1. $$a_{1} \cdot INPUT \mod 2^{128}$$
2. Reverse $$128$$-bit block.
3. $$a_{2} \cdot (2^{128}-INPUT) \mod 2^{128}$$
4. $$a_{3} \cdot INPUT \mod 2^{128}$$
5. Reverse $$128$$-bit block.
6. $$a_{4} \cdot (2^{128}-INPUT) \mod 2^{128}$$

and so on...

Do you see any differentials here? Let's skip the encryption problems with zero-block - it can be solve easily, for example if we will use xoring before every round. Of course it is just keyed Lehmer random number generator with a modulus which is a power of two - and such generators have problems with low bits, but I can't use it to find differentials in that case.

## 1 Answer

Do you see any differentials here?

Yes; consider a differential where one side is the value $$X$$ and the other side is the value $$2^{127}-X$$.

Your cipher consists of three operations:

• Multiplying the current value by an odd value $$a_i$$ modulo $$2^{128}$$

This operation preserves the differential with probability 1; one side would evaluate to $$a_i \cdot X$$ and the other side would evaluate to $$a_i \cdot (2^{127} - X) = a_i \cdot 2^{127} - a_i \cdot X = 2^{127} - a_i \cdot X$$

• Negating the current value (which is done as a part of rounds 2-10)

This operation preserves the differential with probability 1; this happens because $$-(2^{127} - X) = 2^{127} - (-X)$$

• Reversing the bits in the current value

This operation preserves the differential with probability 0.5; namely, if the lsbit of $$X$$ (equivalently, $$2^{127} - X$$) is a 1. This happens because, when the lsbit is a 1, this relationship is equivalent to the relation that $$X \oplus (2^{127}-X) = 2^{127}-2$$. This later relation is preserved when you reverse the bits, and hence the former one is as well.

This gives you a differential that holds with probability $$2^{-10}$$ through the ten rounds of the cipher.

• Thanks, I'm just starting to learn about differential cryptanalysis, so even if it was obvious I didn't see it. Anyway, I was looking hard for differentials which I could use knowing that every number $2^{n} \cdot k$ gives $n$ zeros first. Do you think such differentials has been removed in this scheme? You used these differences to break similar toy cipher from my previous question. Does this problem give any advantage to use it now in differential cryptanalysis?
– Tom
Commented Oct 8, 2020 at 11:10
• What happended with $a_{i}$ in last equation, why it dissapeared? $a_i \cdot (2^{127} - X) = a_i \cdot 2^{127} - a_i \cdot X = 2^{127} - a_i \cdot X$
– Tom
Commented Oct 9, 2020 at 10:49
• @Tom: because $a_i$ is odd (if it were even, decryption would be difficult), and for any odd value $a$, we have $a \cdot 2^{127} \equiv 2^{127} \pmod{ 2^{128}}$ Commented Oct 9, 2020 at 12:43
• That's what I thought, but this is not working. Let's say $a_{i}=13$ and $X=5$. Then $13 \cdot 5 \mod 16=1$ and $13 \cdot (15-5) \mod 16=2$ and $15-13 \cdot 5 \mod 16=14$. So $14$ is not equal to $2$.
– Tom
Commented Oct 9, 2020 at 12:55
• @Tom: if you're working modulo $16 = 2^4$, then the relation would be $a_i \cdot (2^3 - X) = 2^3 - a_i \cdot X$, which does hold; $13 \cdot (8-5) \bmod 16 = 7$ and $8 - 13\cdot 5 \bmod 16 = 7$ (remember, in math, unlike many computer languages designed by nonmathematicians, $-57 \equiv 7 \pmod{16}$ Commented Oct 9, 2020 at 13:24