3
$\begingroup$

I am working on a presentation aimed at developers without a strong mathematical background (like me). I would like to explain how asymetric encryption works with an non-fully-secure but working example.
I found one on Stackoverflow based on addition and modulo :

  • given a range from 1 to M
  • given a and b where a+b = M
  • a is the public key, b is the private key
  • x is the clear data (just a number)
  • y is the encrypted data
  • y = (x + a) mod M
  • x = (y + b) mod M

Example :

M=10, a=3, b=7, x=4  
y = (4+3) mod 10 = 7  
(7 + 7) mod 10 = 4  

Vilain knows the algorithm and a, y, M.
We suppose Vilain cannot guess b from a.
Reverse modulo has multiple results :

4 mod 3 = 1  
7 mod 3 = 1  
13 mod 3 = 1  

Meaning Vilain cannot easyly find

x+a 

from

(x+a) mod M

Even this is really simple, and I "feel" the modulo "wrap-around" I could not find anyway to explain WHY this works :

y = (x + a) mod M
x = (y + b) mod M

Does anyone could try to explain it to me ?

$\endgroup$
  • 3
    $\begingroup$ Note: in crypto, we assume the adversary (vilain) is smart. Knowing $a$, $M$, and with given that $a+b=M$, the adversary can find $b$, thus the system is insecure. Hint at why $x=(y+b)\bmod M$ holds: in the expression $(y+b)\bmod M$, replace $y$ according to the given $y=(x+a)\bmod M$, then use the given $a+b=M$, and the properties of the $\bmod$ operator (which stands for rest of the Euclidean division by); the property you want is that $(((u\bmod M)+(v\bmod M))\bmod M)=((u+v)\bmod M)$. $\endgroup$ – fgrieu Feb 9 '17 at 16:16
  • 1
    $\begingroup$ If you want one with a less obvious backdoor than $b = M-a$, you might want to try the same with modular multiplication; if $M$ is a large number, and $a \cdot b = 1 \bmod M$, then $y = (x \cdot a) \bmod M$ is "encryption", and $x = (y \cdot b) \bmod M$ is "decryption". One way to select such a 'key pair' is by selecting $a, b$ and setting $M = a \cdot b - 1$. Of course, this doesn't really work, it's actually fairly easy to find $b$ given $a, M$ (which you need to highlight, lest anyone thing this is actually usable), however it isn't as immediately obvious as $b = M-a$... $\endgroup$ – poncho Feb 9 '17 at 16:31
  • $\begingroup$ Thanks both of you. I know how much insecure is the modular addition. But my goal is to explain the basic principles, not ensure a "real" crypto algorithm. @poncho I am still struggling, could you give the whole process ? $\endgroup$ – Antoine Feb 10 '17 at 8:30
  • $\begingroup$ Whole process: key generation might be 'select $a, b$ at random, compute $M = ab - 1$, publish $M, a$ as your public key, keep $M, b$ as your private key; to encrypt the message $x$, you'd compute $y = ax \bmod M$; to decrypt the message $y$, you'd compute $x = by \bmod M$. This works because the result of an encryption followed by decryption is $b(ax \bmod M) \bmod M = abx \bmod M = (M+1)x \bmod M = x \bmod M$ (which is $x$ if the original plaintext are $0 \le x < M$) $\endgroup$ – poncho Feb 10 '17 at 13:47
  • $\begingroup$ I am struggling with the modular addition (sorry !). Given y = (x+a)%M and x = (y+b)%M, if I replace y I have : x = ((x+a)%M+b)%M and then what ? $\endgroup$ – Antoine Feb 10 '17 at 14:06
3
$\begingroup$

If you were to plot the numbers 0-M on a straight horizontal line in increasing order from left to right, your message would become a point on that line. When you apply the key, it moves the message over $a$ spaces to the right. The modulo operator means that if your message goes too far off the right side of the line, then it wraps back around to the left side of the line.

If you were to apply the key $a$ again, your ciphertext message would move over another $a$ spaces to the right, which, assuming an appropriate modulus, implies that the result will not line up with the original plaintext message.

With this in mind, if you were move the ciphertext message instead $b$ spaces forward, you would end up back at the original message.

If you wanted to use $a$ as a symmetric key, you would instead perform modular subtraction on the ciphertext using $a$. Basically, symmetric decryption "reverses" the transformation, while in the case of asymmetric encryption, the ciphertext is decrypted by going forward, as opposed to going backwards. This is what enables us to build public key encryption from non-invertible functions - we do not invert the transformation, we design it such that "going forward" (in a particular way) happens to "line up" and result in the original message.

Other operations can be used to create this asymmetric effect, usually employing a modulus. As mentioned by @poncho in the comments, multiplication is often used as a way to demonstrate "asymmetric crypto", but it should be noted neither addition nor multiplication is "strong enough", typically: modular exponentiation is what is used in practice to achieve the effect.

Here are some simple diagrams using your example. We'll start with a number line:

-----0-----1-----2-----3-----4-----5-----6-----7-----8-----9-----10-----

Setting $a$ at 3:

-----0-----1-----2-----a-----4-----5-----6-----7-----8-----9-----10-----

After we add $x$ (which is 4) to $a$ (which is 3); Since $a$ has been encrypted, we shall refer to the ciphertext as $b$ (as you did), which now has the value of $7$; The addition moves the value to the right on the number line:

                                   +x
                       +-----------------------+ 
                       |                       v
-----0-----1-----2-----a-----4-----5-----6-----b-----8-----9-----10-----

If we were to add $x$ to our ciphertext again, we would end up at $1$ ($11 \bmod 10 = 1$)

                                                           +x
... -------+                                   +------------------ ...
           v                                   |
-----0-----1-----2-----3-----4-----5-----6-----b-----8-----9-----10-----

This obviously leads to incorrect decryption. To decrypt correctly, we can add the corresponding private key $y=6$ ($x + y = 10$) to make the ciphertext "go forward" to the correct plaintext, remembering to wrap around when we get to the end of the number line:

                                                         +y
... -------------------+                       +------------------ ...
                       v                       |
-----0-----1-----2-----3-----4-----5-----6-----b-----8-----9-----10-----

Remark: here $10$ and $0$ are the same number (because $\mod 10$) !

$\endgroup$
  • $\begingroup$ This is a very good explanation, thank you very much ! I think I will use your process for my presentation. I am also looking for something "more mathematical", meaning : given y = (a+x) mod M, what is the process to find back x with the help of b (what is the process to go from y = (a+x) mod m to x = (y+b) mod m) $\endgroup$ – Antoine Feb 10 '17 at 8:36

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.