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?

  • 1
    $\begingroup$ 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? $\endgroup$ – Ruben De Smet Jan 29 at 9:05

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<m<p$ 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.

| improve this answer | |
  • $\begingroup$ Thankyou very much, for your elaborate answer! Thankyou very much! $\endgroup$ – Vivekanand V Jan 29 at 9:47
  • $\begingroup$ 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) ! $\endgroup$ – Vivekanand V Jan 29 at 10:18
  • 1
    $\begingroup$ @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. $\endgroup$ – fgrieu Jan 29 at 10:25
  • 1
    $\begingroup$ I have edited the question and also removed the reference... :) $\endgroup$ – Vivekanand V Jan 29 at 10:38

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.