Join Log in
Score:1
Bobby Lefto avatar Crypto

Completing RSA Encryption

bl flag
Bobby Lefto

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!

66
1 + 3
rsa
dave_thompson_085 avatar
cn flag
dave_thompson_085
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.
1
Reply
fgrieu avatar
ng flag
fgrieu
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](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Computing_multiplicative_inverses_in_modular_structures) or [this](https://crypto.stackexchange.com/q/5889/555). 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](https://en.wikipedia.org/wiki/Modular_exponentiation).
0
Reply
jjj avatar
cn flag
jjj
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)
0
Reply
Score:1
Meir Maor avatar Crypto
in flag
Meir Maor

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

0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.