5
$\begingroup$

This comment from Reddit math, in response to a statement about how people can communicate secrets to each other with a third party listening, has a very small, simple example of public key cryptography:

Take your message, treat it as a number and multiply it by a bunch of primes.

Send it to me. I will then multiply by a bunch of primes too.

I send it back to you. You then divide by all of your primes.

Send it back to me. I divide by all of my primes and get the original message.

This comment has 5700+ upvotes by Reddit math, but it strikes me as unusual because there's no modular arithmetic used, only primes.

Does this example actually work, if sufficiently large primes are used?

|improve this question
$\endgroup$
  • 5
    $\begingroup$ This concept is known as Three-pass protocol and requires encryption to be commutative. There are secure instantiations of this protocol, but the one you quote is not secure. $\endgroup$ – CodesInChaos Feb 20 '16 at 14:46
10
$\begingroup$

Breaking such a scheme is easy.

Suppose Alice wants to transmit a message $M$ to Bob. First thing, Alice picks an integer $R_a$ and sends the cipher text $C_a = M \times R_a$ to Bob. Bob then picks another integer $R_b$ and transmits $C_b = C_a \times R_b$ back to Alice. Alice calculates $D_a = \frac{C_b}{R_a}$ and sends $D_a$ to Bob. Bob calculates $D_b = \frac{D_a}{R_b}$ and clearly $D_b = M$.

Now, Eve intercepts the messages $C_a, C_b, D_a$ and might easily calculate $R_a = \frac{C_b}{D_a}$ and consequently $M = \frac{C_a}{R_a}$. Eve is clearly not supposed to be able to do this, so this constitutes a break.

Furthermore, it doesn't really matter if the multiplication is done in a finite group or not. In a group, division would be defined as multiplication with the inverse element of the divisor, e.g. $D_a = {C_b} \times {R_a}^{-1}$. Eve would still be able to calculate $M$.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ While this scheme is also broken for modular multiplication (using the extended Euclidean algorithm), you can't conclude that it's insecure in every finite group, because that inverse might not be efficiently computable. (e.g. Shamir three-pass protocol is secure and apart from using modular exponentiation it's nearly identical to this proposal) $\endgroup$ – CodesInChaos Feb 20 '16 at 14:52
  • $\begingroup$ @CodesInChaos: Well, the difference is that with Shamir three-pass, the multiplication operations wouldn't be performed in the same group that the cipher text messages belong to. If the Diffie-Hellman assumption applies to the group, the "multiplication" would be impossible to compute. $\endgroup$ – Henrick Hellström Feb 20 '16 at 16:34
  • $\begingroup$ Thanks @HenrickHellström, the answer is clear and concise (and I've tested it and it works). Would using multiple primes as the Reddit post mentioned help, if they were sufficiently large? $\endgroup$ – mikemaccana Feb 23 '16 at 18:01
  • $\begingroup$ @mikemaccana: No, it doesn't matter. It doesn't matter if the numbers are primes, smooth or products of large primes - either way the number will be a large integer, and Eves attack works for any large integer, as long as it is not so large it will be infeasible to carry out any arithmetic operation at all on it. But if Alice and Bob are able to multiply and divide the numbers, so will Eve. $\endgroup$ – Henrick Hellström Feb 23 '16 at 18:31
1
$\begingroup$

Except above attack,modular arithmetic reduces the amount of calculation and computation with modular properties(example:5832 mod 33=24) and if you want to have a number similar to n=pq that n is difficult to factor,you should choose two large numbers(p,q) and then calculate n=pq , so your algorithm needs large numbers that it needs big memory and long time for calculation,and it is not good.

in other words modular arithmetic in cryptography has a good advantage in calculation with large number that large numbers are necessary for security of cryptosystems because the attacker can not have a brute force attack

|improve this answer
$\endgroup$

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.