Simple explanation/example of RSA encryption?

Question

Hello, I am trying to understand how public key encryption works -- I've looked through several websites, but I find them very confusing and if they do manage to provide an example I find myself quickly lost. Can someone explain simply how it works? I think the part I'm having the most trouble with is understanding how "trap door" function works? I really want to understand this so please explain it simply and using small numbers :)
Thanks!

Answer 1

RSA is a public key encryption system that gets its security from the difficulty of factoring large numbers. This is the so-called trap door. Two different, but intimately related, numbers are used for the encryption and decryption. The public key is used to encrypt the message, but it can not be used to decrypt the message. The same is true for the private key. It is used to decrypt only.

How does this work, and where is the trap door? Well, to generate the two keys choose 2 large prime numbers p and q. First compute and save the product of p and q:

n = p x q

Now, randomly select a number e such that e and ((p - 1) x (q - 1)) have no common factors, i.e., they are relatively prime. Now, find a d (usually computed with Euclid's algorithm) such that

e x d ≡ 1 mod ((p - 1) x (q - 1))

Note that d shares no common factors with n, either. Publish e and n, they are the public key; d is the secret key that should not be revealed, and discard but never reveal p and q.

Now to encrypt a plain message --let's call it 'pm'-- into an secret message --let's call that sm-- you jst do this:

sm = pm^e (mod n)

To decrypt you just do this:

pm = sm^d (mod n)

Now, the keys are symmetric in the sense that you can encrypt with either key, and decrypt with the other key not used for the encryption. Let's try an example.

p = 47
q = 71
n = p x q = 47 x 71 = 3337

e must be relatively prime to ((p - 1) x (q - 1))
(p - 1) x (q - 1) = 3220, so choose e at random with that in mind. I choose

e = 79

Now, find a d such that
e x d = 1 mod 3220

d = 1019

e, n are the public key, I keep d a secret and discard p and q.

To encrypt this message 6882326879666683, I'll break it into small blocks (easier to do the math!)

pm1 = 688
pm2 = 232
pm3 = 687
pm4 = 966
pm5 = 668
pm6 = 3

To encrypt pm1 we do

688^79 (mod 3337) = 1570 = sm1

Doing this for the rest of the message I string the sm's together like so:

1570 2756 2714 2276 2423 158

To decrypt I just do the reverse:

1570^1019 (mod 3337) = 688 = pm1

Now if you have *only* e and n can you can you calculate d? You can if you are able to fully factor n and so recover p and q. How easy is it to factor n? That depends on how big n is --this is the trap door. In actual practice how big are the numbers we are talking about? Anywhere from 200 to 1000 digits. If I give you a number 1000 digits long can you quickly factor it? So far, the answer is no. There is as yet no publicly known way to factor numbers that large quickly.

HTH

Charles

Answer 2

Rsa Encryption Explained

Answer 3

This Site Might Help You.

RE:
Simple explanation/example of RSA encryption?
Hello, I am trying to understand how public key encryption works -- I've looked through several websites, but I find them very confusing and if they do manage to provide an example I find myself quickly lost. Can someone explain simply how it works? I think the part I'm having the most...

Answer 4

For the best answers, search on this site https://shorturl.im/avOt1

Public key crypto uses asymmetric key pairs. A symmetric key can be used for both encrypting information and decrypting information. The problem is you must first give the key to someone for them to be able to decrypt the information. This is just fine for small wireless networks, where the key is pre-shared by whoever is setting up the network. But for robust information sharing, passing a key around that can encrypt and decrypt the info being sent along with it is not such a good solution. Public key encryption uses two (asymmetric) key pairs. Though one is called a private key and the other is called a public key, they are basically the same thing. Any data encrypted with one key may only be decrypted using the other key. It is a one way cipher, or a trap door cipher as you put it. In this way if someone encrypts some information using your public key, only you can decrypt the information with your private key. In the same regard, if you encrypt something with your private key, it can be decrypted with your publicly available key. It is essentially guaranteeing that the information was from you, and no one else. In this way you can have an encrypted transaction with someone if they also have a public and private key pair. They encrypt something using their private key (so it is guaranteed to be coming directly from them) and then encrypt the data again with your public key (so that it can only be decrypted by you). This is basically the idea, though there is much more to it.

Answer 5

There are many people who would laugh at the possibility of altering their fates. This is due to the fact that it thinks that no one gets more that what is put in his destiny.

Answer 6

I would like to know this too... I have never heard of it before.



What he said

I I
I I
I I
I I
V