Completing RSA Encryption

Being new to cryptology, I'm trying to understand how I would complete RSA encryption by hand. I can only follow the formula so far before becoming very confused.

I want to encrypt the value "123"

First, I am to select 2 primes. I choose: $$p = 101\\ q = 103$$

Next, I compute: $$n = p\cdot q = 10403$$.

After that, I compute: $$\varphi(n) = (p-1)\cdot(q-1) = 10200$$

Now, I want to choose a public exponent, and I choose 3 for this.

I believe the formula to use is: $$d = e^{−1}\bmod\varphi(n)$$

I don't understand how to plug this formula in, nor do I know how I would encrypt "123" using this formula. Also, I don't know how I would find the decryption exponent either.

Any help would be much appreciated!

• e (and also d, but you don't choose that) must be co-prime to p-1 and q-1. Your q-1 is 102 and 3 is not co-prime to 102. If you wanted actual security, which is impossible with a tiny toy size like this, choosing p and q adjacent or near is defective. d can be computed as e inverse mod either phi(n) (Euler) or lambda(n) (Carmichael). All of the above are covered by wikipedia, and by many many many existing Qs. Jul 11 at 1:51
• As stated above, your choice of $e$ is incompatible with your choice of $q$. For the computation of $d$, see the (half-)extended Euclidean algorithm or this. Textbook RSA encryption is per $m\to c=m^e\bmod n$. Decryption is per $c\to m=c^d\bmod n$. These computations are modular exponentiation.
– fgrieu
Jul 11 at 7:28
• In practice p and q should not be too close, because this makes factorization of n easy. (Just telling, because you choose p and q close together)
– jjj
Jul 11 at 12:47

Fgrieu essentially gave the answer in comment, I will try to elaborate a bit in answer form.

You can use extended euclidean algorithm to find d from e, but note the e you selected will not work. Because e is not co-prime with $$\varphi(n)$$ You need to select another one. For efficiency we usually like to select a small e with few set bits, usually of the form $$2^k+1$$ since 3 doesn't work you can try others. https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm Here is an online calculator: https://planetcalc.com/3298/

It will not only give you the gcd (which needs to be 1) it will also give you a,b so that: $$a*e + b*\varphi(n) = 1$$ which essentially means $$a*e = 1 mod \varphi(n)$$ which is what we wanted.

You then encrypt by calculating $$c = m^e\space mod(n)$$ and decrypt using $$m = c^d\space mod(n)$$ Both done via https://en.wikipedia.org/wiki/Modular_exponentiation