-2
$\begingroup$

Everywhere in the lessons on asymmetric encryption explains the process of encryption and messaging, but I'm interested in the asymmetric encryption algorithms themselves. The only thing I have so far realized is that the whole point of such encryption is the use of the mathematical operation of the mod. But how do I create my own primitive asymmetric encryption algorithm?

$\endgroup$
3
  • $\begingroup$ 'But how do I create my own primitive asymmetric encryption algorithm?'; are you asking how to create your own implementation of (say) RSA? Or, are you asking how to design your own novel algorithm? $\endgroup$
    – poncho
    Feb 15, 2018 at 17:24
  • $\begingroup$ I want to understand how to encrypt data using one key and decrypt it using another key. for now I only understand that it can be realized with mod $\endgroup$ Feb 15, 2018 at 17:28
  • 1
    $\begingroup$ You have two questions, one in the title and one in the last line. The answer to the one in the last line is "you don't, because doing that takes about a decade of your life in a PHD program + gaining experience afterwards" the answer to the one in the title is going to amount to "read a good book/tutorial on this" probably with some links. $\endgroup$ Feb 15, 2018 at 17:41

1 Answer 1

2
$\begingroup$

the whole point of such encryption is the use of the mathematical operation of the mod

It's not the whole point, the modulo operation is just useful for a few reasons. One of which is that it facilitates the existence of inverse elements, which can be used to undo the relevant operation. Finding a way to generate an element and it's inverse where it is hard for anyone else to generate the inverse from the element can form the basis of a key generation algorithm for a trapdoor style algorithm.

A basic (insecure) example of an asymmetric encryption and decryption algorithm uses an operation such as addition or multiplication modulo operation a prime.

  • Given a public modulus $N$
  • Generate a encryption key $k_e$ by selecting a value between $[1, N]$
  • Assuming the addition operator is what we will use, generate a decryption key $k_d$ by computing $N - k_e$

To encrypt a message $m$:

  • Compute $c = m + k_e \bmod N$

To decrypt a ciphertext $c$:

  • Compute $m = c + k_d \bmod N$

Since $k_e \neq k_d$ (with high probability), this algorithm qualifies as asymmetric in the sense of one key being used for one operation and the other being used for the inverse operation. It is completely insecure for a variety of reasons, but it demonstrates the nature of some* asymmetric algorithms:

  • You generate two keys, one of which can be used to invert the action of the other key not by "undoing it", but by instead going forward to the equivalent result had you undone the action. We did not subtract $k_e$, we instead added some other $k_d$ that happens to produce the same result that subtracting $k_e$ would have produced.

You could change the operator in the above example to multiplication instead of addition, and generate the inverse accordingly. However, that is still insecure for a variety of reasons. Finding an appropriate operator is part of the challenge of developing such a system.

Given $k_e, N$, it needs to be infeasible to generate $k_d$.

  • It is usually easier to generate $k_d$ first and generate $k_e$ from it. For basic addition and multiplication, given $k_e, N$, it is trivial to recover the inverse $k_d$. Part of the challenge is finding a way to generate $k_e$ such that finding $k_d$ when given $k_e, N$ is hard.

A Good Example

You can see an example of these points in RSA. In order to recover $d$ from $e, N$, it would require you to first factor $N$, which is (believed to be) hard. The fact that ${m^e}^d \equiv m \bmod N$ is what enables decryption. Note that $d \neq e$, and we use $d$ to exponentiate $m^e \bmod N$ again to get back to $m$.

*Key agreement style algorithms

Key agreement algorithms such as Diffie-Hellman don't require the computation of an inverse and don't necessarily require you to invert anything. Classic Diffie-Hellman is actually a generic recipe (in the sense of functional correctness) when given a group structure. Noisy Diffie-Hellman provides approximate key agreement, but is more or less a different beast completely.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.