# How to make this cipher strong?

Suppose I have an arbitrary 256 bit number $$m$$ another secret number $$k$$ of the same bit length, and then I multiply them both modulo a 256 bit prime number $$p$$ to get $$c$$ as follows: $$c = (m\cdot k) \mod p$$ Is there any way to get $$m$$ back without knowing $$k$$?

Can anyone please clarify a bit more on that, and also please explain to me why my example can be broken by an attacker?

• If $k$ is unique and perfectly random for every $m$, this is a one-time pad and thus perfectly confidential. May I suggest you write out the scheme in this question as well, for clarity? – Ruben De Smet Jan 29 at 9:05

## 1 Answer

The cryptosystem enciphers plaintext $$m$$ as ciphertext $$c \gets (m\cdot k) \bmod p$$ where $$k$$ is the secret key, and $$p$$ is a prime. It is (silently) assumed $$0 and $$k\bmod p\ne 0$$; otherwise decryption by $$m \gets (c\cdot k^{-1}) \bmod p$$ is not possible. Not told, and of paramount importance: is $$k$$ used just once, or reused?

• Once: the system is information-theoretically secure, which is the best it can get, but is not a cipher per both the academic and practical definitions of that. It's like a One Time Pad, as inconvenient from the standpoint of transmitting the key, and much less convenient to use afterwards.
• Reused: The system is a cipher, but it is trivial to find (a working equivalent $$\hat k$$ of) $$k$$ from a single known pair $$(m,c)$$, per $$\hat k \gets (c\cdot m^{-1}) \bmod p$$; then decipher the rest. This is below what the expectation for good crypto has been since at least Kerckhoffs.

There's no bad crypto that can't be improved: if we use OAEP padding like in RSA to turn the message into $$m$$, and undo that on decryption, I believe the combination becomes a provably secure IND-CPA (perhaps IND-CCA2) symmetric cipher. But we have simpler and more efficient ones.

• Thankyou very much, for your elaborate answer! Thankyou very much! – Vivekanand V Jan 29 at 9:47
• I realize that even if the key is used once, an attacker (may be a spyware on the host system) can get k back if he knows the pair (m, c) ! – Vivekanand V Jan 29 at 10:18
• @VivekanandV: I suggest that you remove the question from Math Overflow, where it is off-topic. And edit the current question here on cryto.SE to make it self-contained (and perhaps more precise): or just remove it. It can't stand as is: questions here can't point to a question elsewhere. – fgrieu Jan 29 at 10:25
• I have edited the question and also removed the reference... :) – Vivekanand V Jan 29 at 10:38