# How to solve polynomial modular equation to create a correct decryption algorithm

I recently had a variant of the following problem in my cryptography course and I had trouble solving it and was looking to get some help.

Given the symmetric key cryptosystem: $$\text{KG, Enc, Dec}$$ where $$\text{KG}$$ is a key generator that produces a random key in the space $$Z_n = \{1, 2, 3, \ldots, n-1\}$$, $$m$$ is a message from the space $$Z_n$$, and $$\text{Enc}(K, m)$$ is an encryption algorithm which computes ciphertext $$c = (5m - 4k + 3) \bmod n$$, design a decryption algorithm $$\text{Dec}(K, c)$$ such that it fulfills decryption correctness.

At first, I just tried solving for $$c$$ in $$c = 5m - 4k + 3$$, but realized that it does not account for $$\bmod n$$. Then it tried the following solution:

$$\text{let} (d, x, y) = \text{extGCD}(c, n), m = (c\times x+4k-3)/5$$

Where $$\text{extGCD}$$ is the Euclidian extended GCD function (essentially finding the modular inverse). That did not work either.

How would one go about solving this problem? What am I missing (so I can look into it further)?

We can write $$m$$ as

$$m = (c -3 + 4k) \cdot 5^{-1} \pmod n$$

There is a problem here that the 5 may not has an inverse for every $$n$$. For example, it doesn't have an inverse in $$\mathbb{Z}_{10}$$.

It has an inverse in $$\mathbb{Z}_{n}$$ if $$\gcd(5,n) =1$$.

If it has the inverse one can find it by the Extended Euclidean Algorithm to form the Bézout's identity $$5 x + n y = 1$$ then take $$\bmod n$$ to achive the inverse as $$5 x = 1 \bmod n$$

As pointed by poncho, for finding the inverse of $$5$$ there is a better method $$(n+1)/5, (2n+1)/5, (3n+1)/5, (4n+1)/5$$ if the inverse exist. To see the inverse exist, one first needs to see that the $$\gcd(5,n)=1$$.

In the general case, after some threshold, this approach may not be helpful, since testing all $$(n+1)/x, (2n+1)/x, \ldots, ((x-1)n+1)/x$$ will pass the calculation of the Bézout's identity.

• Even easier way to find $5^{-1}$ (if it exists); it's the one of $(n+1)/5, (2n+1)/5, (3n+1)/5, (4n+1)/5$ that's an integer. Obviously, this doesn't scale for finding $x^{-1}$ for large $x$; for $x=5$, it works... – poncho Mar 25 at 19:39
• @poncho Thanks, extended a bit with this trick. – kelalaka Mar 25 at 19:56