2
$\begingroup$

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)?

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – poncho Mar 25 at 19:39
  • $\begingroup$ @poncho Thanks, extended a bit with this trick. $\endgroup$ – kelalaka Mar 25 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.