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$? Is this problem as hard as the discrete log problem? How can this task be made more computationally difficult?
$\begingroup$
$\endgroup$
11
-
1$\begingroup$ Without knowing $k$, $m$ can be literally anything. So discrete log is not going to help you, the problem is simply impossible. $\endgroup$– Emil JeřábekCommented Jan 28, 2020 at 14:23
-
$\begingroup$ @Emil Jeřábek supports Monica Can this be used as a good crypto system ? $\endgroup$– Aravind ACommented Jan 28, 2020 at 14:54
-
1$\begingroup$ It’s just as good and just as bad as any other one-time pad. (The most common construction uses XOR, which is slightly easier to implement, but mathematically speaking any abelian group will work just the same, such as the one you use.) $\endgroup$– Emil JeřábekCommented Jan 28, 2020 at 15:16
-
$\begingroup$ @Emil Jeřábek supports Monica Thankyou very much ! Is this easy for a Quantum computer to break ? $\endgroup$– Aravind ACommented Jan 28, 2020 at 15:19
-
$\begingroup$ Neither quantum computers nor any other kind can break a one-time pad. $\endgroup$– Nate EldredgeCommented Jan 28, 2020 at 17:27
|
Show 6 more comments
2 Answers
$\begingroup$
$\endgroup$
9
$c$ represents a congruence class, and there are $p$ of them. However both $m$ and $k$ belong to the same complete residue system, and so for any given $c$ there are $2^{256}$ pairs of $m,k$ that satisfy the equation. So, the answer is no.
-
$\begingroup$ Is it wise to use this a good crypto system ? $\endgroup$ Commented Jan 28, 2020 at 14:55
-
1$\begingroup$ That's a good question for crypto.stackexchange.com. $\endgroup$– JMPCommented Jan 28, 2020 at 14:56
-
$\begingroup$ Thankyou very much for your answer ! How can I move this question to get more answers from there regarding crypto? $\endgroup$ Commented Jan 28, 2020 at 15:00
-
1$\begingroup$ This question isn't very crypto, so belongs here. Ask different questions over at crypto and see what responses you get. $\endgroup$– JMPCommented Jan 28, 2020 at 15:06
-
$\begingroup$ Thankyou, that's the same reason why I felt it should be posted it here. I am very much happy with your explanation. By the way can you please tell me how you calculated that there are 2 raised to 256 pairs for any given c ? $\endgroup$ Commented Jan 28, 2020 at 15:21
$\begingroup$
$\endgroup$
1
This is a special case of an affine cipher. See the Wikipedia article on affine ciphers (https://en.wikipedia.org/wiki/Affine_cipher) for a discussion on weaknesses and cryptanalysis. It is not considered a good system of encryption.
-
$\begingroup$ I read that page, but I don't think that it will be easy to guess the key here, because of its large bit size. Further more I am thinking that if we use a different k, frequency analysis won't be able to crack it. I don't think my question is along the lines of a mono alphabet substitution cipher, where each letter is mapped to an element in the field {0, ..., p-1}. Please can you explain a little more, of why you thought my method, is weak like the Affine cipher... $\endgroup$ Commented Jan 29, 2020 at 7:16