1
$\begingroup$

There was a time when I wondered about multiplication as an encryption operation. That was when I was thinking in terms of modular multiplication. But how about based around simple multiplication.

Pretend $M$ is a message represented as a number. $K$ is the secret key. Encryption is $C=M \times K$ and decryption is $M=C \div K$. Pretty simple and probably untouched. Has anyone ever suggested this?

$\endgroup$
1
  • 3
    $\begingroup$ $K \: = \: C \div M \;\;\;\;$ $\endgroup$ – user991 Feb 8 '15 at 5:47
4
$\begingroup$

As Ricky Demer comments above, an obvious weakness of this scheme is that if you know (or can guess) the plaintext $M$ corresponding to any ciphertext $C$, then you can immediately recover the key by calculating $K = C/M$. Modern ciphers are generally expected to resist such known-plaintext attacks, making your cipher insecure by any current standards.

In fact, even if we don't know any plaintexts, there are still ways to attack your cipher. For example, let's say that we've intercepted $k$ ciphertexts $C_1, C_2, \dots, C_k$, and we wish to decrypt them. The obvious attack is based on the fact that, by definition, each of the ciphertexts is divisible by $K$. More specifically, $$\gcd(C_1, C_2, \dots, C_k) = K \cdot \gcd(M_1, M_2, \dots, M_k),$$ where $\gcd(\dots)$ denotes the greatest common divisor of the ciphertexts and the plaintexts respectively. Assuming that the plaintexts are not specifically chosen to all share a common divisor (in which case we might as well regard this deliberate common divisor as part of the key), as the number of intercepted messages $k$ grows, the probability that $\gcd(M_1, M_2, \dots, M_k) = 1$ approaches 100%.

Thus, having intercepted enough ciphertexts, we may calculate $K' = \gcd(C_1, C_2, \dots, C_k)$, which can be done efficiently e.g. using Euclid's algorithm, and be reasonably confident that $K' = K$, possibly times a small factor coincidentally shared by all the plaintext messages. Thus, we can try decrypting the ciphertexts using $K'$ and see if the results look like plausible messages; if they do not, we can either intercept more ciphertexts, or simply try multiplying the decrypted plaintexts with small factors of $K'$ and see if this yields more plausible-looking results. Either way, it should not take too many ciphertexts to recover the key and intercept all the messages.


Of course, the attacks above are only practical if the same key $K$ is used to encrypt multiple messages. If the key for each message is (somehow) chosen independently at random, they do not yield any useful information to the attacker.

However, even in this case, your scheme still leaks some information to the attacker. As a basic observation, we may note that, if $C$ is not divisible by some number $X$, then $M$ also cannot be divisible by $X$. This observation alone is enough to show that your cipher lacks semantic security, which, again, makes it insecure by modern standards.

For a more concrete attack, let us assume that you regularly send messages consisting of the same plaintext $M$ (say, "nothing to report"), with different keys $K_1, K_2, \dots, K_n$. With sufficiently many message, it's very unlikely that all the keys would just happen to share any common factor (unless this is done deliberately, in which case we're just back at the fixed-key case), so I can simply compute $M' = \gcd(C_1, C_2, \dots, C_n)$ and be reasonably confident that $M' = M$.

(Of course, for a more advanced attack, I can look for factors that are shared by most of the ciphertexts you send, which most likely correspond to either repeated plaintexts or repeated keys. Then, observing any ciphertext that doesn't share one of these factors would be a strong indication that something unusual is going on.)

$\endgroup$
2
  • $\begingroup$ And if it's a one time key? $\endgroup$ – Melab Feb 8 '15 at 18:53
  • 1
    $\begingroup$ See the part below the horizontal line. $\endgroup$ – Ilmari Karonen Feb 8 '15 at 18:55
1
$\begingroup$

Following Keelan, mathematically there is no difference with the Caesar system. For instance, let $M=a^m$ and $K=a^k$ for an appropriate number (or generator a), then: $$a^{m+k}=a^m \times a^k=M \times K \; mod \;N$$

$\endgroup$
0
$\begingroup$

This is basically substitution using some special bijective function, so yes, the principle has been suggested (and used, in ancient times).

Also, the main problem with a substitution cipher is present in this scheme: frequency analysis. One could count the frequencies of the numbers in your encrypted message, and, assuming he knows the language of the plaintext, compare it to the letter frequencies in plaintext.

Also note that one can find the key easily when one has both plaintext and encrypted text.

$\endgroup$
5
  • $\begingroup$ It doesn't use modular arithmetic. The whole message is treated as a number, so how can frequency analysis apply. The keys can be one-time only, generated by some master key and a nonce. $\endgroup$ – Melab Feb 8 '15 at 16:03
  • $\begingroup$ @Melab ah, you're not dividing the plaintext in blocks at all? Then, you would have extremely large numbers. Suppose I have a document of 10kB. Do you have an idea of how large a number that would be? To prevent brute force attacks, you would need a large key as well, making this scheme impossible to handle. $\endgroup$ – user4686 Feb 8 '15 at 16:10
  • $\begingroup$ Would breaking into smaller blocks change anything then? $\endgroup$ – Melab Feb 8 '15 at 17:16
  • $\begingroup$ Add isn't hard to factor a number with brute force? $\endgroup$ – Melab Feb 8 '15 at 17:16
  • $\begingroup$ @Melab your numbers will be too big for small texts already, is my point. Breaking into smaller blocks will make a difference, this will allow frequency analysis. $\endgroup$ – user4686 Feb 8 '15 at 17:28

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.