1
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – dave_thompson_085
    Jul 11, 2021 at 1:51
  • $\begingroup$ 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. $\endgroup$
    – fgrieu ♦
    Jul 11, 2021 at 7:28
  • $\begingroup$ 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) $\endgroup$
    – jjj
    Jul 11, 2021 at 12:47

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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