For example:

Encrypt with: $M^{k_1} \bmod k_2$

where $M$ is message, $k_1$ and $k_2$ are independent keys

If it is possible, what is the decryption algorithm?



I don't think 'mod' can be reversed, so it is not possible.
Consider k1 = 2, k2 = 6.
M = 1 => C (ciphertext) = 1.
M = 5 => C = 1

You have no way of knowing whether the cleartext was 1 or 5, as you get the same ciphertext for both.


So it's $$C=M^{k_1}\bmod{k_2}$$for decryption you need $k_1 \text{ and } k_2$ and $\gcd(\varphi(k_2),k_1)=1$ must hold where $\varphi:\mathbb N\rightarrow \mathbb N$ is the euler totient function.

The formula is $M=C^{k_1^{-1}\bmod{\varphi(k_2)}}\bmod{k_2}$.

So why does this work?

We're constructing a ring here, $\mathbb Z_{k_2}^*$ by applying all operations $\bmod{k_2}$. This ring has multiplicative order $\varphi(k_2)$ and thus we can do the same as we would with RSA and find the inverse of the encryption exponent in the ring of the order ($\mathbb Z_{\varphi(k_2)}^*$) by finding $d$ such that $k_1\cdot d\equiv 1\pmod{\varphi(k_2)}$ which is normally written as $d=k_1^{-1}\bmod{\varphi(k_2)}$.

Please note: Analyzing the basic security of this scheme is non-trivial, because of the relations $M,k_1,k_2$ may have with each other (f.ex. $m$ could only generate a small subgroup, the factorization of $\varphi(k_2)$ may be smooth, ...) and of course this scheme is not IND-CPA secure as it stands (because it is deterministic).


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.