# RSA How to select a value K such that $e d = 1 + k \varphi(N)$ holds

I am learning RSA cryptography. The part I am stuck on is understanding how k and the public exponent $$e$$ is selected.

Given the formulas;

Decrypting: $$c^d \bmod N = (m^e)^d \bmod N$$ Which is equal to m the message

Encrypting: $$m^e \bmod N = c$$

My question is when generating the private exponent how do we find what the public exponent should be and what k should be in the formula

$$d = (1 + k*\varphi(N))/e$$

I understand it has something to do with the inverse of modules but I don t get the math behind it.

• You can find examples in this site as this and this – kelalaka Nov 13 '18 at 21:38

You apply the extended Euclidean algorithm to $$e$$ and $$\phi(N)$$ (which have to have gcd equal to $$1$$) and we get $$x,y \in \mathbb{Z}$$ such that
$$xe + y\phi(N) = 1$$
The $$x$$ (taken modulo $$\phi(N)$$, if needed) is the $$e$$ you are looking for. The $$k$$ is totally irrelevant for encryption/decryption, but it's actually the $$y$$ in the above equation (rewrite your equation and see).
• @User You cannot, unless it's a puzzle with a special trick. Like taking $d$ too small, or $N$ being easily factorisable etc. – Henno Brandsma Nov 13 '18 at 22:05