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.

  • 1
    You can find examples in this site as this and this – kelalaka Nov 13 at 21:38
up vote 1 down vote accepted

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).

  • HI, so a question I am working on asks to find d given the public key N and e. But I didn't think it was possible unless you knew what p1 and p2 are so you can find phi(N). I am given e and N but not p1 or p2 so how do I find what d is? – User Nov 13 at 22:04
  • I am trying a couple things to figure out how to find D given e and N so if I am doing something wrong just let me know. – User Nov 13 at 22:05
  • 1
    @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 at 22:05
  • I think your right since N is a small number. – User Nov 13 at 22:17
  • 1
    @User wolframalpha.com also does modular inverse for you. Or the Crypto modulo in Python. etc. – Henno Brandsma Nov 13 at 22:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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